Ours & Hippy — le blog [caml]

Voilà un article qui devrait certainement être posté sur le SDZ pour être lu par d'avantages de Zéros.

davantage* d'ailleurs.

Je l'ai effectivement envisagé, et j'ai prévu d'en discuter avec des validos quand j'aurai à nouveau accès à IRC, mais je pense qu'il n'est pas directement utilisable en l'état. Je pourrais en extraire la partie de vulgarisation sur le POLA et en faire un article, mais ça demande un peu de travail.

C'est normal de se perdre dans tous les types présentés commes naturels ? 

Est-ce que c'est le parser qui dit à Macaque "bon dans cette table y'a une colonne d'entier et une autre de chaîne" ? Apparement y'a des choix de designs 'évidents' après deux mois passés dessus ou en étant un codeur caml mais que je comprend pas. Par exemple je vois pas du tout d'où vient le type pour table qui ne marche pas. Est-il possible d'avoir des exemples ?

La valeur témoin est quand même réellement utile pour traiter la table, non ? Pourquoi souligner le fait que ça soit un témoin dans ce cas ? Je ne devrais peut-être pas faire d'analogie involontaire avec la POO ici.

Par ailleurs, tu aurais pu faire un lien vers [les sources de Macaque](http://forge.ocamlcore.org/frs/?group_id=115), pour les lecteurs curieux. J'y ai jeté un coup d'oeil pour mieux comprendre l'article mais ça ne m'a pas trop aidé, j'avoue. :)

Et oui, une description haut-niveau de Tacaque m'intéresse autant que les points particuliers comme celui-ci même si j'y pine pas grand chose pour l'instant.

Non, le parser s’occupe seulement de la construction d’une structure correspondant à la ligne, à partir du résultat de la requête SQL. Par exemple le SQL renvoie [|"1"; "blabla"|] et le parseur produit le résultat {id = 1; nom = "blabla"} (enfin l’objet correspondant), en utilisant entre autres le parser du champ id, qui convertit "1" en 1 (c’est donc int_of_string, plus du code qui sert à avancer dans le tableau d’entrée). En fait, il joue aussi un rôle au niveau du typage (le résultat du parsage est bien typé, donc détermine le type de la table produite), mais c’est plutôt un rôle secondaire.

La valeur témoin est quand même réellement utile pour traiter la table, non ? Pourquoi souligner le fait que ça soit un témoin dans ce cas ?

Si je parle de valeur témoin, c’est parce que l’utilisateur n’y a jamais accès directement, il ne peut que s’en servir pour "faire faire des choses" à Macaque. C’est un type abstrait, il n’a aucune idée de ce qu’il contient, il sait juste que sans elle il n’a le droit de rien faire.

En général on réserve le nom de "valeur témoin" pour les valeurs qui sont juste des témoins, c’est à dire qui transportent des types (utile pendant la compilation pour propager des informations de typage) mais ne jouent aucun rôle pendant l’exécution (au runtime). Ici mes valeurs ont aussi un rôle au runtime, mais seulement côté Macaque, l’utilisateur ne le sait pas. J’ai mis en avant l’aspect "témoin" pour insister sur l’aspect "dialogue" de l’interaction avec une interface qui cache son implémentation : tu essaies de lui faire faire le plus de choses possibles, elle essaie de te laisser faire le moins de choses possibles, donc vous utilisez des "témoins" pour lui prouver que tu peux bien faire certaines choses en fonction de ce qu’elle t’a accordé dans le passé.

Je ne connais pas l’analogie avec l’OO. Ils ont un concept de témoins ?

Effectivement, les sources de Macaque n’aident sans doute pas énormément. C’est assez gros, il est facile de s’y perdre (je dois décrire une documentation pour les développeurs, mais je ne l’ai pas encore fait), et il y a beaucoup de choses dedans, c’est pas forcément facile d’étudier un point isolé.

Tes questions m’ont en fait motivé pour écrire un autre billet "Singeries", dédié uniquement à la question des témoins. Je vais voir si j’ai le temps de faire ça (et il faut encore que je termine la deuxième partie de celui-ci), mais si je le fais, tu pourras le lire en premier et éventuellement venir relire celui-ci ensuite.

(On m'a dit de commenter, je commente !)
Je tiens à remercier pour l'article : jusqu'ici je ne connaissais le polymorphisme d'ordre supérieur que de nom, et les vagues explications que j'avais lues ne donnaient pas d'exemple *concret* (c'est un problème fréquent malheureusement :/). Là, je vois à quoi ça sert.
Je ne suis cependant pas assez expérimenté pour (comme Cygal) commenter utilement, donc je vais me limiter aux remerciements : Merci !

Merci pour les explications, ça m’a permis de beaucoup mieux comprendre ce qui se passe avec ton histoire de tables, et du coup de comprendre tes explications jusqu’au bout.

Je pense qu’il serait utile de préciser pourquoi on propose à l’utilisateur de créer un parser, surtout qu’apparement y’a une "macro qui le fait tout seul". C’est un point qui m’a vraiment gêné dans la compréhension de ta démarche. C’est dommage parce qu’une fois qu’on voit comment le parser fonctionne (surtout qu’il n’est pas compliqué en soi), le reste est beaucoup plus facile.

Quant à la valeur témoin, je pense que la confusion vient du fait que :

• d’un côté, tu dis que c’est juste utilisé pour dire que j’ai le droit, en tant qu’utilisateur, de toucher à cette table
• de l’autre, tu dis que c’est utilisé au runtime pour faire quelque chose, mais on sait pas trop quoi (mais pourrait-on s’en passer par exemple ?)

Et non y’a pas de témoin en POO à ma connaissance, il suffit de se trimballer l’objet pour pouvoir y toucher (bon y’a la notion d’amis aussi mais on commence à s’éloigner pas mal). En tout cas n’hésite pas de faire un petit post sur les valeurs témoins, je suis sûr que ça peut être intéressant.

Et donc j’ai enfin une vraie question : est-ce que le trick que tu présentes est aussi possible sans aide à partir du langage ?

J’avoue avoir eu également du mal à comprendre de quoi il en retournait au début (bien que tu m’aies déjà parlé de ce problème). À mon avis c’est la resituation au niveau de Macaque qui n’est pas évidente à comprendre : peu de gens connaissent effectivement Macaque ou ont vu des exemples de code utilisant Macaque. Malgré tout, le problème se comprend bien et on reste effectivement sur sa faim (il faut dire, on est pas habitué aux articles courts de ta part), donc ça c’est plutôt sympa.

À mon avis, tu passes quand même un peu trop de temps à décrire des choses macaques-related qui n’ont pas forcément d’intérêt pour le problème que tu présentes ; et à mon avis tu devrais te contenter de présenter le problème et sa solution, et de garder son rapport avec Macaque dans des billets de présentations de Macaque. Le principal intérêt à mon avis est que ça peut faire comme une documentation pour Macaque (bon, en français, sauf si tu te mets subitement à rédiger en anglais) et donc pourra peut être s’exporter facilement hors du blog (de son public habitué en tout cas). Ou alors de faire un billet de présentation de Macaque (pour fixer les idées du lecteur, surtout que pour un vrai projet tu en parles assez peu) et après seulement de poster tes singeries.

Cygal > J’ai rajouté un petit paragraphe expliquant pourquoi on demande à l’utilisateur de fournir le parser. Je ne suis pas sûr que l’explication apporte grand chose en l’état, mais c’est déjà ça.

Et donc j’ai enfin une vraie question : est-ce que le trick que tu présentes est aussi possible sans aide à partir du langage ?

Oui et non : le trick est faisable dans essentiellement tout langage, ce qui change c’est la quantité de typage qu’on peut lui apporter. Quand le système de typage de ton langage ne permet pas de représenter ce genre de choses, ou oblige des manipulations très compliquées pour le faire, bah tu passes outre en faisant un truc un peu plus crade mais un peu plus simple (void * en C, Obj.t en OCaml, Object en Java, etc.). Ça reste intéressant mais tu bénéficies de moins de vérification au moment de la compilation, etc. C’est d’ailleurs un choix que j’ai dû faire pour d’autres parties de Macaque.

L’idée c’est plutôt que ce trick là, pour le faire bien, il faut une fonctionnalité de typage avancée, et pas très souvent utilisée. C’est donc intéressant de le remarquer parce que ça permet de voir un cas d’utilisation concret de cette fonctionnalité.

asmanur > si je voulais uniquement parler du polymorphisme d’ordre supérieur, effectivement ce ne serait pas la voie la plus directe. Mais je n’aime pas trop les présentations minimalistes qui te montrent une fonctionnalité avancée sans aucun lien avec ses utilisation potentielle dans du vrai code de vrais gens (type 'R opérateur = { op : 'x. 'x P -> 'R }). Ici je parle du polymorphisme d’ordre supérieur, mais aussi des liens entre l’interface partiellement abstraite d’un module et ses utilisateurs, et je trouve pas ça moins intéressant, à raconter en tout cas.

