Compilation, interprétation, et typage

Bonsoir,

J’ai une impression et je voudrais savoir ce que vous en pensez : il est extrêmement difficile de compiler en langage machine un langage à typage dynamique.

Tous les langages à typage dynamique sont interprétés (Python, PHP, Javascript, ..), et tous les langages compilés sont à typage statique (C, C++, D, Java, Go, ..). Avez-vous un contre-exemple ?

Un autre indice en faveur de cette théorie : Cython propose de compiler des programmes écrits en Python pour les rendre plus performants. Il y a pour cela deux modes d’optimisation : une optimisation légère qui n’accélère en fait pas beaucoup le programme, et une optimisation avancée qui l’accélère bien mais qui requiert de spécifier les types des variables.

Actuellement je suis en train d’écrire un compilateur avec Flex et Bison pour un petit langage que j’ai créé. Pour compiler je transforme mon code en C, en ayant défini d’abord tout un tas de structures et de fonctions pour représenter les classes, les objets, etc. de mon langage. Puis j’appelle gcc pour compiler en machine. Mais en fait mon compilateur ne fait aucune analyse du code autre que syntaxique : tout se fait au runtime. Donc c’est un peu comme si j’avais fait en fait un interpréteur, sauf qu’il est embarqué dans l’exe. En fait je n’interprète pas mon code, mais à part l’analyse syntaxique tout se fait au runtime quand même.

J’aimerais faire un vrai compilateur, qui analyse le code pour trouver les erreurs sémantiques, pour gérer les types, etc. bref tout ce qui permettrait une vraie compilation, avec un code machine correspondant vraiment à mon code, et pas à tout un runtime qui fait qu’un hello world pèse 200ko !

Seulement mon langage est à typage dynamique, pour le moment. J’aimerais pouvoir garder le typage dynamique, mais aller vers une vraie compilation. C’est-à-dire transformer mes 4+3 en 4+3 et pas en (struct Object(4)).call_method("+", vector<struct Object>{struct Object(3)}). D’où ma question : ça me paraît compliqué parce que ça demande une analyse assez poussée. Tellement compliqué que j’ai l’impression que personne ne le fait. D’où ma question… Est-ce possible ?

Allez bonne soirée.

Salut.

C’est tout à fait possible. D’ailleurs, certaines implémentations des langages dynamiques que tu as cité compilent le code en langage machine via un JIT (pypy pour Python, par exemple).

Concernant ce que tu veux faire, ça me semble incompatible avec l’idée du typage dynamique, où tout est un « objet dynamique ». Tu peux manipuler un Object(4) assez librement, par exemple dans un REPL, pour obtenir son type, sa vtable, etc. mais tu ne peux pas faire ça avec juste 4. Pour revenir à pypy et assimilés, c’est comme ça qu’ils fonctionnent, les appels au runtime sont directement générés en langage machine au lieu de passer par l’interprète comme dans CPython.

Ne serais-tu pas plutôt à la recherche de l’inférence de type, où le typage est statique mais où les types peuvent être omis par le programmeur et déduis à la compilation ?

Il me semble que ce problème est indécidable (au sens prouvé mathématiquement) en conséquence du théorème de Rice.

Par exemple il est prouvé, via le problème de l’arret qu’il n’est pas possible de faire un ramasse-miette parfait/optimal, c’est à dire qui libère la mémoire exactement au moment à partir duquel il n’est plus utilisé.

Après cela reste des résultats théoriques, tu ne peux pas trouver de solutions qui fonctionnent dans tous les cas possible et inimaginable de façon optimal, mais cela ne veut pas dire que tu ne peux pas trouver une solution qui fonctionne de façon optimal pour la majorité du temps avec des cas non-optimaux pour le reste. Voir une solution jamais optimal mais généralement suffisante.

On peut parfaitement imaginer un langage compilé typé dynamiquement, ou l’inverse. Ça se fait assez rarement pour plusieurs raisons : notamment, si on compile au lieu d’interpréter, c’est pour les performances. Le « typage » dynamique introduit à l’exécution un surcoût non négligeable, donc c’est contre-productif. De façon liée, un des (faux) avantages perçus par les gens qui aiment bien les langages dynamiques, c’est « c’est plus simple pour prototyper des petits scripts parce que le typage m’embête pas ». Dans cette optique, puisque c’est beaucoup plus simple que compiler, on se contente d’écrire des interpréteurs qui sont suffisants pour le job demandé. Le temps de travail libéré sert ensuite par exemple à rajouter des caractéristiques au langage pour permettre d’écrire plus de choses en moins de lignes, ou à implémenter des bibliothèques. Enfin, le typage statique aide à la compilation, parce que tu trouves des informations sur tes programmes qui peuvent te permettre d’optimiser le résultat de la compilation.

