Le truc pour comprendre c'est qu'il faut simplement lire le code d'Oleg (le dernier lien) et après tout devient limpide, en admettons une certaine familiarité avec ocaml :P En fait j'apprécie l'effort que son auteur a fait pour rendre ce journal précis et didactique : en effet la terminologie utilisée correspond finalement à la doc officielle d'ocaml. Bref grâce à ce journal j'ai appris la technique de fold au lieu de l'éval récursif, le fameux codage de Böhm-Berarducci, Plus simplement c'est un évaluateur en style CPS. Au lieu d'avoir un évaluateur récusrif eval expr = case expr with App x y -> x (eval y) sur le type "expr" on a un type "expr" qui accepte un évaluateur sur X et retourne X: expr_app f x = fun evaluator -> evaluator.app f (x evaluator).
L'astuce qu'Oleg utilise en fait en ocaml pour faire un type paramètrique sans fixer le paramètre, c'est qu'il faut embaler le type des fonctions constructrices d'expression dans un type du genre méthode polymorphique d'objet. En utilisant type expr = { expr : 'a . 'a algebre -> 'a } on arrive à exprimer "une fonction qui en reçevant une algèbre paramètré sur X s'évalue en X", sans fixer le type X au type de expr, i.e. le forall a. d'Haskell mentionné dans le journal. Si l'auteur du journal a trouvé une autre méthode pour exprimer le "forall" sans passer par cette indirection (donc ni par un objet, ni par un module first class), ça m'intéresse. Les GADT ne me semblent pas adaptés, mais, qui sait ?
Par contre à la question de la performance, ben je crains que cette technique soit moins efficace parce que cela revient à construire un objet plus une closure pour chaque "expr" (closure = function partiellement appliqué).
Btw, on pourrait traduire le code d'Oleg en Lua ou en javascript, j'imagine que ça rendrait ce journal plus compréhensible pour la majorité, ceci dit ça n'est pa la première fois que l'on cause ocaml sur ce site :-) Cela donnerait quelque chose comme ceci (note j'y connais pas grand chose en javascript, ça compile probablement pas tel quel).
[^] # Re: Dans l'art voluptueuse de ne rien comprendre
Posté par benja . En réponse au journal EDSL et F-algèbres. Évalué à 1.
Le truc pour comprendre c'est qu'il faut simplement lire le code d'Oleg (le dernier lien) et après tout devient limpide, en admettons une certaine familiarité avec ocaml :P En fait j'apprécie l'effort que son auteur a fait pour rendre ce journal précis et didactique : en effet la terminologie utilisée correspond finalement à la doc officielle d'ocaml. Bref grâce à ce journal j'ai appris la technique de fold au lieu de l'éval récursif, le fameux codage de Böhm-Berarducci, Plus simplement c'est un évaluateur en style CPS. Au lieu d'avoir un évaluateur récusrif
eval expr = case expr with App x y -> x (eval y)sur le type "expr" on a un type "expr" qui accepte un évaluateur sur X et retourne X:expr_app f x = fun evaluator -> evaluator.app f (x evaluator).L'astuce qu'Oleg utilise en fait en ocaml pour faire un type paramètrique sans fixer le paramètre, c'est qu'il faut embaler le type des fonctions constructrices d'expression dans un type du genre méthode polymorphique d'objet. En utilisant
type expr = { expr : 'a . 'a algebre -> 'a }on arrive à exprimer "une fonction qui en reçevant une algèbre paramètré sur X s'évalue en X", sans fixer le type X au type de expr, i.e. le forall a. d'Haskell mentionné dans le journal. Si l'auteur du journal a trouvé une autre méthode pour exprimer le "forall" sans passer par cette indirection (donc ni par un objet, ni par un module first class), ça m'intéresse. Les GADT ne me semblent pas adaptés, mais, qui sait ?Par contre à la question de la performance, ben je crains que cette technique soit moins efficace parce que cela revient à construire un objet plus une closure pour chaque "expr" (closure = function partiellement appliqué).
Btw, on pourrait traduire le code d'Oleg en Lua ou en javascript, j'imagine que ça rendrait ce journal plus compréhensible pour la majorité, ceci dit ça n'est pa la première fois que l'on cause ocaml sur ce site :-) Cela donnerait quelque chose comme ceci (note j'y connais pas grand chose en javascript, ça compile probablement pas tel quel).