Si tu es à la recherche d’un exemple un peu plus épuré de polymorphisme d’ordre supérieur, ça va venir dans le deuxième billet : j’ai rajouté un exemple POO au background "simple".

> avoir une fonction qui renvoie un type différent selon les valeurs qu’on lui donne n’est pas possible dans le système de typage Caml

C'est peut-être un peu hors-sujet, mais, comment fonctionne la fonction Printf.printf alors ? Qu'est-ce qui se cache derrière ('a, out_channel, unit) format -> 'a ?

(Sinon il y a une petite faute : "ce dont" -> "ce sont".)

Désolé pour la latence. J’ai pris un week-end offline et je vous le conseille aussi !

La fonction Printf n’est pas une fonction "utilisateur" de OCaml : on ne peut pas la déclarer en OCaml pur. La chaîne de format est un type prédéfini par le compilateur, qui gère la déduction de types différents selon le format donné. On peut voir ça comme un "hack" permettant de gérer de façon jolie (et sûre, le typage est bien réel) les printf/scanf du C. En gros, le typeur parse la chaîne de format et produit le type quivabien.

Il existe des méthodes pour avoir des printf/scanf "purs", mais ils sont plus lourds à utiliser (on remplace les formats par des combinateurs explicites, c’est nettement plus lourd mais aussi plus typable). C’est ce qu’on appelle le "functional unparsing" et il y a de nombreuses recettes pour faire ça (à base en général de continuations), il me semble que la mode a été lancée par Olivier Danvy (article).

Jérémie Dimino a travaillé sur l’intégration de ce genre de choses dans OCaml, en utilisant une extension syntaxique camlp4 pour regagner la concision perdue, et a obtenu d’assez jolies choses, qui sont plus extensibles que le Printf initial (c’est le module Print de Batteries).

C'est intéressant, surtout via les parallèles avec Macaque, où on se rend compte que certes le typage fort fait du bien, mais faut savoir comment ça marche derrière pour pas se faire avoir.

Les exemples sont un peu tordus par contre. Le compilateur lent n'est pas crédible (surtout vu l'effort demandé par la suite), le programme propriétaire passons, reste la compatibilité de la bibliothèque. Tu connais un cas concret où il y a eu ce besoin ?

