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

module Make (M : sig
  module Error : sig
    exception Unbound_variable of string
  end
end) =
struct
  let mk_fresh =
    let seen = Hashtbl.create 512 in
    fun x ->
      match Hashtbl.find_opt seen x with
      | None ->
          Hashtbl.add seen x 0 ; x
      | Some n ->
          Hashtbl.replace seen x (n + 1) ;
          Format.sprintf "_%s%d" x n

  module Env = Map.Make (String)

  let old_names = Hashtbl.create 512

  let add key value scope =
    Hashtbl.add old_names value key ;
    Env.add key value scope

  let const scope = function
    | Literal b ->
        Literal b
    | Var id -> (
      match Env.find id scope with
      | exception Not_found ->
          raise @@ M.Error.Unbound_variable id
      | id' ->
          Var id' )

  let rec expr scope = function
    | Const c ->
        Const (const scope c)
    | Bind (p, e1, e2) ->
        let fresh_p = mk_fresh p in
        let fresh_e1 = expr scope e1 in
        let scope' = add p fresh_p scope in
        let fresh_e2 = expr scope' e2 in
        Bind (fresh_p, fresh_e1, fresh_e2)
    | Abstract (b, p, e) ->
        let fresh_p = mk_fresh p in
        let scope' = add p fresh_p scope in
        let fresh_e = expr scope' e in
        Abstract (b, fresh_p, fresh_e)
    | Apply (e1, e2) ->
        let fresh_e1 = expr scope e1 in
        let fresh_e2 = expr scope e2 in
        Apply (fresh_e1, fresh_e2)
    | If_then_else (cond, e1, e2) ->
        let fresh_cond = expr scope cond in
        let fresh_e1 = expr scope e1 in
        let fresh_e2 = expr scope e2 in
        If_then_else (fresh_cond, fresh_e1, fresh_e2)
    | Match (origin, match_expr, cases) ->
        let fresh_match_expr = expr scope match_expr in
        let fresh_cases = List.map (fun (p, e) -> (p, expr scope e)) cases in
        Match (origin, fresh_match_expr, fresh_cases)

  let expr = expr Env.empty
end