Compilation, interprétation, et typage

J’ai lu certaines réponses en diagonale, désolé pour les redites éventuelles, mais voici une réponse à la question initiale :

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 ?

Common Lisp.

Il possède un typage dynamique (tu peux difficilement faire plus dynamique, même), mais la majorité des implémentations sérieuses sont des compilateurs : LispWorks, Allegro, SBCL, CMU CL… D’ailleurs SBCL (et sûrement les autres) te permet même d’intégrer de l’assembleur en inline au milieu de tes fonctions.

Attention : les compilateurs que j’ai cités peuvent ressembler à des interpréteurs ou à du JIT (tu as une REPL), mais ce sont bien de «véritables» compilateurs. Ils prennent du code Lisp en entrée et génèrent du code assembleur x86 en sortie. Ils sont parfois appelés à la volée pour «émuler» de l’interprétation, mais dans la majorité des cas le code assembleur est utilisé pour générer un exécutable.

Voici comment fonctionne SBCL (c’est l’exemple que je connais le mieux, mais les autres font sans doute pareil). Chaque fois que le compilateur rencontre une primitive du langage (par exemple une addition), il génère du code assembleur qui teste si les opérandes sont du bon type (dans l’exemple, des entiers) et qui renvoie le bon résultat si c’est le cas. Autrement, une exception est levée. Les exceptions sont compilées de façon classique, un peu comme en C++ ou en Java (il y a une subtilité pour gérer la reprise sur panne, mais tout reste géré en assembleur de façon statique).

Si on applique la technique ci-avant naïvement, le code généré sera atrocement lent. Il faut donc optimiser avec de la propagation de types. Par exemple, si on rencontre une addition suivie d’une multiplication, avec les mêmes opérandes, il n’y a pas besoin de tester deux fois que ces opérandes sont bien des entiers : on peut éliminer le test de types la deuxième fois. En utilisant des algos assez évolués, de la même famille que l’inférence de types à la Caml/Haskell, on peut éliminer la majorité des tests de types et ainsi obtenir un code rapide.

Bien sûr, il y aura toujours des situations où le compilateur ne «sait pas», et doit donc garder les tests de type au cas où. Dans ces cas-là, SBCL affiche un warning en expliquant de son mieux pourquoi il n’a pas pu optimiser le test de type. Assez souvent, on peut ajouter des annotations ou changer légèrement le code pour qu’il puisse le faire quand même.

Bien sûr, si tu es pervers, tu peux imaginer des exemples particulièrement défavorables où il est très difficile d’éliminer les tests de types, même à la main. Mais ces exemples n’apparaissent que très rarement dans du code lambda (pun intended).

C’est ça qui m’interroge. Je trouve le procédé sympa mais j’ai du mal à intuitionner dans quelle mesure il peut être efficace ou pas. Est-ce qu’il y a des chiffres qui traînent, des tests ?

Des tests de quoi ?

Il semblerait que LispWorks, Allegro et SBCL soient au coude à coude en termes de performances. Ils sont bien plus rapides que d’autres implémentations du Common Lisp qui sont basées sur des interpréteurs, ou qui n’utilisent pas cette technique de propagation de types. Au quotidien, je rencontre très rarement les fameux warnings d’échec d’inférence de types. Et même lorsque c’est le cas, ça ne tue pas les performances de mes programmes, j’ai donc rarement besoin d’aller bidouiller. Au pire, si j’ai une portion de code très critique, je écrire de l’assembleur inline pour optimiser à la main.

Au-delà de ça, il est difficile de comparer deux langages en termes de performances. Il est encore plus difficile de comparer l’influence d’un aspect de la compilation en particulier. D’autant plus que Common Lisp adopte un paradigme de programmation très inhabituel, qui favorise la méta-programmation. Pour un même problème donné, un dév. CL écrira un code (voire un algo) très différent d’un dév Python. Dans ces conditions, comparer deux codes «équivalents» ne semble pas très pertinent…

Je me souviens avoir conclu que Common Lisp se situe généralement entre Python et Java dans les benchmarks. Mais je n’ai pas de source à citer là, tout de suite, pour étayer ça.

Je suis désolé pour le HS, mais je tiens à dire que ça m’a fait vachement plaisir de voir un post de GuilOooo.

Tu m’as manqué. <3

(J’ai posté sur le sujet «Open Bar à Smoothies», je propose qu’on se fasse des bisous là-bas. Moi aussi vous m’avez manqué, ZdS et tous les copains. )

EDIT : quelques réflexions supplémentaires sur l’inférence de type.

