Laboratoire 10

Sommaire

Interprèteur minimal

Soit l’interprèteur suivant, supportant les entiers, booléens, et fonctions, y compris les fonction récursives.

type expr =
  | Int of int
  | Bool of bool
  | Minus of expr * expr
  | IsZero of expr
  | If of expr * expr * expr
  | Var of string
  | Let of string * expr * expr
  | Function of string * expr 
  | Call of expr * expr
  | LetRec of string * string * expr * expr

exception TypeError

type value =
  | VInt of int
  | VBool of bool
  | VClosure of string option * string * expr * env
and env = (string * value) list

let lookup (env : env) (var : string) : value = List.assoc var env

let extend (env : env) (var : string) (value : value) : env = (var, value) :: env

let rec eval (env : env) (e : expr) : value =
  match e with
  | Int n -> VInt n
  | Bool b -> VBool b
  | Minus (e1, e2) ->
    begin match eval env e1, eval env e2 with
      | VInt x, VInt y -> VInt (x + y)
      | _ -> raise TypeError
    end
  | IsZero e1 ->
    begin match eval env e1 with
      | VInt 0 -> VBool true
      | VInt _ -> VBool false
      | _ -> raise TypeError
    end
  | If (condition, consequent, alternative) ->
    begin match eval env condition with
    | VBool true -> eval env consequent
    | VBool false -> eval env alternative
    | _ -> raise TypeError
    end
  | Var v -> lookup env v
  | Let (x, e1, e2) ->
    let v = eval env e1 in
    eval (extend env x v) e2
  | LetRec (f, param, body, e2) ->
    let v = VClosure (Some f, param, body, env) in
    eval (extend env f v) e2
  | Function (param, body) ->
    VClosure (None, param, body, env)
  | Call (f, arg) ->
    begin match eval env f with
      | VClosure (name, param, body, def_env) as f ->
        let rec_def_env = match name with
          | None -> def_env
          | Some n -> extend def_env n f in
        let arg_value = eval env arg in
        let new_env = extend rec_def_env param arg_value in
        eval new_env body
      | _ -> raise TypeError
    end

Affichage d’expressions

Définir une fonction value_to_string qui affiche une valeur (type value).

Traçage

Dans cet exercice, nous allons représenter des traces d’évaluation. On cherche à représenter les appels à eval avec ses arguments, ainsi qu’une représentation des appels récursifs sous forme arborescente.

Par exemple, pour l’expression let x = 5 in x + 1, une trace d’évaluation est la suivante :

Représentation sous forme d’AST : l’expression correspond à (Let ("x", Int 5, Plus (Var "x", Int 1)))
Appel initial : eval [] (Let ("x", Int 5, Plus (Var "x", Int 1)))
- appelle eval [] (Int 5)
  - -> renvoie VInt 5
- appelle ensuite eval [("x", VInt 5)] (Plus (Var "x", Int 1))
  - appelle eval [("x", VInt 5)] (Var "x")
    - -> renvoie VInt 5
  - appelle ensuite eval [("x", VInt 5)] (Int 1)
    - -> renvoie VInt 1
  - -> renvoie VInt 6
- -> renvoie VInt 6

Ajouter dans eval, avant le match, un affichage de l’expression en train d’être évaluée.
Confirmer que la trace ci-dessus correspond bien à ce que vous voyez en pratique avec l’interpréteur fourni
Représenter les traces des expressions suivantes, et confirmer avec l’implémentation :

(1 + 2) * (3 + 4)
let x = 1 in let y = x + 2 in y + 3
let x = 1 in let x = 2 in x
((function x -> (function y -> x + y)) 1) 2
let rec f x = f x in f 1 (cela donne lieu à une évaluation infinie, ne représenter qu’un préfixe fini de cette évaluation)
let rec count n = if n = 0 then 1 else count (n - 1) in count 2 (utiliser IsZero pour le test de n = 0)

Plusieurs arguments

Modifier l’interpréteur afin de supporter les fonctions a plusieurs arguments. Écrire un programme d’exemple et confirmer que son exécution se passe comme il faut.

Combinateur Y (bonus)

Exécuter l’interpréteur avec traçage sur le programme suivant :

let y = function f -> (function x -> f (x x)) (function x -> f (x x)) in
let g = function f -> function x -> f x in
(y g) 2

Que se passe-t-il ? Pourquoi observe-t-on ce comportement ?

Exprimer la fonction factorielle sans fonction récursive, avec le combinateur Y comme défini ci-dessus. Pour cela, il est utile d’observer la définition de g ci-dessus, qui correspondrait à la fonction récursive let rec f x = f x : g prend un paramètre supplémentaire, qui est une fonction correspondant à g elle-même : c’est au travers de ce paramètre que g fera l’appel récursif.
Essayer la même chose on OCaml. Quel est le problème ?