Je compte sortir un vrai commentaire quand j'aurai vraiment lu l'article (il me manque un certain nombre de subtilités qui sont apparement tout le but ici).

Je ne connais pas d’exemple concret utilisant explicitement l’extensibilité dans les deux directions à grande échelle, mais je ne me suis pas non plus beaucoup intéressé au code des gros projets logiciels existant dans les langages qui proposent ce genre d’outils. Je connais par contre des cas où cette extensibilité pourrait être profitable pour améliorer le design d’une application déjà existante.

Un exemple générique est le cas où tu veux étendre ton couple (données, opérations) de deux manières différentes, indépendamment. Si tu n’as pas de solution sans modification du code, tu es obligé soit de faire cohabiter les deux extensions au même endroit (en rajoutant de vieux hack du genre "si le booléen machin faut false, on vérifie au runtime l’absence des données de ce genre là"), soit de dupliquer ton couple initial pour le modifier séparément. Les deux solutions donnent lieu à des problèmes de maintenance non négligeables, et la première détruit en plus la sûreté langage de ton application.

Un cas particulier de ce cas général est assez courant, c’est celui où tu veux étendre ton couple (données, opérations), mais en conservant à côté la version initiale, parce que les deux sont pertinents dans ton application. Typiquement, imagine l’auteur d’un compilateur ou interpréteur Lisp, qui a commencé par coder son langage sans supporter les macros. Il a envie de rajouter les macros, qu’il définit comme un "sucre syntaxique" par dessus le langage de base : il y a un langage étendu (langage de base + macros) et une passe de désucrification qui applique toutes les macros et te renvoie le programme entièrement dans le langage de base. Pour faire ça on a besoin d’une représentation, simultanément, du langage de base et du langage étendu. Dans ce cas, tu te retrouves souvent à avoir besoin d’extensibilité dans les deux directions.
Ce qui est fait en pratique, dans les outils que je connais, c’est soit d’abandonner des garanties de typage (en oubliant le langage de base, mais en garantissant que les données que tu fournis aux passes ultérieures, bien que typées "langage avec macro", n’utilisent aucune des constructions macro-esques; inutile de préciser que ça fait des trucs un peu moches), soit de dupliquer les structures de données, ce qui donne lieu à la production d’une certaine quantité de code boilerplate (par exemple tu codes une fonction "map" sur ton langage de base puis ton langage étendu, sans pouvoir réutiliser la première pour coder la deuxième car les types sont disjoints).
Les alternatives plus extensibles (ici on pense très fort aux polymorphic variants de OCaml que je compte mentionner dans un futur billet) permettraient de résoudre le problème, mais viennent aussi avec leurs inconvénients (des messages d’erreurs de typage un peu plus lourds, mais surtout c’est plus sophistiqué donc il faut l’apprendre et ça fait peur) qui font que les programmeurs préfèrent souvent encore the good old way.