Comparativement à d’autres langages, du code Common Lisp typique modifie très rarement les valeurs des variables. On fait plutôt comme en Caml et en Haskell : on travaille beaucoup par appels de fonctions et avec des constructions comme let … in …. En conséquence de ça, on peut propager les types très loin sans trop de problèmes. Ça marcherait peut-être moins bien dans un langage impératif comme Python, justement.

Les langages dynamiques compilés peuvent aussi utiliser du code auto-modifiant. C’est par exemple le cas dans certaines versions de la VM Javascript de Google chrome : le code JS est initialement compilé (en langage machine et tout) de façon relativement naïve. Ensuite, si la VM s’apperçoit que telle fonction est appelée 99% du temps sur des entiers (elle fait des stats), elle va en recompiler une copie en l’optimisant spécialement pour ce cas de figure. Même si la compilation a lieu au moment de l’exécution, ça n’a rien à voir avec de l’interprétation ou du bytecode (on génère bien ici du langage machine), donc ça rentre dans la case «compilation». On a donc un deuxième contre-exemple : Javascript possède au moin une implémentation où il est entièrement compilé.

Je pense que c’est la tendance d’avenir : des compilateurs qui s’adaptent au programme dynamiquement, et qui reviennent sur leurs décisions en recompilant certains bouts de code pendant l’exécution. Ça existe aussi pour les langages aux types plus statiques, notamment Java et C# (pour optimiser le polymorphisme entre autres). Ça me rend assez enthousiaste : à ce rythme-là, dans quelques années on aura de bonnes techniques de compilation pour les langages dynamiques, et on pourra les exécuter avec d’excellentes performances. Ce sera un bon premier pas pour commencer à abandonner le C.

(Je suis un peu parti en hors-sujet, mais je m’étais promis de faire un post de blog où j’étale toutes ces idées là, et… j’ai pas de blog. Alors j’ai profité de l’occasion. J’espère que ce sera utile à quelqu’un.)

Comparativement à d’autres langages, du code Common Lisp typique modifie très rarement les valeurs des variables. On fait plutôt comme en Caml et en Haskell : on travaille beaucoup par appels de fonctions et avec des constructions comme let … in …. En conséquence de ça, on peut propager les types très loin sans trop de problèmes. Ça marcherait peut-être moins bien dans un langage impératif comme Python, justement.

OCaml est impératif (et même orienté objet mais personne l’utilise). Rust est aussi une preuve qu’il n’est pas difficile de typé un langage impératif comme Python (c’est juste qu’on l’a pas fait et que, eh, ça demande quand même pas mal de boulot).

Concernant la compilation JIT, c’est en effet un gros progrès mais c’est très (parfois trop) compliqué pour imaginer l’appliquer à l’existant - où il est encore difficile de s’en y abstraire de la machine virtuelle basique (garbage collector, intégrité des pointeurs, barrière d’écriture, etc. qui peuvent amener à changer le comportement défini du langage). Pour preuve, LLVM, un des fer de lance de la compilation JIT a encore du mal assimiler l’idée de garbage collector externe (ce qui a valu certains patch-monkeys pour intégrer le runtime haskell).

Après, il est très intéressant de faire un langage avec une compilation JIT, ça c’est sûr.

J’ai l’intuition, sans publications pour l’étayer, envoyez moi si vous avez, qu’un tracing JIT pourra toujours battre une compilation AOT dans le cas très général. Un avis ?

(Vu que ça a été mentionné ici, si vous vous intéressé aux JIT js de Google, il y a un article ici et quelques uns sur mon blog. Notez enfin que depuis la semaine dernière il ne JIT plus direct vers du code machine, il a désormais un byte code.)

Cela dépend de ce que tu autorises ton compilateur à faire. Il y a certaines techniques de compilations (probablement assez théoriques) qui s’apparentent beaucoup à insérer du JIT au sein d’un programme compilé. Par exemple, si tu as une configuration qui est chargé au démarrage du programme et qui ne change pas, le compilateur pourrait ajouter un bout de code qui va faire la propagation de constante (qui n’étaient pas connu à la compilation) au runtime et qui va patcher les bouts de code optimisés. Runtime constant propagation te donne quelques papiers de recherches sur le sujet.

De la même manière, la technique de Profile-guided optimization permet un certain nombre d’optimisations qui proviennent de connaissances d’exécution. Un compilateur AOT au sens premier du terme ne pourra pas faire ce genre d’optimisation parce qu’il n’est pas sensé pouvoir récupérer des données d’exécution.

Tout ça pour dire que la frontière entre compilation et JIT n’est pas forcément toujours claire. Par contre, avoir des informations sur les données que le programme va voir à l’exécution permet quasiment toujours de faire tout plein d’optimisations qu’un simple compilateur AOT ne pourra pas faire.

