lundi 8 septembre 2008

Démonologie Informatique 2/2

Il s'est passé quelques semaines depuis le dernier billet sur le sujet, veuillez m'en excuser. J'étais en vacances, sans Internet et avec quelques autres petites choses à faire.

On en était resté à ce qui distingue les langages informatiques entre eux par rapport au fait de déclarer le type des variables. Pour celles et ceusses qui ont la mémoire qui flanche et que le sujet intéresserait, allez .

Je pensais écrire la seconde partie du billet dans la même veine que la première quand un commentaire d'un lecteur m'a fait réagir. Ce commentaire dit en substance : "Comment gérer des structures de données complexes avec un langage dynamique ?"

D'abord, qu'est-ce qu'on entend par structure de données complexe ?
Et d'abord, ce quoi une structure de données ?

En informatique, l'un des problèmes de base qu'un concepteur a à résoudre est celui de la représentation des données. Tout le monde a une idée assez précise de ce que c'est qu'un nombre entier (il en existe même quelques définitions mathématiques assez formelles) mais comment le représente t'on ?

Pour un humain standard et normal (ni informaticien, ni mathématicien), la question ne se pose pas, il écrit le nombre entier avec des chiffres décimaux, c'est ce qu'on appelle la représentation positionnelle en base décimale d'un nombre.
La représentation décimale est tellement courante que l'on est arrivé à confondre l'essence d'un nombre et sa représentation. Mais ces deux notions sont distinctes.

