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

module Env = Set.Make (struct
  type t = Lang.expr

  (* TODO: compare them modulo alpha-equivalence *)
  let compare = Stdlib.compare
end)

module Make (M : sig
  module Error : sig
    exception Duplication of Lang.expr

    exception Known_value of Lang.expr

    exception Useless_if of Lang.expr
  end
end) =
struct
  let tbl = Hashtbl.create 512

  let add e =
    (* TODO: compare them modulo alpha-equivalence *)
    match Hashtbl.find_opt tbl e with
    | Some () ->
        raise @@ M.Error.Duplication e
    | None ->
        Hashtbl.add tbl e ()

  let rec expr env e =
    if Env.mem e env then raise @@ M.Error.Known_value e ;
    match e with
    | Const _ ->
        ()
    | Bind (_, e1, e2) ->
        expr env e1 ; expr env e2 ; add e
    | Abstract (_, _, e1) ->
        expr env e1 ; add e
    | Apply (e1, e2) ->
        expr env e1 ; expr env e2 ; add e
    | If_then_else (cond, e1, e2) ->
        ( match (e1, e2) with
        | Const (Literal (Bool true)), Const (Literal (Bool false)) ->
            raise @@ M.Error.Useless_if e
        | _ ->
            () ) ;
        let env' = Env.add cond env in
        expr env cond ; expr env' e1 ; expr env' e2 ; add e
    | Match (_orig, match_expr, cases) ->
        expr env match_expr ;
        let diff = ref false in
        ( try
            List.iter
              (function
                | x, Const (Literal y) -> if x <> y then diff := true | _ -> ())
              cases
          with Exit -> () ) ;
        (* TODO: M.Error.Useless_match *)
        if not !diff then failwith "useless match" ;
        let env' = Env.add match_expr env in
        List.iter (expr env') (List.map snd cases) ;
        add e

  let expr e = expr Env.empty e
end