OCaml est impératif (et même orienté objet mais personne l’utilise). Rust est aussi une preuve qu’il n’est pas difficile de typé un langage impératif comme Python (c’est juste qu’on l’a pas fait et que, eh, ça demande quand même pas mal de boulot).

On ne parle pas de la même chose. Je pars d’un langage à typage dynamique, ce qui (pour moi) signifie qu’une variable donnée peut changer librement de type à chaque affectation, et je cherche à déterminer l’ensemble des types possibles pour chaque sous-expression. OCaml n’est pas dynamique au sens de ma définition, ce qui rend le problème d’inférence de types plus simple. (En outre, je ne dirais pas qu’il est impératif ; il autorise la programmation impérative, mais la syntaxe et la structure du langage la rendent moins agréable que d’autres styles). Enfin, la discussion portait sur les performances, les problématiques sont donc différentes de l’inférence de type de sécurité. On va par exemple chercher à propager les informations de typage bien plus loin, à travers les fonctions et peut-être même les modules (pour savoir si l’inlining est opportun par exemple), ce qui n’est pas du tout nécessaire quand tu t’intéresses à la sécurité.

Pour preuve, LLVM, un des fer de lance de la compilation JIT a encore du mal assimiler l’idée de garbage collector externe (ce qui a valu certains patch-monkeys pour intégrer le runtime haskell).

Pourrais-tu développer cet aspect ? Ou bien, as-tu un bon article à lire sur le sujet ? Ça m’intéresse.

Pourrais-tu développer cet aspect ? Ou bien, as-tu un bon article à lire sur le sujet ? Ça m’intéresse.

En ayant regardant en profondeur LLVM-IR (enfin sa spécification), j’ai remarqué quelques notes sur Haskell. Notamment un appel de fonction spécifique à Haskell (cf. cc 10). Après discussion avec certains, il se trouve que l’intégration du GC dans un runtime produit en LLVM-IR est vachement difficile et qu’il a fallut pas mal de contorsions des deux côtés (LLVM et GHC) pour parvenir à un résultat sans régression.

Et c’est normal, LLVM veut être le plus abstrait possible et se foutre (à raison) du modèle mémoire et d’évaluation du langage qui tente de l’utiliser. Dans le cas d’Haskell malheureusement, une telle abstraction fait perdre drastiquement en performance le code produit par le compilateur (ici GHC). Même si l’équipe de GHC a essayé de minimiser l’impact, il y en a un qui se voit dans la spécification de LLVM-IR.

C’est pas vraiment une critique de la compilation JIT ou même de LLVM qui font un super travail - et qui aujourd’hui essayent justement de proposer une manière d’intégrer un GC externe (je dis bien externe car LLVM propose des GCs) sans se fouetter. Mais après, c’est une question très épineuse pour tout ce qui touche à la cohérence des pointeurs entre le code produit en LLVM-IR et se qu’on a dans le GC.

Pour OCaml, j’ai eu pas mal cette discussion et il y a toujours eu un ou deux projets qui ont essayé d’utiliser LLVM derrière. Pour ce qui est d’utiliser LLVM à la place de la toolchain courante, l’avantage est quasi nul (OCaml a un bon compilateur AOT pour le coup). Mais après il a été question de la compilation JIT et pour le coup, cela questionne sur l’intérêt même d’une compilation JIT pour un langage (ici statiquement typé). Et c’est là où le travail nécessaire pour avoir une compilation JIT est bien trop important par rapport aux avantages que l’on peut avoir (en constat de ce qu’est la compilation JIT aujourd’hui).

Le typage statique (à hauteur de ce qu’est le typeur d’OCaml) permet déjà de faire des optimisations sur le code produit (entre autre des spécialisations et la vérification de l’exhaustivité dans la production des branchements conditionnels) qui sont pour l’instant suffisantes à ce que pourrait offrir une compilation JIT. De plus que l’optimisation, dans OCaml, est encore très jeune et on a encore du mal à cerner une bonne politique d’optimisation pour ce langage. La compilation JIT, par le biais des statistiques, pourrait nous aider à définir une politique d’optimisation mais pour le coup, ça reste assez contraire à la philosophie qui gravite autour de la compilation et de exécution d’un code OCaml où son déterminisme est chéri par ses utilisateurs.

GHC a fait le pas vers LLVM (mais ça toolchain de compilation était naze à la base) et on peut voir quelques projets sur la compilation JIT avec Haskell mais ça reste rudimentaire et montre bien tout le travail qu’il faut faire qui n’est pas encore si avantageux que ça par rapport à un compilateur AOT pour un langage statiquement typé (mais je dis bien "pas encore").

Mais bon après, qui vivra verra !