Common — library colibrilib.summarize — module Export

The functor seen by OCaml. Extraction makes a functor of a scope that begins with its parameters (F, FI), and such a scope cannot be used from another module, so this Export is also the core: it holds only fold and mk_partly_defensive.

35
module Export
36
use bool.Bool
37
use int.Int
38
use array.Array
39
scope List
40
use export list.List
41
use export list.Length
42
use export list.NthNoOpt
43
type
t
'a = list 'a
44
end
45
46
scope Make
47
48
clone F {… begin (* cloned colibrilib.summarize.F *) type
Make.F.t
predicate
Make.F.(<)
t t predicate
Make.F.(<=)
t t axiom
Make.F.total
axiom
Make.F.transitive
val
Make.F.lt
t t : bool end
}
with axiom total, axiom transitive
49
50
scope FI
51
type
intervals
= List.t ( t, t)
52
53
predicate
ordered1
(ord:intervals) =
54
(forall i, j. Int.(0 <= i < j < List.length ord) ->
55
let (_,b) = List.nth i ord in
56
let (a,_) = List.nth j ord in
57
b < a)
58
59
predicate
ordered2
(ord:intervals) =
60
(forall i. Int.(0 <= i < List.length ord) ->
61
let (a,b) = List.nth i ord in
62
a <= b)
63
64
65
predicate
ordered
(ord:intervals) =
66
ordered1 ord /\ ordered2 ord
67
Valid (27ms) (colibri2)
68
lemma
G1
: forall i:int. forall x:'a. forall l:List.t 'a.
69
Int.(0 <= i < List.length l) ->
70
List.nth (i+1) (List.Cons x l) = List.nth i l
71
Valid (46ms) (cvc5)
72
let lemma
gg1
(x:(t,t)) (ord:intervals)
73
requires { ordered2 (List.Cons x ord) }
74
ensures { ordered2 ord } =
75
let lemma f (i:int)
76
requires { Int.(0 <= i < List.length ord) }
77
ensures { let (a,b) = List.nth i ord in
78
a <= b }
79
= ()
80
in
81
()
82
83
Valid (64ms) (cvc5)
84
let lemma
gg2
(x:(t,t)) (ord:intervals)
85
requires { ordered1 (List.Cons x ord) }
86
ensures { ordered1 ord } =
87
let lemma f (i j:int)
88
requires { Int.(0 <= i < j < List.length ord) }
89
ensures { let (_,b) = List.nth i ord in
90
let (a,_) = List.nth j ord in
91
b < a }
92
= ()
93
in
94
()
95
96
type
u
= {
97
u
: intervals ;
98
nan
: bool;
99
}
100
invariant { nan = true \/ u <> List.Nil }
101
invariant { ordered u } Valid (24ms) (colibri2)
102
by { nan = true; u = List.Nil }
103
104
predicate
mem
(x:t) (l:List.t ( t, t)) = exists i.
105
Int.(0 <= i < List.length l) /\
106
let (a,b) = List.nth i l in
107
a <= x <= b
108
Valid (28ms) (colibri2)
109
let ghost function
index
(x:t) (l:List.t ( t, t)) : int
110
requires { mem x l }
111
ensures { Int.(0 <= result < List.length l) }
112
ensures { let (a,b) = List.nth result l in
113
a <= x <= b } =
114
any int ensures {
115
Int.(0 <= result < List.length l) /\
116
let (a,b) = List.nth result l in
117
a <= x <= b }
118
119
end
120
Valid (35ms) (colibri2)
121
type
t
'a = {
122
is_top
: 'a -> bool;
123
nan
: 'a;
124
steps
: array F.t;
125
values
: array 'a;
126
join
: 'a -> 'a -> 'a;
127
ghost
inc
: 'a -> 'a -> bool;
128
} invariant { steps.length + 1 = values.length }
129
invariant { forall i j. Int.(0 <= i < j < steps.length) ->
130
F.(steps[i] < steps[j]) }
131
invariant { forall x y:'a. inc x (join x y) }
132
invariant { forall x y:'a. inc y (join x y) }
133
invariant { forall x:'a. inc x x }
134
invariant { forall x y z:'a. inc x y -> inc y z -> inc x z }
135
invariant { forall x y:'a. is_top y -> inc x y }
136
by (let x = any 'a ensures { result = result } in
137
let f = any F.t ensures { result = result } in
138
{ is_top = (fun _ -> true); nan = x; steps = Array.make 0 f;
139
values = Array.make 1 x; join = (fun x _ -> x); inc = (fun _ _ -> true) })
140
Valid (44ms) (colibri2)
141
let ghost function
find
(x: t 'a) (f:F.t) : int =
142
ensures { Int.(0 <= result-1 < Array.length x.steps) -> F.(x.steps[result-1] < f )}
143
ensures { Int.(0 <= result < Array.length x.steps) -> F.(f <= x.steps[result] )}
144
ensures { Int.(0 <= result < Array.length x.steps + 1) }
145
let rec aux i : int
146
variant { Array.length x.steps - i }
147
requires { Int.(0 <= i <= Array.length x.steps) }
148
requires { Int.(1 <= i -> F.(x.steps[i-1] < f)) }
149
ensures { Int.(0 <= result-1 < Array.length x.steps) -> F.(x.steps[result-1] < f )}
150
ensures { Int.(0 <= result < Array.length x.steps) -> F.(f <= x.steps[result] )}
151
ensures { Int.(0 <= result < Array.length x.steps + 1) }
152
=
153
if Int.(Array.length x.steps <= i) then i
154
else if F.(<=) f x.steps[i] then i
155
else aux (i+1)
156
in
157
aux 0
158
159
function
get_value
(x: t 'a) (f:F.t) : 'a = x.values[find x f]
160
Valid (169ms) (colibri2 57) (cvc5 3) (split_vc) (depth 1)
161
let
fold
(t:t 'a) (l:FI.u) : 'a
162
ensures { l.FI.nan -> t.inc t.nan result }
163
ensures { forall x. FI.mem x l.FI.u -> t.inc (get_value t x) result }
164
=

r is steps.(i–1) and s is steps.(i)

166
let rec r_lt_a (t:t 'a) (i:int) (v:'a) (l:FI.intervals) (ghost j:int)
167
requires { Int.(0 <= i - 1 < Array.length t.steps) -> match l with
168
| List.Nil -> true
169
| List.Cons (a,_) _ -> F.(t.steps[i-1] < a) end }
170
requires { Int.(0 <= i < Array.length t.values) }
171
requires { FI.ordered l }
172
ensures { t.inc v result }
173
ensures { forall x. FI.mem x l -> Int.(i <= find t x) -> t.inc (get_value t x) result }
174
variant { Array.length t.steps - i,l,j }
175
=
176
let _ = j in
177
match l with
178
| List.Nil -> v
179
| List.Cons (a,_) _ ->
180
if Array.length t.steps <= i then
181
t.join v t.values[i]
182
else
183
if F.lt t.steps[i] a then begin
184
assert { forall x. F.(a <= x) -> Int.(i+1 <= find t x) };
185
r_lt_a t (i+1) v l 1
186
end else
187
let v = t.join v t.values[i] in
188
if t.is_top v then v else r_ge_a t (i + 1) v l 1
189
end
190
with r_ge_a (t:t 'a) (i:int) (v:'a) (l:FI.intervals) (ghost j:int)
191
requires { Int.(0 <= i - 1 < Array.length t.steps) -> match l with
192
| List.Nil -> true
193
| List.Cons (a,_) _ -> F.(a <= t.steps[i-1]) end }
194
requires { Int.(1 <= i < Array.length t.values) }
195
requires { FI.ordered l }
196
ensures { t.inc v result }
197
ensures { forall x. FI.mem x l -> Int.(i <= find t x) -> t.inc (get_value t x) result }
198
variant { Array.length t.steps - i,l,j }
199
=
200
let _ = j in
201
match l with
202
| List.Nil -> v
203
| List.Cons (_,b) l' ->
204
if not (F.lt t.steps[i-1] b) then begin
205
assert { forall x. F.(x <= b) -> Int.(find t x < i) };
206
r_unk t i v l' 1
207
end else
208
let v = t.join v t.values[i] in
209
if t.is_top v then v else
210
if Array.length t.steps <= i then
211
v
212
else
213
r_ge_a t (i + 1) v l 1
214
end
215
with r_unk (t:t 'a) (i:int) (v:'a) (l:FI.intervals) (ghost j:int)
216
requires { Int.(1 <= i < Array.length t.values) }
217
requires { FI.ordered l }
218
requires { j = 1 }
219
ensures { t.inc v result }
220
ensures { forall x. FI.mem x l -> Int.(i <= find t x) -> t.inc (get_value t x) result }
221
variant { Array.length t.steps - i,l,j }
222
=
223
match l with
224
| List.Nil -> v
225
| List.Cons (a,_) _ ->
226
if F.lt t.steps[i-1] a then begin
227
r_lt_a t i v l 0
228
end else
229
r_ge_a t i v l 0
230
end
231
in
232
let rec find_first (t:t 'a) (i:int) (l:FI.intervals)
233
requires { Int.(0 <= i - 1 < Array.length t.steps) -> match l with
234
| List.Nil -> true
235
| List.Cons (a,_) _ -> F.(t.steps[i-1] < a) end }
236
requires { Int.(0 <= i < Array.length t.values) }
237
requires { FI.ordered l }
238
requires { l <> List.Nil }
239
ensures { forall x. FI.mem x l -> Int.(i <= find t x) -> t.inc (get_value t x) result }
240
variant { Array.length t.steps - i }
241
=
242
match l with
243
| List.Nil -> absurd
244
| List.Cons (a,_) _ ->
245
if Array.length t.steps <= i then
246
t.values[i]
247
else
248
if F.lt t.steps[i] a then begin
249
find_first t (i+1) l
250
end else
251
let v = t.values[i] in
252
if t.is_top v then v else r_ge_a t (i + 1) v l 1
253
end
254
in
255
if l.FI.nan then
256
r_lt_a t 0 t.nan l.FI.u 1
257
else
258
find_first t 0 l.FI.u
259
260
exception
Defensive_assert
261
Valid (151ms) (cvc5)
262
let
mk_partly_defensive
[@requires:trusted "the caller in fp_interval.ml gives a join and is_top that fit an order inc; inc is ghost, so it cannot be tested"] vis_top (vnan:'a) vsteps vvalues vjoin (ghost vinc)
263
requires { forall x y:'a. vinc x (vjoin x y) }
264
requires { forall x y:'a. vinc y (vjoin x y) }
265
requires { forall x:'a. vinc x x }
266
requires { forall x y z:'a. vinc x y -> vinc y z -> vinc x z }
267
requires { forall x y:'a. vis_top y -> vinc x y }
268
raises { Defensive_assert ->
269
not (vsteps.length + 1 = vvalues.length) \/
270
(exists i. Int.(0 <= i < vsteps.length) /\
271
not F.(vsteps[i] < vsteps[i+1])) }
272
=
273
if vsteps.length + 1 <> vvalues.length then raise Defensive_assert;
274
for k=0 to vsteps.length-2 do
275
invariant { forall i j. Int.(0 <= i < j <= k) ->
276
F.(vsteps[i] < vsteps[j]) }
277
if not (F.lt vsteps[k] vsteps[k+1]) then raise Defensive_assert;
278
done;
279
{ is_top = vis_top; nan = vnan; steps = vsteps; values = vvalues; join = vjoin;
280
inc = vinc }
281
282
end
283
284
end