-
Notifications
You must be signed in to change notification settings - Fork 0
/
lambdacalcul.ml
69 lines (53 loc) · 2.21 KB
/
lambdacalcul.ml
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
(* *)
(* Filename lambdacalcul.ml *)
(* Project Lambda-calcul_eval_AST *)
(* Authors Idriss Moutawakil, Noëlie Sylvain, Barbara Lepage *)
(* *)
(* Lambda-calcul_eval_AST is a λ-calcul interpretor. *)
(* *)
(* ## Types *)
(* *)
type e = (* ## Expression : *)
| Var of string (* Identifier (value) *)
| Const of int (* Constant number *)
| App of (e * e) (* Application of a function *)
| Abs of (string * e) (* Abstraction (function declaration)*)
type env = ((string * e) list) (* ## Environment : *)
(* list of identifier + expression *)
type res = (* ## Result of an eval *)
| Rconst of int (* Constant number *)
| Closure of (string * e * env) (* Closure (identifier, expression *)
(* and current environment) *)
| Error of string (* Error string *)
(* *)
(* ## Environment tools : get and set *)
(* *)
(* val getInEnv : string -> env -> e *)
let rec getInEnv x = function
| [] -> raise (Failure "Undefined identifier")
| (str, exp)::rest -> if str = x then exp else getInEnv x rest
(* val setInEnv : env -> string -> e -> env *)
let setInEnv env str e = (str, e)::env
(* create an empty environement : unit -> env *)
let createEnv () = []
(* *)
(* ## details of the evaluator : deconstruction and applications functions *)
(* *)
(* val dec : res -> e *)
let dec = function
| Closure (str, e, env) -> e
| Rconst r -> Const r
| _ -> raise (Failure "Closure application error")
(* val apply : res -> res -> env -> res *)
let rec apply res1 res2 env = match res1 with
| Closure (str, e, env) -> eval_lambda (setInEnv env str (dec res2)) e
| _ -> Error ("Expression is not a Closure")
(* *)
(* ## Evaluator *)
(* *)
(* val eval_lambda : env -> e -> res *)
and eval_lambda env = function
| Const n -> Rconst n
| Var x -> eval_lambda env (getInEnv x env)
| Abs (str, exp) -> Closure (str, exp, env)
| App (e1, e2) -> apply (eval_lambda env e1) (eval_lambda env e2) env