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
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)
| 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)
| Type (id, cons, e) ->
let fresh_e = expr scope e in
Type (id, cons, fresh_e)
let expr = expr Env.empty
end