URL: https://linuxfr.org/users/aluminium95/journaux/edsl-et-f-algebres Title: EDSL et F-algèbres Authors: Aluminium95 Date: 2016年06月12日T22:13:19+02:00 License: CC By-SA Tags: ocaml, rien_compris et wat Score: 16 Bonjour, J'ai récemment eu à concevoir un [DSL](https://en.wikipedia.org/wiki/Domain-specific_language) et en recherchant quelques informations et bonnes pratiques je suis tombé sur ce lien contenant une vidéo youtube [instructive](https://www.reddit.com/r/haskell/comments/3w3zkx/folding_domainspecific_languages/). L'idée est la suivante, pour intégrer un langage dédié dans un langage hôte (qui supporte des types algébriques), il y a au premier abord deux méthodes : 1. Construire un type algébrique correspondant à la _syntaxe_ des expressions du langage, et ensuite construire des fonctions d'évaluation qui produisent les valeurs attendues à partir de cette syntaxe 2. Se passer de cette représentation intermédiaire et représenter directement l'évaluation (la sémantique) du langage On constate facilement que la première méthode est au moins plus puissante que la seconde, mais que la seconde peut être beaucoup plus efficace (pas de construction de structure intermédiaire). Le petit exemple en ocaml (pour changer) : ```ocaml type expr = Add of expr * expr | Val of int ;; let rec evaluate = function | Val x -> x | Add (x,y) -> x + y;; ``` Ici, on sait quelle est la sémantique (c'est l'entier qui est calculé par l'expression) et on peut se passer de la représentation intermédiaire comme suit : ```ocaml type expr = int;; let add x y = x + y;; let lit x = x;; ``` Bien sûr cet exemple est trivial. La question que l'on peut se poser est la suivante : est-ce qu'il est rentable de faire cette élimination ? Les deux méthodes sont-elles équivalentes, quels sont les compromis ? Bien sûr, c'est dans la vidéo :p. On termine par des concepts intéressants comme 1. L'encodage de Böhm-Berarducci des types récursifs 2. La notion de [catamorphisme](https://en.wikipedia.org/wiki/Catamorphism) qui est lié à celui [d'algèbre en général](https://en.wikipedia.org/wiki/F-algebra) et [d'objet initial](https://en.wikipedia.org/wiki/Initial_and_terminal_objects) en théorie des catégories. Un [article en parle pour haskell](https://www.schoolofhaskell.com/user/bartosz/understanding-algebras) et il a des jolies images Cela donne lieu à des codes très génériques et concis, bien que performants. En revanche, cela introduit de la complexité dans les concepts que le code utilise, le rendant plus difficile à lire. Par exemple à la fin de la vidéo on obtient pour les expressions avec des entiers et plus la « signature » `F(A) = Int + A*A`. Ce qui va donner le type de l'algèbre que l'on construit : `(Int -> a, a -> a -> a)`. En effet, une F-algèbres, pour les gens qui n'ont pas le temps de cliquer sur le lien, c'est un foncteur F (comme celui précédent), et une fonction de « calcul » de type `F A -> A`. Or, ici le type `F A` est une union disjointe entre le type `Int` et le type `A*A`, donc la donnée de cette fonction est la donnée d'une paire de fonctions, une de type `Int -> A`, une autre de type `A*A -> A`. ```ocaml type 'a algebre = (int -> 'a) * ('a -> 'a -> 'a);; type 'a expr = 'a algebre -> a;; (* Les constructeurs sont des choses qui renvoient des expressions * donc te type blabla -> expr *) let lit n = (fun (f,g) -> f n);; let sub x y = (fun (f,g) -> g (x (f,g)) (y (f,g));; (* faire une fonction qui évalue une expression en un entier, c'est facile ! * int -> a ... on prend l'identité * a -> a -> a ... on prend (-) *) let eval e = e (fun x -> x, (-));; ``` Attention, ce code ne fait pas ce que l'on veut. En effet, si on construit une autre manière d'évaluer, par exemple avec une paire `(string_of_int, fun a b -> "(" ^ a ^ "+" ^ b ^ ")")` qui permet de construire une chaine, on ne peut pas utiliser les deux évaluations sur une même structure. C'est parce que le système de type identifie le `'a` dans le `'a expr` avec le type de retour du éval utilisé ... En haskell, le monsieur donne un type pour les expressions qui quantifie sur les `'a` : `type expr = forall 'a. 'a algebre -> 'a` et il faudrait faire de même ici. Pour un exemple plus détaillé (qui reprend en fait l'encodage de Böhm-Berarducci) en ocaml, qui lui utilise la quantification sur les types évoquée plus haut [voilà où aller](http://kinokkory.github.io/okmij/boehm-berarducci/BoehmBerarducci.ml.html). Voilà de la lecture pour le lundi qui arrive à grands pas !

AltStyle によって変換されたページ (->オリジナル) /