Générateurs

Ça faisait longtemps que je voulais m'essayer à camlp4, je me suis donné pour exercice d'implémenter des générateurs à la Python -- ce n'est pas nouveau, il me semble avoir déja vu passer ça sur la liste Caml. Le résultat final fait plaisir.

let c = mkseq [-102;1;5;10;33;42;77] ;;
let s = mkseq [1;0;-1] ;;

list_of s*x for x in c if x#even for s in s ;;
= [-42;0;42;-10;0;10;102;0;-102]
list_of x*s for s in s for x in c if x#even ;;
= [-42;-10;102;0;0;0;42;10;-102]
table_of (x,x#even) for x in c ;;
= {77:false;42:true;33:false;10:true;
5:false;1:false;-102:true}

are_all x#even for x in c ;;
= false
is_any s#null for s in s ;;
= true
max_of x#abs for x in c if x#even) ;;
= 102

Comme vous pouvez le voir j'ai orienté objet, car c'est un aspect de Caml que j'essaie d'explorer plus à fond ces temps-ci.

Venons en directement aux conclusions avant de passer aux morceaux de code:

• Camlp4 c'est puissant, mais faut tâtonner pour s'en sortir au début, avec un oeil sur le manuel. De façon générale je suis sympathique à l'idée d'un préprocesseur qui s'assume en tant qu'outil de meta-programmation, plutôt que des capacités vicieuses d'introspection.
• Les générateurs sont facilement réalisés comme un sucre syntaxique à base de fold. Je ne sais pas pourquoi Python utilise des itérateurs/coroutines, yield & co., peut-être parce que l'utilisation de clôtures n'y est pas efficace. En Caml je ne vois aucun problème à mon approche, rien qui justifierait l'ajout du concept de coroutine ici. J'aime à voir ici une réponse à un post de Guido où il annonce la suppression de map, iter, reduce (le fold de Python) et lambda: pour lui reduce est incompréhensible et inutile, pour moi c'est habituel et fondamental. Là où Guido marque un point c'est qu'ayant cette syntaxe naturelle, je ne suis pas sûr de vouloir utiliser map ou iter directement si j'ai le sucre syntaxique à disposition.
• Je suis fan du sous-typage structurel pour les objets dans Caml, mais l'inférence échoue et renvoie des erreurs cryptiques. C'est loin d'être intuitif et j'ai dû sévèrement annoter mes méthodes. C'est encore pire si on essaie d'exprimer le schéma [.. for x in ..] comme une fonction. Il faut alors spécifier le type des objets itérables et générables, et effectuer des coercions explicites vers ces types, ce qui est piégeux à cause de la récursivité du type.
• Les listes et autres types de base en OO, c'est moche, surtout quand on imagine ces valeurs omniprésentes se trimballer leur collection de méthodes triviales tout du long.

Pour vous avouer le fond de ma pensée, j'aimerais trouver/écrire un langage de script (au sens de la facilité d'utilisation, pas de l'absence de compilation) typé statiquement avec sous-typage structurel pour des objets et des variants polymorphes à la OCaml, avec une bonne inférence qui rende le tout utilisable par Monsieur Toulmonde. J'aimerais voir ce genre de concept se répandre. Je me doute que le problème de l'inférence n'est pas simple, j'essaierai d'étudier ça de plus près à l'occasion.

Le code

Mon fichier ML définit quelques classes qui pourraient faire partie de la lib standard OO s'il y en avait une -- même si ça fait peur, disons qu'on imagine. À la fin, j'y utilise la notation que je ne définis que plus bas, mais c'est pour présenter le type des méthodes
fold. La longueur vient uniquement du choix OO, et du fait que je définis plusieurs
itérateurs (seq et table) et générateurs (seq, table, max, conjunction et disjunction mais pas iter).

(* Fichier geno.ml *)

class boolean (b:bool) =
object
method in_val = b
method to_s = if b then "true" else "false"
end

class conjunction (b:bool) =
object
inherit boolean b
method add (x:boolean) = new conjunction (x#in_val && b)
end

class disjunction (b:bool) =
object
inherit boolean b
method add (x:boolean) = new disjunction (x#in_val || b)
end

class integer (i:int) =
object
method in_val = i
method to_s = string_of_int i
method times (y:integer) = new integer (i*y#in_val)
method abs = new integer (abs i)
method null = new boolean (i = 0)
method even = new boolean (i mod 2 = 0)
end

class max (i:int) =
object
inherit integer i
method add (x:integer) = new max (max i x#in_val)
end

class ['a] seq (l:'a list) =
object
method add x : 'a seq = new seq (x::l)
method fold : 'b. 'b -> ('b -> 'a -> 'b) -> 'b =
fun x0 f -> List.fold_left f x0 l
method to_s =
"[" ^ (String.concat ";" (List.map (fun s -> s#to_s) l)) ^ "]"
end

class ['k,'v] table (l:('k*'v)list) =
object
method add x : ('k,'v) table = new table (x::l)
method get k = List.assoc k l
method fold : 'b. 'b -> ('b -> 'k -> 'b) -> 'b =
fun x0 f -> List.fold_left (fun acc (k,v) -> f acc k) x0 l
method to_s =
"{" ^
(String.concat ";" (List.map (fun (k,v) -> k#to_s^":"^v#to_s) l)) ^
"}"
end

let mkseq l = new seq (List.map (fun i -> new integer i) l)
let print x = Printf.printf "%s\n%!" x#to_s
let ( * ) x y = x#times y

let _ =
let c = mkseq [-102;1;5;10;33;42;77] in
let s = mkseq [1;0;-1] in

print (list_of s*x for x in c if x#even for s in s) ;
print (list_of x*s for s in s for x in c if x#even) ;
print (table_of (x,x#even) for x in c) ;

print (are_all x#even for x in c if x#even) ;
print (is_any s#null for s in s) ;
print (max_of x#abs for x in c if x#even)

Maintenant je définis l'extension de syntaxe qui traduit les constructions type générateurs vers la bonne recette à base de fold (ce qu'on parcourt) et add (ce qu'on construit).

(* Fichier pa_geno.ml *)

open Pcaml

let genseq = Grammar.Entry.create gram "genseq" ;;

EXTEND
genseq: [
[ "for" ; x=patt ; "in" ; c=expr ; gs=genseq ->
fun body -> let g = gs body in <:expr<
(fun acc -> $c$#fold acc (fun acc $x$ -> $g$ acc))
>>
| "if" ; test=expr ; gs=genseq ->
fun body -> let g = gs body in <:expr<
(fun acc -> if $test$#in_val then $g$ acc else acc)
>>
| -> fun body -> <:expr< (fun acc -> acc#add $body$) >> ]
] ;
END ;;

EXTEND
expr: BEFORE "expr1" [ "genexpr" NONA
[ "list_of" ; fx=expr ; gs=genseq ->
let g = gs fx in <:expr< $g$ (new seq []) >>
| "table_of" ; fx=expr ; gs=genseq ->
let g = gs fx in <:expr< $g$ (new table []) >>
| "are_all" ; fx=expr ; gs=genseq ->
let g = gs fx in <:expr< $g$ (new conjunction True) >>
| "is_any" ; fx=expr ; gs=genseq ->
let g = gs fx in <:expr< $g$ (new disjunction False) >>
| "max_of" ; fx=expr ; gs=genseq ->
let g = gs fx in <:expr< $g$ (new max 0) >>
]
] ;
END ;;

Enfin pour compiler le tout:

>camlp4o pa_extend.cmo q_MLast.cmo pa_geno.ml -o pa_geno.ppo
ocamlc -I `camlp4 -where` -c -impl pa_geno.ppo
camlp4o ./pa_geno.cmo geno.ml -o geno.ppo
ocamlc -I `camlp4 -where` -c -impl geno.ppo
ocamlc geno.cmo -o gen

Pour afficher la traduction du fichier ML par le préprocesseur, c'est camlp4o ./pa_geno.cmo pr_o.cmo geno.ml et on y lit que max_of x#abs for x in c if x#even devient:

c#fold (new max 0) (* for x in c *)
(fun acc x ->
if x#even#in_val then (* if x#even *)
acc#add x#abs (* x#abs *)
else acc)

Je suis sûr que ça change vos perspectives pour la journée :p