Le problème de l'expression vient de ce que le découpage par les fonctions (programmation fonctionnelle) ou par les données (POO) s'excluent l'un et l'autre et qu'on a pas d'abstraction unifiée pour les deux. Ce problème est élégamment résolu par le pattern calculus, où on a droit à des variables libres dans les motifs qui deviennent des citoyens de première classe qui subsument à la fois les données et les fonctions. Un point remarquable c'est que le pattern calculus reste typable statiquement, pour une implantation en OCaml voir le langage Bondi de Barry Jay. En plus de résoudre l'expression problem le pattern calculus offre une approche rigoureuse pour repenser certains autres motifs de conception à la frontière de plusieurs paradigmes (par exemple iterators en POO vs. zippers en fonctionnel).

je suis tout aussi intéressé par des commentaires généraux sur la réaction : avez-vous trouvé ça intéressant ? Trop détaillé ? Pas assez détaillé ?

A mon avis, il serait plus intéressant d’approfondir le sujet plus que de paraphraser le paper comme tu dis, avec éventuellement une courte bibliographie (le problème des papers c’est quand même la taille énorme des bibliographies). Après ça dépend le public que tu vises, si tu préfères faire de la vulgarisation ou de l’approfondissement, en tout cas là j’ai bof envie de lire l’article (en plus c’est du SML, bouh).

Un problème aussi c’est la longueur du coup ; franchement le format de blog de rz0 actuel rend la lecture de l’article quelque peu indigeste (à quand l’export PDF ?). A mon avis, il vaudrait mieux publier ce genre d’articles en plusieurs parties, ne serait-ce que pour tenir le lecteur en haleine et le laisser méditer sur le sujet.