Cela dit, il existe quand même des langages non typés et compilés, par exemple des dialectes de Lisp. Mais la plupart du temps, les gens qui veulent des performances sur des langages dynamiques utilisent des compilateurs JIT, en utilisant des informations qu’ils connaissent à l’exécution pour spécialiser la compilation des fonctions critiques.

Kje : je ne comprends pas de quoi tu parles, ni quel est le rapport avec l’indécidabilité. Quel est le problème indécidable auquel tu fais référence ?

C’est pas ce qu’il entend à priori, car le JIT reste du bytecode (ou autre) qui est compilé à partir d’un certain moment (puis rebasculer vers le bytecode quand les types ne correspondent plus).

@Society, comme dit précédemment, tu ne peux pas (facilement ?), il faudrait réussir "suivre" le typage de toutes les variables dans tous les cas possibles et générer une version de chaque fonction pour chaque "type" trouvé (un peu comme les templates en C++).

Après, tu peux peut-être simuler le typage dynamique en générant du C++ où toutes tes variables sont du type std::variant.

Après, tu peux peut-être simuler le typage dynamique en générant du C++ où toutes tes variables sont du type std::variant.

C’est pas une simulation, c’est exactement le principe du "typage" dynamique : pas de type à proprement parler, mais un tag (selon l’implémentation, ça peut être un champ d’une structure, ou n’importe quelle autre méthode) présent à l’exécution qui permet de distinguer des variables qui représentent des choses différentes. C’est d’ailleurs là qu’on voit que l’argument qu’on entend parfois, "le typage dynamique, parfois c’est utile, donc les langages statiques sont gênants dans ces cas" ne tient pas : dans un langage typé, on peut choisir d’"oublier" les types pour avoir une vérification dynamique à la place. Évidemment, l’inverse n’est pas vrai

Ce qui ressort de vos réponses (dont je vous remercie), c’est qu’il y a trois possibilités :

• typage statique explicite, type C, qui permet de se passer de runtime ou quasiment (comme le C++ avec ses vtable..)
• inférence de types, qui permet la même chose en ayant un côté pratique pour le développeur et en conservant la sûreté et la rapidité d’exécution d’un typage statique, type templates du C++
• typage dynamique, qui nécessite du runtime au moins sous la forme de variants mais apporte une plus grande flexibilité

En fait ce que je fais actuellement ça se rapproche des JIT si j’ai bien compris : un runtime, mais en code machine quand même.

Du coup l’inférence de types m’intéresse, mais je voudrais savoir dans quelle mesure ça peut limiter la flexibilité. J’aimerais trouver un compromis entre flexibilité et rapidité d’exécution… Par ex si je veux pouvoir modifier dynamiquement les classes, celles-ci ne doivent pas correspondre à un schéma mémoire fixé type C struct, mais doivent être elles-mêmes stockées, donc un minimum de runtime. Est-ce que je peux faire de l’inférence de types compile-time quand même ? (par ex).

Comme l’a dit minirop ça semble de toute façon assez compliqué à faire, d’ailleurs peu de langages l’exploitent de ce que j’ai compris. Mais j’ai quand même lu que C# le faisait..

Le typage, quand c’est fait correctement (c’est-à-dire pas comme en C++), repose sur une approche scientifique et des théories solides. Si tu souhaites t’y intéresser, c’est très bien, c’est un domaine passionnant. Mais c’est aussi quelque chose d’un peu exigeant si tu ne veux pas faire les choses à moitié : on ne peut pas faire d’à peu près, sous peine de perdre toutes les garanties qu’on cherchait à obtenir.

À toi donc de voir si tu souhaites continuer dans la compilation ou si tu veux approfondir les systèmes de type, mais tu auras du mal à faire les deux en même temps sur le même projet : il y a des liens, mais mener les deux combats de front est le meilleur moyen de n’en gagner aucun. Pour ton compilateur, je te suggère pour l’instant de te limiter à un système de type simple que tu connais déjà (un truc à la Basic/Pascal par exemple, et sans inférence).

Pour approfondir le typage, le mieux est de commencer par s’en servir : tout comme on n’apprend pas la compilation avant de savoir programmer, il est à mon avis souhaitable d’avoir manipulé un langage proprement typé avant de chercher à manipuler les systèmes de type eux-mêmes. Actuellement, ça veut concrètement dire "apprendre un langage fonctionnel typé", comme OCaml ou Haskell (le premier est plus accessible, et je pense que la communauté ici est plus réactive). Quand tu verras un peu plus où tu vas, tu pourras lire par exemple "types and programming languages" de Pierce, qui est une bon livre sur le sujet.

derrière ton ton très autoritaire j’ai la vague impression (donc je me trompe probablement) que tu confonds légèrement typage dynamique et typage faible Eusèbe.

