Ours & Hippy — le blog [caml]

Il y a quelques temps je m'intéressais un peu à Ocsigen (vraiment très peu), ça aurait été l'occasion de regarder Macaque aussi, mais c'était encore en cours de développement il me semble.

Sinon je ne sais pas non plus résoudre le problème de typage.

Solution de l'exercice : Il faut ajouter un + ? :)

J'aurais été curieux d'en savoir plus sur la conférence : je crois que tu as été pris ? Et si oui, ça s'est bien passé ?

Ca a l'air vraiment sympas ce truc ! Je l'utiliserai si l'occasion se présente :p.

Le nouveau blog est certes assez ressemblant, mais il donne l'impression d'être encore plus "propre", je ne sais pas comment exprimer ça.

Concernant l'article en lui-même, peu de choses que je ne savais pas déjà, à part le problème de typage que je ne sais pas résoudre.

Concernant Macaque comme projet libre, ne t'embête pas trop, fais un peu de pub ici et là, réponds aux mails, mais si ça ne prend pas, c'est pas grave.. Pour en avoir fait, c'est pas une activité passionante la chasse *active* aux contributeurs, et au final ça n'a que peu d'intérêt.

Youhou, j’aime bien réagir des mois en retard moi en ce moment ! Bref, je ne m’intéresse que peu à Macaque (no offense) mais la mention « polymorphisme d’ordre supérieur » m’a alléché donc je suis venu voir de quoi il retournait.

Je m’attendais à avoir une explication quant à la restriction du polymorphisme aux enregistrements et aux objets (comme annoncé dans le premier article donc), au final tu n’en parles pas et même si tu proposes un article il semble a priori ne pas traiter la question¹. Je reste donc un peu sur ma faim.

Par contre je me demandais si ça ne pourrait pas être intéressant de revenir sur ce point puisqu’il semblerait que cette restriction va être (en partie) supprimé dans OCaml 3.12 (avec l’ordre supérieur apparaissant au niveau des fonctions).

À la revoyure.

– Notes –

1. Et en plus tu nous fais peur en ajoutant qu’il est trop technique pour toi.

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 !

Mince. Je viens de lire les articles, et après le premier j’me suis dit : « ok c’est une introduction, dans le prochain il va parler des variants polymorphes », et finalement j’arrive et je vois de l’OO donc j’me dis : « bon tant pis, ça sera dans le 3e ». Et là j’regarde les commentaires et j’vois qu’en fait y’aura fort probablement pas de 3e article, du coup j’suis pas mal déçu. Parce que j’ai découvert les variants polymorphes y’a pas très longtemps et j’aurais bien aimé voir un exemple d’utilisation.

Bref, tout ça pour dire que je trouve le sujet des articles intéressant et que j’aimerais vraiment que tu fasses une suite !

J’ai un peu honte de l’avouer, mais la partie 3 n’est pas encore prête, et je ne suis pas sûre de la publier prochainement : ça demande du travail, je n’ai pas énormément de temps, et je suis plus motivé pour écrire d’autres choses ces temps ci (surtout au vu de l’indifférence tangible¹ qu’on rencontré les deux premières parties, sur un sujet que je trouve pourtant intéressant).

¹ : à l’exception des commentaires pertinent de toi et SpiceGuid; au passage (pour SpiceGuid), j’ai un peu farfouillé du côté du Pattern Calculus mentionné par SpiceGuid (indépendamment, mais je pense que nos sources se recoupent) et c’est effectivement intéressant, même si je me demande s’il ne promet pas un peu trop par rapport à ce qu’il apporte ; je ne suis pas encore assez loin pour m’en assurer.

Je compte évidemment parler des polymorphic variants. D’ailleurs, ces trois billets sont en fait nés d’une réaction au sujet du papier Code Reuse Through Polymorphic Variants de Jacques Garrigue.

J’ai jeté un coup d’oeil à ton lien d’Edward Kwett, mais ça m’a l’air un peu jeune : impossible de trouver quoi que ce soit sur la toile à ce sujet (à part le travail de l’auteur sur le monoidal parsing qui est certainement intéressant, j’avais lu des choses à ce sujet sur Planet Haskell), et ça sent un peu le projet ambitieux qui n’a pas encore porté ses fruits. Ce que je vois dans ce code c’est que les fonctionnalités qu’il met en avant, ensure et unifies, demanderaient un travail de preuve de programmes pour être correctement formalisées au niveau du langage, et que ce serait donc forcément un langage relativement "lourd", ou alors très restrictif.

Si tu t’intéresses à la formulation "informatique" de concepts mathématiques, je te conseille aussi de jeter un oeil aux travaux du projet Focal; il est maintenant plus orienté vers la sécurité, mais ils ont étudié la question de la présentation des arborescences d’objets mathématiques, avec en particulier le très intéressant article Les objets des mathématiques.

Par ailleurs, ceci pourrait t'intéresser (ainsi que tes lecteurs) :
http://comonad.com/Category.ks-old
Un langage sur lequel bosse Edward Kmett. Ce fichier montre comment modéliser les catégories & compagnie dans son langage, il mélange pas mal polymorphisme nominal et structurel c'est plutôt impressionnant.

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

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).

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)

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

Merci.

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.

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 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.

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).

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).

> 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".)

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".

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.

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 ?

(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 !

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.

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.