Prenons par exemple l'entier N représenté communément par l'écriture décimale suivante : 10.
N peut aussi s'écrire 5 x 2 ou comme la somme des 4 premiers entiers naturels non nuls : 1+2+3+4. A chaque fois, on parle du même nombre, du même être mais sous des représentations différentes. On peut aller encore plus loin en disant que ce nombre entier N est unique mais qu'il lui est associé une infinité de représentations (ça se démontre facilement en disant qu'un entier N peut être représenté dans toute base de numération p où p est un entier, comme il existe une infinité d'entiers p, N peut être représenté d'une infinité de façons)

Quel rapport avec notre choucroute de structure de données ? Et bien, le voilà : une structure de données est la représentation d'un type.

Dans notre exemple avec l'entier, 10 est une structure de données qui représente de manière numérique le nombre en question de type entier. Le type est entier, le nombre est une réalisation du type, un être si on veut et l'écriture décimale, sa représentation (très efficace pour le calcul manuel ou mental sur les entiers).
Une autre représentation du même être est Dix. Cette représentation est lexicale, dépendante d'une langue nationale. Peu pratique pour le calcul ou même la communication...

Dans le premier cas, on exprime notre élément de type (on dit instance ou réalisation) par une structure de données qui est une séquence de chiffres de 0 à 9.
Dans le second cas, on exprime le même être par une structure de données qui est une séquence de lettres d'un alphabet qui suit les règles de vocabulaire et de syntaxe d'un langage (en l'occurrence, une langue naturelle, le français).

Maintenant, qu'on voit peut-être un peu mieux ce qu'est une structure de données et à quoi ça sert, on va pouvoir répondre à la première question : en quoi une structure de données peut être complexe et si les langages dynamiques sont mieux à même de les gérer.

Avant toute chose, il faut vous prévenir que ce n'est pas parce qu'un langage ne force pas le développeur à utiliser des types que ce langage n'en possède pas.
En Perl (langage à typage dynamique faible), vous ne voyez jamais quelquechose du style my int $n = 10;
Et pourtant, écrire quelque chose comme my $n = 1+2+3+4; printf "%d\n",$n; donnera bien 10.
Perl possède bien en interne un type Entier mais il décharge le développeur du souci de s'en préoccuper en inférant le type des variables à l'exécution. En clair, Perl contient un petit démon qui regarde l'intérieur des boîtes pour mettre tout le temps la bonne étiquette dessus.

Et nos structures complexes alors ? Et bien, on s'en fiche. Pouvoir créer des structures complexes n'a rien à voir avec les types supportés d'un langage mais avec sa syntaxe.
Quand on parle de structure de données complexes, on parle en fait de représentations suffisamment sophistiquées pour représenter des types de plus en plus abstraits.

Représenter un entier est une chose, représenter un une carte géographique et un itinéraire dans cette carte (comme Google Maps le fait) en est une autre.

Prenons une structure de données sophistiquées, la liste chaînée. Il s'agit d'une collection de variables dont on accède aux valeurs par itération de proche en proche depuis la tête de liste jusqu'à la fin.

Son expression dans un langage informatique ne dépend aucunement de la capacité dudit langage à gérer le typage de manière forte ou faible, statique ou dynamique mais uniquement de sa capacité à gérer des liens entre variables (qu'on les appelle pointeurs ou références) donc de la syntaxe.
Exemples : C (fort, statique) possède des pointeurs, on peut y définir une structure de liste chaînée. Perl (faible, dynamique) permet de gérer des références à des variables, on peut y définir une structure de liste chaînée (c'est idiot car Perl les supporte de manière native), Lisp (pas de typage) est entièrement basé sur la structure de liste (un programme Lisp est une liste). A contrario, PL-SQL (fort, statique) ne supporte ni pointeurs, ni références et n'autorise pas la définition de telles structures.

En conclusion, la capacité d'un langage informatique à gérer des représentation sophistiquées des données dépend de la puissance et de l'expressivité de sa syntaxe.
Le typage n'intervient que dans le contrôle de la syntaxe pour assurer une exécution correcte.

A noter que beaucoup de langages dynamiques possèdent une syntaxe puissante et expressive à la différence de certains langages statiques.


4 commentaires:

  1. Je réagis (tardivement...) à ton article. Simplement du fait que je ne trouve pas vraiment de réponse à ma question ! Ou peut-être nh'ai-je pas bien compris...

    Je vais donc partir sur un exemple.

    Histoire d'éviter tout conflit de terme, je vais appeler "encapsulage" un ensemble de type comme une Structure en C.

    J'ai deux encapsulages : un représentant par exemple une position sur un damier avec deux entiers (qu'importe leur représentation), l'autre sera le nombre de cylindres et la puissance d'une voitures (mêmes entiers que plus hauts).

    On a donc deux représentations parfaitement identiques, mais qui n'ont pas du tout le même but.

    Or comment un langage dynamique peut différencier ces deux encapsulages et garder leur corrélation ? Le petit démon saura reconnaître deux boîtes ayant le même contenant mais pas la même couleur ?

    Pierre.

    RépondreSupprimer
  2. Je dirais ça dépend du langage et de la représentation du type que tu as choisie. Si dans les deux cas, tu as choisi un type abstrait genre tableau de deux entiers, il n'y aucun pour le "démon" de faire la différence. Si tu as choisis une représentation à base de tableau associatif avec pour clé de hachage le nom de l'attribut (colonne,ligne dans un cas, puissance et cylindrée dans l'autre), il est possible de faire la différence entre les types sur la base des noms d'attribut. Bien sûr, si tu as choisi de nommer ton type, là, il n'y a plus d'équivoque.

    RépondreSupprimer
  3. Donc si je pige bien, derrière le typage dynamique se cachent des mécanismes plus statiques (ici, tableau + hachage).

    Ca fait un peu beaucoup pour représenter un couple d'entiers tout simple !

    Tout ce typage dynamique me semble aller à l'encontre d'un gain de performance (et, conviction tout à fait perso pour moi-même, d'un gain de temps sur le codage d'applis autre que du script léger) ? Quand on voit la lenteur d'exécution du Javascript par exemple, alors que ce cher Web 2.0 en use et en abuse... Le temps d'interprétation doit s'en prendre un sacré coup dans les dents avec des représentations alambiquées !

    Sans compter une hausse de la consommation mémoire...

    RépondreSupprimer
  4. En fait non. C'est pas évident non plus d'exposer ça dans un commentaire de blog.
    Ta dernière remarque est cependant juste. Le temps que passe l'interpréteur à typer dynamiquement est là mais son importance en terme de performance est relativisée par le fait que les programmes sont concis et expressifs, ce qui est souvent le but recherché quand on utilise ce type de langage (cf Javascript pour l'exemple)
    la perte de performance est somme toute assez limitée pour les langages type fort dynamique. Ce sont pour l'essentiel des langages compilés qui font de l'inférence de type à la compilation (haskell, mercury, perl 6 peut-être). Malheureusement, ces langages souffrent d'un déficit de popularité peut-être à cause du fait qu'il faut avoir fait des études d'informatique (de science informatique) pour les utiliser.
    Reste que les langages à typage dynamique faible/fort (i.e. "langages de script") ont de beaux jours devant eux. Ils sont expressifs, ont une syntaxe proche de celle du C et surtout supportent des paradigmes multiples (procédural,objet et fonctionnel). Le mot-clé est ici expressivité. S'ajoute à cela que ces langages sont incorporables dans toute application (l'interpréteur dispose d'une API) ce qui permet de donner une fonction d'extension par scriptage comme The GIMP et emacs avec leur langage interne basé rspectivement sur Scheme et LISP.

    RépondreSupprimer