Réécriture d'AST
Types récursifs explicites
J'ai entrepris une grosse passe de réécriture peu après la fin des demies finales. Il s'agissait de remplacer d'une part les AST walkers par des fold sur des types fixés, et d'autre part de supprimer les objets dans les printers.
Le commit qui débute la réécriture présente un nouveau module Fix, avec quelque signatures de modules et foncteurs qui proposent un nouveau type de walker d'urls. L'avantage par rapport au walker qui se trouve dans Ast/astWriter.ml se comprend (difficilement, certes mais se comprend :) ) juste en lisant les types : dans AstWriter.Traverse :
foldmap : (('a -> 'b t -> 'a * 'b t) -> 'a -> 'b t -> 'a * 'b t) -> 'a -> 'b t -> 'a * 'b t
Le premier paramètre de la lambda passée en premier argument permet de controller l'ordre du parcours d'AST ; ensuite on a l'accumulateur et enfin, on renvoie un couple accumulateur et Ast réécrit. Ce foldmap est incapable de changer l'argument de type 'b.
Fix2 est très différent, en voici un extrait simplifié :
type 'a t = ('a t, 'a) tofix
val mapg : ('a -> 'b) -> 'a t -> 'b t
val foldg : ('a -> 'b -> 'b) -> 'a t -> 'b -> 'b
val foldmapg : ('b -> 'a -> 'a * 'c) -> 'b t -> 'a -> 'a * 'c t
val fold2_bottomup : (('a, 'rb) tofix -> 'a) -> ('b -> 'rb) -> 'b t -> 'a
On pourrait écrire un type tofix de la façon suivante :
type ('a, 'b) e =
Value of 'b
| Add of 'a * 'a
Ici, on voit une récursion possible sur le paramètre de type 'b pour contenir un ast d'additions. Voici comment je construis ensuite mes walkers :
module E = Fix2 ( struct
type ('a, 'b) tofix = ('a, 'b) e
module Make (F:Applicative) = struct
open F
let foldmap f g t = match t with
| Value v -> ret (fun v -> Value v) <*> g v
| Add (e1, e2) -> ret (fun e1 e2 -> Add (e1, e2)) <*> f e1 <*> f e2
end
end)
La fonction foldmap permet d'appliquer f sur les parametres de type 'b, et g sur les paramètres de types 'a. En fonction des implémentations de ret et <*>, on peut écrire fold, map et plus si affinités. Ecrire un foldmap est relativement facile, sauf quand on a un mélange entre deux AST : les deux doivent etre écrits avec cette méthode (dans Ast/ast.ml on a des exemples avec ça). Ce foldmap est plus sécurisant que la méthode que j'utilisais précédement car on est obligé de faire du ('a, 'b) tofix -> (\c, 'd) tofix et donc, on ne peut pas oublier un appel aux fonctions f et g. Le typage vérifie donc plus de choses grace à cette écriture.
Un petit exemple pour l'évaluation :
let eval = E.Deep.fold (function
| Value i -> i
| Add (e1, e2) -> e1 + e2)
let () = Printf.printf "val = %d\n"
(eval (E.fix (Add (E.fix (Value 3), (E.fix (Value 4))))))
Fix2 propose les fonctions classiques pour parcourrir les éléments 'a et 'b d'un ('a, 'b) tofix. mapg permet de passer d'un 'a t vers un 'b t, le polymorphisme de l'AST permet des réécritures sympatiques et lorsque l'on renvoie une lambda et non une valeur, on peut controller le parcours de l'AST. C'est peut-etre moins efficace mais ça rend le code beaucoup plus court et évite donc potentiellement les bugs.