Enfin bon voilà, moi je serais plus pour des articles relevant quelques détails un peu flous ou qui ont des liens avec des trucs intéressant sur le paper (la lecture du paper serait un pré-requis).

Je ne veux pas que la lecture du paper soit un prérequis; mon but ce n’est pas de commenter de manière pertinente un paper d’info, en espérant rajouter quelque chose de valeur derrière l’auteur (ce serait assez vain étant donné que je ne connais essentiellement pas les domaines concernés), mais plutôt de préparer à la lecture en indiquant au lecteur les choses intéressantes, les choses que j’ai trouvées incompréhensible mais dont on peut se passer (afin qu’il ne croit pas qu’il faut tout comprendre), et les choses qu’on peut facilement rater si on ne fait pas assez attention.

Dans l’absolu, c’est plus pensé pour être un teaser qu’un post-commentaire. Pour cet article je me rends compte effectivement que j’ai fait trop de paraphrase, mais c’est parce qu’il est vraiment très elliptique et que ça demande donc un effort assez important de le lire sans préparation. Je n’ai pas abordé toutes les notions de l’article originel, et mon billet ne peut pas remplacer sa lecture, mais je pense que ça le rend accessible à un public plus large.

Par contre tu as totalement raison sur la longueur : c’est trop long. J’ai beaucoup de mal à estimer au départ la longueur que je vais produire, et j’ai tendance à être assez verbeux, donc ça fait vite des trucs très gros. Ça me demande aussi pas mal de travail. Je pense essayer de découper en plusieurs billets ce genre de chose dans le futur (j’ai déjà commencé pour des billets en préparation), et on va réfléchir aux méthodes pour faciliter la navigation (hier déjà rz0 a ajouté des boutons "billet précédent / suivant" pour faciliter la navigation, il est très réactif sur ce genre de choses).

Merci pour l’idée de l’export PDF. Je n’y ai pas pensé, je vais faire des essais, même si je ne suis pas sûr que ce soit pratique au final.

Je me sens stupide quand je lis tes articles :p

Hum, bah côté technique, c’est du Caml, on n’en fait pas à l’Ensimag, et si tu n’en as pas fait avant, forcément, quand on n’a pas l’habitude, c’est pas évident. Par contre, côté théorique, toute la première partie de l’article, jusqu’aux fonctions SR, c’est de la redite de nos cours de TL (S1) et calculabilité (S2).

Enfin, personnellement, je trouve ça pas trop mal comme article de vulgarisation sur un domaine qui ne m’est pas complètement familier (mais demeure connexe à mes intérêts). Si tu as un avis plus précis, Bastien, sur ce qui t’a plu ou pas, ou sur l’organisation générale, n’hésite pas à nous en faire part. :)

J'ai une petite question à propos de "l'enrobage mathématique" présenté en début d'article. Je préviens tout de suite, même si j'ai une licence en maths, j'en ai surtout une en info, et les maths c'est pas spécialement mon trip. Donc désolé si la question est conne.

On prend une fonction de A dans B, sauf qu'elle peut échouer, donc "en fait elle est de A dans (B + {⊥})". Et pour une fonction A -> B -> C, ça veut dire qu'on a une fonction de A dans (B + {⊥}), puis une fonction de (B + {⊥}) dans (C + {⊥}) ? On peut donc "passer la divergence" comme un paramètre ? J'ai un peu du mal avec la notion. Plus tard tu considères que "tout retourne ⊥ si A retourne ⊥", mais est-ce qu'on est passé par la fonction qui va de B dans C ?

J'ai l'impression que ce sont des points qui sont "logiques" pour toi mais il me manque des éléments là.

Alors déjà pour le traitement de (A -> B -> C), c’est curryfié, donc c’est exactement équivalent à (A -> (B -> C)). De là on peut sans doute appliquer la définition et obtenir une réponse claire, mais il faut y penser et tu as raison de demander à expliciter ce point là.

