(* 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 e1[xe2], e2 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 (opsubst a1 x e2subst a2 x e2)
Ifz (a1,a2,a3) ->
    Ifz (subst a1 x e2subst a2 x e2subst 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 (yb1b2)
App (a1,a2) ->
    App (subst a1 x e2subst 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"))

This document was translated from LATEX by HEVEA.