tag:linuxfr.org,2005:/users/kantienLinuxFr.org : les contenus de kantien2019-12-04T16:56:08+01:00/favicon.pngtag:linuxfr.org,2005:Diary/388202019-12-03T16:05:49+01:002019-12-04T16:58:39+01:00Sémantiques mécanisées : quand la machine raisonne sur ses programmes.Licence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<p>Depuis l'an dernier, Xavier Leroy est le nouveau titulaire de la chaire « sciences du logiciel » au <a href="https://fr.wikipedia.org/wiki/Coll%C3%A8ge%20de%20France" title="Définition Wikipédia">Collège de France</a>. J'en avais fait un <a href="//linuxfr.org/users/kantien/journaux/nouvelle-chaire-sciences-du-logiciel-au-college-de-france">journal</a> pour présenter le thème de sa première année de cours où il abordait la correspondance entre programmes et démonstrations mathématiques, connue sous le nom de <a href="https://fr.wikipedia.org/wiki/Correspondance_de_Curry-Howard">correspondance de Curry-Howard</a>.</p>
<p>Cette année, il a décidé d'aborder la formalisation de la sémantique des langages de programmation avec l'aide de la machine (en utilisant l'assistant de preuve Coq). On pourra trouver <a href="http://www.college-de-france.fr/site/xavier-leroy/course-2019-2020.htm">le programme de l'année sur le site du Collège de France</a> :</p>
<blockquote>
<p>« Que fait ce programme, au juste ? » Pour répondre à cette question avec la précision des mathématiques, il nous faut une sémantique formelle du langage dans lequel ce programme est écrit. Plusieurs approches de la sémantique formelle sont bien maîtrisées aujourd'hui : sémantiques dénotationnelles, qui interprètent le programme comme un élément d'une structure mathématique ; sémantiques opérationnelles, qui décrivent les étapes successives des exécutions du programme ; sémantiques axiomatiques, qui décrivent les assertions logiques satisfaites par ces exécutions. Ces sémantiques formelles ont de nombreuses applications : non seulement définir les langages de programmation avec une précision bien plus grande qu'un manuel de référence écrit en français ou en anglais, mais aussi vérifier la correction des algorithmes et des outils qui opèrent sur les programmes, comme les compilateurs, les analyses statiques, et les logiques de programmes.</p>
<p>La sémantique d'un langage de programmation peut être volumineuse et complexe, rendant les démonstrations « sur papier » utilisant ces sémantiques pénibles et peu fiables. Mais nous pouvons nous adjoindre l'aide de l'ordinateur ! Les assistants à la démonstration (Coq, HOL, Isabelle, etc.) fournissent un langage rigoureux pour définir les sémantiques, énoncer leurs propriétés, écrire des démonstrations, et vérifier automatiquement la cohérence de ces démonstrations. Cette mécanisation est un puissant levier pour faire passer les approches sémantiques à l'échelle des langages et des outils de programmation réalistes.</p>
<p>Le cours présentera cette approche de sémantique mécanisée sur l'exemple de petits langages impératifs ou fonctionnels, avec des applications aux logiques de programmes et à la vérification de compilateurs et d'analyseurs statiques. Toutes ces notions seront entièrement mécanisées avec l'assistant Coq. Cependant, une grande partie du cours restera accessible sans connaissance préalable de Coq. Le séminaire approfondira l'approche dans plusieurs directions, allant de la mécanisation des « gros » langages comme Javascript et Rust à l'utilisation d'assistants à la démonstration pour enseigner les fondements des langages de programmation.</p>
</blockquote>
<p>Les cours ont commencé jeudi dernier et se tiendront tous les jeudis jusqu'à début février (sauf ce jeudi, le cours étant annulé suite au mouvement de grève pour la réforme des retraites). On peut ensuite les retrouver au format audio (dès le lendemain) ou vidéo (quelques jours plus tard, celui de jeudi dernier est disponible depuis hier lundi) sur la page du cours accompagnés du pdf de la présentation.</p>
<p>Mais, chose exceptionnelle et même une première pour cet institut, les cas pratiques étudiés ont <a href="https://github.com/xavierleroy/cdf-sem-meca">leur dépôt github</a> pour ceux qui voudrait jouer avec. Xavier Leroy y traitera la formalisation et l'implémentation de deux langages simples, l'un impératif et l'autre fonctionnel statiquement typé.</p>
<p>Parmi les séminaires qui suivent l'enseignement, on trouvera, entre autres, Philip Wadler (auteur des types classes de Haskell ou des génériques en Java) parlant de l'utilité des assistants de preuve pour enseigner la théorie des langages de programmation, ou d'autres intervenants sur l'usage des méthodes de sémantiques formelles pour étudier des langages comme javascript ou rust.</p>
<div><a href="https://linuxfr.org/users/kantien/journaux/semantiques-mecanisees-quand-la-machine-raisonne-sur-ses-programmes.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/118810/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/kantien/journaux/semantiques-mecanisees-quand-la-machine-raisonne-sur-ses-programmes#comments">ouvrir dans le navigateur</a>
</p>
kantienhttps://linuxfr.org/nodes/118810/comments.atomtag:linuxfr.org,2005:Diary/382162018-11-14T15:43:36+01:002018-11-14T15:43:36+01:00Nouvelle chaire Sciences du logiciel au Collège de France.Licence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<p>À partir de cette année l'informatique et les sciences du numériques se voient dotées d'une nouvelle chaire au Collège de France, intitulée « Sciences du logiciel », dont le titulaire est <a href="https://fr.wikipedia.org/wiki/Xavier%20Leroy" title="Définition Wikipédia">Xavier Leroy</a>. Xavier Leroy est connu pour être l'architecte et un des principaux développeurs du langage de programmation fonctionnel <a href="https://ocaml.org/">OCaml</a> ainsi que du compilateur C formellement vérifié <a href="http://compcert.inria.fr/">CompCert</a>. <a href="//linuxfr.org/users/kantien/journaux/xavier-leroy-est-le-laureat-2016-du-prix-milner">Il a reçu en 2016 le prix Milner</a> pour récompenser ses travaux sur la fiabilité des systèmes informatiques.</p>
<p>La leçon inaugurale de cette nouvelle chaire aura lieu demain à 18h00, sera <a href="http://www.college-de-france.fr/site/xavier-leroy/Retransmission-en-direct-lecon-inaugurale-xavier-leroy.htm">diffusée en direct via le site du Collège de France</a> et aura pour thème <em>« Le logiciel, entre l'esprit et la matière »</em>.</p>
<p>Les leçons de cette année se tiendront le mercredi matin à 10h00 dès la semaine prochaine sur le thème <em>« Programmer = démontrer ? La correspondance de Curry-Howard aujourd'hui »</em> (<a href="http://www.college-de-france.fr/site/xavier-leroy/course-2018-2019.htm">programme de l'année</a>). Usuellement, les cours sont disponibles en streaming ou en téléchargement une semaine après sur <a href="http://www.college-de-france.fr/site/xavier-leroy/course-2018-2019.htm">la page dédiée</a>. Le cours est présenté en ces termes sur le site du Collège de France :</p>
<blockquote>
<p>Informatique et logique mathématique sont historiquement liées : Alan Turing, John von Neumann, Alonzo Church et bien d’autres fondateurs de l’informatique étaient logiciens, professionnels ou de formation. Le cours 2018-2019 de la chaire de Sciences du logiciel étudie un autre lien, de nature mathématique celui-là (il s’agit d’un isomorphisme), entre langages de programmation et logiques mathématiques. Dans cette approche, démontrer un théorème, c’est la même chose que d’écrire un programme ; énoncer le théorème, c’est la même chose que de spécifier partiellement un programme en donnant le type qu’il doit avoir. […]</p>
<p>Le cours retracera ce bouillonnement d’idées à la frontière entre logique et informatique, et mettra l’accent sur les résultats récents et les problèmes ouverts dans ce domaine. Le séminaire donnera la parole à 7 experts du domaine pour des approfondissements et des points de vue complémentaires.</p>
</blockquote>
<p>Pour ma part, une leçon a particulièrement retenu mon attention, celle du 9 janvier : <em>Le forcing, une transformation de programme comme une autre ?</em> Le forcing, pour ceux qui ne connaissent pas, est une technique de démonstration inventée dans les années 1960 par <a href="https://fr.wikipedia.org/wiki/Paul_Cohen">Paul Cohen</a> pour prouver l'indécidabilité de certains énoncés en théorie axiomatique des ensembles, comme <a href="https://fr.wikipedia.org/wiki/Hypoth%C3%A8se_du_continu">l'hypothèse du continu de Cantor</a>.</p>
<div><a href="https://linuxfr.org/users/kantien/journaux/nouvelle-chaire-sciences-du-logiciel-au-college-de-france.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/115727/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/kantien/journaux/nouvelle-chaire-sciences-du-logiciel-au-college-de-france#comments">ouvrir dans le navigateur</a>
</p>
kantienhttps://linuxfr.org/nodes/115727/comments.atomtag:linuxfr.org,2005:Diary/376112017-11-29T18:09:55+01:002017-11-29T18:09:55+01:00Que fait `man` passé minuit ?Licence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<p>Au détour de mes pérégrinations sur la toile, je suis tombé sur un fil au contenu amusant et étonnant sur le <a href="https://unix.stackexchange.com/questions/405783/why-does-man-print-gimme-gimme-gimme-at-0030">stack exchange Unix</a>. Mais que fait la commande <code>man</code> après minuit ? Se transforme-t-elle en Gremlins si on lui donne à manger ? Non, elle se met à chanter ! mais à une heure bien précise. :-)</p>
<p>Cet <em>easter egg</em> est resté confidentiel pendant 6 ans. Il fut introduit par ce <a href="http://git.savannah.nongnu.org/cgit/man-db.git/commit/src/man.c?id=002a6339b1fe8f83f4808022a17e1aa379756d99">commit</a> et trouve son origine dans <a href="https://twitter.com/marnanel/status/132280557190119424">une blague faite sur twiiter</a> par un des amis de l'auteur de <code>man</code>. L'auteur vient de le retirer du code et il disparaîtra à partir de la version <code>2.8.0</code> à venir de <code>man-db</code>. Pour ceux qui veulent le tester et sans attendre l'heure fatidique de minuit et demi, le plus simple et de taper cette commande en root (pour pouvoir changer l'heure locale de la machine) :</p>
<pre><code class="sh">$ date +%T -s <span class="s2">"00:30:00"</span><span class="p">;</span> man
<span class="m">00</span>:30:00
gimme gimme gimme</code></pre>
<p>pour les fans de <a href="https://fr.wikipedia.org/wiki/ABBA" title="Définition Wikipédia">ABBA</a>, vous aurez reconnu la référence au fameux titre <em>Gimme, gimme, gimme a man after midnight</em>. :-D</p>
<p>La prochaine découverte sera peut être que Satoshi Nakomoto a placé une référence à <em>Money, Money, Money</em> dans le code des clients bitcoin.</p><div><a href="https://linuxfr.org/users/kantien/journaux/que-fait-man-passe-minuit.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/113214/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/kantien/journaux/que-fait-man-passe-minuit#comments">ouvrir dans le navigateur</a>
</p>
kantienhttps://linuxfr.org/nodes/113214/comments.atomtag:linuxfr.org,2005:News/380962017-07-06T11:29:33+02:002017-07-08T17:10:04+02:00Qui est le coupable ? Le processeur ! Retour sur un bogue important des SkyLake & Kaby Lake IntelLicence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<div><p>Certains d’entre vous ont peut‐être vu passer l’information : les derniers processeurs Intel des familles Skylake et Kaby Lake sont victimes d’un bogue lorsque l’<em>hyper‐threading</em> est activé. On trouve par exemple <a href="https://arstechnica.com/information-technology/2017/06/skylake-kaby-lake-chips-have-a-crash-bug-with-hyperthreading-enabled/">un article sur <em>Ars Technica</em></a>, et Debian <a href="https://lists.debian.org/debian-devel/2017/06/msg00308.html">propose des instructions détaillées pour corriger le problème en mettant à jour le microcode (<em>firmware</em>) du processeur</a>.</p>
<p>Cette dépêche propose revenir sur les événements qui ont mené à la découverte du problème. Xavier Leroy le décrit en détail dans un article sur le blog de l’équipe Gallium, dont je proposerai un résumé pour les lecteurs francophones.</p></div><ul><li>lien nᵒ 1 : <a title="https://linuxfr.org/users/kantien/journaux/un-bug-qui-est-le-coupable-le-processeur" hreflang="fr" href="https://linuxfr.org/redirect/100218">Journal à l’origine de la dépêche</a></li><li>lien nᵒ 2 : <a title="http://gallium.inria.fr/blog/intel-skylake-bug/" hreflang="en" href="https://linuxfr.org/redirect/100219">Blog Gallium : « How I find a bug in Intel Skylake processors »</a></li><li>lien nᵒ 3 : <a title="http://www.intel.co.uk/content/dam/www/public/us/en/documents/specification-updates/desktop-6th-gen-core-family-spec-update.pdf" hreflang="en" href="https://linuxfr.org/redirect/100220">Mise à jour des spécifications Intel</a></li><li>lien nᵒ 4 : <a title="https://news.ycombinator.com/item?id=14630183" hreflang="en" href="https://linuxfr.org/redirect/100221">Discussion sur ycombinator</a></li><li>lien nᵒ 5 : <a title="https://tech.ahrefs.com/skylake-bug-a-detective-story-ab1ad2beddcd" hreflang="en" href="https://linuxfr.org/redirect/100226">Skylake bug: a detective story</a></li><li>lien nᵒ 6 : <a title="https://fr.wikipedia.org/wiki/Hyper-Threading" hreflang="fr" href="https://linuxfr.org/redirect/100248">Hyper‐threading sur Wikipédia</a></li></ul><div><p>Tout commence en avril 2016 lorsqu’un SIOU (<em>Serious Industrial OCaml User</em>), comme il les appelle, le contacte en privé pour lui signaler un bogue dans un de leur logiciel : ce dernier subit des erreurs de segmentation de manière aléatoire après un certain temps. Il n’arrive pas à reproduire le bogue sur sa propre machine et le côté aléatoire du bogue lui fait soupçonner un problème matériel chez le client (mémoire vive défectueuse, surchauffe…). Il leur propose de tester leur mémoire et de désactiver l’<em><a href="https://fr.wikipedia.org/wiki/Hyper-Threading">hyper‐threading</a></em>. La mémoire était bonne, mais il ne teste pas la désactivation (ce qui aurait résolu le problème).</p>
<p>De son côté, le client fait ses tests et aboutit aux résultats suivants : le bogue est présent avec la version 4.03 mais pas la 4.02.3 du compilateur OCaml, avec GCC mais pas Clang (l’environnement d’exécution d’OCaml est en C), sur GNU/Linux et Windows mais pas macOS (ce qui se comprend, ce dernier utilisant Clang). Les coupables semblent identifiés : OCaml 4.03 et GCC, et le client suppose qu’il y a une erreur dans le code C de l’environnement d’exécution d’OCaml.</p>
<p>Début mai 2016, le client offre un accès à sa machine à Xavier Leroy pour qu’il puisse identifier le problème. Il analyse des vidages mémoire (<em>dumps</em>) post‐plantage, voit bien des problèmes avec le ramasse‐miettes, mais ne comprend pas ce qui peut causer un tel comportement dans son code. Il fait alors des tests en lançant le programme en parallèle (1, 2, 4, 8 ou 16 instances) et, là, tout devient clair : pas de bogue quand l’<em>hyper‐threading</em> n’est pas utilisé. Ils font des tests en le désactivant dans le BIOS et le problème ne se manifeste plus.</p>
<p>Cela aurait pu en rester là : le client était satisfait de pouvoir utiliser une version de l’environnement d’exécution avec Clang, et Xavier Leroy ne sachant pas comment signaler le problème à Intel en reste là. Mais, début 2017, un autre SIOU fait un <a href="https://caml.inria.fr/mantis/view.php?id=7452">rapport de bogue sur le système de suivi d’OCaml</a>. Les symptômes étaient similaires et la discussion sur le ticket fut la suivante :</p>
<ul>
<li>douze heures après l’ouverture, une des ingénieurs précise que tous les ordinateurs qui ont pu reproduire le bogue ont un processeur de la famille Skylake ;</li>
<li>le lendemain, Xavier Leroy signale son expérience passée et propose de désactiver l’<em>hyper‐threading</em> ;</li>
<li>le jour suivant, un autre ingénieur du SIOU rapporte qu’en désactivant l’<em>hyper‐threading</em> le problème disparaît ;</li>
<li>en parallèle, il constate que si l’environnement d’exécution est compilé avec <code>gcc -O1</code> et non <code>gcc -O2</code> alors le bogue disparaît. Ce qui permet de comprendre pourquoi cela apparaît avec la version 4.03, qui est celle inaugurant l’option <code>-O2</code> par défaut pour l’environnement d’exécution ;</li>
<li>Mark Shinwell contacte des collègues chez Intel et s’occupe de rapporter le problème au support client d’Intel.</li>
</ul><p>Enfin, cinq mois plus tard, Debian publie une mise à jour du microcode des processeurs Intel et Intel publie, en avril, <a href="http://www.intel.co.uk/content/dam/www/public/us/en/documents/specification-updates/desktop-6th-gen-core-family-spec-update.pdf">une mise à jour des spécifications de la 6<sup>e</sup> génération de ses processeurs</a>. On trouve à la page 65 de ce document une mention du problème SKL150 qui était à l’origine de tous ces bogues, présenté en ces termes chez Debian :</p>
<blockquote>
<p>SKL150 - Short loops using both the AH/BH/CH/DH registers and<br>
the corresponding wide register <em>may</em> result in unpredictable<br>
system behavior. Requires both logical processors of the same<br>
core (i.e. sibling hyperthreads) to be active to trigger, as<br>
well as a “complex set of micro‐architectural conditions”.</p>
</blockquote>
<p>Pour ceux que cela intéresse et qui comprennent l’assembleur (ce qui n’est pas mon cas), le problème venait de ce bout de code du <a href="https://fr.wikipedia.org/wiki/Ramasse-miettes_(informatique)">ramasse‐miettes</a> d’OCaml :</p>
<pre><code class="C"><span class="n">hd</span> <span class="o">=</span> <span class="n">Hd_hp</span> <span class="p">(</span><span class="n">hp</span><span class="p">);</span>
<span class="cm">/*...*/</span>
<span class="n">Hd_hp</span> <span class="p">(</span><span class="n">hp</span><span class="p">)</span> <span class="o">=</span> <span class="n">Whitehd_hd</span> <span class="p">(</span><span class="n">hd</span><span class="p">);</span></code></pre>
<p>Qui après expansion des macros donne :</p>
<pre><code class="C"><span class="n">hd</span> <span class="o">=</span> <span class="o">*</span><span class="n">hp</span><span class="p">;</span>
<span class="cm">/*...*/</span>
<span class="o">*</span><span class="n">hp</span> <span class="o">=</span> <span class="n">hd</span> <span class="o">&</span> <span class="o">~</span><span class="mh">0x300</span><span class="p">;</span></code></pre>
<p>Avec Clang, cela donnait :</p>
<pre><code class="asm"><span class="nf">movq</span> <span class="p">(</span><span class="o">%</span><span class="nb">rbx</span><span class="p">),</span> <span class="o">%</span><span class="nb">rax</span>
<span class="err">[</span><span class="nf">...</span><span class="p">]</span>
<span class="nf">andq</span> <span class="kc">$</span><span class="o">-</span><span class="mi">769</span><span class="p">,</span> <span class="o">%</span><span class="nb">rax</span> <span class="err">#</span> <span class="nv">imm</span> <span class="err">=</span> <span class="mh">0xFFFFFFFFFFFFFCFF</span>
<span class="nf">movq</span> <span class="o">%</span><span class="nb">rax</span><span class="p">,</span> <span class="p">(</span><span class="o">%</span><span class="nb">rbx</span><span class="p">)</span></code></pre>
<p>Tandis que le code optimisé de GCC donnait :</p>
<pre><code class="asm"><span class="nf">movq</span> <span class="p">(</span><span class="o">%</span><span class="nb">rdi</span><span class="p">),</span> <span class="o">%</span><span class="nb">rax</span>
<span class="err">[</span><span class="nf">...</span><span class="p">]</span>
<span class="nf">andb</span> <span class="kc">$</span><span class="mi">252</span><span class="p">,</span> <span class="o">%</span><span class="nb">ah</span>
<span class="nf">movq</span> <span class="o">%</span><span class="nb">rax</span><span class="p">,</span> <span class="p">(</span><span class="o">%</span><span class="nb">rdi</span><span class="p">)</span></code></pre>
<p>Qui pouvait lever le bogue du processeur s’il se trouvait dans une petite boucle ?</p>
<p>Ce bogue sur ces processeurs impacte tous les systèmes d’exploitation. Le correctif du microcode pour la génération Skylake existe donc depuis avril, car Intel distribue ses mises à jour à toutes et tous, permettant aux mainteneurs des distributions de réaliser l’empaquetage afin de les rendre disponibles.</p>
<p>Cependant, il n’en va pas de même pour la génération Kaby Lake, pour laquelle Intel ne distribue ses correctifs de microcodes qu’aux seuls constructeurs ou assembleurs. Il résulte de cette situation une grande disparité des disponibilités pour cette mise à jour : certains constructeurs l’ont déjà proposée, d’autres ne le font pas.</p>
<p>Au final, il semblerait que Skylake se soit transformé en Skyfall et que la légendaire crainte gauloise que le ciel leur tombe sur la tête était fondée ! :-D</p></div><div><a href="https://linuxfr.org/news/qui-est-le-coupable-le-processeur-retour-sur-un-bogue-important-des-skylake-kaby-lake-intel.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/112231/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/news/qui-est-le-coupable-le-processeur-retour-sur-un-bogue-important-des-skylake-kaby-lake-intel#comments">ouvrir dans le navigateur</a>
</p>
kantienbubar🦥Benoît SibaudDavy DefaudZeroHeureNils Ratusznikpatrick_ghttps://linuxfr.org/nodes/112231/comments.atomtag:linuxfr.org,2005:Diary/373922017-07-04T15:32:27+02:002017-07-05T00:47:16+02:00Un bug ? Qui est le coupable ? Le processeur !!!Licence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<p>Certains d'entre vous ont peut-être vu passer l'information : les derniers processeurs Intel des familles Skylake et Kaby Lake sont victimes d'un bug lorsque l'hyperthreading est activé. On trouve par exemple <a href="https://arstechnica.com/information-technology/2017/06/skylake-kaby-lake-chips-have-a-crash-bug-with-hyperthreading-enabled/">un article sur Ars Technica</a>, et Debian <a href="https://lists.debian.org/debian-devel/2017/06/msg00308.html">propose des instructions détaillées pour corriger le problème en mettant à jour le firmware du CPU</a>.</p>
<p>Néanmoins, dans ce journal, je vais revenir sur les événements qui ont mené à la découverte du problème. Xavier Leroy le décrit en détail dans un article sur le blog de l'équipe Gallium : <a href="http://gallium.inria.fr/blog/intel-skylake-bug/">How I found a bug in Intel Skylake processors</a>, dont je proposerai un résumé pour les lecteurs francophones.</p>
<p>Tout commence en avril 2016 lorsqu'un SIOU (Serious Industrial OCaml User), comme il les appelle, le contacte en privé pour lui signaler un bug dans un de leur logiciel : ce dernier subit des erreurs de ségmentation de manière aléatoire après un certain temps. Il n'arrive pas à reproduire le bug sur sa propre machine et le côté aléatoire du bug lui fait soupçonner un problème matériel chez le client (ram défectueuse, surchauffe…). Il leur propose de tester leur mémoire et de désactiver l'hyperthreading, la mémoire était bonne mais il ne teste pas la désactivation (ce qui aurait résolu le problème).</p>
<p>De son côté le client fait ses tests et aboutit aux résultats suivants : le bug est présent avec la version 4.03 mais pas 4.02.3 du compilateur OCaml, avec GCC mais pas Clang (le runtime OCaml est en C), sur Linux et Windows mais pas OSX (ce qui se comprend, ce dernier utilisant Clang). Les coupables semblent identifiés : OCaml 4.03 et GCC, et le client suppose qu'il y a une erreur dans le code C du runtime.</p>
<p>Début mai 2016, le client offre un accès à leur machine à Xavier Leroy pour qu'il puisse identifier le problème. Il analyse des dumps post-plantage, voit bien des problèmes avec le ramasse-miette mais ne comprend pas ce qui peut causer un tel comportement dans son code. Il fait alors des tests en lançant le programme en parallèle (1, 2 , 4, 8 ou 16 instances) et là tout devient clair : pas de bug quand l'hyperthreading n'est pas utilisé. Ils font des tests en le désactivant dans le BIOS et le problème ne se manifeste plus.</p>
<p>Cela aurait pu en rester là : le client était satisfait de pouvoir utiliser une version du runtime avec Clang, et Xavier Leroy ne sachant pas comment signaler le problème à Intel en reste là. Mais, début 2017, un autre SIOU fait un <a href="https://caml.inria.fr/mantis/view.php?id=7452">rapport de bug sur le tracker OCaml</a>. Les symptomes étaient similaires et la discussion sur le ticket fut la suivante :</p>
<ul>
<li>douze heures après l'ouverture, une des ingénieurs précise que tous les ordinateurs qui ont pu reproduire le bug ont un CPU de la famille Skylake</li>
<li>le lendemain, Xavier Leroy signale son expérience passée et propose de désactiver l'hyperthreading</li>
<li>le jour suivant, un autre ingénieur du SIOU rapporte qu'en désactivant l'hyperthreading le problème disparaît</li>
<li>en parallèle, il constate que si le runtime est compilé avec <code>gcc -O1</code> et non <code>gcc -O2</code> alors le bug disparaît. Ce qui permet de comprendre pourquoi cela apparaît avec la version 4.03 qui est celle inaugurant l'option <code>-O2</code> par défaut pour le runtime</li>
<li>Mark Shinwell contacte des collègues chez Intel et s'occupe de rapporter le problème au support client de Intel.</li>
</ul><p>Enfin 5 mois plus tard, Debian publie une mise à jour du firmware des CPU Intel et Intel publie, en avril, <a href="http://www.intel.co.uk/content/dam/www/public/us/en/documents/specification-updates/desktop-6th-gen-core-family-spec-update.pdf">une mise à jour des spécifications de la 6ème génération de ses CPU</a>. On trouve à la page 65 de ce document une mention du problème SKL150 qui était à l'origine de tous ces bugs, présenté en ces termes chez Debian :</p>
<pre><code>SKL150 - Short loops using both the AH/BH/CH/DH registers and
the corresponding wide register *may* result in unpredictable
system behavior. Requires both logical processors of the same
core (i.e. sibling hyperthreads) to be active to trigger, as
well as a "complex set of micro-architectural conditions"
</code></pre>
<p>Pour ceux que cela intéresse et qui comprennent l'assembleur (ce qui n'est pas mon cas), le problème venait de ce bout de code du GC OCaml :</p>
<pre><code class="C"><span class="n">hd</span> <span class="o">=</span> <span class="n">Hd_hp</span> <span class="p">(</span><span class="n">hp</span><span class="p">);</span>
<span class="cm">/*...*/</span>
<span class="n">Hd_hp</span> <span class="p">(</span><span class="n">hp</span><span class="p">)</span> <span class="o">=</span> <span class="n">Whitehd_hd</span> <span class="p">(</span><span class="n">hd</span><span class="p">);</span></code></pre>
<p>qui après expansion des macros donne :</p>
<pre><code class="C"><span class="n">hd</span> <span class="o">=</span> <span class="o">*</span><span class="n">hp</span><span class="p">;</span>
<span class="cm">/*...*/</span>
<span class="o">*</span><span class="n">hp</span> <span class="o">=</span> <span class="n">hd</span> <span class="o">&</span> <span class="o">~</span><span class="mh">0x300</span><span class="p">;</span></code></pre>
<p>Avec Clang, cela donnait :</p>
<pre><code class="asm"><span class="nf">movq</span> <span class="p">(</span><span class="o">%</span><span class="nb">rbx</span><span class="p">),</span> <span class="o">%</span><span class="nb">rax</span>
<span class="err">[</span><span class="nf">...</span><span class="p">]</span>
<span class="nf">andq</span> <span class="kc">$</span><span class="o">-</span><span class="mi">769</span><span class="p">,</span> <span class="o">%</span><span class="nb">rax</span> <span class="err">#</span> <span class="nv">imm</span> <span class="err">=</span> <span class="mh">0xFFFFFFFFFFFFFCFF</span>
<span class="nf">movq</span> <span class="o">%</span><span class="nb">rax</span><span class="p">,</span> <span class="p">(</span><span class="o">%</span><span class="nb">rbx</span><span class="p">)</span></code></pre>
<p>tandis que le code optimisé de GCC donnait :</p>
<pre><code class="asm"><span class="nf">movq</span> <span class="p">(</span><span class="o">%</span><span class="nb">rdi</span><span class="p">),</span> <span class="o">%</span><span class="nb">rax</span>
<span class="err">[</span><span class="nf">...</span><span class="p">]</span>
<span class="nf">andb</span> <span class="kc">$</span><span class="mi">252</span><span class="p">,</span> <span class="o">%</span><span class="nb">ah</span>
<span class="nf">movq</span> <span class="o">%</span><span class="nb">rax</span><span class="p">,</span> <span class="p">(</span><span class="o">%</span><span class="nb">rdi</span><span class="p">)</span></code></pre>
<p>qui pouvait lever le bug du CPU si il se trouvait dans une petite boucle.</p>
<p>Au final, il semblerait que Skylake se soit transformé en Skyfall et que la légendaire crainte gauloise que le ciel leur tombe sur la tête était fondée ! :-D</p>
<p><img src="//img.linuxfr.org/img/687474703a2f2f70617373696f6e67656e65616c6f6769652e686175746574666f72742e636f6d2f6d656469612f30302f30302f323238343530313137312e6a7067/2284501171.jpg" alt="astérix" title="Source : http://passiongenealogie.hautetfort.com/media/00/00/2284501171.jpg"></p><div><a href="https://linuxfr.org/users/kantien/journaux/un-bug-qui-est-le-coupable-le-processeur.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/112223/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/kantien/journaux/un-bug-qui-est-le-coupable-le-processeur#comments">ouvrir dans le navigateur</a>
</p>
kantienhttps://linuxfr.org/nodes/112223/comments.atomtag:linuxfr.org,2005:News/379412017-04-21T08:44:18+02:002017-04-21T15:57:12+02:00Résultat électoral : le nouveau DPL est…Licence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<div><p>La période électorale franco‐française arrive bientôt à son terme, ce qui nous a valu des journaux sur les systèmes de vote et d’autres, un peu plus gratinés, de colleurs d’affiches. Pendant ce temps, dans le monde du logiciel libre, une élection avait lieu de son côté : Debian élisait son nouveau responsable en la personne de Chris Lamb. Cette dépêche est l’occasion de revenir sur son déroulement et son résultat.</p></div><ul><li>lien nᵒ 1 : <a title="https://linuxfr.org/users/kantien/journaux/resultat-electoral-le-nouveau-dpl-est" hreflang="fr" href="https://linuxfr.org/redirect/99680">Journal à l’origine de la dépêche</a></li><li>lien nᵒ 2 : <a title="https://www.debian.org/vote/index.fr.html" hreflang="fr" href="https://linuxfr.org/redirect/99681">Informations sur le vote chez Debian</a></li><li>lien nᵒ 3 : <a title="https://www.debian.org/vote/2017/vote_001.fr.html" hreflang="fr" href="https://linuxfr.org/redirect/99682">Élection du responsable du projet Debian 2017</a></li><li>lien nᵒ 4 : <a title="https://www.debian.org/devel/constitution.fr.html#item-5" hreflang="fr" href="https://linuxfr.org/redirect/99690">Le responsable du projet dans la Constitution Debian</a></li></ul><div><h2 id="lélection">L’élection.</h2>
<p>Le processus Debian, pour désigner leur nouveau responsable de projet, se déroule en trois phases. Dans un premier temps, cette année du 5 au 11 mars, les développeurs sont invités à proposer leur candidature pour le poste. Cette année, deux candidats se sont présentés :</p>
<ul>
<li>Mehdi Dogguy, le responsable sortant ;</li>
<li>Chris Lamb.</li>
</ul><p>S’ensuit une période de campagne, cette année du 12 mars au 1<sup>er</sup> avril, durant laquelle les candidats se présentent et proposent leur vision et les actions qu’ils entendent mener au cours de l’année à venir :</p>
<ul>
<li>
<a href="https://www.debian.org/vote/2017/platforms/mehdi">le programme de Mehdi</a> ;</li>
<li>
<a href="https://www.debian.org/vote/2017/platforms/lamby">le programme de Chris</a>.</li>
</ul><p>Enfin, le scrutin, du 2 au 15 avril, est organisé selon une <a href="https://fr.wikipedia.org/wiki/m%C3%A9thode%20de%20Condorcet" title="Définition Wikipédia">méthode de Condorcet</a> : la <a href="https://fr.wikipedia.org/wiki/m%C3%A9thode%20Schulze" title="Définition Wikipédia">méthode Schulze</a>. Les résultats définitifs, qui ont vu la victoire de Chris Lamb, sont <a href="https://www.debian.org/vote/2017/vote_001#outcome">consultables sur le site du projet Debian</a>.</p>
<p>Suite à <a href="//linuxfr.org/users/kantien/journaux/resultat-electoral-le-nouveau-dpl-est#comment-1699073">une question de <em>Liorel</em> sur le journal à l’origine de la dépêche</a>, les remarques suivantes pourront en intéresser certains. Liorel se demandait quel était l’intérêt, comme il n’y avait que deux candidats, d’utiliser une méthode de Condorcet par rapport au scrutin uninominal que les Français utilisent (situation de second tour en France). D’abord, en sus des deux candidats, Debian rajoute une troisième option sur les bulletins de vote : « aucun des deux » (ce qui correspond à un vote blanc). Les électeurs sont alors invités à classer ces trois options selon leur ordre de préférence, et le système de vote prend en compte le « vote blanc », mais de manière non uniforme pour chacun des candidats. Un <em>ratio</em> est calculé entre le nombre de fois où un candidat est arrivé en tête et le nombre de fois où le choix « aucun des deux » lui a été préféré. Dans le cas de cette élection, <a href="https://www.debian.org/vote/2017/vote_001#majorityreq">on obtient pour les deux candidats</a> :</p>
<ul>
<li>Mehdi : 17,588 (299/17) ;</li>
<li>Chris : 25,250 (303/12).</li>
</ul><p>Ici, la prise en compte du « vote blanc » n’est pas uniforme entre les candidats (17 pour Medhi, contre 12 pour Chris), et le ratio doit être supérieur à un pour que le candidat soit bien élu. Il donne aussi une certaine mesure de la position des « abstentionnistes » par rapport au candidat (plus le ratio est proche de un, moins le candidat est désiré).</p>
<p>Pour les lecteurs intéressés par les systèmes de vote, on pourra lire l’article <a href="http://images.math.cnrs.fr/La-quete-du-Graal-electoral.html"><em>La quête du Graal électoral</em></a> sur le site <em>Images des Maths</em> du CNRS où est présenté, entre autres, un système <em>à la Condorcet</em> intéressant : le scrutin <em>bipartiludique</em> (ou « vote chifoumi » :-P) qui possède la propriété importante (contrairement à la méthode Schulze de Debian) de ne pas permettre le « vote utile ».</p>
<h2 id="le-nouveau-responsable-chrislamb">Le nouveau responsable : Chris Lamb.</h2>
<p>Le rôle et les pouvoirs précis dont dispose le responsable du projet Debian sont <a href="https://www.debian.org/devel/constitution#item-5">définis dans la constitution du projet</a>. Ils consistent essentiellement à déterminer des orientations techniques, politiques et la gestion des fonds qui seront, <em>in fine</em>, soumises à discussions sur les listes adaptées.</p>
<p>Le nouveau responsable, Chris Lamb, est contributeur Debian depuis dix ans (il a commencé par un <em>Google Summer of Code</em>) et officiellement développeur Debian depuis 2008. Il est en charge du maintien de <a href="https://qa.debian.org/developer.php?login=lamby&comaint=no">certains paquets dans l’archive</a>. Dans le cadre de son travail, il contribue au projet <a href="https://wiki.debian.org/fr/LTS">Debian LTS</a> (projet visant à maintenir au moins cinq ans les corrections de sécurité sur une version stable, en prenant le relai de l’équipe sécurité après la sortie d’une nouvelle version stable) et il participe également au projet <a href="https://wiki.debian.org/ReproducibleBuilds/About"><em>Debian Reproducible Builds</em></a>, qui vise à pouvoir recompiler un paquet source Debian en obtenant le même SHASUM que le binaire publié, cela afin de mieux contrôler qu’il n’y a pas d’action « malicieuse » lors de la production des binaires diffusés (un code source cela s’inspecte, mais un binaire ?).</p>
<p><a href="https://www.debian.org/vote/2017/platforms/lamby">Dans son programme</a>, Chris Lamb pointe du doigt un problème de communication et perception par rapport au monde extérieur : <a href="https://www.debian.org/">site Web austère</a>, <a href="https://wiki.debian.org/fr/FrontPage">wiki</a> à des années lumières du <a href="https://wiki.archlinux.org/index.php/">wiki d’Arch Linux</a>, par moment mauvais accueil des utilisateurs non familiers avec Debian… Sans pour autant négliger les aspects purement techniques de gestion d’une distribution, il souhaite agir principalement sur quatre axes :</p>
<ul>
<li>organiser plus de rencontres ;</li>
<li>améliorer le processus d’accueil et d’intégration ;</li>
<li>créer leur propre programme d’ouverture (il cite le projet Outreachy de GNOME en exemple) ;</li>
<li>supprimer fermement tout bloqueur pour travailler efficacement dans Debian.</li>
</ul><p>Félicitations à Chris pour sa victoire, et souhaitons lui bonne chance pour la mise en œuvre de son programme.</p></div><div><a href="https://linuxfr.org/news/resultat-electoral-le-nouveau-dpl-est.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/111715/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/news/resultat-electoral-le-nouveau-dpl-est#comments">ouvrir dans le navigateur</a>
</p>
kantienDavy Defaudbubar🦥palm123Benoît SibaudBAudpatrick_ghttps://linuxfr.org/nodes/111715/comments.atomtag:linuxfr.org,2005:Diary/372602017-04-18T14:22:56+02:002017-04-21T12:59:34+02:00Arrestation du développeur Debian Dmitry BogatovLicence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<p>Le 17 avril, le projet Debian a appris <a href="https://www.debian.org/News/2017/20170417">l'arrestation de Dmitry Bogatov</a> (en) par les autorités russes.</p>
<p>Dmitry Bogatov est un enseignant en mathématiques, et un contributeur Debian actif. En tant que mainteneur Debian, par exemple, il travaillait dans le groupe Haskell et maintenait actuellement de nombreux paquets d'outils systèmes et en ligne de commande.</p>
<p>Pour le moment, les raisons de son arrestation et ce qui lui est reproché ne sont pas connues. Le projet a tout de même pris des mesures de sécurité en révoquant ses clefs au cas où celles-ci seraient compromises.</p><div><a href="https://linuxfr.org/users/kantien/journaux/arrestation-du-developpeur-debian-dmitry-bogatov.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/111723/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/kantien/journaux/arrestation-du-developpeur-debian-dmitry-bogatov#comments">ouvrir dans le navigateur</a>
</p>
kantienhttps://linuxfr.org/nodes/111723/comments.atomtag:linuxfr.org,2005:Diary/372562017-04-17T15:22:06+02:002017-04-17T15:36:12+02:00Résultat électoral : le nouveau DPL est...Licence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<p>En cette période électoral, dans la lignée de certains journaux polémiques de ces derniers jours, je me devais de faire un journal pour relater le résultat d'une élection tombé hier. Non, il ne s'agit pas du résultat du référendum s'étant déroulé en Turquie ! On est sur LinuxFr.org, on y parle de logiciels libres et de ce qui gravite autour du libre en général. Je parlerais donc de l'élection du nouveau <em>leader</em> d'une des distributions majeures (et celle que j'utilise) : Debian !</p>
<p>Les périodes de candidature et de campagne se sont déroulées, respectivement, du 5 au 11 mars puis du 12 mars au 1er avril. Seuls deux candidats se sont retrouvés en lice cette année :</p>
<ul>
<li>
<a href="https://www.debian.org/vote/2017/platforms/mehdi">Mehdi Dogguy</a>, le DPL en titre ;</li>
<li>
<a href="https://www.debian.org/vote/2017/platforms/lamby">Chris Lamb</a>.</li>
</ul><p>Après deux semaines de scrutins (entre le 2 et le 15 avril), selon la <a href="http://fr.wikipedia.org/wiki/M%C3%A9thode_Condorcet">méthode de Condorcet</a>, les résultats sont tombés hier : <a href="https://www.debian.org/vote/2017/vote_001.en.html">Chris Lamb sera le nouveau DPL (Debian Project Leader)</a> (en).</p>
<p>Félicitation à lui, et bonne chance pour la mise en œuvre de <a href="https://www.debian.org/vote/2017/platforms/lamby">son programme</a>.</p>
<p>Je laisse à la sagacité des commentateurs le soin de déterminer si un tel élu est prêt à défendre les valeurs du libre, et si l'organisation qu'il représente peut laisser espérer un engagement réel et profond en faveur du mouvement pour le logiciel libre. :-P</p><div><a href="https://linuxfr.org/users/kantien/journaux/resultat-electoral-le-nouveau-dpl-est.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/111713/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/kantien/journaux/resultat-electoral-le-nouveau-dpl-est#comments">ouvrir dans le navigateur</a>
</p>
kantienhttps://linuxfr.org/nodes/111713/comments.atomtag:linuxfr.org,2005:Diary/369792016-11-25T09:05:37+01:002016-11-26T14:02:54+01:00Xavier Leroy est le lauréat 2016 du Prix Milner.Licence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<p>Hier, jeudi 24 novembre 2016, <a href="https://fr.wikipedia.org/wiki/Xavier%20Leroy" title="Définition Wikipédia">Xavier Leroy</a> a reçu le <a href="https://fr.wikipedia.org/wiki/prix%20Milner" title="Définition Wikipédia">prix Milner</a> à Londres à la Royal Society. Le prix Milner est le plus grand prix européen en informatique; il est décerné conjointement par la Royal Society, l'Académie des Sciences et l'académie allemande Leopoldina. Il est décerné en l'honneur de l'informaticien britannique <a href="https://fr.wikipedia.org/wiki/Robin%20Milner" title="Définition Wikipédia">Robin Milner</a> qui fut lauréat du Prix Turing en 1992.</p>
<p>Le prix revient cette année à Xavier Leroy pour ses travaux tant théoriques que pratiques sur la fiabilité des systèmes informatiques. Xavier Leroy est directeur de recherche à l'INRIA et il y dirige l'équipe <a href="http://gallium.inria.fr/">Gallium</a>. Il est à l'origine du langage <a href="https://ocaml.org/">OCaml</a> ainsi que du compilateur C certifié <a href="http://compcert.inria.fr/">CompCert</a>. Ce dernier est un compilateur C écrit en Coq et « garanti sans bugs ». Pour reprendre la présentation qu'en donne Gérard Berry dans le <a href="http://www.societe-informatique-de-france.fr/wp-content/uploads/2016/11/1024-no9-Leroy.pdf">bulletin de la Société Informatique de France</a> :</p>
<blockquote>
<p>Un tel développement est une course de haies : il faut d’abord choisir un sous-ensemble approprié de C, qui est loin d’être un langage bien défini. Le sous-ensemble C-light que compile CompCert correspond bien aux besoins du logiciel industriel embarqué dans les systèmes physiques. Il faut ensuite choisir des sous-ensembles des langages machine des processeurs (Intel, Motorola, Mips, etc.) qui soient également formellement définissables. Une fois ces sous-ensembles choisis, il faut définir leur sémantique mathématique de façon appropriée et directement implémentable dans un assistant de vérification. Enfin, il faut démontrer un théorème du type « pour tout programme P écrit en C et toute machine cible M, si CompCert produit un code machine PM pour M à partir de P, alors exécuter PM sur M donne pour toute entrée le même résultat qu’exécuter P dans la sémantique de C ».</p>
</blockquote>
<p>(<strong>NdM.</strong> : la dernière phrase de cette citation comprend une coquille à la source au moment de la rédaction du journal, corrigée ici, la dernière occurrence de P étant par erreur un M à la source)</p>
<p>Autrement dit, le compilateur <em>n'introduit pas</em> de bugs en traduisant le code C en langage machine. S'il y a un bug dans le programme compilé, alors il se trouve dans le code C et non dans le compilateur.</p>
<p>La remise du prix a eu lieu hier et <a href="https://royalsociety.org/science-events-and-lectures/2016/11/milner-award-lecture/">la vidéo de la cérémonie</a> est disponible sur le site de la Royal Society.</p>
<p>Pour conclure sur une note de chauvinisme, chantons le cri du <a href="https://coq.inria.fr/">Coq</a> : Cocorico !</p><div><a href="https://linuxfr.org/users/kantien/journaux/xavier-leroy-est-le-laureat-2016-du-prix-milner.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/110607/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/kantien/journaux/xavier-leroy-est-le-laureat-2016-du-prix-milner#comments">ouvrir dans le navigateur</a>
</p>
kantienhttps://linuxfr.org/nodes/110607/comments.atomtag:linuxfr.org,2005:Diary/369732016-11-22T13:00:43+01:002016-11-22T13:00:43+01:00Tagless-final ou l'art de l'interprétation modulaire.Licence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<h2 class="sommaire">Sommaire</h2>
<ul class="toc">
<li>
<a href="#approche-par-ast-comme-structure-de-donn%C3%A9es-ou-m%C3%A9thode-initiale">Approche par AST comme structure de données ou méthode <em>initiale</em>.</a><ul>
<li><a href="#langage-additif-et-multiplicatif-sur-les-entiers">Langage additif et multiplicatif sur les entiers.</a></li>
<li><a href="#interpr%C3%A9tation-contextualis%C3%A9e--le-cas-du-pretty-printing">Interprétation contextualisée : le cas du <em>pretty printing</em>.</a></li>
<li><a href="#enrichissons-le-langage-avec-des-bool%C3%A9ens-et-conditions">Enrichissons le langage avec des booléens et conditions.</a></li>
</ul>
</li>
<li>
<a href="#approche-par-ast-sous-forme-de-fonctions-ou-m%C3%A9thode-tagless-final">Approche par AST sous forme de fonctions ou méthode <em>tagless-final</em>.</a><ul>
<li><a href="#langage-additif-et-multiplicatif-sur-les-entiers-1">Langage additif et multiplicatif sur les entiers.</a></li>
<li><a href="#enrichissons-le-langage-avec-des-bool%C3%A9ens-et-conditions-1">Enrichissons le langage avec des booléens et conditions.</a></li>
<li><a href="#fiat-lux--que-la-lumi%C3%A8re-soit-et-la-lumi%C3%A8re-fut">Fiat lux : Que la lumière soit, et la lumière fut !</a></li>
</ul>
</li>
<li>
<a href="#optimisons-un-peu-nos-interpr%C3%A8tes">Optimisons un peu nos interprètes !</a><ul>
<li><a href="#suppression-des-op%C3%A9randes-nuls">Suppression des opérandes nuls.</a></li>
<li><a href="#principe-g%C3%A9n%C3%A9ral-des-transformations">Principe général des transformations.</a></li>
<li><a href="#simplification-de-la-multiplication-par-un">Simplification de la multiplication par un.</a></li>
<li><a href="#r%C3%A9utilisation-de-nos-passes-sur-le-langage-%C3%A9tendu">Réutilisation de nos passes sur le langage étendu.</a></li>
</ul>
</li>
<li>
<a href="#%C3%89tendre-le-langage-avec-des-fonctions">Étendre le langage avec des fonctions.</a><ul>
<li><a href="#la-symantique-%C3%A9tendue-et-ses-interpr%C3%A8tes">La symantique étendue et ses interprètes.</a></li>
<li><a href="#%C3%89valuation-partielle-et-statique">Évaluation partielle et statique.</a></li>
</ul>
</li>
<li><a href="#conclusion">Conclusion.</a></li>
</ul><p>Dans la lignée du journal <a href="//linuxfr.org/users/aluminium95/journaux/edsl-et-f-algebres">EDSL et F-algèbres</a>, ce journal présente une méthode pour plonger un langage dans un autre (ici OCaml) qui généralise la précédente et centrée autour de la notion d'<em>interprétation</em>. Contrairement aux méthodes plus courantes pour résoudre cette question, la méthode <em>tagless-final</em> permet également de résoudre le <a href="https://en.wikipedia.org/wiki/Expression_problem">problème de l'extensibilité</a> : étendre un type de donnés, ajouter des opérations dessus, sans avoir à réécrire du code déjà compilé et cela avec la sécurité du typage statique.</p>
<p>J'ai essayé d'écrire le journal de telle façon qu'il ne soit pas nécessaire de connaître les fondamentaux du paradigme fonctionnel en programmation, même si une familiarité avec d'autres langages que OCaml sont indispensables. Si certains points vous semblent trop obscurs ou mal expliqués, les commentaires sont là pour vos questions.</p>
<p>Avant de présenter l'approche <em>tagless-final</em> et son originalité, je commencerai par présenter la façon plus « standard » de procéder. Celle-ci consistant à manipuler des structures de données, elle est moins spécifique au langage fonctionnel. Elle sera sans doute plus facile à appréhender dans un premier temps, et permettra de servir de point de comparaison.</p>
<h2 id="approche-par-ast-comme-structure-de-données-ou-méthode-initiale">Approche par AST comme structure de données ou méthode <em>initiale</em>.</h2>
<p>Dans cette première partie, nous étudierons la manière usuelle de représenter les termes d'un langage via une structure de données correspondant à son AST (<a href="https://fr.wikipedia.org/wiki/Arbre_syntaxique_abstrait">arbre de syntaxe abstrait</a>). Nous commencerons en présentant cette méthode sur un langage algébrique simple d'expressions sur des entiers.</p>
<h3 id="langage-additif-et-multiplicatif-sur-les-entiers">Langage additif et multiplicatif sur les entiers.</h3>
<p>Dans un premier temps, nous allons voir comment représenter en OCaml un langage de calcul sur les entiers avec des expressions comme <code>1 + 2 + 3</code>, ou <code>1 + 2 * 3</code>, ou encore <code>(1 + 2) * (3 + 4)</code>. La technique courante pour traiter un tel langage en OCaml est de définir un type de données représentant les termes du langage :</p>
<pre><code class="ocaml"><span class="k">type</span> <span class="n">expr</span> <span class="o">=</span>
<span class="o">|</span> <span class="nc">Lit</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">-></span> <span class="n">expr</span> <span class="c">(* un littéral représentant un entier *)</span>
<span class="o">|</span> <span class="nc">Add</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">*</span> <span class="n">expr</span> <span class="o">-></span> <span class="n">expr</span> <span class="c">(* une expression représentant une addition *)</span>
<span class="o">|</span> <span class="nc">Mul</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">*</span> <span class="n">expr</span> <span class="o">-></span> <span class="n">expr</span> <span class="c">(* une expression représentant une multiplication *)</span></code></pre>
<p>Ce <em>type</em> de données est ce que l'on appelle un type somme ou <em>variant</em>, et ressemble un peu au <a href="https://en.wikipedia.org/wiki/Union_type"><code>union</code> du C</a> (en). Chaque ligne définit un <em>constructeur</em> pour ce type de données (par exemple le constructeur <code>Add</code> prend un <em>couple</em> de <code>expr</code> et renvoie un <code>expr</code>) et chaque <em>valeur</em> de ce type correspond à <em>un et un seul</em> de ces trois cas. Afin d'obtenir une expression, on utilise nos constructeurs comme dans ces exemples :</p>
<pre><code class="ocaml"><span class="c">(* 1 + 2 *)</span>
<span class="k">let</span> <span class="n">ex1</span> <span class="o">=</span> <span class="nc">Add</span><span class="o">(</span><span class="nc">Lit</span> <span class="mi">1</span><span class="o">,</span> <span class="nc">Lit</span> <span class="mi">2</span><span class="o">);;</span>
<span class="k">val</span> <span class="n">ex1</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">=</span> <span class="nc">Add</span> <span class="o">(</span><span class="nc">Lit</span> <span class="mi">1</span><span class="o">,</span> <span class="nc">Lit</span> <span class="mi">2</span><span class="o">)</span>
<span class="c">(* (1 + 2) * (3 + 4) *)</span>
<span class="k">let</span> <span class="n">ex2</span> <span class="o">=</span> <span class="nc">Mul</span><span class="o">(</span><span class="nc">Add</span><span class="o">(</span><span class="nc">Lit</span> <span class="mi">1</span><span class="o">,</span> <span class="nc">Lit</span> <span class="mi">2</span><span class="o">),</span> <span class="nc">Add</span><span class="o">(</span><span class="nc">Lit</span> <span class="mi">3</span><span class="o">,</span> <span class="nc">Lit</span> <span class="mi">4</span><span class="o">));;</span>
<span class="k">val</span> <span class="n">ex2</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">=</span> <span class="nc">Mul</span> <span class="o">(</span><span class="nc">Add</span> <span class="o">(</span><span class="nc">Lit</span> <span class="mi">1</span><span class="o">,</span> <span class="nc">Lit</span> <span class="mi">2</span><span class="o">),</span> <span class="nc">Add</span> <span class="o">(</span><span class="nc">Lit</span> <span class="mi">3</span><span class="o">,</span> <span class="nc">Lit</span> <span class="mi">4</span><span class="o">))</span></code></pre>
<p>Une façon de se représenter visuellement une telle structure est sous la forme d'un arbre dont les nœuds sont étiquetés par les constructeurs <code>Add</code> ou <code>Mul</code> et où les feuilles sont des <em>littéraux</em>.</p>
<pre><code> Mul
/ \
/ \
/ \
Add Add
/ \ / \
/ \ / \
Lit 1 Lit 2 Lit 3 Lit 4
</code></pre>
<p>Cette représentation est ce que l'on appelle l'arbre de syntaxe abstrait de l'expression qui, dans notre cas, est le produit de deux additions. Maintenant, afin d'<em>évaluer</em> la valeur entière de celle-ci, on va définir une fonction <code>eval</code> qui parcourt l'arbre <em>récursivement</em> pour le convertir en un entier.</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="k">rec</span> <span class="n">eval</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">-></span> <span class="kt">int</span> <span class="o">=</span> <span class="k">function</span>
<span class="o">|</span> <span class="nc">Lit</span> <span class="n">n</span> <span class="o">-></span> <span class="n">n</span>
<span class="o">|</span> <span class="nc">Add</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">-></span> <span class="o">(</span><span class="n">eval</span> <span class="n">e1</span><span class="o">)</span> <span class="o">+</span> <span class="o">(</span><span class="n">eval</span> <span class="n">e2</span><span class="o">)</span>
<span class="o">|</span> <span class="nc">Mul</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">-></span> <span class="o">(</span><span class="n">eval</span> <span class="n">e1</span><span class="o">)</span> <span class="o">*</span> <span class="o">(</span><span class="n">eval</span> <span class="n">e2</span><span class="o">)</span></code></pre>
<p>La définition de la fonction est simple et va de soi : on fait une étude de cas sur la forme que peut avoir notre expression, et on effectue le traitement adapté. Par exemple, dans le cas du constructeur <code>Add</code> on commence par évaluer <em>récursivement</em> chacune des sous-expressions <code>e1</code> et <code>e2</code> puis on en calcule la somme. Le compilateur se charge de vérifier que tous les cas possibles sont bien gérés et que l'analyse est exhaustive, sinon il émet un avertissement :</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="k">rec</span> <span class="n">eval</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">-></span> <span class="kt">int</span> <span class="o">=</span> <span class="k">function</span>
<span class="o">|</span> <span class="nc">Lit</span> <span class="n">n</span> <span class="o">-></span> <span class="n">n</span>
<span class="o">|</span> <span class="nc">Add</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">-></span> <span class="o">(</span><span class="n">eval</span> <span class="n">e1</span><span class="o">)</span> <span class="o">+</span> <span class="o">(</span><span class="n">eval</span> <span class="n">e2</span><span class="o">);;</span>
<span class="nc">Characters</span> <span class="mi">29</span><span class="o">-</span><span class="mi">93</span><span class="o">:</span>
<span class="nc">Warning</span> <span class="mi">8</span><span class="o">:</span> <span class="n">this</span> <span class="n">pattern</span><span class="o">-</span><span class="n">matching</span> <span class="n">is</span> <span class="n">not</span> <span class="n">exhaustive</span><span class="o">.</span>
<span class="nc">Here</span> <span class="n">is</span> <span class="n">an</span> <span class="n">example</span> <span class="k">of</span> <span class="n">a</span> <span class="n">case</span> <span class="n">that</span> <span class="n">is</span> <span class="n">not</span> <span class="n">matched</span><span class="o">:</span>
<span class="nc">Mul</span> <span class="o">(_,_)</span>
<span class="k">val</span> <span class="n">eval</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">-></span> <span class="kt">int</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span></code></pre>
<p>Ici on a oublié de traiter le cas de la multiplication. On peut maintenant tester notre fonction d'évaluation sur nos exemples :</p>
<pre><code class="ocaml"><span class="c">(* 1 + 2 *)</span>
<span class="n">eval</span> <span class="n">ex1</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">3</span>
<span class="c">(* (1 + 2) * (3 + 4) *)</span>
<span class="n">eval</span> <span class="n">ex2</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">21</span></code></pre>
<p>On pourrait aussi, au lieu d'évaluer la valeur du terme, afficher l'arbre sous forme de chaîne de caractères exprimant le calcul à effectuer.</p>
<pre><code class="ocaml"><span class="c">(* une fonction qui prend deux chaînes puis rajoute un + entre les deux *)</span>
<span class="k">let</span> <span class="n">show_add</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">=</span> <span class="n">s</span> <span class="o">^</span> <span class="s2">" + "</span> <span class="o">^</span> <span class="n">s'</span>
<span class="c">(* la même mais pour la multiplication *)</span>
<span class="k">let</span> <span class="n">show_mul</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">=</span> <span class="n">s</span> <span class="o">^</span> <span class="s2">" * "</span> <span class="o">^</span> <span class="n">s'</span>
<span class="c">(* une fonction qui met une chaîne entre paranthèses *)</span>
<span class="k">let</span> <span class="n">paren</span> <span class="n">s</span> <span class="o">=</span> <span class="s2">"("</span> <span class="o">^</span> <span class="n">s</span> <span class="o">^</span> <span class="s2">")"</span>
<span class="c">(* notre fonction d'affichage *)</span>
<span class="k">let</span> <span class="k">rec</span> <span class="n">view</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">-></span> <span class="kt">string</span> <span class="o">=</span> <span class="k">function</span>
<span class="o">|</span> <span class="nc">Lit</span> <span class="n">n</span> <span class="o">-></span> <span class="n">string_of_int</span> <span class="n">n</span>
<span class="o">|</span> <span class="nc">Add</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">-></span> <span class="n">paren</span> <span class="o">(</span><span class="n">show_add</span> <span class="o">(</span><span class="n">view</span> <span class="n">e1</span><span class="o">)</span> <span class="o">(</span><span class="n">view</span> <span class="n">e2</span><span class="o">))</span>
<span class="o">|</span> <span class="nc">Mul</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">-></span> <span class="n">paren</span> <span class="o">(</span><span class="n">show_mul</span> <span class="o">(</span><span class="n">view</span> <span class="n">e1</span><span class="o">)</span> <span class="o">(</span><span class="n">view</span> <span class="n">e2</span><span class="o">))</span>
<span class="k">let</span> <span class="o">_</span> <span class="o">=</span> <span class="n">view</span> <span class="n">ex1</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"(1 + 2)"</span>
<span class="k">let</span> <span class="o">_</span> <span class="o">=</span> <span class="n">view</span> <span class="n">ex2</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"((1 + 2) * (3 + 4))"</span></code></pre>
<p>Si l'on regarde le code des deux fonctions <code>eval</code> et <code>view</code> ci-dessus, l'on constate un motif commun :</p>
<ul>
<li>on décompose l'arbre en ses constituants et on applique une fonction aux éléments dans chaque cas ;</li>
<li>la valeur d'un nœud ne dépend que de la valeur des ses sous-arbres.</li>
</ul><p>On peut alors coder une fonction générique capturant ce motif qui porte traditionnellement le nom de <a href="https://en.wikipedia.org/wiki/Fold_(higher-order_function)"><code>fold</code></a> (en) :</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="k">rec</span> <span class="n">fold</span> <span class="n">lit</span> <span class="n">add</span> <span class="n">mul</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">e</span> <span class="o">-></span>
<span class="k">let</span> <span class="n">eval_or_view</span> <span class="o">=</span> <span class="n">fold</span> <span class="n">lit</span> <span class="n">add</span> <span class="n">mul</span> <span class="k">in</span>
<span class="k">match</span> <span class="n">e</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Lit</span> <span class="n">i</span> <span class="o">-></span> <span class="n">lit</span> <span class="n">i</span>
<span class="o">|</span> <span class="nc">Add</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">-></span> <span class="n">add</span> <span class="o">(</span><span class="n">eval_or_view</span> <span class="n">e1</span><span class="o">)</span> <span class="o">(</span><span class="n">eval_or_view</span> <span class="n">e2</span><span class="o">)</span>
<span class="o">|</span> <span class="nc">Mul</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">-></span> <span class="n">mul</span> <span class="o">(</span><span class="n">eval_or_view</span> <span class="n">e1</span><span class="o">)</span> <span class="o">(</span><span class="n">eval_or_view</span> <span class="n">e2</span><span class="o">)</span>
<span class="k">let</span> <span class="n">eval</span> <span class="o">=</span> <span class="n">fold</span> <span class="o">(</span><span class="k">fun</span> <span class="n">i</span> <span class="o">-></span> <span class="n">i</span><span class="o">)</span> <span class="o">(+)</span> <span class="o">(</span> <span class="o">*</span> <span class="o">)</span>
<span class="k">let</span> <span class="n">view</span> <span class="o">=</span>
<span class="n">fold</span> <span class="n">string_of_int</span>
<span class="o">(</span><span class="k">fun</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">-></span> <span class="n">paren</span> <span class="o">(</span><span class="n">show_add</span> <span class="n">s</span> <span class="n">s'</span><span class="o">))</span>
<span class="o">(</span><span class="k">fun</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">-></span> <span class="n">paren</span> <span class="o">(</span><span class="n">show_mul</span> <span class="n">s</span> <span class="n">s'</span><span class="o">))</span></code></pre>
<p>Dans la définition de <code>fold</code>, j'ai volontairement définie une fonction locale <code>eval_or_view</code> pour souligner la correspondance avec les codes précédents. Regardons un instant le type inféré pour ces trois fonctions :</p>
<pre><code class="ocaml"><span class="k">val</span> <span class="n">fold</span> <span class="o">:</span> <span class="o">(</span><span class="kt">int</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span><span class="o">)</span> <span class="o">-></span> <span class="o">(</span><span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span><span class="o">)</span> <span class="o">-></span> <span class="o">(</span><span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span><span class="o">)</span> <span class="o">-></span> <span class="n">expr</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span>
<span class="k">val</span> <span class="n">eval</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">-></span> <span class="kt">int</span>
<span class="k">val</span> <span class="n">view</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">-></span> <span class="kt">string</span></code></pre>
<p>La fonction <code>fold</code> prend pour argument une fonction <code>lit : int -> 'a</code>, une fonction <code>add : 'a -> 'a -> 'a</code> et une fonction <code>mul : 'a -> 'a -> 'a</code> qui constituent les <em>interprétations</em> des littéraux et des opérateurs du langage. Le type <code>'a</code> constitue le <em>domaine</em> dans lequel on <em>interprète</em> nos termes, à savoir <code>int</code> dans le cas de <code>eval</code> et <code>string</code> dans le cas de <code>view</code>. Le principe général de la fonction <code>fold</code> consiste alors à parcourir l'arbre et à remplacer <em>récursivement</em> chaque constructeur par l'application d'une fonction correspondant à l'interprétation de celui-ci.</p>
<p>Nous avons vu là les principes de base pour définir un langage en OCaml :</p>
<ul>
<li>on représente les termes du langage via un <em>variant</em> ;</li>
<li>on code une fonction <code>fold</code> générique sur celui-ci ;</li>
<li>on se sert de cette fonction pour faire varier les interprétations.</li>
</ul><p>Nous allons voir, à présent, comment faire pour coder des interprétations dites <em>contextuelles</em> à travers l'exemple du <em>pretty printing</em>.</p>
<h3 id="interprétation-contextualisée--le-cas-du-pretty-printing">Interprétation contextualisée : le cas du <em>pretty printing</em>.</h3>
<p>Dans cette section, nous allons traiter la notion d'interprétation dite <em>contextualisée</em> : l'interprétation d'un terme ne dépend plus alors seulement de ses constituants ou sous-termes, mais également du contexte dans lequel il est utilisé. Un exemple classique de telles interprétations est celui du <em>pretty printing</em> lorsque l'on cherche à afficher élégamment la structure de l'arbre syntaxique.</p>
<p>L'objectif ici sera d'afficher l'arbre en supprimant certaines parenthèses superflues. Si l'on reprend les deux exemples de la section précédente, nous avons pour l'instant :</p>
<pre><code class="ocaml"><span class="n">view</span> <span class="n">ex1</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"(1 + 2)"</span>
<span class="n">view</span> <span class="n">ex2</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"((1 + 2) * (3 + 4))"</span></code></pre>
<p>Et l'on voudrait arriver à un affichage minimisant les parenthèses nécessaires à la représentation textuelle de la structure de l'arbre, les opérations étant vues comme associatives à <em>gauche</em> (ce qui est le cas en OCaml) :</p>
<pre><code class="ocaml"><span class="n">show</span> <span class="n">ex1</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"1 + 2"</span>
<span class="n">show</span> <span class="n">ex2</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"(1 + 2) * (3 + 4)"</span></code></pre>
<p>Ici l'interprétation d'un terme sous forme de <code>string</code> dépend du <em>contexte</em> dans lequel il est employé : dans le cas de <code>ex2</code> le terme <code>1 + 2</code> qui apparaît comme premier opérande de la multiplication est mis entre parenthèses, alors qu'il ne l'est pas dans le cas de <code>ex1</code>. Une solution consiste à utiliser un contexte <code>p</code> de type <code>int</code> représentant le niveau de précédence dans lequel se trouve le terme, puis de mettre des parenthèses en fonction de la valeur de celui-ci.</p>
<pre><code class="ocaml"><span class="c">(* une fonction de parenthésage sous condition *)</span>
<span class="k">let</span> <span class="n">cparen</span> <span class="n">b</span> <span class="o">=</span> <span class="k">if</span> <span class="n">b</span> <span class="k">then</span> <span class="n">paren</span> <span class="k">else</span> <span class="o">(</span><span class="k">fun</span> <span class="n">s</span> <span class="o">-></span> <span class="n">s</span><span class="o">)</span>
<span class="k">let</span> <span class="k">rec</span> <span class="n">cshow</span> <span class="n">p</span> <span class="n">e</span> <span class="o">=</span> <span class="k">match</span> <span class="n">p</span><span class="o">,</span><span class="n">e</span> <span class="k">with</span>
<span class="o">|</span> <span class="o">_</span> <span class="o">,</span> <span class="nc">Lit</span> <span class="n">n</span> <span class="o">-></span> <span class="n">string_of_int</span> <span class="n">n</span>
<span class="o">|</span> <span class="n">p</span> <span class="o">,</span> <span class="nc">Add</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">-></span> <span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">3</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_add</span> <span class="o">(</span><span class="n">cshow</span> <span class="mf">3 e1</span><span class="o">)</span> <span class="o">(</span><span class="n">cshow</span> <span class="mf">4 e2</span><span class="o">)</span>
<span class="o">|</span> <span class="n">p</span> <span class="o">,</span> <span class="nc">Mul</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">-></span> <span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">4</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_mul</span> <span class="o">(</span><span class="n">cshow</span> <span class="mf">4 e1</span><span class="o">)</span> <span class="o">(</span><span class="n">cshow</span> <span class="mf">5 e2</span><span class="o">)</span>
<span class="n">cshow</span> <span class="mi">0</span> <span class="n">ex1</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"1 + 2"</span>
<span class="n">cshow</span> <span class="mi">0</span> <span class="n">ex2</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"(1 + 2) * (3 + 4)"</span>
<span class="c">(* avec un nouvel exemple : 1 + (2 + 3 * 4) *)</span>
<span class="k">let</span> <span class="n">ex3</span> <span class="o">=</span> <span class="nc">Add</span><span class="o">(</span><span class="nc">Lit</span> <span class="mi">1</span><span class="o">,</span> <span class="nc">Add</span><span class="o">(</span><span class="nc">Lit</span> <span class="mi">2</span><span class="o">,</span> <span class="nc">Mul</span><span class="o">(</span><span class="nc">Lit</span> <span class="mi">3</span><span class="o">,</span> <span class="nc">Lit</span> <span class="mi">4</span><span class="o">)));;</span>
<span class="k">val</span> <span class="n">ex3</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">=</span> <span class="nc">Add</span> <span class="o">(</span><span class="nc">Lit</span> <span class="mi">1</span><span class="o">,</span> <span class="nc">Add</span> <span class="o">(</span><span class="nc">Lit</span> <span class="mi">2</span><span class="o">,</span> <span class="nc">Mul</span> <span class="o">(</span><span class="nc">Lit</span> <span class="mi">3</span><span class="o">,</span> <span class="nc">Lit</span> <span class="mi">4</span><span class="o">)))</span>
<span class="n">cshow</span> <span class="mi">0</span> <span class="n">ex3</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"1 + (2 + 3 * 4)"</span></code></pre>
<p>Dans le code ci-dessus, on vient de rencontrer une nouvelle notation pour l'application de fonction avec l'opérateur infixe <code>@@</code>. Il est défini en OCaml par l'expression <code>let (@@) f x = f x</code>, ce qui signifie que les expressions <code>f @@ x</code> et <code>f x</code> sont équivalentes. Il permet d'éviter d'avoir recours à de trop nombreuses parenthèses — contrairement au LISP par exemple — autour des arguments d'une fonction, et de faciliter ainsi la lecture et la compréhension du code.</p>
<p>Le motif de la fonction <code>cshow : int -> expr -> string</code> ne suit malheureusement pas celui générique du <code>fold</code> : l'interprétation d'un terme ne dépend pas seulement de la valeur de ses sous-termes. Ici le paramètre <code>p : int</code> sert d'<em>accumulateur</em> quand on descend dans la structure et porte avec lui l'information pour savoir s'il faut ou non parenthèser l'expression — information non prise en compte pour les littéraux.</p>
<p>Que se passe-t-il si l'on définit la même fonction mais en inversant l'ordre des arguments ?</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="k">rec</span> <span class="n">cshow</span> <span class="n">e</span> <span class="n">p</span> <span class="o">=</span> <span class="k">match</span> <span class="n">e</span><span class="o">,</span><span class="n">p</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Lit</span> <span class="n">n</span> <span class="o">,</span> <span class="o">_</span> <span class="o">-></span> <span class="n">string_of_int</span> <span class="n">n</span>
<span class="o">|</span> <span class="nc">Add</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">,</span> <span class="n">p</span> <span class="o">-></span> <span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">3</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_add</span> <span class="o">(</span><span class="n">cshow</span> <span class="n">e1</span> <span class="mi">3</span><span class="o">)</span> <span class="o">(</span><span class="n">cshow</span> <span class="n">e2</span> <span class="mi">4</span><span class="o">)</span>
<span class="o">|</span> <span class="nc">Mul</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">,</span> <span class="n">p</span> <span class="o">-></span> <span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">4</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_mul</span> <span class="o">(</span><span class="n">cshow</span> <span class="n">e1</span> <span class="mi">4</span><span class="o">)</span> <span class="o">(</span><span class="n">cshow</span> <span class="n">e2</span> <span class="mi">5</span><span class="o">)</span>
<span class="k">val</span> <span class="n">cshow</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">-></span> <span class="kt">int</span> <span class="o">-></span> <span class="kt">string</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span></code></pre>
<p>On commence à se rapprocher du motif de la fonction <code>fold</code> et la fonction prend bien une valeur de type <code>expr</code> pour renvoyer une fonction de type <code>int -> string</code>. Et si l'on pouvait se ramener à une interprétation via <code>fold</code> mais où l'on interpréterait notre arbre comme une fonction de type <code>int -> string</code> ?</p>
<p>Pour y arriver, faisons un petit détour par la <em>curryfication</em> de fonctions. Le principe est bien connu chez les adeptes de la programmation fonctionnelle, mais peut être moins chez les développeurs non habitués à ce paradigme. C'est surtout pour eux que le présent passage est écrit, pour les autres il suffit de le survoler.</p>
<p>Une fonction est caractérisée par un ensemble de définition (son domaine), un ensemble d'arrivée (son codomaine) et une relation <em>univoque</em> entre un élément du domaine vers un élément du codomaine. Lorsque l'on traite des fonctions de plusieurs variables, le domaine est constitué de <em>n-uplets</em> ou <em>tuples</em>. Le principe de la curryfication consiste à se ramener, dans ce cas, à des fonctions d'<em>une seule</em> variable. Illustrons la chose en python :</p>
<pre><code class="python"><span class="k">def</span> <span class="nf">plus</span> <span class="p">(</span><span class="n">x</span><span class="p">,</span> <span class="n">y</span><span class="p">):</span>
<span class="k">return</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span>
<span class="o">>>></span> <span class="n">plus</span> <span class="p">(</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">)</span>
<span class="mi">3</span></code></pre>
<p>Ici le domaine est constitué des <em>couples d'entiers</em> et le codomaine des <em>entiers</em>. La <em>curryfication</em> de cette fonction va consister à la transformer en une fonction dont le domaine est constitué des <em>entiers</em> et le codomaine des <em>fonctions des entiers vers les entiers</em> :</p>
<pre><code class="python"><span class="n">plus_curry</span> <span class="o">=</span> <span class="k">lambda</span> <span class="n">x</span> <span class="p">:</span> <span class="k">lambda</span> <span class="n">y</span> <span class="p">:</span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span>
<span class="o">>>></span> <span class="n">plus_curry</span> <span class="p">(</span><span class="mi">1</span><span class="p">)</span>
<span class="o"><</span><span class="n">function</span> <span class="o"><</span><span class="k">lambda</span><span class="o">>.<</span><span class="nb">locals</span><span class="o">>.<</span><span class="k">lambda</span><span class="o">></span> <span class="n">at</span> <span class="mh">0x7f64b9d46f28</span><span class="o">></span>
<span class="o">>>></span> <span class="n">plus_curry</span> <span class="p">(</span><span class="mi">1</span><span class="p">)</span> <span class="p">(</span><span class="mi">2</span><span class="p">)</span>
<span class="mi">3</span></code></pre>
<p>En OCaml, ces exemples donneraient :</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="n">plus</span> <span class="o">=</span> <span class="k">fun</span> <span class="o">(</span><span class="n">x</span><span class="o">,</span> <span class="n">y</span><span class="o">)</span> <span class="o">-></span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span>
<span class="k">let</span> <span class="n">plus_curry</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">x</span> <span class="o">-></span> <span class="k">fun</span> <span class="n">y</span> <span class="o">-></span> <span class="n">x</span> <span class="o">+</span> <span class="n">y</span>
<span class="n">plus</span> <span class="o">(</span><span class="mi">1</span><span class="o">,</span> <span class="mi">2</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">3</span>
<span class="n">plus_curry</span> <span class="mi">1</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">-></span> <span class="kt">int</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="n">plus_curry</span> <span class="mi">1</span> <span class="mi">2</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">3</span></code></pre>
<p>Après cette légère digression, revenons à notre fonction de <em>pretty printing</em> :</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="k">rec</span> <span class="n">cshow</span> <span class="n">e</span> <span class="n">p</span> <span class="o">=</span> <span class="k">match</span> <span class="n">e</span><span class="o">,</span><span class="n">p</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Lit</span> <span class="n">n</span> <span class="o">,</span> <span class="o">_</span> <span class="o">-></span> <span class="n">string_of_int</span> <span class="n">n</span>
<span class="o">|</span> <span class="nc">Add</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">,</span> <span class="n">p</span> <span class="o">-></span> <span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">3</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_add</span> <span class="o">(</span><span class="n">cshow</span> <span class="n">e1</span> <span class="mi">3</span><span class="o">)</span> <span class="o">(</span><span class="n">cshow</span> <span class="n">e2</span> <span class="mi">4</span><span class="o">)</span>
<span class="o">|</span> <span class="nc">Mul</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">,</span> <span class="n">p</span> <span class="o">-></span> <span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">4</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_mul</span> <span class="o">(</span><span class="n">cshow</span> <span class="n">e1</span> <span class="mi">4</span><span class="o">)</span> <span class="o">(</span><span class="n">cshow</span> <span class="n">e2</span> <span class="mi">5</span><span class="o">)</span>
<span class="k">val</span> <span class="n">cshow</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">-></span> <span class="kt">int</span> <span class="o">-></span> <span class="kt">string</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span></code></pre>
<p>On décompose le couple <code>(e, p)</code> et selon les cas l'on renvoie une chaîne de caractères particulière, il suffit donc de <em>curryfier</em> chaque branche de l'alternative pour obtenir :</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="k">rec</span> <span class="n">cshow</span> <span class="n">e</span> <span class="o">=</span> <span class="k">match</span> <span class="n">e</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Lit</span> <span class="n">n</span> <span class="o">-></span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span> <span class="n">string_of_int</span> <span class="n">n</span>
<span class="o">|</span> <span class="nc">Add</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">-></span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span>
<span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">3</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_add</span> <span class="o">(</span><span class="n">cshow</span> <span class="n">e1</span> <span class="mi">3</span><span class="o">)</span> <span class="o">(</span><span class="n">cshow</span> <span class="n">e2</span> <span class="mi">4</span><span class="o">)</span>
<span class="o">|</span> <span class="nc">Mul</span> <span class="o">(</span><span class="n">e1</span><span class="o">,</span><span class="n">e2</span><span class="o">)</span> <span class="o">-></span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span>
<span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">4</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_mul</span> <span class="o">(</span><span class="n">cshow</span> <span class="n">e1</span> <span class="mi">4</span><span class="o">)</span> <span class="o">(</span><span class="n">cshow</span> <span class="n">e2</span> <span class="mi">5</span><span class="o">)</span>
<span class="k">val</span> <span class="n">cshow</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">-></span> <span class="kt">int</span> <span class="o">-></span> <span class="kt">string</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span></code></pre>
<p>Ce qui, au final, donne la version suivante de <code>show</code> à base de <code>fold</code> :</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="n">show</span> <span class="n">e</span> <span class="o">=</span>
<span class="k">let</span> <span class="n">lit</span> <span class="n">i</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span> <span class="n">string_of_int</span> <span class="n">i</span> <span class="k">in</span>
<span class="k">let</span> <span class="n">add</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span> <span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">3</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_add</span> <span class="o">(</span><span class="n">x</span> <span class="mi">3</span><span class="o">)</span> <span class="o">(</span><span class="n">y</span> <span class="mi">4</span><span class="o">)</span> <span class="k">in</span>
<span class="k">let</span> <span class="n">mul</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span> <span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">4</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_mul</span> <span class="o">(</span><span class="n">x</span> <span class="mi">4</span><span class="o">)</span> <span class="o">(</span><span class="n">y</span> <span class="mi">5</span><span class="o">)</span> <span class="k">in</span>
<span class="n">fold</span> <span class="n">lit</span> <span class="n">add</span> <span class="n">mul</span> <span class="n">e</span> <span class="mi">0</span>
<span class="n">show</span> <span class="n">ex2</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"(1 + 2) * (3 + 4)"</span>
<span class="n">show</span> <span class="n">ex3</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"1 + (2 + 3 * 4)"</span></code></pre>
<p>Nous avons vu que même dans le cas où l'interprétation semblait devoir dépendre d'un contexte, l'on pouvait se ramener au cas d'une interprétation sans contexte en changeant le domaine d'interprétation via la <em>curryfication</em>. Essayons à présent d'enrichir un peu notre langage en lui rajoutant une structure conditionnelle du genre if-then-else.</p>
<h3 id="enrichissons-le-langage-avec-des-booléens-et-conditions">Enrichissons le langage avec des booléens et conditions.</h3>
<p>La première idée qui vient à l'esprit est de faire comme précédemment en définissant un <em>variant</em> pour représenter notre nouveau langage. Pour la structure if-then-else, on placera chaque branche dans un <a href="https://en.wikipedia.org/wiki/Thunk"><em>thunk</em></a> (en) car le langage OCaml fait de l'appel par valeur, ainsi l'expression ne sera évaluée que si l'on en a réellement besoin.</p>
<pre><code class="ocaml"><span class="k">type</span> <span class="n">expr</span> <span class="o">=</span>
<span class="o">|</span> <span class="nc">Lit</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">-></span> <span class="n">expr</span>
<span class="o">|</span> <span class="nc">Add</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">*</span> <span class="n">expr</span> <span class="o">-></span> <span class="n">expr</span>
<span class="o">|</span> <span class="nc">Mul</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">*</span> <span class="n">expr</span> <span class="o">-></span> <span class="n">expr</span>
<span class="o">|</span> <span class="nc">Bool</span> <span class="o">:</span> <span class="kt">bool</span> <span class="o">-></span> <span class="n">expr</span>
<span class="o">|</span> <span class="nc">If</span> <span class="o">:</span> <span class="n">expr</span> <span class="o">*</span> <span class="o">(</span><span class="kt">unit</span> <span class="o">-></span> <span class="n">expr</span><span class="o">)</span> <span class="o">*</span> <span class="o">(</span><span class="kt">unit</span> <span class="o">-></span> <span class="n">expr</span><span class="o">)</span> <span class="o">-></span> <span class="n">expr</span></code></pre>
<p>Voilà qui est bien mais cela pose deux problèmes :</p>
<ul>
<li>ce nouveau type n'est pas compatible avec le premier et il faut réécrire toutes nos fonctions ;</li>
<li>il permet de construire des expressions mal typées, comme ajouter deux booléens.</li>
</ul><p>Le premier point peut être géré, entre autre, via ce que l'on appelle les <em>variants polymorphes</em> mais cette solution, que je ne traiterai pas, ne permet pas de résoudre le second point. Je vais néanmoins montrer comment résoudre le second grâce aux GADT ou <em>types algébriques généralisés</em>. En revanche le premier problème persistera : il faudra réécrire nos fonctions.</p>
<p>Un GADT consiste à utiliser un type <em>paramétré</em> par un autre type et à s'en servir pour typer tant les paramètres que la sortie de chacun des constructeurs du variant.</p>
<pre><code class="ocaml"><span class="k">type</span> <span class="o">_</span> <span class="n">expr</span> <span class="o">=</span>
<span class="o">|</span> <span class="nc">Lit</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">-></span> <span class="kt">int</span> <span class="n">expr</span>
<span class="o">|</span> <span class="nc">Add</span> <span class="o">:</span> <span class="kt">int</span> <span class="n">expr</span> <span class="o">*</span> <span class="kt">int</span> <span class="n">expr</span> <span class="o">-></span> <span class="kt">int</span> <span class="n">expr</span>
<span class="o">|</span> <span class="nc">Mul</span> <span class="o">:</span> <span class="kt">int</span> <span class="n">expr</span> <span class="o">*</span> <span class="kt">int</span> <span class="n">expr</span> <span class="o">-></span> <span class="kt">int</span> <span class="n">expr</span>
<span class="o">|</span> <span class="nc">Bool</span> <span class="o">:</span> <span class="kt">bool</span> <span class="o">-></span> <span class="kt">bool</span> <span class="n">expr</span>
<span class="o">|</span> <span class="nc">If</span> <span class="o">:</span> <span class="kt">bool</span> <span class="n">expr</span> <span class="o">*</span> <span class="o">(</span><span class="kt">unit</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="n">expr</span><span class="o">)</span> <span class="o">*</span> <span class="o">(</span><span class="kt">unit</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="n">expr</span><span class="o">)</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="n">expr</span></code></pre>
<p>En fixant les bonnes valeurs du paramètre de type dans chacune des branches, on s'assure ainsi de ne jamais pouvoir ajouter deux booléens sans déclencher d'erreurs de typage à la compilation :</p>
<pre><code class="ocaml"><span class="nc">Add</span> <span class="o">(</span><span class="nc">Bool</span> <span class="bp">true</span><span class="o">,</span> <span class="nc">Bool</span> <span class="bp">false</span><span class="o">);;</span>
<span class="o">^^^^^^^^^</span>
<span class="nc">Error</span><span class="o">:</span> <span class="nc">This</span> <span class="n">expression</span> <span class="n">has</span> <span class="k">type</span> <span class="kt">bool</span> <span class="n">expr</span>
<span class="n">but</span> <span class="n">an</span> <span class="n">expression</span> <span class="n">was</span> <span class="n">expected</span> <span class="k">of</span> <span class="k">type</span> <span class="kt">int</span> <span class="n">expr</span>
<span class="nc">Type</span> <span class="kt">bool</span> <span class="n">is</span> <span class="n">not</span> <span class="n">compatible</span> <span class="k">with</span> <span class="k">type</span> <span class="kt">int</span></code></pre>
<p>Outre la garantie de typage qu'ils offrent pour notre langage, les GADT sont un outil puissant afin de garantir de nombreux invariants sur des structures de données. Leurs possibilités dépassent de loin le cadre de ce journal, mais on pourra trouver un exposé détaillé dans <a href="https://www.cl.cam.ac.uk/teaching/1516/L28/gadts.pdf">cette leçon en anglais</a> accompagné de <a href="https://ocamllabs.github.io/iocamljs/GADTs-json.html">son TD</a> qui permet d'utiliser OCaml dans son navigateur.</p>
<p>Le typage de fonctions impliquant des GADT n'est en général pas décidable et il n'est pas possible de définir une fonction aussi générique que le <code>fold</code> comme pour les variants classiques. Je me contenterai simplement de montrer comment écrire la fonction <code>eval</code> pour ce nouveau langage.</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="k">rec</span> <span class="n">eval</span> <span class="o">:</span> <span class="k">type</span> <span class="n">a</span><span class="o">.</span> <span class="n">a</span> <span class="n">expr</span> <span class="o">-></span> <span class="n">a</span> <span class="o">=</span> <span class="k">function</span>
<span class="o">|</span> <span class="nc">Lit</span> <span class="n">n</span> <span class="o">-></span> <span class="n">n</span>
<span class="o">|</span> <span class="nc">Add</span> <span class="o">(</span><span class="n">x</span><span class="o">,</span><span class="n">y</span><span class="o">)</span> <span class="o">-></span> <span class="o">(</span><span class="n">eval</span> <span class="n">x</span><span class="o">)</span> <span class="o">+</span> <span class="o">(</span><span class="n">eval</span> <span class="n">y</span><span class="o">)</span>
<span class="o">|</span> <span class="nc">Mul</span> <span class="o">(</span><span class="n">x</span><span class="o">,</span><span class="n">y</span><span class="o">)</span> <span class="o">-></span> <span class="o">(</span><span class="n">eval</span> <span class="n">x</span><span class="o">)</span> <span class="o">*</span> <span class="o">(</span><span class="n">eval</span> <span class="n">y</span><span class="o">)</span>
<span class="o">|</span> <span class="nc">Bool</span> <span class="n">b</span> <span class="o">-></span> <span class="n">b</span>
<span class="o">|</span> <span class="nc">If</span> <span class="o">(</span><span class="n">b</span><span class="o">,</span><span class="n">th</span><span class="o">,</span><span class="n">el</span><span class="o">)</span> <span class="o">-></span> <span class="k">if</span> <span class="o">(</span><span class="n">eval</span> <span class="n">b</span><span class="o">)</span> <span class="k">then</span> <span class="n">eval</span> <span class="o">(</span><span class="n">th</span> <span class="bp">()</span><span class="o">)</span> <span class="k">else</span> <span class="n">eval</span> <span class="o">(</span><span class="n">el</span> <span class="bp">()</span><span class="o">)</span></code></pre>
<p>Il faut ajouter une annotation de typage avec un <em>type local abstrait</em> (<code>type a</code>) pour préciser au compilateur que le type de retour est le même que le paramètre de type de l'expression. En dehors de cette annotation, le corps de la fonction est équivalente à sa version avec variant classique. Son retour sur un exemple :</p>
<pre><code class="ocaml"><span class="n">eval</span> <span class="o">(</span><span class="nc">If</span> <span class="o">(</span><span class="nc">Bool</span> <span class="bp">true</span><span class="o">,</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="nc">Lit</span> <span class="mi">1</span><span class="o">),</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="nc">Lit</span> <span class="mi">2</span><span class="o">)));;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">1</span></code></pre>
<h2 id="approche-par-ast-sous-forme-de-fonctions-ou-méthode-tagless-final">Approche par AST sous forme de fonctions ou méthode <em>tagless-final</em>.</h2>
<p>Maintenant que nous avons vu comment comment plonger un langage en OCaml selon la méthode initiale, nous traiterons une autre méthode — objet principal du présent journal — qui permet de résoudre un problème inaccessible à l'autre manière de procéder : étendre les langages en réutilisant le code déja écrit.</p>
<h3 id="langage-additif-et-multiplicatif-sur-les-entiers-1">Langage additif et multiplicatif sur les entiers.</h3>
<p>Le principe de base de cette méthode consistera à utiliser <a href="http://caml.inria.fr/pub/docs/manual-ocaml/moduleexamples.html">le système de modules du langage OCaml</a> (en), de s'inspirer des GADT pour garantir le bon typage du langage et de la fonction <code>fold</code> pour déterminer le contenu des modules. Dans un premier temps, un module peut être vu comme un espace de noms contenant des déclarations de type et de valeurs. Chaque module dispose d'une signature, qui est l'équivalent des types pour les modules, et celle-ci exprime la nature des éléments déclarés par le module.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="k">type</span> <span class="nc">SIG</span> <span class="o">=</span> <span class="k">sig</span>
<span class="k">type</span> <span class="n">t</span>
<span class="k">val</span> <span class="n">i</span> <span class="o">:</span> <span class="n">t</span>
<span class="k">end</span>
<span class="k">module</span> <span class="nc">M</span> <span class="o">:</span> <span class="nc">SIG</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">type</span> <span class="n">t</span> <span class="o">=</span> <span class="kt">int</span>
<span class="k">let</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span>
<span class="k">end</span>
<span class="nn">M</span><span class="p">.</span><span class="n">i</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="nn">M</span><span class="p">.</span><span class="n">t</span> <span class="o">=</span> <span class="o"><</span><span class="n">abstr</span><span class="o">></span></code></pre>
<p>Dans cet exemple, un module satisfaisant la signature <code>SIG</code> doit déclarer un type <code>t</code> et une valeur <code>i</code> de type <code>t</code>. Ce que fait le module <code>M</code> définit ensuite, et l'on accède aux valeurs définies dans le module par la notation pointée. Ici c'est de peu d'utilité car comme <em>extérieurement</em> on ne sait rien sur le type <code>t</code> de la valeur, on ne peut pas en faire usage. Pour pouvoir l'utiliser, il faudrait que le module M définisse également des fonctions pour <em>opérer</em> sur les valeurs du type qu'il déclare. C'est ce que nous allons faire avec notre langage sur les entiers.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="k">type</span> <span class="nc">SYM_INT</span> <span class="o">=</span> <span class="k">sig</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">repr</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">obs</span>
<span class="k">val</span> <span class="n">lit</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">-></span> <span class="kt">int</span> <span class="n">repr</span>
<span class="k">val</span> <span class="n">add</span> <span class="o">:</span> <span class="kt">int</span> <span class="n">repr</span> <span class="o">-></span> <span class="kt">int</span> <span class="n">repr</span> <span class="o">-></span> <span class="kt">int</span> <span class="n">repr</span>
<span class="k">val</span> <span class="n">mul</span> <span class="o">:</span> <span class="kt">int</span> <span class="n">repr</span> <span class="o">-></span> <span class="kt">int</span> <span class="n">repr</span> <span class="o">-></span> <span class="kt">int</span> <span class="n">repr</span>
<span class="k">val</span> <span class="n">observe</span> <span class="o">:</span> <span class="k">'</span><span class="n">a</span> <span class="n">repr</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="n">obs</span>
<span class="k">end</span></code></pre>
<p>Cette signature définit deux types et quelques fonctions pour opérer dessus. On peut remarquer que le type des fonctions <code>lit</code>, <code>add</code> et <code>mul</code> mime, sous forme curryfiée, les constructeurs du GADT de la première partie. Le type paramétré <code>'a repr</code> servira à la représentation <em>interne</em> des termes de notre langage, tandis que le type <code>'a obs</code> permettra de les présenter <em>extérieurement</em>. Le nom de la signature est préfixée par <code>SYM</code> ce qui renvoie au néologisme <em>symantique</em> forgée par les inventeurs de la méthode afin de signifier que celle-ci exprime à la fois la <em>syntaxe</em> et la <em>sémantique</em> du langage.</p>
<p>Pour implémenter un module satisfaisant cette signature, il suffit alors de réutiliser ce que nous avons fait précédemment pour diversifier les interprétations avec la fonction <code>fold</code>. Chaque module correspondra à une interprétation différente de notre langage, et le code des fonctions sera celui des arguments passés à la fonction <code>fold</code>. On se retrouve alors avec ces deux interprétations possibles :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">EvalInt</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">repr</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">obs</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span>
<span class="k">let</span> <span class="n">lit</span> <span class="n">n</span> <span class="o">=</span> <span class="n">n</span>
<span class="k">let</span> <span class="n">add</span> <span class="o">=</span> <span class="o">(</span> <span class="o">+</span> <span class="o">)</span>
<span class="k">let</span> <span class="n">mul</span> <span class="o">=</span> <span class="o">(</span> <span class="o">*</span> <span class="o">)</span>
<span class="k">let</span> <span class="n">observe</span> <span class="n">x</span> <span class="o">=</span> <span class="n">x</span>
<span class="k">end</span>
<span class="k">module</span> <span class="nc">ShowInt</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">repr</span> <span class="o">=</span> <span class="kt">int</span> <span class="o">-></span> <span class="kt">string</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">obs</span> <span class="o">=</span> <span class="kt">string</span>
<span class="c">(* quelques fonctions utilitaires *)</span>
<span class="k">let</span> <span class="n">paren</span> <span class="n">s</span> <span class="o">=</span> <span class="s2">"("</span> <span class="o">^</span> <span class="n">s</span> <span class="o">^</span> <span class="s2">")"</span>
<span class="k">let</span> <span class="n">cparen</span> <span class="n">b</span> <span class="o">=</span> <span class="k">if</span> <span class="n">b</span> <span class="k">then</span> <span class="n">paren</span> <span class="k">else</span> <span class="o">(</span><span class="k">fun</span> <span class="n">s</span> <span class="o">-></span> <span class="n">s</span><span class="o">)</span>
<span class="k">let</span> <span class="n">show_int</span> <span class="o">=</span> <span class="n">string_of_int</span>
<span class="k">let</span> <span class="n">show_add</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">=</span> <span class="n">s</span> <span class="o">^</span> <span class="s2">" + "</span> <span class="o">^</span> <span class="n">s'</span>
<span class="k">let</span> <span class="n">show_mul</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">=</span> <span class="n">s</span> <span class="o">^</span> <span class="s2">" * "</span> <span class="o">^</span> <span class="n">s'</span>
<span class="k">let</span> <span class="n">lit</span> <span class="n">n</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span> <span class="n">show_int</span> <span class="n">n</span>
<span class="k">let</span> <span class="n">add</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span>
<span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">3</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_add</span> <span class="o">(</span><span class="n">x</span> <span class="mi">3</span><span class="o">)</span> <span class="o">(</span><span class="n">y</span> <span class="mi">4</span><span class="o">)</span>
<span class="k">let</span> <span class="n">mul</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span>
<span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">4</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_mul</span> <span class="o">(</span><span class="n">x</span> <span class="mi">4</span><span class="o">)</span> <span class="o">(</span><span class="n">y</span> <span class="mi">5</span><span class="o">)</span>
<span class="k">let</span> <span class="n">observe</span> <span class="n">x</span> <span class="o">=</span> <span class="n">x</span> <span class="mi">0</span>
<span class="k">end</span></code></pre>
<p>Afin de les tester, définissons un module d'exemples :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">ExInt</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">open</span> <span class="nc">I</span>
<span class="k">let</span> <span class="n">observe</span> <span class="o">=</span> <span class="n">observe</span>
<span class="k">let</span> <span class="o">(</span> <span class="o">+</span> <span class="o">)</span> <span class="o">=</span> <span class="n">add</span>
<span class="k">let</span> <span class="o">(</span> <span class="o">*</span> <span class="o">)</span> <span class="o">=</span> <span class="n">mul</span>
<span class="k">let</span> <span class="n">ex1</span> <span class="o">=</span> <span class="n">lit</span> <span class="mi">1</span> <span class="o">+</span> <span class="n">lit</span> <span class="mi">2</span>
<span class="k">let</span> <span class="n">ex2</span> <span class="o">=</span> <span class="o">(</span><span class="n">lit</span> <span class="mi">1</span> <span class="o">+</span> <span class="n">lit</span> <span class="mi">2</span><span class="o">)</span> <span class="o">*</span> <span class="o">(</span><span class="n">lit</span> <span class="mi">3</span> <span class="o">+</span> <span class="n">lit</span> <span class="mi">4</span><span class="o">)</span>
<span class="k">let</span> <span class="n">ex3</span> <span class="o">=</span> <span class="n">lit</span> <span class="mi">1</span> <span class="o">+</span> <span class="o">(</span><span class="n">lit</span> <span class="mi">2</span> <span class="o">+</span> <span class="n">lit</span> <span class="mi">3</span> <span class="o">*</span> <span class="n">lit</span> <span class="mi">4</span><span class="o">)</span>
<span class="k">end</span></code></pre>
<p>Ce module, contrairement aux précédents, est paramétré par un autre module d'interprétation de notre langage : c'est ce que l'on appelle un <em>foncteur</em>. La directive <code>open</code> permet d'ouvrir l'espace de nom du module <code>I</code> pour ne pas avoir besoin d'utiliser la notation pointée. Pour l'usage, cela se passe comme suit :</p>
<pre><code class="ocaml"><span class="c">(* on applique notre foncteur sur nos deux modules *)</span>
<span class="k">module</span> <span class="nc">ExEval</span> <span class="o">=</span> <span class="nc">ExInt</span><span class="o">(</span><span class="nc">EvalInt</span><span class="o">)</span>
<span class="k">module</span> <span class="nc">ExShow</span> <span class="o">=</span> <span class="nc">ExInt</span><span class="o">(</span><span class="nc">ShowInt</span><span class="o">)</span>
<span class="c">(* on teste le bon fonctionnement de nos interprétations *)</span>
<span class="nn">ExEval</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex2</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">21</span>
<span class="nn">ExShow</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex2</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"(1 + 2) * (3 + 4)"</span>
<span class="nn">ExShow</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex3</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"1 + (2 + 3 * 4)"</span></code></pre>
<h3 id="enrichissons-le-langage-avec-des-booléens-et-conditions-1">Enrichissons le langage avec des booléens et conditions.</h3>
<p>Comme dans la première partie nous allons maintenant tenter d'étendre notre langage, et c'est là que nous verrons la supériorité de cette méthode sur l'autre : on pourra réutiliser le code déjà écrit. On commence par définir la signature définissant la <em>symantique</em> du langage étendu.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="k">type</span> <span class="nc">SYM_INT_COND</span> <span class="o">=</span> <span class="k">sig</span>
<span class="k">include</span> <span class="nc">SYM_INT</span>
<span class="k">val</span> <span class="n">bool_</span> <span class="o">:</span> <span class="kt">bool</span> <span class="o">-></span> <span class="kt">bool</span> <span class="n">repr</span>
<span class="k">val</span> <span class="n">if_</span> <span class="o">:</span> <span class="kt">bool</span> <span class="n">repr</span> <span class="o">-></span> <span class="o">(</span><span class="kt">unit</span> <span class="o">-></span> <span class="k">'</span><span class="n">x</span><span class="o">)</span> <span class="o">-></span> <span class="o">(</span><span class="kt">unit</span> <span class="o">-></span> <span class="k">'</span><span class="n">x</span><span class="o">)</span> <span class="o">-></span> <span class="o">(</span><span class="k">'</span><span class="n">a</span> <span class="n">repr</span> <span class="k">as</span> <span class="k">'</span><span class="n">x</span><span class="o">)</span>
<span class="k">val</span> <span class="n">eq</span> <span class="o">:</span> <span class="kt">int</span> <span class="n">repr</span> <span class="o">-></span> <span class="kt">int</span> <span class="n">repr</span> <span class="o">-></span> <span class="kt">bool</span> <span class="n">repr</span>
<span class="k">val</span> <span class="n">lt</span> <span class="o">:</span> <span class="kt">int</span> <span class="n">repr</span> <span class="o">-></span> <span class="kt">int</span> <span class="n">repr</span> <span class="o">-></span> <span class="kt">bool</span> <span class="n">repr</span>
<span class="k">end</span></code></pre>
<p>Afin d'<em>étendre</em> le langage, il suffit d'utiliser la directive <code>include</code> puis de rajouter ensuite les nouvelles constructions du langage. On en a profité ici pour ajouter des fonctions de comparaisons sur les entiers. Pour les nouvelles interprétations, on procède de même :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">EvalIntCond</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">include</span> <span class="nc">EvalInt</span>
<span class="k">let</span> <span class="n">bool_</span> <span class="n">b</span> <span class="o">=</span> <span class="n">b</span>
<span class="k">let</span> <span class="n">if_</span> <span class="n">b</span> <span class="n">th</span> <span class="n">el</span> <span class="o">=</span> <span class="k">if</span> <span class="n">b</span> <span class="k">then</span> <span class="n">th</span> <span class="bp">()</span> <span class="k">else</span> <span class="n">el</span> <span class="bp">()</span>
<span class="k">let</span> <span class="n">eq</span> <span class="o">=</span> <span class="o">(</span> <span class="o">=</span> <span class="o">)</span>
<span class="k">let</span> <span class="n">lt</span> <span class="o">=</span> <span class="o">(</span> <span class="o"><</span> <span class="o">)</span>
<span class="k">end</span>
<span class="k">module</span> <span class="nc">ShowIntCond</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">include</span> <span class="nc">ShowInt</span>
<span class="k">let</span> <span class="n">show_bool</span> <span class="o">=</span> <span class="n">string_of_bool</span>
<span class="k">let</span> <span class="n">show_if</span> <span class="n">bs</span> <span class="n">ts</span> <span class="n">es</span> <span class="o">=</span> <span class="s2">"if "</span> <span class="o">^</span> <span class="n">bs</span> <span class="o">^</span> <span class="s2">" then "</span> <span class="o">^</span> <span class="n">ts</span> <span class="o">^</span> <span class="s2">" else "</span> <span class="o">^</span> <span class="n">es</span>
<span class="k">let</span> <span class="n">show_eq</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">=</span> <span class="n">s</span> <span class="o">^</span> <span class="s2">" = "</span> <span class="o">^</span> <span class="n">s'</span>
<span class="k">let</span> <span class="n">show_lt</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">=</span> <span class="n">s</span> <span class="o">^</span> <span class="s2">" < "</span> <span class="o">^</span> <span class="n">s'</span>
<span class="k">let</span> <span class="n">bool_</span> <span class="n">b</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span> <span class="n">show_bool</span> <span class="n">b</span>
<span class="k">let</span> <span class="n">if_</span> <span class="n">b</span> <span class="n">th</span> <span class="n">el</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span>
<span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">0</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_if</span> <span class="o">(</span><span class="n">b</span> <span class="mi">0</span><span class="o">)</span> <span class="o">(</span><span class="n">th</span> <span class="bp">()</span> <span class="mi">0</span><span class="o">)</span> <span class="o">(</span><span class="n">el</span> <span class="bp">()</span> <span class="mi">0</span><span class="o">)</span>
<span class="k">let</span> <span class="n">eq</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span>
<span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">0</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_eq</span> <span class="o">(</span><span class="n">x</span> <span class="mi">1</span><span class="o">)</span> <span class="o">(</span><span class="n">y</span> <span class="mi">1</span><span class="o">)</span>
<span class="k">let</span> <span class="n">lt</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">p</span> <span class="o">-></span>
<span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">0</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_lt</span> <span class="o">(</span><span class="n">x</span> <span class="mi">1</span><span class="o">)</span> <span class="o">(</span><span class="n">y</span> <span class="mi">1</span><span class="o">)</span>
<span class="k">end</span></code></pre>
<p>On peut de même étendre notre module d'exemples pour tester ces nouvelles interprétations :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">ExIntCond</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT_COND</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">include</span> <span class="nc">ExInt</span><span class="o">(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">open</span> <span class="nc">I</span>
<span class="k">let</span> <span class="o">(</span> <span class="o">=</span> <span class="o">)</span> <span class="o">=</span> <span class="n">eq</span>
<span class="k">let</span> <span class="o">(</span> <span class="o"><</span> <span class="o">)</span> <span class="o">=</span> <span class="n">lt</span>
<span class="k">let</span> <span class="bp">true</span><span class="o">_</span> <span class="o">=</span> <span class="n">bool_</span> <span class="bp">true</span>
<span class="k">let</span> <span class="bp">false</span><span class="o">_</span> <span class="o">=</span> <span class="n">bool_</span> <span class="bp">false</span>
<span class="k">let</span> <span class="n">ex4</span> <span class="o">=</span> <span class="n">if_</span> <span class="bp">true</span><span class="o">_</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">ex3</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">ex2</span><span class="o">)</span>
<span class="k">let</span> <span class="n">ex5</span> <span class="o">=</span> <span class="n">if_</span> <span class="o">(</span><span class="n">lit</span> <span class="mi">1</span> <span class="o"><</span> <span class="n">lit</span> <span class="mi">2</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">ex3</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">ex4</span><span class="o">)</span>
<span class="k">let</span> <span class="n">ex6</span> <span class="o">=</span> <span class="n">if_</span> <span class="o">(</span><span class="n">ex5</span> <span class="o">=</span> <span class="n">ex3</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="bp">true</span><span class="o">_)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="bp">false</span><span class="o">_)</span>
<span class="k">end</span></code></pre>
<p>Quelques tests :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">ExEval</span> <span class="o">=</span> <span class="nc">ExIntCond</span><span class="o">(</span><span class="nc">EvalIntCond</span><span class="o">)</span>
<span class="k">module</span> <span class="nc">ExShow</span> <span class="o">=</span> <span class="nc">ExIntCond</span><span class="o">(</span><span class="nc">ShowIntCond</span><span class="o">)</span>
<span class="nn">ExEval</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex4</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">15</span>
<span class="nn">ExEval</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex5</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">15</span>
<span class="nn">ExEval</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex6</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">bool</span> <span class="o">=</span> <span class="bp">true</span>
<span class="nn">ExShow</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex6</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span>
<span class="s2">"if (if 1 < 2 then 1 + (2 + 3 * 4)</span>
<span class="s2"> else if true then 1 + (2 + 3 * 4)</span>
<span class="s2"> else (1 + 2) * (3 + 4)) = 1 + (2 + 3 * 4)</span>
<span class="s2">then true else false"</span>
<span class="nn">ExShow</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex4</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"if true then 1 + (2 + 3 * 4) else (1 + 2) * (3 + 4)"</span></code></pre>
<h3 id="fiat-lux--que-la-lumière-soit-et-la-lumière-fut">Fiat lux : Que la lumière soit, et la lumière fut !</h3>
<p>Jusqu'ici nous avons représenté les termes de nos langages objets directement dans le langage hôte OCaml de deux manières distinctes :</p>
<ul>
<li>arbre syntaxique comme structure de données ;</li>
<li>arbre syntaxique sous forme de fonctions.</li>
</ul><p>Nous allons montrer qu'au fond la première technique n'est qu'un cas particulier de la seconde, et illustrer comment l'approche <em>tagless-final</em> généralise la première. Ainsi, la première se subsumant sous la seconde, dans la suite du journal nous n'utiliserons plus que cette dernière.</p>
<p>Reprenons le code écrit jusqu'ici pour la méthode avec structures de données et <code>fold</code> pour le langage additif et multiplicatif, puis encapsulons le dans un <em>module</em>.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">Ast</span> <span class="o">=</span> <span class="k">struct</span>
<span class="c">(* on y met les définitions du type, du fold</span>
<span class="c"> * et des différentes intéprétations *)</span>
<span class="k">end</span></code></pre>
<p>À partir de là, rien de plus simple que de définir des modules de signature <code>SYM_INT</code> qui s'intègrent parfaitement dans l'approche <em>tagless-final</em>.</p>
<p>On commence par un module dont la représentation interne est justement notre structure de données :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">AstBase</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">type</span> <span class="o">_</span> <span class="n">repr</span> <span class="o">=</span> <span class="nn">Ast</span><span class="p">.</span><span class="n">expr</span>
<span class="k">let</span> <span class="n">lit</span> <span class="n">n</span> <span class="o">=</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Lit</span> <span class="n">n</span>
<span class="k">let</span> <span class="n">add</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Add</span> <span class="o">(</span><span class="n">x</span><span class="o">,</span><span class="n">y</span><span class="o">)</span>
<span class="k">let</span> <span class="n">mul</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="nn">Ast</span><span class="p">.</span><span class="nc">Mul</span> <span class="o">(</span><span class="n">x</span><span class="o">,</span><span class="n">y</span><span class="o">)</span>
<span class="k">end</span></code></pre>
<p>puis on l'étend vers différents modules de signature <code>SYM_INT</code> qui <em>observeront</em> ou <em>interpréteront</em> nos arbres différemment.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">AstEval</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">include</span> <span class="nc">AstBase</span>
<span class="k">type</span> <span class="o">_</span> <span class="n">obs</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span>
<span class="k">let</span> <span class="n">observe</span> <span class="o">=</span> <span class="nn">Ast</span><span class="p">.</span><span class="n">eval</span>
<span class="k">end</span>
<span class="k">module</span> <span class="nc">AstShow</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">include</span> <span class="nc">AstBase</span>
<span class="k">type</span> <span class="o">_</span> <span class="n">obs</span> <span class="o">=</span> <span class="kt">string</span>
<span class="k">let</span> <span class="n">observe</span> <span class="o">=</span> <span class="nn">Ast</span><span class="p">.</span><span class="n">show</span>
<span class="k">end</span></code></pre>
<p>On peut maintenant les utiliser sans problème avec notre module d'exemples :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">ExEval</span> <span class="o">=</span> <span class="nc">ExInt</span><span class="o">(</span><span class="nc">AstEval</span><span class="o">)</span>
<span class="k">module</span> <span class="nc">ExShow</span> <span class="o">=</span> <span class="nc">ExInt</span><span class="o">(</span><span class="nc">AstShow</span><span class="o">)</span>
<span class="nn">ExEval</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex3</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">15</span>
<span class="nn">ExShow</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex3</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"1 + (2 + 3 * 4)"</span></code></pre>
<h2 id="optimisons-un-peu-nos-interprètes">Optimisons un peu nos interprètes !</h2>
<p>Dans cette section nous présenterons un cadre général, et ses principes, pour effectuer des optimisations sur nos langages. Nous verrons aussi comment tirer profit de la structure modulaire du code pour réaliser cette tâche.</p>
<h3 id="suppression-des-opérandes-nuls">Suppression des opérandes nuls.</h3>
<p>La première optimisation que l'on va voir est celle qui consiste à supprimer tous les litéraux nuls, en appliquant les règles : <code>x + 0 = 0 + x = 0</code> et <code>x * 0 = 0 * x = 0</code>.</p>
<p>Pour ce faire, on partira d'un interprète <code>I</code> quelconque puis on représentera chaque terme à l'aide d'un GADT qui exprimera notre connaissance sur sa nullité. Enfin, pour l'observer, on se contentera de renvoyer l'observation par <code>I</code>.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">RemoveZero</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">repr</span> <span class="o">=</span>
<span class="o">|</span> <span class="nc">Unk</span> <span class="o">:</span> <span class="k">'</span><span class="n">a</span> <span class="nn">I</span><span class="p">.</span><span class="n">repr</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="n">repr</span>
<span class="o">|</span> <span class="nc">Zero</span> <span class="o">:</span> <span class="kt">int</span> <span class="n">repr</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">obs</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span> <span class="nn">I</span><span class="p">.</span><span class="n">obs</span>
<span class="k">let</span> <span class="n">lit</span> <span class="n">n</span> <span class="o">=</span> <span class="k">if</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">0</span> <span class="k">then</span> <span class="nc">Zero</span> <span class="k">else</span> <span class="nc">Unk</span> <span class="o">(</span><span class="nn">I</span><span class="p">.</span><span class="n">lit</span> <span class="n">n</span><span class="o">)</span>
<span class="k">let</span> <span class="n">add</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">match</span> <span class="n">x</span><span class="o">,</span><span class="n">y</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Zero</span><span class="o">,</span> <span class="o">_</span> <span class="o">-></span> <span class="n">y</span>
<span class="o">|</span> <span class="o">_,</span> <span class="nc">Zero</span> <span class="o">-></span> <span class="n">x</span>
<span class="o">|</span> <span class="nc">Unk</span> <span class="n">x</span><span class="o">,</span> <span class="nc">Unk</span> <span class="n">y</span> <span class="o">-></span> <span class="nc">Unk</span> <span class="o">(</span><span class="nn">I</span><span class="p">.</span><span class="n">add</span> <span class="n">x</span> <span class="n">y</span><span class="o">)</span>
<span class="k">let</span> <span class="n">mul</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">match</span> <span class="n">x</span><span class="o">,</span><span class="n">y</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Zero</span><span class="o">,</span> <span class="o">_</span>
<span class="o">|</span> <span class="o">_,</span> <span class="nc">Zero</span> <span class="o">-></span> <span class="nc">Zero</span>
<span class="o">|</span><span class="nc">Unk</span> <span class="n">x</span><span class="o">,</span> <span class="nc">Unk</span> <span class="n">y</span> <span class="o">-></span> <span class="nc">Unk</span> <span class="o">(</span><span class="nn">I</span><span class="p">.</span><span class="n">mul</span> <span class="n">x</span> <span class="n">y</span><span class="o">)</span>
<span class="k">let</span> <span class="n">observe</span> <span class="o">:</span> <span class="k">type</span> <span class="n">a</span><span class="o">.</span> <span class="n">a</span> <span class="n">repr</span> <span class="o">-></span> <span class="n">a</span> <span class="n">obs</span> <span class="o">=</span> <span class="k">function</span>
<span class="o">|</span> <span class="nc">Unk</span> <span class="n">x</span> <span class="o">-></span> <span class="nn">I</span><span class="p">.</span><span class="n">observe</span> <span class="n">x</span>
<span class="o">|</span> <span class="nc">Zero</span> <span class="o">-></span> <span class="nn">I</span><span class="p">.</span><span class="n">observe</span> <span class="o">(</span><span class="nn">I</span><span class="p">.</span><span class="n">lit</span> <span class="mi">0</span><span class="o">)</span>
<span class="k">end</span></code></pre>
<p>On écrit un module de test pour vérifier que tout se passe bien :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">Test</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">open</span> <span class="nc">I</span>
<span class="k">let</span> <span class="n">observe</span> <span class="o">=</span> <span class="n">observe</span>
<span class="k">let</span> <span class="o">(+)</span> <span class="o">=</span> <span class="n">add</span>
<span class="k">let</span> <span class="o">(</span> <span class="o">*</span> <span class="o">)</span> <span class="o">=</span> <span class="n">mul</span>
<span class="k">let</span> <span class="n">e1</span> <span class="o">=</span> <span class="n">lit</span> <span class="mi">1</span> <span class="o">+</span> <span class="n">lit</span> <span class="mi">0</span> <span class="o">+</span> <span class="n">lit</span> <span class="mi">2</span>
<span class="k">let</span> <span class="n">e2</span> <span class="o">=</span> <span class="n">e1</span> <span class="o">+</span> <span class="n">lit</span> <span class="mi">0</span> <span class="o">*</span> <span class="n">lit</span> <span class="mi">3</span>
<span class="k">end</span>
<span class="c">(* sans optimisation *)</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">Test</span><span class="o">(</span><span class="nc">ShowInt</span><span class="o">)</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">e2</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"1 + 0 + 2 + 0 * 3"</span>
<span class="c">(* l'optimiseur en pratique *)</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">Test</span><span class="o">(</span><span class="nc">RemoveZero</span><span class="o">(</span><span class="nc">ShowInt</span><span class="o">))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">e2</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"1 + 2"</span>
<span class="c">(* sur un interprète issu de la méthode avec variant *)</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">Test</span><span class="o">(</span><span class="nc">RemoveZero</span><span class="o">(</span><span class="nc">AstShow</span><span class="o">))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">e2</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"1 + 2"</span></code></pre>
<h3 id="principe-général-des-transformations">Principe général des transformations.</h3>
<p>Lorsque l'on a supprimé les littéraux nuls, on a au fond <em>transformer</em> l'arbre syntaxique (comme le montre leur représentation sous forme de chaîne de caractères) mais sans modifier son interprétation <em>naturelle</em> en tant qu'entier.</p>
<p>À cet effet, on est parti d'une représentation donnée par un interprète <code>I</code>, puis l'on a envoyé les représentations dans un autre domaine <code>Unk : 'a I.repr -> 'a repr | Zero : int repr</code> afin d'opérer dessus, pour enfin revenir dans le domaine de l'interpréteur <code>I</code> et <em>observer</em> la transformation. Le principe de l'aller-retour entre deux domaines est capturé par la signature de module suivante :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="k">type</span> <span class="nc">TRANS</span> <span class="o">=</span> <span class="k">sig</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">from</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">term</span>
<span class="k">val</span> <span class="n">fwd</span> <span class="o">:</span> <span class="k">'</span><span class="n">a</span> <span class="n">from</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="n">term</span>
<span class="k">val</span> <span class="n">bwd</span> <span class="o">:</span> <span class="k">'</span><span class="n">a</span> <span class="n">term</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="n">from</span>
<span class="k">end</span></code></pre>
<p>L'optimiseur travaille sur des <code>'a term</code> qui contiennent les informations nécessaires à sa tâche. Ils sont obtenus à partir d'une autre représentation intermédiaire <code>'a from</code> via la fonction <code>fwd</code> puis, une fois l'optimisation terminée, on revient dans la représentation de départ à l'aide de la fonction <code>bwd</code>.</p>
<p>On peut coder à partir d'une transformation <code>X : TRANS</code> un « optimiseur » trivial qui… ne change rien :-P</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">SymIntT</span> <span class="o">(</span><span class="nc">X</span> <span class="o">:</span> <span class="nc">TRANS</span><span class="o">)</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT</span> <span class="k">with</span> <span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">repr</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span> <span class="nn">X</span><span class="p">.</span><span class="n">from</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">open</span> <span class="nc">X</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">repr</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span> <span class="n">term</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">obs</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span> <span class="nn">I</span><span class="p">.</span><span class="n">obs</span>
<span class="k">let</span> <span class="n">lit</span> <span class="n">n</span> <span class="o">=</span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">lit</span> <span class="n">n</span>
<span class="k">let</span> <span class="n">add</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">add</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">y</span><span class="o">)</span>
<span class="k">let</span> <span class="n">mul</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">mul</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">y</span><span class="o">)</span>
<span class="k">let</span> <span class="n">observe</span> <span class="n">x</span> <span class="o">=</span> <span class="nn">I</span><span class="p">.</span><span class="n">observe</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span>
<span class="k">end</span></code></pre>
<p>Pour avoir un optimiseur plus utile que celui-ci, il faut fournir deux choses :</p>
<ul>
<li>une transformation <code>X : TRANS</code> pour obtenir des termes sur lesquels opérer ;</li>
<li>un interprète <em>partiel</em> qui opère sur la partie du langage qu'il optimise.</li>
</ul><p>Le plus simple est de mettre le tout dans un module, ce qui dans le cas de la suppression des zéros donne :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">RemoveZeroPass</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="c">(* la transformation pour faire l'aller-retour entre les deux domaines *)</span>
<span class="k">module</span> <span class="nc">X</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">from</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span> <span class="nn">I</span><span class="p">.</span><span class="n">repr</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">term</span> <span class="o">=</span>
<span class="o">|</span> <span class="nc">Unk</span> <span class="o">:</span> <span class="k">'</span><span class="n">a</span> <span class="nn">I</span><span class="p">.</span><span class="n">repr</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="n">term</span>
<span class="o">|</span> <span class="nc">Zero</span> <span class="o">:</span> <span class="kt">int</span> <span class="n">term</span>
<span class="k">let</span> <span class="n">fwd</span> <span class="n">x</span> <span class="o">=</span> <span class="nc">Unk</span> <span class="n">x</span>
<span class="k">let</span> <span class="n">bwd</span> <span class="o">:</span> <span class="k">type</span> <span class="n">a</span><span class="o">.</span> <span class="n">a</span> <span class="n">term</span> <span class="o">-></span> <span class="n">a</span> <span class="n">from</span> <span class="o">=</span> <span class="k">function</span>
<span class="o">|</span> <span class="nc">Unk</span> <span class="n">x</span> <span class="o">-></span> <span class="n">x</span>
<span class="o">|</span> <span class="nc">Zero</span> <span class="o">-></span> <span class="nn">I</span><span class="p">.</span><span class="n">lit</span> <span class="mi">0</span>
<span class="k">end</span>
<span class="k">open</span> <span class="nc">X</span>
<span class="c">(* la passe d'optimisation proprement dite *)</span>
<span class="k">module</span> <span class="nc">IDelta</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">let</span> <span class="n">lit</span> <span class="n">n</span> <span class="o">=</span> <span class="k">if</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">0</span> <span class="k">then</span> <span class="nc">Zero</span> <span class="k">else</span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">lit</span> <span class="n">n</span>
<span class="k">let</span> <span class="n">add</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">match</span> <span class="n">x</span><span class="o">,</span><span class="n">y</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Zero</span><span class="o">,</span> <span class="o">_</span> <span class="o">-></span> <span class="n">y</span>
<span class="o">|</span> <span class="o">_,</span> <span class="nc">Zero</span> <span class="o">-></span> <span class="n">x</span>
<span class="o">|</span> <span class="o">_</span> <span class="o">-></span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">add</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">y</span><span class="o">)</span>
<span class="k">let</span> <span class="n">mul</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">match</span> <span class="n">x</span><span class="o">,</span><span class="n">y</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Zero</span><span class="o">,</span> <span class="o">_</span>
<span class="o">|</span> <span class="o">_,</span> <span class="nc">Zero</span> <span class="o">-></span> <span class="nc">Zero</span>
<span class="o">|</span> <span class="o">_</span> <span class="o">-></span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">mul</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">y</span><span class="o">)</span>
<span class="k">end</span>
<span class="k">end</span></code></pre>
<p>Afin de préserver l'interprétation des termes qui ne sont pas concernés par la passe d'optimisation, il faut s'assurer que l'on a toujours <code>bwd (fwd x) = x</code>, ce qui est évident dans notre cas. Le module <code>IDelta</code> porte ce nom pour signifier qu'il contient la différence (le delta) d'interprétation par rapport à l'interprète initial <code>I</code>.</p>
<p>À partir de là, on obtient l'optimiseur de la manière suivante :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">RemoveZeroInt</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">module</span> <span class="nc">OptM</span> <span class="o">=</span> <span class="nc">RemoveZeroPass</span><span class="o">(</span><span class="nc">I</span><span class="o">)</span>
<span class="c">(* on inclut l'optimiseur trivial qui ne fait rien *)</span>
<span class="k">include</span> <span class="nc">SymIntT</span><span class="o">(</span><span class="nn">OptM</span><span class="p">.</span><span class="nc">X</span><span class="o">)(</span><span class="nc">I</span><span class="o">)</span>
<span class="c">(* on surcharge les fonctions lit, add et mul *)</span>
<span class="k">include</span> <span class="nn">OptM</span><span class="p">.</span><span class="nc">IDelta</span>
<span class="k">end</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">Test</span><span class="o">(</span><span class="nc">RemoveZeroInt</span><span class="o">(</span><span class="nc">ShowInt</span><span class="o">))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">e2</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"1 + 2"</span></code></pre>
<p>Pour le lecteur qui aime bien les graphiques, on pourrait représenter la passe d'optimisation ainsi :</p>
<pre><code>Domaine 'a from : terme t t optimisé ------> t observé : 'a obs
| ^ I.observe
| |
fwd | | bwd
| |
V passe |
Domaine 'a term : terme t' -----> t' optimisé
</code></pre>
<p>Cette façon de procéder peut sembler étrange au premier abord : pourquoi inclure un optimiseur qui ne fait rien, pour ensuite remplacer immédiatement les fonctions qu'il importe ? Cela n'a effectivement aucun intérêt dans ce cas précis, mais elle illustre un principe général qui sera fort apprécié lorsque la passe ne modifiera pas toutes les constructions du langage : seules les fonctions de l'optimiseur trivial réellement utilisées par le notre seront remplacées et les autres resteront inchangées.</p>
<h3 id="simplification-de-la-multiplication-par-un">Simplification de la multiplication par un.</h3>
<p>Dans la même lignée que l'optimisation précédente, on peut simplifier nos termes du langage en faisant usage de la règle : <code>x * 1 = 1 * x = x</code>.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">RemoveOnePass</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">module</span> <span class="nc">X</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">from</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span> <span class="nn">I</span><span class="p">.</span><span class="n">repr</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">term</span> <span class="o">=</span>
<span class="o">|</span> <span class="nc">Unk</span> <span class="o">:</span> <span class="k">'</span><span class="n">a</span> <span class="n">from</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="n">term</span>
<span class="o">|</span> <span class="nc">One</span> <span class="o">:</span> <span class="kt">int</span> <span class="n">term</span>
<span class="k">let</span> <span class="n">fwd</span> <span class="n">x</span> <span class="o">=</span> <span class="nc">Unk</span> <span class="n">x</span>
<span class="k">let</span> <span class="n">bwd</span> <span class="o">:</span> <span class="k">type</span> <span class="n">a</span><span class="o">.</span> <span class="n">a</span> <span class="n">term</span> <span class="o">-></span> <span class="n">a</span> <span class="n">from</span> <span class="o">=</span> <span class="k">function</span>
<span class="o">|</span> <span class="nc">Unk</span> <span class="n">x</span> <span class="o">-></span> <span class="n">x</span>
<span class="o">|</span> <span class="nc">One</span> <span class="o">-></span> <span class="nn">I</span><span class="p">.</span><span class="n">lit</span> <span class="mi">1</span>
<span class="k">end</span>
<span class="k">open</span> <span class="nc">X</span>
<span class="k">module</span> <span class="nc">IDelta</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">let</span> <span class="n">lit</span> <span class="n">n</span> <span class="o">=</span> <span class="k">if</span> <span class="n">n</span> <span class="o">=</span> <span class="mi">1</span> <span class="k">then</span> <span class="nc">One</span> <span class="k">else</span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">lit</span> <span class="n">n</span>
<span class="k">let</span> <span class="n">mul</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">match</span> <span class="n">x</span><span class="o">,</span><span class="n">y</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">One</span><span class="o">,</span> <span class="o">_</span> <span class="o">-></span> <span class="n">y</span>
<span class="o">|</span> <span class="o">_,</span> <span class="nc">One</span> <span class="o">-></span> <span class="n">x</span>
<span class="o">|</span> <span class="o">_</span> <span class="o">-></span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">mul</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">y</span><span class="o">)</span>
<span class="k">end</span>
<span class="k">end</span>
<span class="c">(* on utilise la passe comme au-dessus *)</span>
<span class="k">module</span> <span class="nc">RemoveOneInt</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">module</span> <span class="nc">OptM</span> <span class="o">=</span> <span class="nc">RemoveOnePass</span><span class="o">(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">include</span> <span class="nc">SymIntT</span><span class="o">(</span><span class="nn">OptM</span><span class="p">.</span><span class="nc">X</span><span class="o">)(</span><span class="nc">I</span><span class="o">)</span>
<span class="c">(* on surcharge lit et mul *)</span>
<span class="k">include</span> <span class="nn">OptM</span><span class="p">.</span><span class="nc">IDelta</span>
<span class="k">end</span></code></pre>
<p>Ici la transformation triviale est utile car la passe ne touche pas à l'addition. Un petit test qui combine les deux passes :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">Test</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">open</span> <span class="nc">I</span>
<span class="k">let</span> <span class="n">observe</span> <span class="o">=</span> <span class="n">observe</span>
<span class="k">let</span> <span class="o">(</span> <span class="o">+)</span> <span class="o">=</span> <span class="n">add</span>
<span class="k">let</span> <span class="o">(</span> <span class="o">*</span> <span class="o">)</span> <span class="o">=</span> <span class="n">mul</span>
<span class="k">let</span> <span class="n">e</span> <span class="o">=</span> <span class="n">lit</span> <span class="mi">1</span> <span class="o">*</span> <span class="n">lit</span> <span class="mi">2</span> <span class="o">+</span> <span class="n">lit</span> <span class="mi">0</span>
<span class="k">end</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">Test</span><span class="o">(</span><span class="nc">RemoveZeroInt</span><span class="o">(</span><span class="nc">ShowInt</span><span class="o">))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">e</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"1 * 2"</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">Test</span><span class="o">(</span><span class="nc">RemoveOneInt</span><span class="o">(</span><span class="nc">ShowInt</span><span class="o">))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">e</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"2 + 0"</span>
<span class="c">(* nos deux passes commutent *)</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">Test</span><span class="o">(</span><span class="nc">RemoveOneInt</span><span class="o">(</span><span class="nc">RemoveZeroInt</span><span class="o">(</span><span class="nc">ShowInt</span><span class="o">)))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">e</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"2"</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">Test</span><span class="o">(</span><span class="nc">RemoveZeroInt</span><span class="o">(</span><span class="nc">RemoveOneInt</span><span class="o">(</span><span class="nc">ShowInt</span><span class="o">)))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">e</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"2"</span></code></pre>
<h3 id="réutilisation-de-nos-passes-sur-le-langage-étendu">Réutilisation de nos passes sur le langage étendu.</h3>
<p>Un des grands avantages de la méthode <em>tagless-final</em> est de pouvoir réutiliser du code déjà écrit en structurant le programme de façon modulaire. Les optimisations n'échappent pas à la règle. Pour récupérer nos précédentes passes, il faut d'abord définir notre transformation triviale pour le langage étendu.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">SymIntCondT</span> <span class="o">(</span><span class="nc">X</span> <span class="o">:</span> <span class="nc">TRANS</span><span class="o">)</span>
<span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT_COND</span> <span class="k">with</span> <span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">repr</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span> <span class="nn">X</span><span class="p">.</span><span class="n">from</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="c">(* on commence par récupérer la précédente *)</span>
<span class="k">include</span> <span class="nc">SymIntT</span> <span class="o">(</span><span class="nc">X</span><span class="o">)(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">open</span> <span class="nc">X</span>
<span class="c">(* on ajoute les nouvelles constructions du langage *)</span>
<span class="k">let</span> <span class="n">bool_</span> <span class="n">b</span> <span class="o">=</span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">bool_</span> <span class="n">b</span>
<span class="k">let</span> <span class="n">if_</span> <span class="n">b</span> <span class="n">th</span> <span class="n">el</span> <span class="o">=</span>
<span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">if_</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">b</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">bwd</span> <span class="o">@@</span> <span class="n">th</span> <span class="bp">()</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">bwd</span> <span class="o">@@</span> <span class="n">el</span> <span class="bp">()</span><span class="o">)</span>
<span class="k">let</span> <span class="n">eq</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">eq</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">y</span><span class="o">)</span>
<span class="k">let</span> <span class="n">lt</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">lt</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">y</span><span class="o">)</span>
<span class="k">end</span></code></pre>
<p>Et l'on peut alors réutiliser nos passes directement :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">RemoveZeroIntCond</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT_COND</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">module</span> <span class="nc">OptM</span> <span class="o">=</span> <span class="nc">RemoveZeroPass</span><span class="o">(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">include</span> <span class="nc">SymIntCondT</span><span class="o">(</span><span class="nn">OptM</span><span class="p">.</span><span class="nc">X</span><span class="o">)(</span><span class="nc">I</span><span class="o">)</span>
<span class="c">(* on ne surcharge que les constructeurs optimisés *)</span>
<span class="k">include</span> <span class="nn">OptM</span><span class="p">.</span><span class="nc">IDelta</span>
<span class="k">end</span>
<span class="k">module</span> <span class="nc">RemoveOneIntCond</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT_COND</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">module</span> <span class="nc">OptM</span> <span class="o">=</span> <span class="nc">RemoveOnePass</span><span class="o">(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">include</span> <span class="nc">SymIntCondT</span><span class="o">(</span><span class="nn">OptM</span><span class="p">.</span><span class="nc">X</span><span class="o">)(</span><span class="nc">I</span><span class="o">)</span>
<span class="c">(* on ne surcharge que les constructeurs optimisés *)</span>
<span class="k">include</span> <span class="nn">OptM</span><span class="p">.</span><span class="nc">IDelta</span>
<span class="k">end</span></code></pre>
<p>Un petit test pour la route :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">Test</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT_COND</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">open</span> <span class="nc">I</span>
<span class="k">let</span> <span class="n">observe</span> <span class="o">=</span> <span class="n">observe</span>
<span class="k">let</span> <span class="o">(</span> <span class="o">+</span> <span class="o">)</span> <span class="o">=</span> <span class="n">add</span>
<span class="k">let</span> <span class="o">(</span> <span class="o">*</span> <span class="o">)</span> <span class="o">=</span> <span class="n">mul</span>
<span class="k">let</span> <span class="o">(</span> <span class="o">=</span> <span class="o">)</span> <span class="o">=</span> <span class="n">eq</span>
<span class="k">let</span> <span class="n">e</span> <span class="o">=</span>
<span class="n">if_</span> <span class="o">(</span><span class="n">lit</span> <span class="mi">1</span> <span class="o">*</span> <span class="n">lit</span> <span class="mi">2</span> <span class="o">=</span> <span class="n">lit</span> <span class="mi">2</span> <span class="o">+</span> <span class="n">lit</span> <span class="mi">0</span><span class="o">)</span>
<span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">lit</span> <span class="mi">3</span> <span class="o">*</span> <span class="n">lit</span> <span class="mi">1</span><span class="o">)</span>
<span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">lit</span> <span class="mi">4</span> <span class="o">+</span> <span class="n">lit</span> <span class="mi">0</span><span class="o">)</span>
<span class="k">end</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">Test</span><span class="o">(</span><span class="nc">RemoveZeroIntCond</span><span class="o">(</span><span class="nc">ShowIntCond</span><span class="o">))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">e</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"if 1 * 2 = 2 then 3 * 1 else 4"</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">Test</span><span class="o">(</span><span class="nc">RemoveOneIntCond</span><span class="o">(</span><span class="nc">ShowIntCond</span><span class="o">))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">e</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"if 2 = 2 + 0 then 3 else 4 + 0"</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">Test</span><span class="o">(</span><span class="nc">RemoveOneIntCond</span><span class="o">(</span><span class="nc">RemoveZeroIntCond</span><span class="o">(</span><span class="nc">ShowIntCond</span><span class="o">)))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">e</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"if 2 = 2 then 3 else 4"</span></code></pre>
<h2 id="Étendre-le-langage-avec-des-fonctions">Étendre le langage avec des fonctions.</h2>
<p>Notre langage commence à devenir sympa, mais ce serait mieux si on lui rajoutait la possibilité de définir des fonctions. C'est ce que nous ferons dans cette dernière partie, et nous rajouterons une passe de calcul des valeurs <em>statiquement</em> connues.</p>
<h3 id="la-symantique-étendue-et-ses-interprètes">La symantique étendue et ses interprètes.</h3>
<p>Pour étendre la signature du langage et rajouter des fonctions, rien de plus simple :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="k">type</span> <span class="nc">SYM_INT_COND_HO</span> <span class="o">=</span> <span class="k">sig</span>
<span class="k">include</span> <span class="nc">SYM_INT_COND</span>
<span class="k">val</span> <span class="n">lam</span> <span class="o">:</span> <span class="o">(</span><span class="k">'</span><span class="n">a</span> <span class="n">repr</span> <span class="o">-></span> <span class="k">'</span><span class="n">b</span> <span class="n">repr</span><span class="o">)</span> <span class="o">-></span> <span class="o">(</span><span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="k">'</span><span class="n">b</span><span class="o">)</span> <span class="n">repr</span>
<span class="k">val</span> <span class="n">app</span> <span class="o">:</span> <span class="o">(</span><span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="k">'</span><span class="n">b</span><span class="o">)</span> <span class="n">repr</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="n">repr</span> <span class="o">-></span> <span class="k">'</span><span class="n">b</span> <span class="n">repr</span>
<span class="k">end</span></code></pre>
<p>On ajoute un opérateur d'abstraction <code>lam</code> pour créer des fonctions, et un opérateur d'application <code>app</code> pour les utiliser. On étend ensuite nos interprètes en commençant par l'évaluateur.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">EvalIntCondHO</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">include</span> <span class="nc">EvalIntCond</span>
<span class="k">let</span> <span class="n">lam</span> <span class="n">f</span> <span class="o">=</span> <span class="n">f</span>
<span class="k">let</span> <span class="n">app</span> <span class="n">f</span> <span class="n">x</span> <span class="o">=</span> <span class="n">f</span> <span class="n">x</span>
<span class="k">end</span></code></pre>
<p>Pour l'interprète de <em>pretty printing</em>, il va falloir adapter légèrement la représentation interne pour prendre en compte le nombre de paramètres des fonctions.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">ShowIntCondHO</span> <span class="o">=</span> <span class="k">struct</span>
<span class="c">(*</span>
<span class="c"> on ajoute un paramètre entier à nos représentations</span>
<span class="c"> pour prendre en compte le nombre de variables de nos</span>
<span class="c"> fonctions et éviter les colisions de noms.</span>
<span class="c"> *)</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">repr</span> <span class="o">=</span> <span class="kt">int</span> <span class="o">-></span> <span class="kt">int</span> <span class="o">-></span> <span class="kt">string</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">obs</span> <span class="o">=</span> <span class="kt">string</span>
<span class="c">(*</span>
<span class="c"> on surcharge nos fonctions de l'interprète du sous-langage</span>
<span class="c"> avec entiers et booléens que l'on enveloppe pour prendre</span>
<span class="c"> en compte le nouveau paramètre.</span>
<span class="c"> *)</span>
<span class="k">open</span> <span class="nc">ShowIntCond</span>
<span class="k">let</span> <span class="n">lit</span> <span class="n">n</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">c</span> <span class="o">-></span> <span class="n">lit</span> <span class="n">n</span>
<span class="k">let</span> <span class="n">add</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">c</span> <span class="o">-></span> <span class="n">add</span> <span class="o">(</span><span class="n">x</span> <span class="n">c</span><span class="o">)</span> <span class="o">(</span><span class="n">y</span> <span class="n">c</span><span class="o">)</span>
<span class="k">let</span> <span class="n">mul</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">c</span> <span class="o">-></span> <span class="n">mul</span> <span class="o">(</span><span class="n">x</span> <span class="n">c</span><span class="o">)</span> <span class="o">(</span><span class="n">y</span> <span class="n">c</span><span class="o">)</span>
<span class="k">let</span> <span class="n">bool_</span> <span class="n">b</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">c</span> <span class="o">-></span> <span class="n">bool_</span> <span class="n">b</span>
<span class="k">let</span> <span class="n">eq</span> <span class="n">e</span> <span class="n">e'</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">c</span> <span class="o">-></span> <span class="n">eq</span> <span class="o">(</span><span class="n">e</span> <span class="n">c</span><span class="o">)</span> <span class="o">(</span><span class="n">e'</span> <span class="n">c</span><span class="o">)</span>
<span class="k">let</span> <span class="n">lt</span> <span class="n">i</span> <span class="n">j</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">c</span> <span class="o">-></span> <span class="n">lt</span> <span class="o">(</span><span class="n">i</span> <span class="n">c</span><span class="o">)</span> <span class="o">(</span><span class="n">j</span> <span class="n">c</span><span class="o">)</span>
<span class="k">let</span> <span class="n">if_</span> <span class="n">b</span> <span class="n">then_e</span> <span class="n">else_e</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">c</span> <span class="o">-></span>
<span class="n">if_</span> <span class="o">(</span><span class="n">b</span> <span class="n">c</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">then_e</span> <span class="bp">()</span> <span class="n">c</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">else_e</span> <span class="bp">()</span> <span class="n">c</span><span class="o">)</span>
<span class="c">(* quelques fonctions utilitaires *)</span>
<span class="k">let</span> <span class="n">show_lam</span> <span class="n">v</span> <span class="n">body</span> <span class="o">=</span> <span class="s2">"fun "</span> <span class="o">^</span> <span class="n">v</span> <span class="o">^</span> <span class="s2">" -> "</span> <span class="o">^</span> <span class="n">body</span>
<span class="k">let</span> <span class="n">varnames</span> <span class="o">=</span> <span class="s2">"xyztuvw"</span>
<span class="k">let</span> <span class="n">varname</span> <span class="o">=</span> <span class="k">function</span>
<span class="o">|</span> <span class="n">i</span> <span class="k">when</span> <span class="n">i</span> <span class="o"><</span> <span class="nn">String</span><span class="p">.</span><span class="n">length</span> <span class="n">varnames</span> <span class="o">-></span>
<span class="nn">String</span><span class="p">.</span><span class="n">make</span> <span class="mi">1</span> <span class="n">varnames</span><span class="o">.[</span><span class="n">i</span><span class="o">]</span>
<span class="o">|</span> <span class="n">i</span> <span class="o">-></span> <span class="s2">"x"</span> <span class="o">^</span> <span class="n">string_of_int</span> <span class="n">i</span>
<span class="k">let</span> <span class="n">lam</span> <span class="n">f</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">c</span> <span class="n">p</span> <span class="o">-></span>
<span class="k">let</span> <span class="n">v</span> <span class="o">=</span> <span class="n">varname</span> <span class="n">c</span> <span class="k">in</span>
<span class="k">let</span> <span class="n">body</span> <span class="o">=</span> <span class="n">f</span> <span class="o">(</span><span class="k">fun</span> <span class="o">_</span> <span class="o">_-></span> <span class="n">v</span><span class="o">)</span> <span class="o">(</span><span class="n">c</span> <span class="o">+</span> <span class="mi">1</span><span class="o">)</span> <span class="mi">0</span> <span class="k">in</span>
<span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">0</span><span class="o">)</span> <span class="o">@@</span> <span class="n">show_lam</span> <span class="n">v</span> <span class="n">body</span>
<span class="k">let</span> <span class="n">app</span> <span class="n">f</span> <span class="n">x</span> <span class="o">=</span> <span class="k">fun</span> <span class="n">c</span> <span class="n">p</span> <span class="o">-></span>
<span class="n">cparen</span> <span class="o">(</span><span class="n">p</span> <span class="o">></span> <span class="mi">10</span><span class="o">)</span> <span class="o">(</span><span class="n">f</span> <span class="n">c</span> <span class="mi">10</span> <span class="o">^</span> <span class="s2">" "</span> <span class="o">^</span> <span class="n">x</span> <span class="n">c</span> <span class="mi">11</span><span class="o">)</span>
<span class="k">let</span> <span class="n">observe</span> <span class="n">x</span> <span class="o">=</span> <span class="n">x</span> <span class="mi">0</span> <span class="mi">0</span>
<span class="k">end</span></code></pre>
<p>On peut toujours interpréter les précédents exemples avec ces nouveaux modules :</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExIntCond</span><span class="o">(</span><span class="nc">EvalIntCondHO</span><span class="o">)</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex3</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">15</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExIntCond</span><span class="o">(</span><span class="nc">ShowIntCondHO</span><span class="o">)</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex3</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"1 + (2 + 3 * 4)"</span></code></pre>
<p>Mais également des termes du nouveau langage, comme il se doit :</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">ExHO</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT_COND_HO</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">include</span> <span class="nc">ExIntCond</span><span class="o">(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">open</span> <span class="nc">I</span>
<span class="k">let</span> <span class="n">app</span> <span class="o">=</span> <span class="n">app</span>
<span class="k">let</span> <span class="n">lit</span> <span class="o">=</span> <span class="n">lit</span>
<span class="k">let</span> <span class="n">ex7</span> <span class="o">=</span> <span class="n">lam</span> <span class="o">@@</span> <span class="k">fun</span> <span class="n">x</span> <span class="o">-></span>
<span class="o">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">lit</span> <span class="mi">2</span> <span class="o">+</span> <span class="n">lit</span> <span class="mi">3</span> <span class="o">*</span> <span class="n">x</span><span class="o">)</span> <span class="o">*</span> <span class="o">(</span><span class="n">lit</span> <span class="mi">2</span> <span class="o">+</span> <span class="n">x</span><span class="o">)</span>
<span class="k">let</span> <span class="n">ex8</span> <span class="o">=</span> <span class="n">app</span> <span class="n">ex7</span> <span class="o">(</span><span class="n">lit</span> <span class="mi">3</span><span class="o">)</span>
<span class="k">let</span> <span class="n">ex9</span> <span class="n">x</span> <span class="o">=</span> <span class="n">lam</span> <span class="o">@@</span> <span class="k">fun</span> <span class="n">y</span> <span class="o">-></span>
<span class="n">if_</span> <span class="o">(</span><span class="n">y</span> <span class="o"><</span> <span class="n">lit</span> <span class="n">x</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">lit</span> <span class="mi">2</span> <span class="o">*</span> <span class="n">y</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">lit</span> <span class="mi">3</span> <span class="o">*</span> <span class="n">y</span><span class="o">)</span>
<span class="k">end</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExHO</span><span class="o">(</span><span class="nc">EvalIntCondHO</span><span class="o">)</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex7</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">-></span> <span class="kt">int</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExHO</span><span class="o">(</span><span class="nc">EvalIntCondHO</span><span class="o">)</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex7</span><span class="o">)</span> <span class="mi">3</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">70</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExHO</span><span class="o">(</span><span class="nc">EvalIntCondHO</span><span class="o">)</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex8</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">70</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExHO</span><span class="o">(</span><span class="nc">ShowIntCondHO</span><span class="o">)</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex7</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"fun x -> (x + 2 + 3 * x) * (2 + x)"</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExHO</span><span class="o">(</span><span class="nc">ShowIntCondHO</span><span class="o">)</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex8</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"(fun x -> (x + 2 + 3 * x) * (2 + x)) 3"</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExHO</span><span class="o">(</span><span class="nc">StaticHO</span><span class="o">(</span><span class="nc">ShowIntCondHO</span><span class="o">))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="o">(</span><span class="n">ex9</span> <span class="mi">2</span><span class="o">));;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"fun x -> if x < 2 then 2 * x else 3 * x"</span></code></pre>
<h3 id="Évaluation-partielle-et-statique">Évaluation partielle et statique.</h3>
<p>Il ne nous reste plus qu'à réaliser une optimisation qui réduit ce qui est statiquement connu. On commencera par définir notre transformation triviale puis nous passerons à la passe proprement dite.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">SymIntCondHOT</span> <span class="o">(</span><span class="nc">X</span> <span class="o">:</span> <span class="nc">TRANS</span><span class="o">)</span>
<span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT_COND_HO</span> <span class="k">with</span> <span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">repr</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span> <span class="nn">X</span><span class="p">.</span><span class="n">from</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">include</span> <span class="nc">SymIntCondT</span><span class="o">(</span><span class="nc">X</span><span class="o">)(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">open</span> <span class="nc">X</span>
<span class="k">let</span> <span class="n">lam</span> <span class="n">f</span> <span class="o">=</span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">lam</span> <span class="o">@@</span> <span class="k">fun</span> <span class="n">x</span> <span class="o">-></span> <span class="n">bwd</span> <span class="o">(</span><span class="n">f</span> <span class="o">(</span><span class="n">fwd</span> <span class="n">x</span><span class="o">))</span>
<span class="k">let</span> <span class="n">app</span> <span class="n">f</span> <span class="n">x</span> <span class="o">=</span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">app</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">f</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span>
<span class="k">end</span></code></pre>
<p>Pour la passe statique le code est assez simple : on commence par étiquetés nos termes pour savoir s'il sont statiquement connus (<code>Sta</code>), si c'est une fonction (<code>Fun</code>) ou s'ils ne seront connus que dynamiquement (<code>Dyn</code>). Dans le cas des fonctions, on les applique statiquement, si l'on opère avec des valeurs statiques alors on effectue le calcul statiquement, sinon on se rabat sur notre interprète <code>I</code>.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">StaticPass</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT_COND_HO</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">module</span> <span class="nc">X</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">from</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span> <span class="nn">I</span><span class="p">.</span><span class="n">repr</span>
<span class="k">type</span> <span class="k">'</span><span class="n">a</span> <span class="n">term</span> <span class="o">=</span>
<span class="o">|</span> <span class="nc">Dyn</span> <span class="o">:</span> <span class="k">'</span><span class="n">a</span> <span class="n">from</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="n">term</span>
<span class="o">|</span> <span class="nc">Sta</span> <span class="o">:</span> <span class="o">(</span><span class="k">'</span><span class="n">a</span> <span class="o">*</span> <span class="k">'</span><span class="n">a</span> <span class="n">from</span><span class="o">)</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="n">term</span>
<span class="o">|</span> <span class="nc">Fun</span> <span class="o">:</span> <span class="o">(</span><span class="k">'</span><span class="n">a</span> <span class="n">term</span> <span class="o">-></span> <span class="k">'</span><span class="n">b</span> <span class="n">term</span><span class="o">)</span> <span class="o">-></span> <span class="o">(</span><span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="k">'</span><span class="n">b</span><span class="o">)</span> <span class="n">term</span>
<span class="k">let</span> <span class="n">fwd</span> <span class="n">x</span> <span class="o">=</span> <span class="nc">Dyn</span> <span class="n">x</span>
<span class="k">let</span> <span class="k">rec</span> <span class="n">bwd</span> <span class="o">:</span> <span class="k">type</span> <span class="n">a</span><span class="o">.</span> <span class="n">a</span> <span class="n">term</span> <span class="o">-></span> <span class="n">a</span> <span class="n">from</span> <span class="o">=</span> <span class="k">function</span>
<span class="o">|</span> <span class="nc">Dyn</span> <span class="n">x</span> <span class="o">-></span> <span class="n">x</span>
<span class="o">|</span> <span class="nc">Sta</span> <span class="o">(_,</span><span class="n">x</span><span class="o">)</span> <span class="o">-></span> <span class="n">x</span>
<span class="o">|</span> <span class="nc">Fun</span> <span class="n">f</span> <span class="o">-></span> <span class="nn">I</span><span class="p">.</span><span class="n">lam</span> <span class="o">@@</span> <span class="k">fun</span> <span class="n">x</span> <span class="o">-></span> <span class="n">bwd</span> <span class="o">(</span><span class="n">f</span> <span class="o">(</span><span class="n">fwd</span> <span class="n">x</span><span class="o">))</span>
<span class="k">end</span>
<span class="k">open</span> <span class="nc">X</span>
<span class="k">module</span> <span class="nc">IDelta</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">let</span> <span class="n">lit</span> <span class="n">n</span> <span class="o">=</span> <span class="nc">Sta</span> <span class="o">(</span><span class="n">n</span><span class="o">,</span> <span class="nn">I</span><span class="p">.</span><span class="n">lit</span> <span class="n">n</span><span class="o">)</span>
<span class="k">let</span> <span class="n">add</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">match</span> <span class="n">x</span><span class="o">,</span><span class="n">y</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Sta</span> <span class="o">(</span><span class="n">x</span><span class="o">,_)</span> <span class="o">,</span> <span class="nc">Sta</span> <span class="o">(</span><span class="n">y</span><span class="o">,_)</span> <span class="o">-></span> <span class="n">lit</span> <span class="o">(</span><span class="n">x</span> <span class="o">+</span> <span class="n">y</span><span class="o">)</span>
<span class="o">|</span> <span class="o">_</span> <span class="o">-></span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">add</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">y</span><span class="o">)</span>
<span class="k">let</span> <span class="n">mul</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">match</span> <span class="n">x</span><span class="o">,</span><span class="n">y</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Sta</span> <span class="o">(</span><span class="n">x</span><span class="o">,_)</span> <span class="o">,</span> <span class="nc">Sta</span> <span class="o">(</span><span class="n">y</span><span class="o">,_)</span> <span class="o">-></span> <span class="n">lit</span> <span class="o">(</span><span class="n">x</span> <span class="o">*</span> <span class="n">y</span><span class="o">)</span>
<span class="o">|</span> <span class="o">_</span> <span class="o">-></span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">mul</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">y</span><span class="o">)</span>
<span class="k">let</span> <span class="n">bool_</span> <span class="n">b</span> <span class="o">=</span> <span class="nc">Sta</span> <span class="o">(</span><span class="n">b</span><span class="o">,</span> <span class="nn">I</span><span class="p">.</span><span class="n">bool_</span> <span class="n">b</span><span class="o">)</span>
<span class="k">let</span> <span class="n">if_</span> <span class="n">b</span> <span class="n">th</span> <span class="n">el</span> <span class="o">=</span> <span class="k">match</span> <span class="n">b</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Sta</span> <span class="o">(</span><span class="n">b</span><span class="o">,_)</span> <span class="o">-></span> <span class="k">if</span> <span class="n">b</span> <span class="k">then</span> <span class="n">th</span> <span class="bp">()</span> <span class="k">else</span> <span class="n">el</span> <span class="bp">()</span>
<span class="o">|</span> <span class="o">_</span> <span class="o">-></span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">if_</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">b</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">bwd</span> <span class="o">@@</span> <span class="n">th</span><span class="bp">()</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="bp">()</span> <span class="o">-></span> <span class="n">bwd</span> <span class="o">@@</span> <span class="n">el</span><span class="bp">()</span><span class="o">)</span>
<span class="k">let</span> <span class="n">eq</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">match</span> <span class="n">x</span><span class="o">,</span><span class="n">y</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Sta</span> <span class="o">(</span><span class="n">x</span><span class="o">,_)</span> <span class="o">,</span> <span class="nc">Sta</span><span class="o">(</span><span class="n">y</span><span class="o">,_)</span> <span class="o">-></span> <span class="n">bool_</span> <span class="o">(</span><span class="n">x</span> <span class="o">=</span> <span class="n">y</span><span class="o">)</span>
<span class="o">|</span> <span class="o">_</span> <span class="o">-></span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">eq</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">y</span><span class="o">)</span>
<span class="k">let</span> <span class="n">lt</span> <span class="n">x</span> <span class="n">y</span> <span class="o">=</span> <span class="k">match</span> <span class="n">x</span><span class="o">,</span><span class="n">y</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Sta</span> <span class="o">(</span><span class="n">x</span><span class="o">,_)</span> <span class="o">,</span> <span class="nc">Sta</span> <span class="o">(</span><span class="n">y</span><span class="o">,_)</span> <span class="o">-></span> <span class="n">bool_</span> <span class="o">(</span> <span class="n">x</span> <span class="o"><</span> <span class="n">y</span> <span class="o">)</span>
<span class="o">|</span> <span class="o">_</span> <span class="o">-></span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">lt</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">y</span><span class="o">)</span>
<span class="k">let</span> <span class="n">lam</span> <span class="n">f</span> <span class="o">=</span> <span class="nc">Fun</span> <span class="n">f</span>
<span class="k">let</span> <span class="n">app</span> <span class="n">f</span> <span class="n">x</span> <span class="o">=</span> <span class="k">match</span> <span class="n">f</span> <span class="k">with</span>
<span class="o">|</span> <span class="nc">Fun</span> <span class="n">f</span> <span class="o">-></span> <span class="n">f</span> <span class="n">x</span>
<span class="o">|</span> <span class="o">_</span> <span class="o">-></span> <span class="n">fwd</span> <span class="o">@@</span> <span class="nn">I</span><span class="p">.</span><span class="n">app</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">f</span><span class="o">)</span> <span class="o">(</span><span class="n">bwd</span> <span class="n">x</span><span class="o">)</span>
<span class="k">end</span>
<span class="k">end</span></code></pre>
<p>On peut alors définir notre optimiseur et récupérer les précédents.</p>
<pre><code class="ocaml"><span class="k">module</span> <span class="nc">RemoveZeroHO</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT_COND_HO</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">module</span> <span class="nc">OptM</span> <span class="o">=</span> <span class="nc">RemoveZeroPass</span><span class="o">(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">include</span> <span class="nc">SymIntCondHOT</span><span class="o">(</span><span class="nn">OptM</span><span class="p">.</span><span class="nc">X</span><span class="o">)(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">include</span> <span class="nn">OptM</span><span class="p">.</span><span class="nc">IDelta</span>
<span class="k">end</span>
<span class="k">module</span> <span class="nc">RemoveOneHO</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT_COND_HO</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">module</span> <span class="nc">OptM</span> <span class="o">=</span> <span class="nc">RemoveOnePass</span><span class="o">(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">include</span> <span class="nc">SymIntCondHOT</span><span class="o">(</span><span class="nn">OptM</span><span class="p">.</span><span class="nc">X</span><span class="o">)(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">include</span> <span class="nn">OptM</span><span class="p">.</span><span class="nc">IDelta</span>
<span class="k">end</span>
<span class="k">module</span> <span class="nc">StaticHO</span> <span class="o">(</span><span class="nc">I</span> <span class="o">:</span> <span class="nc">SYM_INT_COND_HO</span><span class="o">)</span> <span class="o">=</span> <span class="k">struct</span>
<span class="k">module</span> <span class="nc">OptM</span> <span class="o">=</span> <span class="nc">StaticPass</span><span class="o">(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">include</span> <span class="nc">SymIntCondHOT</span><span class="o">(</span><span class="nn">OptM</span><span class="p">.</span><span class="nc">X</span><span class="o">)(</span><span class="nc">I</span><span class="o">)</span>
<span class="k">include</span> <span class="nn">OptM</span><span class="p">.</span><span class="nc">IDelta</span>
<span class="k">end</span></code></pre>
<p>La passe statique en action :</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExHO</span><span class="o">(</span><span class="nc">ShowIntCondHO</span><span class="o">)</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex8</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"(fun x -> (x + 2 + 3 * x) * (2 + x)) 3"</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExHO</span><span class="o">(</span><span class="nc">StaticHO</span><span class="o">(</span><span class="nc">ShowIntCondHO</span><span class="o">))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="n">ex8</span><span class="o">);;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"70"</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExHO</span><span class="o">(</span><span class="nc">ShowIntCondHO</span><span class="o">)</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="o">(</span><span class="n">ex9</span> <span class="mi">4</span><span class="o">));;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"fun x -> if x < 4 then 2 * x else 3 * x"</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExHO</span><span class="o">(</span><span class="nc">ShowIntCondHO</span><span class="o">)</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="o">@@</span> <span class="n">app</span> <span class="o">(</span><span class="n">ex9</span> <span class="mi">4</span><span class="o">)</span> <span class="o">(</span><span class="n">lit</span> <span class="mi">2</span><span class="o">));;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"(fun x -> if x < 4 then 2 * x else 3 * x) 2"</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExHO</span><span class="o">(</span><span class="nc">StaticHO</span><span class="o">(</span><span class="nc">ShowIntCondHO</span><span class="o">))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="o">@@</span> <span class="n">app</span> <span class="o">(</span><span class="n">ex9</span> <span class="mi">4</span><span class="o">)</span> <span class="o">(</span><span class="n">lit</span> <span class="mi">2</span><span class="o">));;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"4"</span>
<span class="k">let</span> <span class="k">module</span> <span class="nc">M</span> <span class="o">=</span> <span class="nc">ExHO</span><span class="o">(</span><span class="nc">StaticHO</span><span class="o">(</span><span class="nc">ShowIntCondHO</span><span class="o">))</span> <span class="k">in</span>
<span class="nn">M</span><span class="p">.</span><span class="err">(</span><span class="n">observe</span> <span class="o">@@</span> <span class="n">app</span> <span class="o">(</span><span class="n">ex9</span> <span class="mi">1</span><span class="o">)</span> <span class="o">(</span><span class="n">lit</span> <span class="mi">2</span><span class="o">));;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"6"</span></code></pre>
<h2 id="conclusion">Conclusion.</h2>
<p>Le journal n'a présenté que dans les grands traits la méthode dite <em>tagless-final</em> pour plonger un langage dans un langage fonctionnel hôte. Comparée à la méthode plus classique consistant à représenter l'arbre de syntaxe abstrait du langage par un type de données algébriques (généralisé ou non), celle-ci permet d'étendre facilement les langages sans avoir à réécrire de code. De plus, elle garantie la bonne formation (au niveau du typage) des termes de nos langages en <em>réutilisant</em> le système de types du langage hôte : pas besoin d'écrire un <em>type checker</em>. De par sa structure modulaire, le code permet d'écrire des passes d'optimisations qui se concentrent uniquement sur le sous-ensemble du langage à optimiser. Par construction, ces dernières sont assurées de préserver le typage des termes et en « collant » à la sémantique dénotanionnelle du langage il est plus aisé de s'assurer de leur bon fonctionnement.</p>
<p>Les exemples du journal sont surtout des exemples jouets, ils servent essentiellement à illustrer les principes généraux de la méthode <em>tagless-final</em>. Pour un exemple d'application, sans doute plus utile dans la vie courante d'un développeur, on pourra regarder du côté de <a href="http://logic.cs.tsukuba.ac.jp/%7Eken/quel/">quel</a> (sous licence MIT). Il permet de générer des requêtes SQL optimisées avec la garantie du typage statique. Son fonctionnement est présenté dans l'article <a href="http://okmij.org/ftp/meta-programming/quel.pdf">Finally, Safely-Extensible and Efficient Language-Integrated Query</a>.</p>
<p>On pourra également consulter l'exemple du <a href="http://okmij.org/ftp/tagless-final/course/optimizations.html#circuit-tut">langage des circuits logiques</a>. Il se trouve sur la page du <a href="http://okmij.org/ftp/tagless-final/course/optimizations.html">tutoriel</a> sur l'optimisation via la méthode <em>tagless-final</em> de Oleg Kiselyov, tutoriel qui m'a servi de base pour ce journal. On y trouve des exemples de codes en Haskell et OCaml.</p>
<p>Comme référence, il y a enfin l'article originel présentant la méthode : <a href="http://okmij.org/ftp/tagless-final/JFP.pdf">Finally Tagless, Partially Evaluated</a>. Celle-ci y est combinée à MetaOCaml (présenté récemment dans <a href="//linuxfr.org/news/decouvrir-metaocaml-dans-son-navigateur-885a7f75-bc31-4835-9790-b8c969dd6d84">une dépêche</a>) afin d'obtenir un interprète, un compilateur, un évaluateur partiel ou encore différentes transformations ou méthodes d'évaluation (par nom, par valeur…) pour le langage objet.</p><div><a href="https://linuxfr.org/users/kantien/journaux/tagless-final-ou-l-art-de-l-interpretation-modulaire.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/110587/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/users/kantien/journaux/tagless-final-ou-l-art-de-l-interpretation-modulaire#comments">ouvrir dans le navigateur</a>
</p>
kantienhttps://linuxfr.org/nodes/110587/comments.atomtag:linuxfr.org,2005:News/375432016-09-15T20:54:02+02:002016-09-16T14:31:08+02:00Apprendre la programmation fonctionnelle avec le MOOC OCamlLicence CC By‑SA http://creativecommons.org/licenses/by-sa/4.0/deed.fr<div><p>Pour la deuxième année consécutive, l'université Paris Diderot, en partenariat avec la Sorbonne, INRIA, IRILL et OCamlPro, organise un MOOC d'initiation à la programmation fonctionnelle avec le langage OCaml. Les leçons débuteront le 26 septembre 2016 et se termineront le 12 décembre. Les cours seront donnés en anglais mais des sous-titres sont disponibles aussi bien en anglais qu'en français. Il est toutefois possible de s'inscrire jusqu'au 25 novembre pour les retardataires.</p></div><ul><li>lien nᵒ 1 : <a title="https://www.fun-mooc.fr/courses/parisdiderot/56002S02/session02/about" hreflang="en" href="https://linuxfr.org/redirect/98135">Page d'inscription</a></li><li>lien nᵒ 2 : <a title="http://alan.petitepomme.net/cwn/2016.08.02.html#4" hreflang="en" href="https://linuxfr.org/redirect/98136">Annonce du cours sur la liste de diffusion OCaml</a></li><li>lien nᵒ 3 : <a title="https://linuxfr.org/news/ocaml-4-03" hreflang="fr" href="https://linuxfr.org/redirect/98137">Dépêche sur la sortie de la version 4.03 de OCaml</a></li><li>lien nᵒ 4 : <a title="http://www.dicosmo.org/share/Flyer-OCamlMooc-2016.pdf" hreflang="en" href="https://linuxfr.org/redirect/98138">Page de présentation du MOOC</a></li></ul><div><h2 class="sommaire">Sommaire</h2>
<ul class="toc">
<li><a href="#note-pr%C3%A9liminaire-de-lauteur-de-la-d%C3%A9p%C3%AAche">Note préliminaire de l'auteur de la dépêche</a></li>
<li><a href="#la-formation">La formation</a></li>
<li><a href="#le-contenu-des-cours">Le contenu des cours</a></li>
<li>
<a href="#l%C3%A9quipe-p%C3%A9dagogique">L'équipe pédagogique</a><ul>
<li><a href="#roberto-di-cosmo">Roberto Di Cosmo</a></li>
<li><a href="#yann-regis-gianas">Yann Regis-Gianas</a></li>
<li><a href="#ralf-treinen">Ralf Treinen</a></li>
<li><a href="#benjamin-canou">Benjamin Canou</a></li>
<li><a href="#gr%C3%A9goire-henry">Grégoire Henry</a></li>
</ul>
</li>
<li>
<a href="#quelques-exemples-de-code">Quelques exemples de code</a><ul>
<li><a href="#le-traditionnel-hello-world">Le traditionnel "Hello World !"</a></li>
<li><a href="#visitor-pattern-sur-un-arbre-binaire">Visitor pattern sur un arbre binaire</a></li>
<li><a href="#un-adverbe-cest-quoi-au-fait">Un adverbe, c'est quoi au fait ?</a></li>
</ul>
</li>
<li><a href="#conclusion">Conclusion</a></li>
</ul><h2 id="note-préliminaire-de-lauteur-de-la-dépêche">Note préliminaire de l'auteur de la dépêche</h2>
<p>Je ne suis nullement affilié ou lié en quelque façon aux personnes et à l'équipe pédagogique qui sont à l'origine de la formation. Les parties sur la description et le contenu de celle-ci, ainsi que celle sur la présentation de l'équipe, sont mes traductions de matériaux que l'on trouve dans leur courrier d'annonce sur la liste de diffusion ou sur la page d'inscription.</p>
<p>En revanche, les exemples de code en OCaml à la fin de la dépêche sont de moi et relèvent d'un choix personnel pour illustrer le langage. Au cas où ceux-ci seraient jugés confus ou peu pédagogiques, il ne faudrait pas que ces défauts soient considérés comme relevant de l'équipe pédagogique de la formation, mais devrait plutôt être mis au compte de ma seule responsabilité. Au demeurant, je suis conscient de n'être ni fin pédagogue, ni bon didacticien.</p>
<h2 id="la-formation">La formation</h2>
<p>La programmation fonctionnelle attire l'intérêt d'un large spectre de développeurs, car elle permet d'écrire des programmes expressifs, concis et élégants.</p>
<p>La formation « Introduction à la programmation fonctionnelle avec le langage OCaml » introduit progressivement les notions centrales de la programmation fonctionnelle, à travers une série de vidéos pédagogiques complétées par un riche ensemble d'exercices que vous pouvez effectuer entièrement dans votre navigateur… Oui, cela signifie que vous pouvez commencer à apprendre la programmation fonctionnelle sans prise de tête : rien à installer, rien à configurer, l'environnement de programmation est à une portée de clic !</p>
<p>Au cours de la formation, vous découvrirez des mécanismes puissants pour construire et manipuler des structures de données de manière claire et efficace. Et vous verrez comment les fonctions jouent un rôle central, en tant que <em>citoyens de première classe</em> qui peuvent être librement utilisés à chaque endroit où un terme du langage peut apparaître (une fonction peut retourner une fonction, ou prendre une autre fonction parmi ses paramètres).</p>
<p>Les inscriptions sont déjà ouvertes sur la plateforme <em>fun-mooc</em> à l'adresse suivante : <a href="https://www.fun-mooc.fr/courses/parisdiderot/56002S02/session02/about">s'inscrire à la formation « Introduction à la programmation fonctionnelle avec le langage OCaml »</a>. La formation débutera le 26 septembre 2016 et durera six semaines, et la date de clôture des inscriptions est fixée au 25 novembre : vous pouvez prendre le train en marche ! :-)</p>
<p>Le temps de travail attendu est compris entre 2 et 6 heures par semaine — en fonction de votre niveau initial — ce qui comprend le temps passé à visionner les courtes séquences vidéos des leçons, dont la durée est approximativement d'une heure par semaine.</p>
<p>Cela peut sembler un effort significatif, mais à la fin de la formation vous aurez appris de nombreuses choses : le projet final confirmera votre bonne maîtrise de la programmation fonctionnelle et votre capacité à développer des programmes de taille moyenne avec aisance.</p>
<p>Des milliers d'étudiants ont suivi la première session de cette formation qui s'est terminée en janvier 2016, et la majorité d'entre eux en ont été extrêmement satisfaits.</p>
<p>Afin d'introduire la programmation fonctionnelle, nous avons choisi d'utiliser le langage OCaml. OCaml est un langage riche, élégant et efficace qui réconcilie la concision et la flexibilité des langages sans annotations de types (comme Python, par exemple) avec la sécurité des langages fortement et statiquement typés (comme Java, C ou C++ par exemple). Ce qui signifie que si votre programme compile alors vous n'aurez pas d'erreur de typage à l'exécution, sans avoir pour autant à annoter votre code pour cela. Le langage dispose de plus d'une communauté d'utilisateurs dynamique.</p>
<p>Facebook, Microsoft, JaneStreet, Bloomberg font partie des grands noms de l'industrie qui ont adopté OCaml pour développer des applications de pointe. La communauté de la recherche utilise OCaml pour écrire des outils comme l'assistant de preuve <a href="https://coq.inria.fr/">Coq</a>, le convertisseur de programme <a href="http://coccinelle.lip6.fr/">Coccinelle</a>, l'analyseur de code <a href="http://frama-c.com/index.html">Frama-C</a>, ou l'analyseur statique <a href="https://www.absint.com/astree/index.htm">Astree</a>. De nombreuses <em>start-up</em> utilisent OCaml pour décupler leur productivité et la stabilité de leur base de code.</p>
<p>Une fois que vous commencerez à maîtriser la programmation fonctionnelle en OCaml, nous sommes certains que vous ne regarderez plus les autres langages de la même façon.</p>
<p>La formation se déroulera en anglais, mais des sous-titres sont déjà disponibles en anglais et en français. Nous remercions à ce titre les nombreux bénévoles, avec une mention spéciale pour Jean-François Monin qui s'est occupé seul de la version française.</p>
<p>Pour bénéficier pleinement de cette formation il est préférable que vous ayez déjà des connaissances de base en programmation, en particulier vous devriez savoir écrire de simples programmes dans un autre langage. Par exemple, vous devriez connaître des notions comme les variables (ou identifiants), les fonctions (ou procédures, méthodes), les structures conditionnelles, et les boucles.</p>
<h2 id="le-contenu-des-cours">Le contenu des cours</h2>
<p>Les leçons se dérouleront sur six semaines avec une courte introduction en préambule. Chaque semaine abordera un nouveau trait du langage, et elle se conclura par une série d'exercices pour contrôler la bonne assimilation des nouvelles notions introduites. À la fin de celles-ci, chaque étudiant devra réaliser un petit projet afin d'obtenir son certificat de validation.</p>
<ol>
<li>Introduction et vue d'ensemble</li>
<li>Types de base, définitions et fonctions</li>
<li>Structures de données de base</li>
<li>Structures de données plus avancées</li>
<li>Fonctions d'ordre supérieur</li>
<li>Exceptions, entrées/sorties et construction impérative</li>
<li>Modules et abstraction de données</li>
</ol><p>Les vidéos pédagogiques sont diffusées sous licence CC BY-NC-ND et tout le code servant à la formation (environnement de travail, moteur de correction…) sous licence LGPLv2 ou GPLv2 (celui de la première session est disponible à <a href="https://try.ocamlpro.com/fun-demo/tryocaml-fun.tgz">cette adresse</a>)</p>
<h2 id="léquipe-pédagogique">L'équipe pédagogique</h2>
<p>L'équipe pédagogique est constituée de trois enseignants chercheurs de l'université Paris Diderot qui s'occupent des cours en vidéos, et de deux ingénieurs en recherche et développement chez <a href="http://www.ocamlpro.com/">OcamlPro</a> qui se sont occupés des exercices et de l'environnement de développement.</p>
<h3 id="roberto-di-cosmo">Roberto Di Cosmo</h3>
<p>Roberto Di Cosmo est professeur d'informatique à l'Université Paris Diderot, directeur de l'<a href="https://www.irill.org/">IRILL (Initiative de Recherche et Innovation sur le Logiciel Libre)</a>, et actuellement détaché à l'INRIA. Ses thèmes de recherche incluent la programmation fonctionnelle et parallèle, les systèmes de types, la logique, la réécriture et l'analyse statique d'une large collection de logiciels. Dans le milieu du logiciel libre, il est entre autre connu pour être à l'origine du <a href="http://www.mancoosi.org/">projet Mancoosi</a> et du projet <a href="https://www.softwareheritage.org/">Software Heritage</a> présenté dans le journal <a href="//linuxfr.org/users/crashone/journaux/bibliotheque-d-alexandrie-des-logiciels-libres">Bibliothèque d'Alexandrie du logiciel libre</a>.</p>
<h3 id="yann-regis-gianas">Yann Regis-Gianas</h3>
<p>Yann Régis-Gianas enseigne la science informatique à l'Université Paris Diderot. Ses recherches au laboratoire <a href="https://www.irif.univ-paris-diderot.fr/equipes/pps/index">PPS (Preuves, Programmes et Systèmes)</a> se concentrent sur la théorie et la conception des langages. Il a effectué son doctorat dans l'équipe INRIA qui développe OCaml et est maintenant dans l'équipe de développement de l'assistant de preuves Coq.</p>
<h3 id="ralf-treinen">Ralf Treinen</h3>
<p>Ralf Treinen est professeur d'informatique à l'Université Paris Diderot. La résolution par contrainte symbolique, la vérification et l'application des méthodes formelles pour l'assurance qualité des logiciels sont parmi ses thèmes de recherches actuels. Il est également membre de l'<a href="https://www.irill.org/">IRILL</a>.</p>
<h3 id="benjamin-canou">Benjamin Canou</h3>
<p>Benjamin Canou est ingénieur R&D chez OCamlPro. Il a travaillé sur l'environnement des exercices, conçu l'évaluateur automatique, et écrit la plupart des exercices. Il a une solide expérience de l'enseignement d'OCaml à l'université, ainsi que des <a href="http://www.ocamlpro.com/training-ocamlpro/">formations à OCaml pour les professionnels</a>.</p>
<h3 id="grégoire-henry">Grégoire Henry</h3>
<p>Grégoire Henry est ingénieur R&D chez OCamlPro. Il a travaillé sur l'environnement des exercices, en particulier l'éditeur de texte avec coloration syntaxique et indentation automatique, et sur le <em>toplevel</em> (la boucle d'interaction). Il a également de l'expérience dans l'enseignement d'OCaml à l'Université Paris Diderot, et <a href="http://www.ocamlpro.com/training-ocamlpro/">la formation professionnelle pour OCamlPro</a>.</p>
<h2 id="quelques-exemples-de-code">Quelques exemples de code</h2>
<p>Pour terminer cette dépêche, rien de tel que de montrer quelques exemples de code fonctionnel en OCaml. Je montrerai la plupart du temps les résultats suite à l'utilisation de la boucle interactive (REPL).</p>
<h3 id="le-traditionnel-hello-world">Le traditionnel "Hello World !"</h3>
<p>Bon, là on fait dans le classique.</p>
<pre><code class="ocaml"><span class="c">(* pour appeler une fonction on écrit son nom puis</span>
<span class="c"> * ses arguments séparés par des espaces *)</span>
<span class="n">print_endline</span> <span class="s2">"Hello World !"</span><span class="o">;;</span>
<span class="nc">Hello</span> <span class="nc">World</span> <span class="o">!</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">unit</span> <span class="o">=</span> <span class="bp">()</span></code></pre>
<h3 id="visitor-pattern-sur-un-arbre-binaire">Visitor pattern sur un arbre binaire</h3>
<p>Cette fois on aborde une structure de données assez élémentaire : les arbres binaires dont les feuilles sont toutes de type <code>int</code>. Puis on définira une fonction générique de parcours de l'arbre (analogue au <em>visitor pattern</em> de la POO) pour effectuer différentes opérations sur celui-ci.</p>
<pre><code class="ocaml"><span class="c">(* on définit le type de nos arbres binaires :</span>
<span class="c"> * soit on a une feuille avec un int</span>
<span class="c"> * soit on a un nœud avec deux sous arbres *)</span>
<span class="k">type</span> <span class="n">tree</span> <span class="o">=</span>
<span class="o">|</span> <span class="nc">Leaf</span> <span class="k">of</span> <span class="kt">int</span>
<span class="o">|</span> <span class="nc">Node</span> <span class="k">of</span> <span class="n">tree</span> <span class="o">*</span> <span class="n">tree</span>
<span class="c">(* ici on définit une fonction de parcours de l'arbre</span>
<span class="c"> * traditionnellement appelée fold : elle prend deux </span>
<span class="c"> * fonctions f et g comme paramètres et remplace les</span>
<span class="c"> * constructeurs du type par l'application d'une de ces</span>
<span class="c"> * deux fonctions en parcourant récursivement l'arbre</span>
<span class="c"> * de la racine jusqu'aux feuilles *)</span>
<span class="k">let</span> <span class="k">rec</span> <span class="n">fold</span> <span class="n">f</span> <span class="n">g</span> <span class="o">=</span> <span class="k">function</span>
<span class="c">(* si on a une feuille, on applique la fonction f *)</span>
<span class="o">|</span> <span class="nc">Leaf</span> <span class="n">n</span> <span class="o">-></span> <span class="n">f</span> <span class="n">n</span>
<span class="c">(* si on a un nœud, on applique recursivement fold sur</span>
<span class="c"> * chaque sous-arbre, puis la fonction g aux résultats *)</span>
<span class="o">|</span> <span class="nc">Node</span> <span class="o">(</span><span class="n">left</span><span class="o">,</span> <span class="n">right</span><span class="o">)</span> <span class="o">-></span> <span class="n">g</span> <span class="o">(</span><span class="n">fold</span> <span class="n">f</span> <span class="n">g</span> <span class="n">left</span><span class="o">)</span> <span class="o">(</span><span class="n">fold</span> <span class="n">f</span> <span class="n">g</span> <span class="n">right</span><span class="o">)</span>
<span class="c">(* maintenant on va appliquer cette fonction générique</span>
<span class="c"> * de parcours pour obtenir différentes interprétations *)</span>
<span class="c">(* interprétation en tant qu'addition </span>
<span class="c"> * chaque feuille renvoie sa valeur et sur</span>
<span class="c"> * un nœud on additionne les deux sous-arbres*)</span>
<span class="k">let</span> <span class="n">plus</span> <span class="o">=</span> <span class="n">fold</span> <span class="o">(</span><span class="k">fun</span> <span class="n">i</span> <span class="o">-></span> <span class="n">i</span><span class="o">)</span> <span class="o">(</span> <span class="o">+</span> <span class="o">)</span>
<span class="c">(* interprétation en tant que soustraction *)</span>
<span class="k">let</span> <span class="n">moins</span> <span class="o">=</span> <span class="n">fold</span> <span class="o">(</span><span class="k">fun</span> <span class="n">i</span> <span class="o">-></span> <span class="n">i</span><span class="o">)</span> <span class="o">(</span> <span class="o">-</span> <span class="o">)</span>
<span class="c">(* ici on calcule la profondeur de l'arbre </span>
<span class="c"> * une feuille est de profondeur nulle et par définition</span>
<span class="c"> * la profondeur d'un arbre vaut la plus grande des profondeurs</span>
<span class="c"> * de ses sous-arbres augmentée d'une unité *)</span>
<span class="k">let</span> <span class="n">depth</span> <span class="o">=</span> <span class="n">fold</span> <span class="o">(</span><span class="k">fun</span> <span class="n">i</span> <span class="o">-></span> <span class="mi">0</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="n">d</span> <span class="n">d'</span> <span class="o">-></span> <span class="mi">1</span> <span class="o">+</span> <span class="n">max</span> <span class="n">d</span> <span class="n">d'</span><span class="o">)</span>
<span class="c">(* ici on définit différentes fonctions de pretty printing pour nos arbres *)</span>
<span class="k">let</span> <span class="n">show</span> <span class="o">=</span> <span class="n">fold</span> <span class="n">string_of_int</span> <span class="o">(</span><span class="k">fun</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">-></span> <span class="nn">Printf</span><span class="p">.</span><span class="n">sprintf</span> <span class="s2">"(op %s %s)"</span> <span class="n">s</span> <span class="n">s'</span><span class="o">)</span>
<span class="k">let</span> <span class="n">show_p</span> <span class="o">=</span> <span class="n">fold</span> <span class="n">string_of_int</span> <span class="o">(</span><span class="k">fun</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">-></span> <span class="nn">Printf</span><span class="p">.</span><span class="n">sprintf</span> <span class="s2">"(%s + %s)"</span> <span class="n">s</span> <span class="n">s'</span><span class="o">)</span>
<span class="k">let</span> <span class="n">show_m</span> <span class="o">=</span> <span class="n">fold</span> <span class="n">string_of_int</span> <span class="o">(</span><span class="k">fun</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">-></span> <span class="nn">Printf</span><span class="p">.</span><span class="n">sprintf</span> <span class="s2">"(%s - %s)"</span> <span class="n">s</span> <span class="n">s'</span><span class="o">);;</span>
<span class="c">(* le compilateur détermine automatiquement le type de tous</span>
<span class="c"> * les termes bien que l'on n'ait rien précisé *)</span>
<span class="k">type</span> <span class="n">tree</span> <span class="o">=</span> <span class="nc">Leaf</span> <span class="k">of</span> <span class="kt">int</span> <span class="o">|</span> <span class="nc">Node</span> <span class="k">of</span> <span class="n">tree</span> <span class="o">*</span> <span class="n">tree</span>
<span class="k">val</span> <span class="n">fold</span> <span class="o">:</span> <span class="o">(</span><span class="kt">int</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span><span class="o">)</span> <span class="o">-></span> <span class="o">(</span><span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span><span class="o">)</span> <span class="o">-></span> <span class="n">tree</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="k">val</span> <span class="n">plus</span> <span class="o">:</span> <span class="n">tree</span> <span class="o">-></span> <span class="kt">int</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="k">val</span> <span class="n">moins</span> <span class="o">:</span> <span class="n">tree</span> <span class="o">-></span> <span class="kt">int</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="k">val</span> <span class="n">depth</span> <span class="o">:</span> <span class="n">tree</span> <span class="o">-></span> <span class="kt">int</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="k">val</span> <span class="n">show</span> <span class="o">:</span> <span class="n">tree</span> <span class="o">-></span> <span class="kt">string</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="k">val</span> <span class="n">show_p</span> <span class="o">:</span> <span class="n">tree</span> <span class="o">-></span> <span class="kt">string</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="k">val</span> <span class="n">show_m</span> <span class="o">:</span> <span class="n">tree</span> <span class="o">-></span> <span class="kt">string</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="c">(* exemple d'utilisation *)</span>
<span class="c">(* on définit un arbre *)</span>
<span class="k">let</span> <span class="n">x</span> <span class="o">=</span> <span class="nc">Node</span> <span class="o">(</span><span class="nc">Leaf</span> <span class="mi">1</span><span class="o">,</span> <span class="nc">Node</span> <span class="o">(</span><span class="nc">Leaf</span> <span class="mi">2</span><span class="o">,</span> <span class="nc">Leaf</span> <span class="mi">3</span><span class="o">));;</span>
<span class="k">val</span> <span class="n">x</span> <span class="o">:</span> <span class="n">tree</span> <span class="o">=</span> <span class="nc">Node</span> <span class="o">(</span><span class="nc">Leaf</span> <span class="mi">1</span><span class="o">,</span> <span class="nc">Node</span> <span class="o">(</span><span class="nc">Leaf</span> <span class="mi">2</span><span class="o">,</span> <span class="nc">Leaf</span> <span class="mi">3</span><span class="o">))</span>
<span class="c">(* on l'affiche plus joliment *)</span>
<span class="n">show</span> <span class="n">x</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">=</span> <span class="s2">"(op 1 (op 2 3))"</span>
<span class="c">(* on voit l'opérateur op comme une addition *)</span>
<span class="n">show_p</span> <span class="n">x</span><span class="o">,</span> <span class="n">plus</span> <span class="n">x</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">*</span> <span class="kt">int</span> <span class="o">=</span> <span class="o">(</span><span class="s2">"(1 + (2 + 3))"</span><span class="o">,</span> <span class="mi">6</span><span class="o">)</span>
<span class="c">(* la même avec la soustraction *)</span>
<span class="n">show_m</span> <span class="n">x</span><span class="o">,</span> <span class="n">moins</span> <span class="n">x</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">string</span> <span class="o">*</span> <span class="kt">int</span> <span class="o">=</span> <span class="o">(</span><span class="s2">"(1 - (2 - 3))"</span><span class="o">,</span> <span class="mi">2</span><span class="o">)</span>
<span class="c">(* on calcule enfin sa profondeur *)</span>
<span class="n">depth</span> <span class="n">x</span><span class="o">;;</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">=</span> <span class="mi">2</span></code></pre>
<p>Pour mieux se rendre compte de la concision du code, regardons ce que cela donne si l'on ne garde que l'essentiel en retirant les commentaires :</p>
<pre><code class="ocaml"><span class="k">type</span> <span class="n">tree</span> <span class="o">=</span> <span class="nc">Leaf</span> <span class="k">of</span> <span class="kt">int</span> <span class="o">|</span> <span class="nc">Node</span> <span class="k">of</span> <span class="n">tree</span> <span class="o">*</span> <span class="n">tree</span>
<span class="k">let</span> <span class="k">rec</span> <span class="n">fold</span> <span class="n">f</span> <span class="n">g</span> <span class="o">=</span> <span class="k">function</span>
<span class="o">|</span> <span class="nc">Leaf</span> <span class="n">n</span> <span class="o">-></span> <span class="n">f</span> <span class="n">n</span>
<span class="o">|</span> <span class="nc">Node</span> <span class="o">(</span><span class="n">left</span><span class="o">,</span> <span class="n">right</span><span class="o">)</span> <span class="o">-></span> <span class="n">g</span> <span class="o">(</span><span class="n">fold</span> <span class="n">f</span> <span class="n">g</span> <span class="n">left</span><span class="o">)</span> <span class="o">(</span><span class="n">fold</span> <span class="n">f</span> <span class="n">g</span> <span class="n">right</span><span class="o">)</span>
<span class="k">let</span> <span class="n">plus</span> <span class="o">=</span> <span class="n">fold</span> <span class="o">(</span><span class="k">fun</span> <span class="n">i</span> <span class="o">-></span> <span class="n">i</span><span class="o">)</span> <span class="o">(</span> <span class="o">+</span> <span class="o">)</span>
<span class="k">let</span> <span class="n">moins</span> <span class="o">=</span> <span class="n">fold</span> <span class="o">(</span><span class="k">fun</span> <span class="n">i</span> <span class="o">-></span> <span class="n">i</span><span class="o">)</span> <span class="o">(</span> <span class="o">-</span> <span class="o">)</span>
<span class="k">let</span> <span class="n">depth</span> <span class="o">=</span> <span class="n">fold</span> <span class="o">(</span><span class="k">fun</span> <span class="n">i</span> <span class="o">-></span> <span class="mi">0</span><span class="o">)</span> <span class="o">(</span><span class="k">fun</span> <span class="n">d</span> <span class="n">d'</span> <span class="o">-></span> <span class="mi">1</span> <span class="o">+</span> <span class="n">max</span> <span class="n">d</span> <span class="n">d'</span><span class="o">)</span>
<span class="k">let</span> <span class="n">show</span> <span class="o">=</span> <span class="n">fold</span> <span class="n">string_of_int</span> <span class="o">(</span><span class="k">fun</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">-></span> <span class="nn">Printf</span><span class="p">.</span><span class="n">sprintf</span> <span class="s2">"(op %s %s)"</span> <span class="n">s</span> <span class="n">s'</span><span class="o">)</span>
<span class="k">let</span> <span class="n">show_p</span> <span class="o">=</span> <span class="n">fold</span> <span class="n">string_of_int</span> <span class="o">(</span><span class="k">fun</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">-></span> <span class="nn">Printf</span><span class="p">.</span><span class="n">sprintf</span> <span class="s2">"(%s + %s)"</span> <span class="n">s</span> <span class="n">s'</span><span class="o">)</span>
<span class="k">let</span> <span class="n">show_m</span> <span class="o">=</span> <span class="n">fold</span> <span class="n">string_of_int</span> <span class="o">(</span><span class="k">fun</span> <span class="n">s</span> <span class="n">s'</span> <span class="o">-></span> <span class="nn">Printf</span><span class="p">.</span><span class="n">sprintf</span> <span class="s2">"(%s - %s)"</span> <span class="n">s</span> <span class="n">s'</span><span class="o">)</span></code></pre>
<p>Et voilà ! :-)</p>
<h3 id="un-adverbe-cest-quoi-au-fait">Un adverbe, c'est quoi au fait ?</h3>
<p>Sur ce dernier exemple, je vais essayer d'illustrer ce propos : « une fois que vous commencerez à maîtriser la programmation fonctionnelle en OCaml, nous sommes certains que vous ne regarderez plus les autres langages de la même façon »; mais en ne l'illustrant pas vis-à-vis d'un autre langage de programmation, mais par rapport à une langue <a href="https://fr.wiktionary.org/wiki/vernaculaire">vernaculaire</a> : le français. :-)</p>
<p>Ce dernier exemple est un peu plus évolué que les précédents, et s'il ne vous paraît pas clair dès aujourd'hui, cela devrait l'être à l'issue de la formation.</p>
<p>Pour ce faire, je vais partir d'un motif fréquent en programmation impérative : la boucle <code>for</code>, afin d'implémenter un code qui doit effectuer cette tâche : « écrire 5 fois "coin< coin<" » et arriver au code OCaml suivant <code>ecrire (5 |> fois) "coin< coin<"</code>.</p>
<pre><code class="ocaml"><span class="c">(* la solution standard à la mode impératif *)</span>
<span class="k">for</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span> <span class="k">to</span> <span class="mi">5</span> <span class="k">do</span> <span class="n">print_endline</span> <span class="s2">"coin< coin<"</span> <span class="k">done</span><span class="o">;;</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">unit</span> <span class="o">=</span> <span class="bp">()</span></code></pre>
<p>Mais on pourrait vouloir un code plus général au cas où l'on veuille effectuer la boucle plus de 5 fois. Dans ce cas, on crée une fonction qui prend en paramètre un entier qui déterminera le nombre de fois où l'on fait la boucle.</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="n">repete_coin_coin</span> <span class="n">n</span> <span class="o">=</span>
<span class="k">for</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span> <span class="k">to</span> <span class="n">n</span> <span class="k">do</span> <span class="n">print_endline</span> <span class="s2">"coin< coin<"</span> <span class="k">done</span><span class="o">;;</span>
<span class="c">(* le compilateur infère toujours seul le type de la fonction *)</span>
<span class="k">val</span> <span class="n">repete_coin_coin</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">-></span> <span class="kt">unit</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="n">repete_coin_coin</span> <span class="mi">5</span><span class="o">;;</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="o">-</span> <span class="o">:</span> <span class="kt">unit</span> <span class="o">=</span> <span class="bp">()</span></code></pre>
<p>Voilà qui est bien, mais on peut encore essayer de généraliser ce bout de code. Ici l'action à effectuer dans la boucle est constante dans le corps de la fonction, on pourrait en faire un paramètre. La <em>forme</em> générale du corps de la boucle c'est : une fonction (dans notre cas <code>print_endline</code>) appliquée à son paramètre (ici <code>"coin< coin<"</code>). Ce qui donne :</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="n">fois</span> <span class="n">n</span> <span class="n">f</span> <span class="n">x</span> <span class="o">=</span>
<span class="k">for</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span> <span class="k">to</span> <span class="n">n</span> <span class="k">do</span> <span class="n">f</span> <span class="n">x</span> <span class="k">done</span><span class="o">;;</span>
<span class="c">(* inférence du type général de la fonction par le compilateur *)</span>
<span class="k">val</span> <span class="n">fois</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">-></span> <span class="o">(</span><span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="k">'</span><span class="n">b</span><span class="o">)</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="kt">unit</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="n">fois</span> <span class="mi">5</span> <span class="n">print_endline</span> <span class="s2">"coin< coin<"</span><span class="o">;;</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span></code></pre>
<p>Revenons un instant à notre énoncé de départ en français : « écrire 5 fois "coin< coin<" ». Ici ce que l'on doit réitérer 5 fois, c'est « écrire "coin< coin<" ». En grammaire française, un verbe comme « écrire » qui attend un complément pour signifier son action est appelé un <em>verbe transitif</em>. Dans notre code c'est la fonction <code>f</code> qui joue le rôle du verbe, et le compilateur nous dit que son type général est <code>'a -> 'b</code>, autrement dit une fonction qui attend un paramètre de type quelconque <code>'a</code> (son complément) pour retourner un objet d'un type quelconque <code>'b</code> (le produit de l'action). Qu'à cela ne tienne, écrivons tout cela en OCaml !</p>
<pre><code class="ocaml"><span class="c">(* on définit le type général d'un verbe transitif *)</span>
<span class="k">type</span> <span class="o">(</span><span class="k">'</span><span class="n">a</span><span class="o">,</span> <span class="k">'</span><span class="n">b</span><span class="o">)</span> <span class="n">verbe</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="k">'</span><span class="n">b</span>
<span class="c">(* ici je vais rajouter des annotations de types sur les</span>
<span class="c"> * paramètres pour bien montrer l'analogie avec le français *)</span>
<span class="k">let</span> <span class="n">fois</span> <span class="n">n</span> <span class="o">(</span><span class="n">verbe</span><span class="o">:(</span><span class="k">'</span><span class="n">a</span><span class="o">,</span> <span class="k">'</span><span class="n">b</span><span class="o">)</span> <span class="n">verbe</span><span class="o">)</span> <span class="o">(</span><span class="n">cod</span><span class="o">:</span><span class="k">'</span><span class="n">a</span><span class="o">)</span> <span class="o">=</span>
<span class="k">for</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span> <span class="k">to</span> <span class="n">n</span> <span class="k">do</span> <span class="n">verbe</span> <span class="n">cod</span> <span class="k">done</span><span class="o">;;</span>
<span class="k">val</span> <span class="n">fois</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">-></span> <span class="o">(</span><span class="k">'</span><span class="n">a</span><span class="o">,</span> <span class="k">'</span><span class="n">b</span><span class="o">)</span> <span class="n">verbe</span> <span class="o">-></span> <span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="kt">unit</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="c">(* l'usage reste le même qu'avant *)</span>
<span class="n">fois</span> <span class="mi">5</span> <span class="n">print_endline</span> <span class="s2">"coin< coin<"</span><span class="o">;;</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span></code></pre>
<p>Maintenant dans la phrase en français les mots « 5 fois » correspondent à ce que l'on appelle un <em>groupe adverbial</em>. Et si l'on regarde le type général de la fonction <code>fois</code> (que l'on a écrit pour reproduire ce groupe adverbial du français) tel qu'inféré par le compilateur on a : <code>int -> ('a, 'b) verbe -> 'a -> unit</code>. Or si l'on regarde la fin de ce type : <code>'a -> unit</code> on retrouve la forme d'un verbe transitif dont le COD est de type <code>'a</code> et dont le produit de l'action est de type <code>unit</code> (c'est l'équivalent du type <code>void</code> dans des langages comme le C). Ainsi, au fond notre fonction <code>fois</code> prend un entier <code>int</code>, un verbe <code>('a, 'b) verbe</code> et renvoie un autre verbe <code>'a -> unit = ('a, unit) verbe</code>. Autrement dit le groupe adverbial « 5 fois » (ou <code>fois 5</code> en OCaml) prend un verbe et renvoie un verbe (en changeant éventuellement le type du produit de l'action). Essayons d'exprimer cela en OCaml :</p>
<pre><code class="ocaml"><span class="c">(* le type des verbes transitifs *)</span>
<span class="o">(</span><span class="k">'</span><span class="n">a</span><span class="o">,</span> <span class="k">'</span><span class="n">b</span><span class="o">)</span> <span class="n">verbe</span> <span class="o">=</span> <span class="k">'</span><span class="n">a</span> <span class="o">-></span> <span class="k">'</span><span class="n">b</span>
<span class="c">(* celui des adverbes qui peuvent changer le type du résultat de l'action *)</span>
<span class="k">type</span> <span class="o">(</span><span class="k">'</span><span class="n">a</span><span class="o">,</span> <span class="k">'</span><span class="n">b</span><span class="o">,</span> <span class="k">'</span><span class="n">c</span><span class="o">)</span> <span class="n">adverbe</span> <span class="o">=</span> <span class="o">(</span><span class="k">'</span><span class="n">a</span><span class="o">,</span> <span class="k">'</span><span class="n">b</span><span class="o">)</span> <span class="n">verbe</span> <span class="o">-></span> <span class="o">(</span><span class="k">'</span><span class="n">a</span><span class="o">,</span> <span class="k">'</span><span class="n">c</span><span class="o">)</span> <span class="n">verbe</span>
<span class="c">(* on réécrit toujours le même code avec quelques annotations</span>
<span class="c"> * pour mettre en avant le lien avec la grammaire du français *)</span>
<span class="k">let</span> <span class="n">fois</span> <span class="n">n</span><span class="o">:(</span><span class="k">'</span><span class="n">a</span><span class="o">,</span><span class="k">'</span><span class="n">b</span><span class="o">,</span><span class="kt">unit</span><span class="o">)</span> <span class="n">adverbe</span> <span class="o">=</span>
<span class="k">fun</span> <span class="o">(</span><span class="n">verbe</span><span class="o">:(</span><span class="k">'</span><span class="n">a</span><span class="o">,</span> <span class="k">'</span><span class="n">b</span><span class="o">)</span> <span class="n">verbe</span><span class="o">)</span> <span class="o">(</span><span class="n">cod</span><span class="o">:</span><span class="k">'</span><span class="n">a</span><span class="o">)</span> <span class="o">-></span>
<span class="k">for</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span> <span class="k">to</span> <span class="n">n</span> <span class="k">do</span> <span class="n">verbe</span> <span class="n">cod</span> <span class="k">done</span><span class="o">;;</span>
<span class="k">val</span> <span class="n">fois</span> <span class="o">:</span> <span class="kt">int</span> <span class="o">-></span> <span class="o">(</span><span class="k">'</span><span class="n">a</span><span class="o">,</span> <span class="k">'</span><span class="n">b</span><span class="o">,</span> <span class="kt">unit</span><span class="o">)</span> <span class="n">adverbe</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="c">(* et maintenant on définit une fonction écrire qui prendra comme</span>
<span class="c"> * paramètres un adverbe et un texte à afficher sur la sortie standard *)</span>
<span class="k">let</span> <span class="n">ecrire</span> <span class="o">(</span><span class="n">adv</span><span class="o">:(</span><span class="k">'</span><span class="n">a</span><span class="o">,</span><span class="k">'</span><span class="n">b</span><span class="o">,</span><span class="k">'</span><span class="n">c</span><span class="o">)</span> <span class="n">adverbe</span><span class="o">):(</span><span class="k">'</span><span class="kt">string</span><span class="o">,</span> <span class="k">'</span><span class="n">c</span><span class="o">)</span> <span class="n">verbe</span> <span class="o">=</span>
<span class="k">fun</span> <span class="n">texte</span> <span class="o">-></span> <span class="n">adv</span> <span class="n">print_endline</span> <span class="n">texte</span><span class="o">;;</span>
<span class="k">val</span> <span class="n">ecrire</span> <span class="o">:</span> <span class="o">(</span><span class="kt">string</span><span class="o">,</span> <span class="kt">unit</span><span class="o">,</span> <span class="k">'</span><span class="n">c</span><span class="o">)</span> <span class="n">adverbe</span> <span class="o">-></span> <span class="o">(</span><span class="kt">string</span><span class="o">,</span> <span class="k">'</span><span class="n">c</span><span class="o">)</span> <span class="n">verbe</span> <span class="o">=</span> <span class="o"><</span><span class="k">fun</span><span class="o">></span>
<span class="c">(* on retrouve presque la morphologie du français *)</span>
<span class="n">ecrire</span> <span class="o">(</span><span class="n">fois</span> <span class="mi">5</span><span class="o">)</span> <span class="s2">"coin< coin<"</span><span class="o">;;</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="c">(* pour coller encore plus au français on peut utiliser </span>
<span class="c"> * l'opérateur infixe |> qui est l'équivalent du pipe du</span>
<span class="c"> * shell pour placer le paramètre avant la fonction *)</span>
<span class="n">ecrire</span> <span class="o">(</span><span class="mi">5</span> <span class="o">|></span> <span class="n">fois</span><span class="o">)</span> <span class="s2">"coin< coin<"</span><span class="o">;;</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span></code></pre>
<p>Pour ceux qui m'ont suivi jusqu'au bout, afin de montrer toujours la concision du code OCaml, le résumé de tout ce qui précède tient en quelques lignes :</p>
<pre><code class="ocaml"><span class="k">let</span> <span class="n">fois</span> <span class="n">n</span> <span class="n">verbe</span> <span class="n">cod</span> <span class="o">=</span>
<span class="k">for</span> <span class="n">i</span> <span class="o">=</span> <span class="mi">1</span> <span class="k">to</span> <span class="n">n</span> <span class="k">do</span> <span class="n">verbe</span> <span class="n">cod</span> <span class="k">done</span>
<span class="k">let</span> <span class="n">ecrire</span> <span class="n">adv</span> <span class="n">texte</span> <span class="o">=</span> <span class="n">adv</span> <span class="n">print_endline</span> <span class="n">texte</span>
<span class="n">ecrire</span> <span class="o">(</span><span class="mi">5</span> <span class="o">|></span> <span class="n">fois</span><span class="o">)</span> <span class="s2">"coin< coin<"</span><span class="o">;;</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span>
<span class="n">coin</span><span class="o"><</span> <span class="n">coin</span><span class="o"><</span></code></pre>
<p>Qui dit mieux ? \o/</p>
<h2 id="conclusion">Conclusion</h2>
<p>La programmation fonctionnelle a la mauvaise réputation d'être un paradigme de programmation pour « intello ». J'espère avoir réussi à montrer à travers ces exemples qu'il n'en est rien. Au fond, la grammaire d'une langue c'est son <em>système de typage</em>, et quelque que soit la langue l'on ne précise jamais la nature grammaticale (le <em>type</em>) des mots que l'on écrit : pourquoi devrait-il en être autrement en programmation ? En OCaml, c'est pareil grâce au mécanisme d'<em>inférence de types</em> et cela sans sacrifier la sécurité du <em>typage statique</em>.</p>
<p>Lors de la <a href="//linuxfr.org/news/etat-de-l-esperanto-sous-gnu-linux">dépêche sur l'espéranto</a>, les locuteurs de cette langue l'ont défendue en arguant que sa grammaire était plus simple, plus facile à assimiler et que des expériences essayaient de montrer qu'elle facilitait l'apprentissage des autres langues étrangères ainsi que des mathématiques; et tout cela bien que ce soit une langue inventée par une seule personne. Je dirais que cela ne m'étonne guère, et il en est de même avec OCaml : sa grammaire est incomparablement plus simple que n'importe quelle grammaire d'un langage impératif ou orienté objet. Et, à n'en pas douter, lorsque l'on commence à la comprendre, celles des autres langages nous apparaissent sous un autre jour.</p>
<p>Pour ceux qui voudraient tenter l'aventure, que ce soit pour découvrir un nouveau paradigme ou un nouveau langage, il vous suffit de <a href="https://www.fun-mooc.fr/courses/parisdiderot/56002S02/session02/about">vous inscrire</a> : c'est en grande partie libre, gratuit et dispensé par des enseignants de qualité. Et pour ceux qui veulent avoir un avant-goût du contenu et de l'environnement de travail, <a href="https://try.ocamlpro.com/fun-demo/tryocaml_index.html">il existe une démonstration</a> dans laquelle on peut effectuer quelques exercices issus de la première session de la formation.</p></div><div><a href="https://linuxfr.org/news/apprendre-la-programmation-fonctionnelle-avec-le-mooc-ocaml.epub">Télécharger ce contenu au format EPUB</a></div> <p>
<strong>Commentaires :</strong>
<a href="//linuxfr.org/nodes/110032/comments.atom">voir le flux Atom</a>
<a href="https://linuxfr.org/news/apprendre-la-programmation-fonctionnelle-avec-le-mooc-ocaml#comments">ouvrir dans le navigateur</a>
</p>
kantienBenoît Sibaudpalm123jcr83dourouc05https://linuxfr.org/nodes/110032/comments.atom