Stephen Dolan (github, vielle page perso) est un étudiant en thèse d'informatique à Cambridge, UK, et il a de nombreux talents et des centres d'intérêt variés au sein de la discipline. D'un côté il a un goût pour l'élégance mathématique assez visible dans ses travaux (en particulier son travail de thèse très intéressant sur le sous-typage, avec une forte inspiration algébrique), de l'autre c'est aussi un hacker qui s'intéresse à l'implémentation, et a par exemple fait une partie importante du boulot sur "multicore OCaml", un runtime parallèle pour le langage OCaml avec des threads OCaml à mémoire partagée.
Un de ses nouveaux petit projets du moment est Malfunction, un langage fonctionnel bas-niveau qui se traduit directement en une des représentations intermédiaires du compilateur OCaml. L'idée première est de permettre à d'autres langages plus expérimentaux d'obtenir un compilateur pour pas cher, en traduisant leur propre représentation intermédiare en Malfunction, et en réutilisant le compilateur et runtime OCaml derrière—en particulier un gestionnaire de mémoire très bien optimisé pour le style fonctionnel (beaucoup d'allocations de courte durée) et une compilation vers du code natif raisonnablement efficace.
Dans une proposition d'exposé pour le ML Workshop, qui aura lieu en Septembre prochain à Nara, au Japon¹, Stephen Dolan décrit les choix de conception de Malfunction et un prototype de backend pour le langage Idris (un langage de recherche qui permet de programmer avec des types dépendants et de faire des preuves formelles en même temps, un peu comme Coq ou Agda mais plutôt plus orienté programmation), mais les langages plus expérimentaux Links et Eff ont aussi essayé de réutiliser le backend OCaml et pourront être intéressés par Malfunction.
¹: Si vous êtes étudiant ou étudiante en informatique et intéressé-e par la programmation fonctionnelle, le ML Workshop a lieu en même temps que la grosse conférence ICFP 2016 (au Japon cette année) et il existe des financements complets ou partiels pour aider des étudiants assister à la conférence. Voyez la page ci-jointe sur comment candidater à ces financements, il ne faut pas hésiter !
Un truc chouette dans la façon dont c'est pensé est que le langage a une sémantique simple, et en particulier les situations où un comportement est indéfini sont très clairement délimitées. Un comportement indéfini (accéder à un pointeur NULL, etc.) est relativement inévitable dans un langage de bas niveau conçu pour tourner après une vérification de sûreté sur une version plus haut niveau (ou alors juste infligé aux programmeurs et programmeuses comme le C), mais le fait de pouvoir facilement déterminer si un programme donné est bien défini ou non est très important pour certaines applications, et c'est un cauchemar quand les conditions qui le déterminent sont très complexes.
Par exemple, dans le travail sur le test des compilateurs C par génération aléatoire (Csmith), trouver comment générer seulement des programmes bien définis est un des aspects les plus difficiles du problème. Au contraire, on générer des programmes Malfunction aléatoirement, demander à l'interpréteur s'ils sont bien définis et quel résultat ils produisent, et tester que les compilateurs OCaml (code natif ou bytecode) produisent bien le même comportement.
# model
Posté par Nicolas Boulay (site web personnel) . Évalué à 4.
Pour bosser dans ingénierie des modèles et dans une boite qui fait un langage graphique, j'ai l'impression qu'il manque vraiment un "langage" comme library d'un programme plus gros (éditeur, RAD, simulateur…). L'idée est de transformer une représentation du gros programme dans un language qui compile ou s'interprète. Il y a bien lvm mais c'est très bas niveau. Je pense qu'il y a vraiment la place d'un langage "haut niveau" pour faire ça. Cela serait plus facile à utiliser.
Un peu comme si on pouvait utiliser le compilo ocaml dans une lib, pour lui fournir un AST directement ou des string de code.
"La première sécurité est la liberté"
[^] # Re: model
Posté par c^3 . Évalué à 2.
Est-ce que tu as considéré la compilation vers scheme ou luajit? Les deux proposent un langage haut niveau, avec GC (scheme disposant de plusieurs implémentations), et sont conçus pour être embarqués dans d'autres programmes au besoin.
The cake is a lie.
[^] # Re: model
Posté par gasche . Évalué à 4.
Je pense que la suggestion de c3 fait sens, dans le sens où les Scheme sont sans doute plus facilces à produire programmatiquement—et ne demandent pas au programme en entrée d'être bien typé. Mais tu peux aussi bien sûr invoquer le compilateur OCaml depuis un programme, et même utiliser compiler-libs, une bibliothèque qui permet d'appeler les fonctions internes du compilateur depuis un programme OCaml—mais il n'y a pas de garantie de stabilité de l'interface entre les versions du langage.
[^] # Re: model
Posté par Aluminium95 . Évalué à 1.
Après lecture du README, l'entrée attendue par son programme est une sorte de lisp non typé, et visiblement il y a un effort fait sur la facilité de produire du code de manière algorithmique, par exemple les noms de variables commencent tous par un symbole spécial pour ne pas avoir de problème avec des mots réservés du langage.
# Représentations intermédiaires du compilateur OCaml
Posté par Aluminium95 . Évalué à 1.
J'ai une question, est-ce que c'est une partie qui est standardisée (qui n'évolue pas ou presque malgré les changements dans le langage à plus haut niveau) ?
Ce que j'ai trouvé dans real world ocaml dit explicitement :
Mais pour rejoindre les autres commentaires, c'est d'autant plus étrange que cela semble être assez proche d'un LISP au final, quand on regarde l'exemple donné dans la page :
Compilé vers le langage intermédiaire avec
ocamlc -dlambda -c pattern_monomorphic_large.mlMais peut-être que ce n'est pas de cette représentation dont parle le journal (je n'ai pas eu le courage de regarder le code source), quoique le README puisse le laisser penser :
La question est donc : pourquoi utiliser le compilateur OCaml ? Les performances sont-elles vraiment meilleures qu'un lisp compilé ? L'écosystème OCaml est-il facilement accessible ?
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par gasche . Évalué à 3. Dernière modification le 26 juin 2016 à 15:55.
La représentation interne Lambda (qui est bien celle que vise Malfunction) n'est effectivement pas spécifiée et peut changer d'une version du compilateur à l'autre. Par contre le langage d'entrée de Malfunction est spécifiée, et plus simple que Lambda; Malfunction va produire du code pour une version spécifique du compilateur OCaml, mais peut s'adapter pour suivre les changements de représentation du Lambda.
Je pense que les backends/runtimes des bonnes implémentations Lisp (SBCL par exemple) et de OCaml sont relativement comparables en terme de qualité aujourd'hui. La question se pose aussi dans l'autre sens: pourquoi choisir Lisp plutôt que OCaml ?
La gestion des types algébriques, avec une représentation des valeurs efficaces, peut être un argument en faveur de OCaml—à ma connaissance les Lisp n'ont pas de représentation natives pour ce genre de valeurs, qui sont très utilisées par les adopteurs potentiels (Idris, Agda, Eff, Links, etc.).
(À l'inverse certains Scheme ont des continuations efficaces, ce qui peut être important pour certains langages, mais pas les Lisps à ma connaissance.)
Un autre argument est l'interopérabilité : partager une représentation interne et le runtime ça permet aussi une communication inter-langage à moindre coûts (comme c'est facile entre les langages qui tournent sur la JVM ou le CLR), et ces langages peuvent être plus intéressés par le fait d'interagir avec un langage typé, qui permet de donner des garanties partielles de sûreté au niveau du lien entre les fragments de programmes écrits dans différents langages.
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par Aluminium95 . Évalué à 1.
Quand je dis lisp, c'est un lisp ou un scheme. Par exemple chicken scheme. Les avantages sont :
Après, les points négatifs sont bien sûr
Je ne suis pas certain de tout maîtriser, mais il me semble que Lambda ne possède pas
Mais je peux me tromper.
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par gasche . Évalué à 3.
Je n'arrive pas à trouver des informations fiables sur les performances de Chicken Scheme par rapport à OCaml. C'est un des Scheme efficaces, et il y a une communauté derrière (cf. la relativement large couverture de bibliothèque (eggs) disponibles), mais très peu d'information trouvables en ligne sur les performance en pratique.
Par ailleurs pour servir de représentation intermédiaire il faut que les utilisateurs puissent écrire du code bas niveau, où des informations de typage partielles sont connues et exploitées. Il me semblait que Chicken se restreignait à R5RS. Quel est le support dans le langage pour dire qu'une donnée est un entier de 32 bits, ou ne peut pas être un pointeur, pour manipuler des flottants non boxés, etc. ? Ou alors tu as en tête l'usage d'une représentation intermédiaire utilisée par Chicken (comme le bytecode Guile par exemple), mais alors laquelle ?
La syntaxe n'a pas grand chose à voir avec le but de Malfunction. C'est un langage intermédiaire, pas un langage de surface pour les utilisateurs. Du moment que la syntaxe est non-ambiguë, clairement définie et facile à produire et à lire, ça pourrait être du XML ça n'aurait aucune importance.
Beuh, encore une fois le but c'est d'obtenir facilement un compilateur décent pour un langage expérimental à moindre coût, si pour cela il faut piper dans un fichier texte au milieu je ne vois pas vraiment le soucis. Par ailleurs le compilateur OCaml expose une API pour manipuler directement la compilation (mais encore une fois elle n'est pas stable) si c'est vraiment important.
Je ne vois pas vraiment l'intérêt.
Lambda a bien une représentation des valeurs qui permet de manipuler les types sommes (puisque c'est la représentation intermédiaire du compilateur OCaml, qui en a). Par contre il n'y a pas de pattern-matching complexe au niveau de Lambda (seulement des switches sur les tags ou des entiers), puisque le pattern-matching est compilé en amont, après le typage.
Imagine que j'ai un programme OCaml qui veut appeler une fonction Links (ou Eff ou Idris) ou l'inverse. Je peux vérifier que les types sont à peu près cohérents (les deux langages n'ont pas les mêmes types mais il y a sous-ensemble commun qui garantissent à peu près les mêmes comportements), compiler les deux vers Lambda et les lier ensemble. Pas besoin que Lambda lui-même soit typé, il faut seulement que les stratégies de compilation choisies pour ces types communs soient compatibles (ou qu'on sache insèrer un peu de code glue entre les deux).
Par exemple ça peut permettre d'échanger facilement des données de grande taille (par exemple un gros terme de preuve généré par Idris) sans copie/traduction, parce qu'en partageant le backend et le runtime tu as la même représentation des deux côtés.
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par Aluminium95 . Évalué à 1.
Oui, donc il faut encore plus une syntaxe spécifiée, c'est à dire, avec une spécification. Parce que bon, dépendre d'un truc qui peut casser à tout moment je trouve que c'est pas super. Ou alors il faut que ocaml puisse garantir une certaine stabilité de cette représentation intermédiaire, ce qui apparement n'est pas à l'ordre du jour.
C'est en fait le point clef d'utiliser un scheme plutôt qu'une représentation qui de l'avis même de l'auteur, n'aurait jamais du être exposée en dehors du compilateur.
De plus, j'ai l'impression que du confonds la syntaxe de malfunction et la syntaxe de Lambda. Qui sont apparemment deux langages différents, par exemple quand tu parles de
C'est à propos de Malfunction, et non pas de Lambda. Or, la question porte justement sur le fait de remplacer Lambda par un scheme … donc cette remarque n'a strictement aucun intérêt (elle ne porte pas sur le bon objet).
Ensuite, j'ai l'impression que l'objectif n'est pas bien défini. Parce que d'un côté tu dis
Et ensuite
Ce qui veut dire que même une fois que ton langage devient « mûr » tu veux continuer à utiliser cette architecture ? Même si de ton propre avis
Ce qui (pour moi) sous-entends que c'est une phase « alpha », prototype, enfin, quelque chose de pas propre. Et quand on voudra le faire proprement, voilà ce qu'il va se passer :
Ah, bah, on repose sur un truc instable, génial.
Je veux bien te croire sur parole (étant donné qu'il n'existe pas de spécification du langage), mais cet argument est quand même bien foireux, je te le refais
Hophophop, voilà ! Bon, j'ai retiré « intermédiaire » et changé le nom … Soit ce que tu dis est qu'il est possible de le faire simplement, ce qui est le cas dans à peu près n'importe quel langage (même x86) soit tu dis qu'il existe une syntaxe spéciale, et alors l'argument n'a aucune valeur.
C'est minime, c'est juste que bon, tu n'as pas à construire :
En plus, le fait que tout soit « au même niveau » permet aux gens d'ajouter si besoin des syntaxes à ton langage de macros, ou d'en changer le sens plutôt facilement, en restant dans un même langage, plutôt que de devoir utiliser du ocaml pour changer le fonctionnement d'un langage (malfunction) et la manière dont il se compile vers un troisième (Lambda).
Après c'est vrai que c'est beau en théorie, mais qu'en pratique c'est peut être pas idéal du tout. Il faudrait en parler avec l'auteur pour savoir quelles étaient les raisons de son choix.
On ne peut pas le faire en utilisant un programme C intermédiaire ? Ça revient presque au même (parce que la glue et l'analyse de type tu la feras quand même). C'est plus complexe techniquement, certes.
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par kantien . Évalué à 1. Dernière modification le 26 juin 2016 à 18:39.
La syntaxe (et la sémantique !) de Malfunction est spécifiée.
Pour le reste de tes interrogations, la lecture de sa présentation pour le ML Workshop t'éclairera peut être.
J'ai l'impression que Malfunction, dans l'esprit de son auteur, est dans la lignée d'un LLVM mais pour des langages fonctionnels statiquement typés avec gestion automatique de la mémoire. Scheme comme langage cible, par exemple, est exclus à cause de ses vérifications dynamiques de typage ce qui est une perte de temps pour des langages dont le bon typage est déjà vérifié à la compilation.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par Aluminium95 . Évalué à 1.
Merci ! Ça répond exactement à ma question. J'aurais du regarder directement là
C'est l'argument clef qui met Lambda devant Scheme, en particulier il dit après
Cependant on peut quand même se poser quelques questions parce que ce n'est pas vraiment rassurant de lire ensuite :
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par kantien . Évalué à 1. Dernière modification le 26 juin 2016 à 22:25.
Ma réponse du dessous tombe à l'eau, maintenant. :-P
Cela montre surtout qu'il reste encore du travail à faire dessus, mais tout comme lui, sa conjecture me semble plus que vraisemblable. Et il ajoute qu'en cas de problème cela révélerai surtout un bug dans le compilateur OCaml : ce qui est fort possible, il n'a pas été certifié.
Cela étant, il me semble que dans la famille des compilateurs C, seul CompCert est certifié et a résisté aux tests Csmith.
Pour ce qui est de la famille des compilateurs de la famille ML, j'ai cru comprendre que Jacques Garrigue avait certifié certaines implémentations.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par gasche . Évalué à 3.
L'implémentation OCaml n'est pas du tout vérifiée (par contre il y a des versions modifiées et simplifiées qui ont été "certifiées" au sens des normes machin il me semble, en tant que logiciel utilisé par Scade et autres produits Esterel-tech) est est pleine de bugs (comme tous les logiciels de cette ampleur), nous en corrigeons un petit peu chaque jour ou presque.
Effectivement le test aléatoire du compilo OCaml avec Malfunction serait une façon intéressante de découvrir des bugs et j'espère que quelqu'un (Stephen, moi ou quelqu'un d'autre) aura le temps de faire joujou avec ça, c'est assez marrant en plus.
Un autre truc que j'aimerais faire c'est fuzzer le type-checker, mais bien sûr pour cela Malfunction ne peut pas être utilisé. Un autre travail récent qui pourrait aider sur ce sujet est décrit dans A Type Checker for Annotated OCaml Abstract Syntax Trees, or An Effective Type System for OCaml par Pierrick Couderc, Michel Mauny, Grégoire Henry et Fabrice Le Fessant.
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par gasche . Évalué à 3.
P.S.: Stephen Dolan a aussi travaillé sur l'ajout de l'instrumentation pour afl-fuzz dans le compilateur OCaml, donc il est possible qu'il propose un fuzzer passant par malfunction et piloté par AFL. (AFL fait des opérations de fuzzing byte-par-byte, donc Stephen avait proposé d'écrire une fonction qui prend une chaîne d'octets et la transforme en un programme OCaml—ou Malfunction en l'occurence.)
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par Dinosaure (site web personnel) . Évalué à 1.
Encore une fois, la syntaxe importe peu. Malfunction permet d'utiliser le back-end d'OCaml (donc tout la compilation d'un bytecode bas niveau vers du code natif) comme c'est le cas avec LLVM-IR. LLVM-IR a aussi une syntaxe et on peut très bien soit produire à partir d'une librairie du code LLVM-IR et le piper vers le compilateur LLVM (et c'est le cas avec Kaleidoscope) ou utiliser une librairie qui fait cette glue entre représentation intermédiaire et code natif (comme c'est le cas avec le
compiler-libsd'OCaml).Il est en effet dit que le bytecode Lambda d'OCaml n'a pas l'ambition d'être stable. Maintenant, je pense que Malfunction peut se doter de cette caractéristique en étant lui même une abstraction de Lambda (et donc de faire la glue nécessaire entre les différentes versions de Lambda).
Le point est surtout d'offrir un outil qui permet de produire du code natif spécialisé pour des langages fonctionnels. La comparaison, selon l'objectif de Malfunction, avec Scheme ne se porterait, en l'état pour l'instant, que sur les performances - on peut pas vraiment parler encore de stabilité et de compatibilité vu le numéro de version du projet. Un propos, et c'est ce que souligne Gasche, c'est une comparaison des performances entre le runtime OCaml et le runtime des différentes implémentations de Scheme.
Encore une fois, si la différence est purement syntaxique (en incluant les sucres syntaxiques qui peuvent faire la glue entre les différentes versions de Lambda), elle n'est pas importante.
C'est ce que fait un compilation de manière général, piper une représentation intermédiaire d'une passe à une autre et c'est l'objectif même de LLVM-IR ou de Malfunction: passer d'un dialecte à un autre. Si techniquement ensuite, on utilise un pipe nommé ou whatever, ça reste un détail technique qui je pense peut être très facilement remplacé (et qui n'a que peut d'importance et qui, surtout, ne concerne en rien la qualité propre du dit langage).
Justement, Malfunction peut s'assurer d'une API stable en étant lui même une abstraction d'une représentation intermédiaire (le Lambda) qui, heureusement, évolue - tout comme LLVM-IR évolue et a aussi des casse de compatibilité mais qui offre des librairie permettant de produire cette représentation intermédiaire qui garantissent un minimum de stabilité (et c'est le cas pour les librairies disponibles en OCaml et en C++).
C'est là où on voit que tu as une méconnaissance de l'objectif réel de Malfunction. Bien entendu que tu peux faire toi même un back-end vers ASM x86 ayant une représentation optimisé des types sommes mais la véritable question est: est ce que tu veux réellement produire toi même de l'ASM x86 ? et quid des autres ASM ? Malfunction réponds à cette question en te proposant un langage intermédiaire qui produit du Lambda pouvant être directement manipuler par le back-end d'OCaml et ainsi compiler vers du natif (et pas uniquement du x86) en proposant un runtime optimisé pour les langages fonctionnels (comme c'est le cas pour Idris).
C'est comme LLVM-IR mais qui reste un langage intermédiaire bas niveau et pas forcément optimisé pour les langages fonctionnels de base - il peut bien sûr être complété par un runtime optimisé pour un langage fonctionnel (comme c'est le cas pour Haskell - mais ça demande des manipulations qui ont d'ailleurs eu lieu en plein dans la spécification de LLVM-IR). Le point est surtout de proposer un runtime avec un garbage-collector pensé pour les langages fonctionnels (et pour le coup, l'intégration d'un GC fait maison dans LLVM-IR est une tâche difficile).
Bah euh, c'est justement le point. Malfunction offre juste un langage intermédiaire. Après c'est à toi de faire le langage haut niveau par dessus Malfunction qui reste une représentation intermédiaire pour un back-end spécifique aux langages fonctionnels. Et pour preuve, l'auteur a réussi à utiliser Malfunction dans Idris - il a rien changé Idris (même si il dénote que certaines constructions du langage ne sont pas disponible avec Malfunction - mais je pense que c'est surtout une question de temps et de travail) mais il a changé le back-end avec, selon ses dires, un gain de performance non négligeable.
Donc oui, tu devras toujours faire un lexer/parser/passe vers Malfunction comme c'est le cas aussi pour LLVM-IR. Mais c'est l'intérêt même de Malfunction. Donc je vois pas trop ce que tu essayes de dénoter ici.
"C'est plus complexe techniquement, certes." et c'est bien la raison de Malfunction.
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par Aluminium95 . Évalué à 0. Dernière modification le 26 juin 2016 à 21:42.
Je crois qu'il y a incompréhension mutuelle.
La question était : pourquoi ocaml ? Pas pourquoi malfunction, pas pourquoi un mec voudrait écrire un compilateur rapidement, pas pourquoi est-ce que mettre dans le pointeur l'information d'un type somme c'est cool. Juste pourquoi le mec qui fait malfunction utilise ocaml. C'est tout. À partir de là, encore une fois, tes réponses sont à côté de la question, parce que la majorité de ce que tu dis concerne un mec qui veut utiliser malfunction.
Oui, c'est justement la question.
Mais j'en ai rien à faire ! Je te demande pourquoi utiliser ocaml quand tu pouvais par exemple utiliser des macros scheme. C'est le mec qui code malfunction qui se fait chier, pas l'utilisateur final (qui de toute manière, cherche au départ à coder un compilateur, rappelons le).
J'en conclus donc
Idem. Je ne vois pas en quoi tes arguments sont pertinents.
Je n'ai JAMAIS dit que je voulais complier directement du malfunction vers de l'ASM x86, c'était juste une petite pique pour préciser que l'argument avancé n'avait aucune valeur. C'était pourtant assez clair (il me semble).
Pour revenir sur la stabilité
Oui, j'ai même dit que malfunction offrait une interface stable, la question c'est pourquoi ne pas avoir choisi un langage stable pour faire le reste du boulot. C'est peut-être pour des raisons techniques intéressantes, comme par exemple la performance de la gestion des types sommes, comme tu l'as laissé entendre, et ça c'est un argument pertinent.
pour finir
Oui … on est bien d'accord, on ne parle juste pas de la même chose.
Pour reprendre. Malfunction compile vers Lambda, qui est un langage basé sur des S-expressions qui n'est pas standardisé, mais qui est une représentation intermédiaire du langage ocaml, ce qui permet d'être compilé efficacement. Je demande si on ne pourrait pas imaginer utiliser un scheme à la place de lambda : basé sur des s-expressions, standardisé, qui bénéficie d'un compilateur efficace. Je ne dis pas que c'est une idée géniale, juste que pour l'instant je n'ai pas été convaincu par tes arguments.
EDIT: je me suis trompé de destinataire, j'ai mal cliqué pour la réponse :-.
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par kantien . Évalué à 3. Dernière modification le 26 juin 2016 à 22:07.
En même temps, si tu ne lis pas les raisons données par le principal intéressé :
Extrait de son abstract de présentation pour le ML Workshop, seconde partie : Why OCaml ?. ;-)
Il aborde même la solution de Scheme à laquelle il objecte :
Malfunction s'adresse aux personnes qui veulent obtenir rapidement un compilateur performant pour des langages fonctionnels statiquement typé (ce pourquoi ce langage est essentiellement du lambda-calcul non typé). Les systèmes de typage statique semble être le sujet d'étude de l'auteur, et l'exemple qu'il fournit pour Idris (écrit en Haskell) correspond à un langage avec types dépendants. Le développeur du langage peut alors se concentrer uniquement sur son type checker et sa compilation vers Malfunction qui se chargera alors de passer la main au back-end OCaml.
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par gasche . Évalué à 5.
Par ailleurs, tu es aussi très défensif, voire agressif et désagréable, dans tes arguments. C'est une discussion technique où les gens posent des questions et y répondent—il n'y a pas de désaccord de fond, au pire des incompréhensions à clarifier—c'est plus agréable pour tout le monde si tu restes calme et respectueux dans ta façon d'écrire, et si tout le monde suppose que chacun est de bonne foi et fiable dans ses affirmations.
(Par exemple: pas besoin de "je n'en ai rien à faire", pas besoin de petite pique, et pas besoin d'expliquer que les arguments des gens n'ont "aucune valeur".)
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par gasche . Évalué à 3.
On a dû mal se comprendre. Malfunction c'est en gros une version simplifiée (et spécifiée) de Lambda, un langage à une distance minimale qui permet d'être clair et facilement interprétable et quand même se traduire de façon très transparente vers Lambda. Quand tu proposes d'utiliser un Scheme "à la place", je comprends "à la place de Malfunction", et pas "à la place de Lambda", puisque (1) Lambda lui-même n'est pas proposé comme cible directe pour les autres langages et (2) traduire Malfunction tel qu'il est vers Lisp/Scheme serait difficile voire impossible (sans perte d'efficacité) vu l'impedance mismatch entre les représentations. Si tu veux un compilo qui vise une implem. Lisp/Scheme, il faut produire du Lisp/Scheme (ou une de leurs représentations internes), pas du Lambda-de-OCaml-simplifié.
Ou alors tu demandes peut-être si le compilateur OCaml pourrait compiler vers (la représentation intermédiaire d'un compilateur) Lisp ou Scheme, mais là c'est une question encore différente qui n'a pas vraiment de sens—en fait les premiers Caml étaient implémentés de cette façon là, et je crois qu'il y a eu un frontend Bigloo ou Stalin pour Caml, mais aujourd'hui les langages, sémantiques et attentes de domaine optimisé sont trop différentes je pense.
Regarde par exemple la partie lambda_switch de l'AST Lambda, qui définit une construction de switch avec une famille de cas pour gérer les constructeurs constants (représentés comme des entiers) et les constructeurs à paramètres (boxés sur le tas, donc avec un pointeur en tête et un tag de constructeur quand on suit le pointeur).
L'auteur de compilateur continue à viser la représentation Malfunction, qui est stable. C'est s'il veut appeler le compilateur OCaml directement depuis son frontend qu'il doit utiliser l'API du compilo qui n'est pas stable. Mais bon LLVM n'offre pas de stabilité entre les versions non plus et pourtant plein de compilateurs l'utilisent—souvent à raison.
Par ailleurs c'est classique dans un compilateur de produire une représentation intermédiaire dans un fichier et d'appeler derrière un outil externe—au lieu de tout avoir dans un même processus. Chicken Scheme lui-même produit du C et appelle un compilo C derrière. Beaucoup de compilateurs natifs produisent une représentation textuelle de l'assembleur généré et appellent l'assembleur système derrière. Pareil pour le linker, tu ne recodes pas, tu appelles un programme externe. Ce n'est pas fondamentalement "alpha" et ça marche bien.
Sur les macros: que tu définisses un langage propre (Malfunction) ou un ensemble de macros par dessus un langage plus simple, ça ne change pas grand chose du point de vue de l'utilisateur, c'est-à-dire l'implémenteur d'Idris, Eff ou Links. Dans tout les cas il faut produire cette représentation intermédiaire.
Ben ça dépend de comment les deux langages sont compilés et si les représentations sont compatibles. Par exemple si les types algébriques sont représentés différemment, il faut traduire d'une représentation vers l'autre, donc tu as coût important quand tu transfères des données (alors qu'avec une représentation partagée, rien à faire). Si tu as deux GCs avec des attentes incompatibles, encore une fois c'est la prise de tête et une coopération moins efficace.
Par exemple Coq utilise pas mal le fait qu'il compile vers OCaml pour écrire des programmes mixtes. (Dans Compcert par exemple, le gros du compilo est du Coq, mais il y a des parties en OCaml et c'est bien pratique (et l'efficacité est importante).
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par Aluminium95 . Évalué à 1.
En effet, je me suis mal exprimé.
Je voulais savoir pourquoi ocaml était un choix rationnel, ou plutôt, pourquoi malfunction produit du Lambda plutôt que du Scheme par exemple. À priori, je n'avais pas vu la grosse différence entre les deux langages. Pour moi on y trouvait
Mais il est vrai que la gestion des types sommes peut être pénible. L'argument qui consistait à préférer un scheme était celui de dire que contrairement à Lambda, il serait spécifié (un souci de moins).
Oui mais il est utilisé, enfin, c'est le backend.
Une question plus pertinente (puisque visiblement les types sommes en Scheme c'est vraiment peu performant) serait : pourquoi ne pas compiler vers GHC Core. Ici, on a encore un truc interne et pas forcément stable, mais la définition à le mérite d'être assez simple (au moins en surface). Par contre, il faudrait écrire Malfunction en haskell (pour générer l'AST reconnu par GHC Core).
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par gasche . Évalué à 3.
Core est un langage intermédiaire typé, donc pour pouvoir produire une représentation Core il faut construire une dérivation de typage qui montre que ton programme intermédiaire vérifie les règles de typage de Core. C'est très difficile voire impossible en pratique (sans sacrifier les performances), ce qui rend la représentation Malfunction, non typée, plus agréable comme cible.
(C'est un point de détail intéressant qui m'a été rappelé par Sam Lindley, un des implémenteurs de Links et donc une des cibles pour Malfunction. À l'inverse, avoir une représentation intermédiaire typée a aussi des avantages quand on développe un compilateur (par exemple pour débugger, et pour mieux comprendre le typage du langage de surface ou la sémantique des optimisations effectuées), donc ce n'est pas un mauvais choix de la part de GHC.)
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par gasche . Évalué à 2.
Certes, x86 permet d'exprimer efficacement les types sommes. Mais la traduction n'est pas simple et demande beaucoup d'effort; ce n'est pas une représentation intermédiaire adaptée pour un compilateur. Au contraire, une représentation intermédiaire pour OCaml essaie de faciliter la représentation efficace de ce qui existe dans le langage, et de manière agréable à produire (si on suppose que le compilateur est bien conçu), donc c'est une indication forte que tous les aspects importants du langage OCaml seront bien couverts par cette représentation.
Il n'est pas du tout clair que n'importe quel langage permet de représenter les types sommes de façon efficace. En Scheme par exemple, comment coderais-tu quelque chose comme
Mes idées immédiates pour faire cela sont soit de construire des paires
(tag, paramètres), c'est-à-dire une s-exp donc la tête est un symbole'leafou'nodeet le nombre d'éléments suivants est en fonction, ce qui donne une représentation moins efficace (OCaml met le nom de constructeur dans le mot de tête aussi utilisé par le GC, alors que là tu paies avec un mot de plus par valeur; et le test d'égalité de symboles est plus lent), ou alors essaie d'utiliser unstructet tester l'identité du type, ce qui donne encore une représentation moins efficace (le nom du type est dans un espace de nom plus grand que les constructeurs fixés ici, et donc va être plus difficile à encoder comme une série de petits entiers consécutifs).[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par gasche . Évalué à 2.
(Après avoir regardé un peu plus en détail, d'une part il vaudrait mieux utiliser des petits entiers que des symboles dans ma proposition ci-dessus, donc
'(0 leaf-value)et'(1 left right), et d'autre part Chicken Scheme a une notion de tagged pointer qui serait sans doute un meilleur choix ici, où l'information de tag pour les constructeurs non-constants serait stockée avec le pointeur plutôt qu'avec la valeur, même si ça reste une représentation nettement moins compacte—Haskell stocke le constructeur dans le pointeur parfois, mais de façon plus compacte.)[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par Axioplase ıɥs∀ (site web personnel) . Évalué à 3.
et
ou
Modulo les possibles erreurs de syntaxe car j'alterne entre différents Schemes et Lisps, c'est pas dur, quoi…
[^] # Re: Représentations intermédiaires du compilateur OCaml
Posté par gasche . Évalué à 3. Dernière modification le 27 juin 2016 à 21:51.
D'une part, le code est incorrect si je commence à construire des arbres de paires; en OCaml
'apeut être instancié par(int * int)par exemple. D'autre part l'encodage ne passe pas à l'échelle si j'ai plusieurs constructeurs, par exemple un constructeur pour les noeuds noirs et un pour les rouges dans un arbre rouge-noir; ou alors deux types de feuilles différentes, etc.Je ne dis pas que c'est dur (ci-dessus je proposais des encodages qui sont relativement agréables à utiliser si le langage a du pattern-matching comme racket/match par exemple), mais je pense que trouver une représentation générique n'est pas aussi simple et risque de pêcher en performances par rapport à un runtime (et surtout un choix de représentation des valeurs) qui gère ça en dur.
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.