Sinon merci pour la référence.

Non. Le terme de « typage » pour parler des vérifications dynamiques est impropre, mais c’est un abus de langage suffisamment répandu pour que je l’utilise quand même, ce qui explique sans doute ta confusion. Mais quoi qu’il en soit, la conclusion tient : si on veut étudier les systèmes de type (et notamment l’inférence, qui n’a aucun sens dans un langage dynamique), il faut pratiquer avec des langages qui les mettent en oeuvre, et ces langages sont typés statiquement.

"Évidemment".

Si cela prête à confusion, je précise à toutes fins utiles que ce typage statique optionnel, qui n’existe évidemment pas, fait partie de la distribution standard de Python depuis bientôt 2 ans. Et que l’outil sus-cité, quoi qu’il n’est pas encore parfait, réalise également des vérifications par inférence de types.

Sinon, y’a Common Lisp qui accepte des annotations de types comme optimisation. C’est aussi un exemple d’un language à typage dynamique qui est compilé.

Bah ça revient au même, le JIT c’est une forme de compilation. Si tu peux compiler en JIT tu peux compiler en AOT.

Eusèbe : Que peut-on reprocher au typage de C++ par exemple ? Merci pour les conseils en tous cas. Et peux-tu préciser ce que tu entends par "l’inférence n’a aucun sens dans un langage dynamique" ?

nohar & olzd : Merci pour les références. L’idée d’un typage statique au cas par cas est assez séduisante aussi.

Au risque de repeter ce qu’a dit tres justement Kje plus haut, il me semble egalement que compiler AOT un langage dynamique comme Python reviendrait a resoudre le probleme de l’arret, donc impossible theoriquement. Ce qui expliquerait le JIT.

La compilation AOT et la compilation JIT sont la même chose, simplement faites par des programmes avec des intitulés différents. Et pour citer un contre-exemple, il y a Cython. Si la compilation AOT Python -> C est possible alors la compilation AOT Python -> code machine est possible, vu que la compilation AOT C -> code machine est possible.

@Praetonus: Tu as raison, j’ai fait une erreur dans mon raisonnement en supposant que la connaissance du type de chaque objet/variable etait indispensable a la compilation. Du coup, en y reflechissant un peu, je suppose que ne pas pouvoir definir avec certitude le type doit quand meme impacter un minimum les performances

C’est d’ailleurs là qu’on voit que l’argument qu’on entend parfois, "le typage dynamique, parfois c’est utile, donc les langages statiques sont gênants dans ces cas" ne tient pas : dans un langage typé, on peut choisir d’"oublier" les types pour avoir une vérification dynamique à la place. Évidemment, l’inverse n’est pas vrai

"Évidemment".

Évidemment, en effet : dans un langage typé dynamiquement, tu ne peux pas encoder dans le système de types des propriétés statiques. Par contre, tu peux prendre un langage qui ressemble à ton langage dynamique et y rajouter une vérification de types. Mais ce n’est plus le même langage, même si c’est inféré et que ça ne change pas la syntaxe : typer, c’est interdire certains programmes qui étaient autorisés, le langage est donc différent.

Eusèbe : Que peut-on reprocher au typage de C++ par exemple ?

Essentiellement, que le fait qu’un programme C++ compile ne t’apporte en fait aucune garantie sur son fonctionnement.

Et peux-tu préciser ce que tu entends par "l’inférence n’a aucun sens dans un langage dynamique" ?

Qu’est-ce que tu as compris de l’inférence de types exactement ?

Comme tous les autres langages, y compris Ocaml et Haskell. Au mieux, on peux dire que Haskell rend la tâche plus difficile pour faire des conneries, mais comme en C++ tu n’as aucune garantie juste parce que le programme compile.

En fait, mis à part un langage de programmation qui ne compile que s’il y a une preuve valide du bon fonctionnement du programme inclus, tu n’as aucun moyen d’avoir une garantie juste parce que ton programme compile.

Le problème vient de la définition de "bon fonctionnement". Personnellement, la condition "absence de RTE" (et encore une exception reçue pour avoir fait hd sur une liste vide, pour moi c’est une RTE avec un costard) ne suffit pas à dire que le programme fonctionne.

Il s’agit évidemment d’une différence de degré : il y a un monde entre "aucune idée de ce qui va se passer" (qu’on a avec les langages dynamiques) et "je suis sûr que ça fait ce que je veux" (ce qu’on approche avec les langages comme Agda ou Coq), et C++ et les langages avec un système de types réfléchi plus proprement vivent tous les deux dans ce monde. Pour autant, on ne peut pas nier que les seconds apportent beaucoup plus de garanties à la compilation que C++, qui en donne très peu (je vous le concède, "aucune" était un brin provocateur).