Seance 3 -- Arbres syntaxiques

Programmes = Donnees

En programmation fonctionnelle, les programmes et les donnees sont de meme nature : un programme peut etre represente comme une donnee (un arbre), et manipule par des fonctions. C'est le principe des arbres syntaxiques abstraits (AST).

3.1 Arbres syntaxiques abstraits (AST)

(* Type des expressions arithmetiques *)
type expr =
  | Cst of float
  | Var of string
  | Add of expr * expr
  | Sub of expr * expr
  | Mul of expr * expr
  | Div of expr * expr

(* Exemple : (x + 2) * (x - 1) *)
let exemple =
  Mul (Add (Var "x", Cst 2.0),
       Sub (Var "x", Cst 1.0))

Concept — AST

Un AST represente la structure syntaxique d'une expression sous forme d'arbre. Chaque noeud est un constructeur du type ; chaque feuille est une donnee primitive.

3.2 Interpretation

L'interprete ecute l'AST pour en extraire la valeur semantique.

(* Interpreteur : AST -> valeur *)
let rec eval env = function
  | Cst c       -> c
  | Var x       -> List.assoc x env
  | Add (e1, e2) -> eval env e1 +. eval env e2
  | Sub (e1, e2) -> eval env e1 -. eval env e2
  | Mul (e1, e2) -> eval env e1 *. eval env e2
  | Div (e1, e2) -> eval env e1 /. eval env e2

(* Utilisation *)
let resultat = eval [("x", 3.0)] exemple
(* = (3 + 2) * (3 - 1) = 10.0 *)

3.3 Transformation et fold sur les arbres

Fold sur AST

Le fold sur un AST parcourt recursivement l'arbre et combine les resultats des sous-arbres avec des fonctions specifiques a chaque constructeur. Schema :

Cas de base (feuilles : Cst, Var) : traitement immediat
Cas recursif (noeuds : Add, Mul...) : combiner les resultats des sous-arbres

(* Affichage (pretty-printer) *)
let rec afficher = function
  | Cst c        -> string_of_float c
  | Var x        -> x
  | Add (e1, e2) -> afficher e1 ^ " + " ^ afficher e2
  | Sub (e1, e2) -> afficher e1 ^ " - " ^ afficher e2
  | Mul (e1, e2) -> afficher e1 ^ " * " ^ afficher e2
  | Div (e1, e2) -> afficher e1 ^ " / " ^ afficher e2

(* Comptage du nombre d'operateurs *)
let rec nb_op = function
  | Cst _ | Var _ -> 0
  | Add (e1, e2) | Sub (e1, e2) | Mul (e1, e2) | Div (e1, e2) ->
    1 + nb_op e1 + nb_op e2

3.4 Application — Calcul symbolique

3.4.1 Derivation symbolique

(* Derivation symbolique : d/dx *)
let rec deriv x = function
  | Cst _        -> Cst 0.0
  | Var y        -> if x = y then Cst 1.0 else Cst 0.0
  | Add (e1, e2) -> Add (deriv x e1, deriv x e2)
  | Sub (e1, e2) -> Sub (deriv x e1, deriv x e2)
  | Mul (e1, e2) ->
    Add (Mul (deriv x e1, e2), Mul (e1, deriv x e2))  (* Produit de Leibniz *)
  | Div (e1, e2) ->
    Div (Sub (Mul (deriv x e1, e2), Mul (e1, deriv x e2)),
         Mul (e2, e2))  (* Quotient de Leibniz *)

3.4.2 Simplification symbolique

(* Simplification *)
let rec simplifier = function
  | Add (e, Cst 0.) | Add (Cst 0., e) -> simplifier e
  | Mul (_, Cst 0.) | Mul (Cst 0., _) -> Cst 0.
  | Mul (e, Cst 1.) | Mul (Cst 1., e) -> simplifier e
  | Add (e1, e2) -> Add (simplifier e1, simplifier e2)
  | Mul (e1, e2) -> Mul (simplifier e1, simplifier e2)
  | e -> e

(* Exemple : d/dx(x*x + 2*x) = 1*x + x*1 + 2*1 + x*0 = 2*x + 2 *)

3.5 Application — Mini compilateur / Machine virtuelle

Machine a pile

Un compilateur transforme l'AST en une suite d'instructions pour une machine a pile. L'execution emploie/depile les valeurs.

(* Instructions de la machine a pile *)
type instruction =
  | PUSH of float
  | ADD | SUB | MUL | DIV
  | LOAD of string

(* Compilateur : AST -> liste d'instructions *)
let rec compiler = function
  | Cst c        -> [PUSH c]
  | Var x        -> [LOAD x]
  | Add (e1, e2) -> compiler e1 @ compiler e2 @ [ADD]
  | Sub (e1, e2) -> compiler e1 @ compiler e2 @ [SUB]
  | Mul (e1, e2) -> compiler e1 @ compiler e2 @ [MUL]
  | Div (e1, e2) -> compiler e1 @ compiler e2 @ [DIV]

(* Executeur : simule la machine a pile *)
let executer env instrs =
  let pile = Stack.create () in
  let eval_instr = function
    | PUSH c    -> Stack.push c pile
    | LOAD x    -> Stack.push (List.assoc x env) pile
    | ADD       -> let b = Stack.pop pile in Stack.push (Stack.pop pile +. b) pile
    | SUB       -> let b = Stack.pop pile in Stack.push (Stack.pop pile -. b) pile
    | MUL       -> let b = Stack.pop pile in Stack.push (Stack.pop pile *. b) pile
    | DIV       -> let b = Stack.pop pile in Stack.push (Stack.pop pile /. b) pile
  in
  List.iter eval_instr instrs;
  Stack.pop pile

(* Verif : executer env (compiler e) = eval env e *)

Exercices

Etendez le type expr avec Pow et Neg.
Ameliorez le pretty-printer avec la precedence des operateurs.
Compilez vers un code SSA (Static Single Assignment).
Implementez la propagation de constantes.

Lien avec la Seance 6

En Seance 6, nous prouverons en Coq que le compilateur est correct : exec (compile e) [] = Some (eval e).