Donc : [A -> B -> C], c’est [A -> (B -> C)] soit A -> ({⊥} + [B -> C]), c’est-à-dire A -> ({⊥} + (B -> {⊥} + C)). En gros, tu commences par donner l’argument de type A, et là soit ça plante (⊥), soit tu as une fonction partielle [B -> C] à laquelle tu donnes l’argument de type B. On considère donc la fonction qui prend du B en paramètre seulement dans le cas où ça n’a pas planté.

L’idée c’est que ⊥ n’est pas une valeur. Ça ne correspond pas à un objet qui existe dans notre langage, puisque c’est au contraire l’absence de résultat. Si une fonction termine, elle renvoie une valeur (qu’on dénote par un élément de B) mais sinon elle ne termine pas (par exemple elle boucle à l’infini). Ça n’a donc pas de sens de "passer ⊥ en paramètre" puisque ce n’est pas une valeur du langage : si tu as essayé de faire un calcul qui n’a pas terminé, mathématiquement tu as "⊥", mais informatiquement tu as un plantage et tu ne peux pas "continuer" : passer des paramètres, etc.

C’est donc là qu’on rejoint la notion de "⊥ donne tout le temps ⊥" : une fois que tu atteins ⊥ mathématiquement, le calcul a "échoué" et il reste comme ça. Si f x échoue, alors g (f x) échoue, quelle que soit g : on commence par vouloir f x et c’est l’échec. C’est une autre définition des langages stricts.

On peut aussi consolider l’enrobage avec plus d’enrobage : il y a une idée implicite dans ce que je dis, que je peux formaliser. Je parle de la sémantique (l’objet mathématique correspondant au code informatique) des fonctions, mais pas de celle des applications de fonction. Si f est une expression qui désigne une fonction, et x qui désigne une valeur, quel est l’objet mathématique [f x] correspondant à l’application de f à z ?

• si [f] = ⊥, c’est ⊥
• sinon c’est [f]([x]) : [f] est une fonction partielle, donc le résultat peut encore être ⊥

Avec cette définition plus précise, tu peux raisonner formellement (et donc précisément), mais je pense pas que ce soit ce dont tu avais besoin. Ça pourrait cependant servir pour d’autres questions.

En fait les deux premiers paragraphes répondent à ma question, c'est cool. Mais j'aime bien aussi la précision du dernier. :)

Merci.

Je sais que ce billet a été poster il y a plusieurs mois mais, je viens de le lire et la moindre des choses que je puisse faire en tant que humble lecteur est de laisser mon impression a l'auteur.

N'étant pas un habituer de la programmation fonctionnel, et ne maitrisant que vaguement la syntaxe ocaml, je dois avouer que ce biller est très difficile a lire.

D'une par, il fait appelle a des notions de mathématique qui ne sont pas nécessairement connues des développeurs habituer des langages impératif (J'ai crus entrevoir de la topologie?).
D'autre part, une bonne part de l'article repose sur des illustration reposant sur le langage ML, ce qui demande un effort particulier pour visualiser "a quoi ca ressemble" dans notre langage impératif de prédilection.

(Je conçoit que l'approche fonctionnel et impérative sont fondamentalement différente, mais il est toutefois possible d'effectuer des analogies et d'obtenir un comportement déterministe dans un langage impératif. Après tout, l'ocaml s'exécute sur des architectures matériel que l'on peut décrire comme des machine de Turing)

Je pense que le motif de conception POO dont tu parles est connu sous le nom de Interpréteur. Le motif Composite n'a aucun intérêt pour un programmeur Caml, c'est juste un type union mal typé (on peut manipuler les enfants d'une feuille).

J'espère que la partie 3 mentionnera les polymorphic variants... C'est l'un des trucs que je trouve splendide en OCaml.

C'est intéressant, merci. Les exemples sont bien choisis, et on comprend l'utilité. Je suis presque triste que ça ait disparu de ton code.

Quel pirate !