(* TP2: Source eval.ml *)

(* Évaluateur, appel par nom [evaln] / par valeur [evalv]*)

(* Ceci est le corrigé qui est à l'intérieur
   de la bibliothèque. Pour compiler à l'extérieur de la bibliothèque,
   ajouter:
open Pcf *)

open S.Ast (* Documentation de S.Ast *)


(* Évaluateur simple :
     dans e₁[x ← e₂], e₂ n'a pas de variable
     libre, ce qui rend la capure impossible *)

exception Error of string

let rec subst e1 x e2 = match e1 with
| Num _ -> e1
| Var y ->
    if x = y then e2 else e1
| Op (op,a1,a2) ->
    Op (op, subst a1 x e2, subst a2 x e2)
| Ifz (a1,a2,a3) ->
    Ifz (subst a1 x e2, subst a2 x e2, subst a3 x e2)
| Let (y,a1,a2) ->
    let b1 = subst a1 x e2
    and b2 = if x=y then a2 else subst a2 x e2 in
    Let (y, b1, b2)
| App (a1,a2) ->
    App (subst a1 x e2, subst a2 x e2)
| Fun (y,a1) ->
    if x = y then e1 else Fun (y,subst a1 x e2)
| Fix (y,a1) ->
    if x=y then e1 else Fix (y,subst a1 x e2)

(*****************)
(* Appel par nom *)
(*****************)

let rec evaln e = match e with
(* Ce sont les valeurs *)
| Num _|Fun (_,_) -> e
(* Par hypothèse les termes sont clos *)
| Var _ -> raise (Error "Variable libre")
(* Noter la fonction auxiliaire evaln_num (partage de code) *)
| Op (op,e1,e2) ->
    let n1 = evaln_num e1
    and n2 = evaln_num e2 in
    Num (Op.to_fun op n1 n2)
(* Noter l'emploi de « if » dans l'argument de evaln ci-dessous *)
| Ifz (e1,e2,e3) ->
    evaln (if evaln_num e1 = 0 then e2 else e3)
(* Pas grand chose à dire : juste substituer *)
| Let (x,ex,e) -> evaln (subst e x ex)
(* Évaluer à gauche d'abord *)
| App (e1,e2)  ->
    let x,ex = evaln_fun e1 in
    evaln (subst ex x e2)
| Fix (x,ex) -> evaln (subst ex x e)

and evaln_num e = match evaln e with
| Num i -> i
| _     -> raise (Error ("Num expected"))

and evaln_fun e = match evaln e with
| Fun (x,ex) -> x,ex
| _ ->  raise (Error ("Fun (x,ex) expected"))


(********************)
(* Appel par valeur *)
(********************)

let rec evalv e = match e with
| Num _|Fun (_,_) -> e
| Var _ -> raise (Error "Variable libre")
| Op (op,e1,e2) ->
    let n1 = evalv_num e1
    and n2 = evalv_num e2 in
    Num (Op.to_fun op n1 n2)
| Ifz (e1,e2,e3) ->
    evalv (if evalv_num e1 = 0 then e2 else e3)
(* Différent de l'appel  par nom :
   l'argument ex est évalué avant substitution *)
| Let (x,ex,e) -> evalv (subst e x (evalv ex))
| App (e1,e2)  ->
    let x,e = evalv_fun e1 in
    evalv (subst e x (evalv e2))
(* Ici pas de changement : (evalv e) bouclerait certainement *)
| Fix (x,ex) -> evalv (subst ex x e)

and evalv_num e = match evalv e with
| Num i -> i
| _     -> raise (Error ("Num expected"))

and evalv_fun e = match evalv e with
| Fun (x,ex) -> x,ex
| _ ->  raise (Error ("Fun (x,ex) expected"))