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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
open Qed.Logic
open Lang
open Lang.F
type 'a occur =
| TOP
| TRUE
| FALSE
| EQ of 'a
let cup eq a y = match a with
| EQ x when eq x y -> a
| _ -> TOP
let cup_true = function
| TRUE -> TRUE
| _ -> TOP
let cup_false = function
| FALSE -> FALSE
| _ -> TOP
let add_term m t = Vars.fold (fun x m -> Vmap.add x TOP m) (F.vars t) m
let add_prop m p = add_term m (F.e_prop p)
let add eq x d m = Vmap.add x (try cup eq (Vmap.find x m) d with Not_found -> EQ d) m
let add_true m x = Vmap.add x (try cup_true (Vmap.find x m) with Not_found -> TRUE) m
let add_false m x = Vmap.add x (try cup_false (Vmap.find x m) with Not_found -> FALSE) m
let add_var = add Var.equal
let add_fun = add Fun.equal
let rec add_pred m p =
match F.p_expr p with
| And ps -> List.fold_left add_pred m ps
| If(e,a,b) -> add_pred (add_pred (add_prop m e) a) b
| Eq(a,b) ->
begin
match F.p_expr a , F.p_expr b with
| Fvar x , Fvar y -> add_var x y (add_var y x m)
| _ -> add_prop m p
end
| Fvar x -> add_true m x
| Not p ->
begin
match F.p_expr p with
| Fvar x -> add_false m x
| _ -> add_prop m p
end
| _ -> add_prop m p
let rec add_type m p =
match F.p_expr p with
| And ps -> List.fold_left add_type m ps
| Fun(f,[e]) ->
begin
match F.e_expr e with
| Fvar x -> add_fun x f m
| _ -> add_prop m p
end
| _ -> add_prop m p
type usage = {
mutable eq_var : var occur Vmap.t ;
mutable eq_fun : lfun occur Vmap.t ;
}
let create () = { eq_var = Vmap.empty ; eq_fun = Vmap.empty }
let as_term m t = m.eq_var <- add_term m.eq_var t
let as_atom m p = m.eq_var <- add_prop m.eq_var p
let as_have m p = m.eq_var <- add_pred m.eq_var p
let as_init m p = m.eq_fun <- add_type m.eq_fun p
let as_type m p = m.eq_fun <- add_type m.eq_fun p
let get x m = try Some (Vmap.find x m) with Not_found -> None
let is_true x m =
try match Vmap.find x m with TRUE -> true | _ -> false
with Not_found -> false
let is_false x m =
try match Vmap.find x m with FALSE -> true | _ -> false
with Not_found -> false
let is_var x m =
try match Vmap.find x m.eq_var with
| EQ y ->
begin
match get x m.eq_fun , get y m.eq_fun with
| None , _ -> true
| Some (EQ f) , Some (EQ g) -> Fun.equal f g
| _ -> false
end
| _ -> false
with Not_found -> false
let rec filter_pred m p =
match F.p_expr p with
| And ps -> F.p_all (filter_pred m) ps
| If(e,a,b) -> p_if e (filter_pred m a) (filter_pred m b)
| Eq(a,b) ->
begin
match F.p_expr a , F.p_expr b with
| Fvar x , Fvar y when is_var x m || is_var y m -> p_true
| _ -> p
end
| Fvar x when is_true x m.eq_var -> p_true
| Not q ->
begin
match F.p_expr q with
| Fvar x when is_false x m.eq_var -> p_true
| _ -> p
end
| _ -> p
let rec filter_type m p =
match F.p_expr p with
| And ps -> F.p_all (filter_type m) ps
| Fun(_,[e]) ->
begin
match F.p_expr e with
| Fvar x when is_var x m -> p_true
| _ -> p
end
| _ -> p