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
open Lang

module Eval () = struct
  let tbl = Hashtbl.create 512

  let const = function
    | Literal l ->
        Const (Literal l)
    | Var x -> (
      try Hashtbl.find tbl x with Not_found -> Const (Var x) )

  let rec expr = function
    | Const c ->
        const c
    | Bind (x, e, e') ->
        let res = expr e in
        Hashtbl.add tbl x res ; expr e'
    | Abstract (b, p, e) ->
        Abstract (b, p, expr e)
    | Apply (e1, e2) -> (
        let e1' = expr e1 in
        let e2' = expr e2 in
        match e1' with
        | Abstract (_, p, e) -> (
          match e2' with
          | Const (Literal _) ->
              Hashtbl.add tbl p e2' ; expr e
          | Abstract _ ->
              Hashtbl.add tbl p e2' ; expr e
          | _ ->
              Apply (e1', e2') )
        | _ ->
            Apply (e1', e2') )
    | If_then_else (cond, e1, e2) -> (
        let cond = expr cond in
        match cond with
        | Const (Literal (Bool x)) ->
            expr (if x then e1 else e2)
        | _ ->
            let e1' = expr e1 in
            let e2' = expr e2 in
            if e1' = e2' then e1' else If_then_else (cond, e1', e2') )
    | Match (_origin, match_expr, cases) -> (
        let match_expr = expr match_expr in
        let res = ref None in
        List.iter
          (function
            | x, y when Const (Literal x) = match_expr ->
                res := Some y
            | _ ->
                ())
          cases ;
        (* TODO: add a check for exhaustiveness with proper error at some point and make this an internal error *)
        (* TODO: this could be a hashtbl instead of a list ? *)
        match !res with
        | None ->
            failwith "missing match case"
        | Some res ->
            res )
end