Common — library colibrilib.union — module Export

What OCaml calls: the contracts of Union.Make. Records built in OCaml (reducer, fmap) have their invariants trusted: only the fields that are not ghost exist there.

4047
module Export
4048
use int.Int
4049
use bool.Bool
4050
use option.Option
4051
use colibrilib.bound.Bound
4052
use real.RealInfix
4053
use colibrilib.stda.StdA as Q
4054
use colibrilib.q.Real as Real
4055
use real.Square
4056
use real.MinMax
4057
use colibrilib.spec.Sound
4058
use colibrilib.spec.Opt
4059
use colibrilib.spec.Test
4060
use colibrilib.q.Ord as Ord
4061
use real.Abs
4062
use real.Truncate
4063
use real.FromInt
4064
use list.List
4065
use Union
4066
import Make
4067
import Make.Increasing
4068
import Make.Increasing.Unary
4069
import Make.Increasing.Binary
4070
import Make.NonIncreasing
4071
import Make.IsComparable
4072
import Make.Map
4073
import Make.ED
4074
Valid (32ms) (colibri2)
4075
let
singleton
(q:Q.t) : t
4076
ensures { exact memt (fun (x:real) -> x = q) result }
4077
= Make.singleton q
4078
Valid (40ms) (colibri2)
4079
let
is_singleton
(u:t) : (option Q.t, ghost real, ghost real)
4080
ensures {
4081
let (o,x1,x2) = result in
4082
match o with
4083
| Some q -> forall x:real. mem x u.a <-> x = q
4084
| None -> x1 <> x2 /\ mem x1 u.a /\ mem x2 u.a
4085
end
4086
}
4087
= Make.is_singleton u
4088
Valid (28ms) (colibri2)
4089
let
inter
(u:t) (v:t) : option t
4090
ensures { exact_opt memt (fun (x:real) -> memt x u /\ memt x v) result }
4091
ensures {
4092
match result with
4093
| None -> true
4094
| Some w ->
4095
le_sup_infr (le_min_sup_infr (infr_bound u.a) (infr_bound v.a)) (infr_bound w.a)
4096
end
4097
}
4098
= Make.inter u v
4099
Valid (33ms) (colibri2)
4100
let
union
(u:t) (v:t) : t
4101
ensures { exact memt (fun (x:real) -> memt x u \/ memt x v) result }
4102
= Make.union u v
4103
Valid (29ms) (colibri2)
4104
let
mem
(x:Q.t) (l:t)
4105
ensures { decides (memt x.Q.real l) result }
4106
= Make.mem x l
4107
Valid (32ms) (colibri2)
4108
let
except
l x
4109
ensures {
4110
match result with
4111
| Some res -> forall q. (mem q l.a /\ q <> x.Q.real) <-> mem q res.a
4112
| None -> forall q. mem q l.a <-> q = x.Q.real
4113
end
4114
}
4115
= Make.except l x
4116
Valid (30ms) (colibri2)
4117
let
complement
l
4118
ensures { exact_opt memt (fun (x:real) -> not (memt x l)) result }
4119
= Make.complement l
4120
Valid (24ms) (colibri2)
4121
let
for_all
test t1 t2
4122
ensures { result -> (forall q. test (mem q t1.a) (mem q t2.a)) }
4123
= Make.for_all test t1 t2
4124
Valid (39ms) (colibri2)
4125
let
is_included
t1 t2
4126
ensures { result -> (forall q. (mem q t1.a) -> (mem q t2.a)) }
4127
= Make.is_included t1 t2
4128
Valid (40ms) (colibri2)
4129
let
gt
(q:Q.t)
4130
ensures { exact memt (fun (x:real) -> q <. x) result }
4131
= Make.gt q
4132
Valid (30ms) (colibri2)
4133
let
lt
(q:Q.t)
4134
ensures { exact memt (fun (x:real) -> x <. q) result }
4135
= Make.lt q
4136
Valid (31ms) (colibri2)
4137
let
ge
(q:Q.t)
4138
ensures { exact memt (fun (x:real) -> q <=. x) result }
4139
ensures { R q = infr_bound result.a }
4140
= Make.ge q
4141
Valid (22ms) (colibri2)
4142
let
le
(q:Q.t)
4143
ensures { exact memt (fun (x:real) -> x <=. q) result }
4144
= Make.le q
4145
Valid (22ms) (colibri2)
4146
let
le'
(u:t)
4147
ensures { sound_rel memt (<=.) u result }
4148
= Make.le' u
4149
Valid (32ms) (colibri2)
4150
let
lt'
(u:t)
4151
ensures { sound_rel memt (<.) u result }
4152
= Make.lt' u
4153
Valid (28ms) (colibri2)
4154
let
gt'
(u:t)
4155
ensures { sound_rel memt (>.) u result }
4156
= Make.gt' u
4157
Valid (32ms) (colibri2)
4158
let
ge'
(u:t)
4159
ensures { sound_rel memt (>=.) u result }
4160
= Make.ge' u
4161
Valid (30ms) (colibri2)
4162
let
is_comparable
(t1:t) (t2:t)
4163
ensures { match result with
4164
| Gt -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 >. q2
4165
| Lt -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 <. q2
4166
| Ge -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 >=. q2
4167
| Le -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 <=. q2
4168
| Eq -> forall q1 q2. mem q1 t1.a -> mem q2 t2.a -> q1 = q2
4169
| Uncomparable -> true
4170
end }
4171
= Make.IsComparable.is_comparable t1 t2
4172
Valid (19ms) (colibri2)
4173
let
from_convex_hull
x : option t
4174
ensures { includes_opt memt (fun (q:real) -> in_hull q x) result }
4175
= Make.from_convex_hull x
4176
Valid (22ms) (colibri2)
4177
let
get_convex_hull
x : convex_hull
4178
ensures { includes in_hull (fun (q:real) -> memt q x) result }
4179
= Make.get_convex_hull x
4180
Valid (33ms) (colibri2)
4181
let
neg
l
4182
ensures { sound1 memt (fun (x:real) -> -. x) l result }
4183
= Make.Increasing.Unary.neg l
4184
Valid (24ms) (colibri2)
4185
let
mult_cst
c l
4186
ensures { sound1 memt (fun (x:real) -> c *. x) l result }
4187
= Make.Increasing.Unary.mult_cst c l
4188
Valid (24ms) (colibri2)
4189
let
abs_forward
(l:t) : t
4190
ensures { sound1 memt (fun (x:real) -> abs x) l result }
4191
= Make.Increasing.abs_forward l
4192
Valid (40ms) (colibri2)
4193
let
abs_backward
(l:t) : t
4194
ensures { preimage1 memt (fun (x:real) -> abs x) l result }
4195
= Make.Increasing.abs_backward l
4196
Valid (30ms) (colibri2)
4197
let
add_cst
l x
4198
ensures {
4199
forall q. (mem q l.a) <-> mem (x+.q) result.a
4200
}
4201
= Make.Increasing.Binary.add_cst l x
4202
Valid (36ms) (colibri2)
4203
let
add
u v: (result:t)
4204
ensures { sound2 memt (fun (x y:real) -> x +. y) u v result }
4205
= Make.Increasing.Binary.add u v
4206
Valid (32ms) (colibri2)
4207
let
mul
u v: (result:t)
4208
ensures { sound2 memt (fun x y -> x *. y) u v result }
4209
= Make.Increasing.Binary.mul u v
4210
Valid (32ms) (colibri2)
4211
let
inv
(u:t): (result:t)
4212
ensures { sound1 memt (fun (x:real) -> 1. /. x) u result }
4213
= Make.Increasing.Binary.inv u
4214
Valid (36ms) (colibri2)
4215
let
div
u v : t
4216
ensures { sound2 memt (fun (x y:real) -> x /. y) u v result }
4217
= Make.Increasing.Binary.div u v
4218
Valid (27ms) (colibri2)
4219
let
ceil
l
4220
ensures { sound1 memt (fun (x:real) -> from_int (ceil x)) l result }
4221
= Make.NonIncreasing.ceil l
4222
Valid (28ms) (colibri2)
4223
let
floor
l
4224
ensures { sound1 memt (fun (x:real) -> from_int (floor x)) l result }
4225
= Make.NonIncreasing.floor l
4226
Valid (29ms) (colibri2)
4227
let
truncate
l
4228
ensures { sound1 memt (fun (x:real) -> from_int (truncate x)) l result }
4229
= Make.NonIncreasing.truncate l
4230
Valid (30ms) (colibri2)
4231
let
relu
l
4232
ensures { sound1 memt (fun (x:real) -> max 0. x) l result }
4233
= Make.NonIncreasing.relu l
4234
Valid (39ms) (colibri2)
4235
let
square_backward
l
4236
ensures { preimage1_opt memt (fun (x:real) -> sqr x) l result }
4237
= Make.square_backward l
4238
Valid (35ms) (colibri2)
4239
let
reduce_integers
(l:t) : option t
4240
ensures { restrict memt (fun (x:real) -> Real.is_integer x) l result }
4241
= Make.reduce_integers l
4242
Valid (30ms) (colibri2)
4243
let
div_e_forward
(l1 l2:t) : t
4244
ensures { sound2 memt div_e_real l1 l2 result }
4245
= Make.ED.div_e_forward l1 l2
4246
Valid (28ms) (colibri2)
4247
let
mod_e_forward
(l1 l2:t) : t
4248
ensures { sound2 memt (fun (x y:real) -> Real.mod_e x y) l1 l2 result }
4249
= Make.ED.mod_e_forward l1 l2
4250
Valid (37ms) (colibri2)
4251
let
mod_e_backward_num
(num:t) (denl:t) (modl:t) : option t
4252
ensures { back2 memt (fun (x y:real) -> Real.mod_e x y) num denl modl result }
4253
= Make.ED.mod_e_backward_num num denl modl
4254
Valid (29ms) (colibri2)
4255
let
div_t_forward
(l1 l2:t) : t
4256
ensures { sound2 memt div_t_real l1 l2 result }
4257
= Make.ED.div_t_forward l1 l2
4258
Valid (26ms) (colibri2)
4259
let
mod_t_forward
(l1 l2:t) : t
4260
ensures { sound2 memt (fun (x y:real) -> Real.mod_t x y) l1 l2 result }
4261
= Make.ED.mod_t_forward l1 l2
4262
Valid (29ms) (colibri2)
4263
let
mod_t_backward_num
(num:t) (denl:t) (modl:t) : option t
4264
ensures { back2 memt (fun (x y:real) -> Real.mod_t x y) num denl modl result }
4265
= Make.ED.mod_t_backward_num num denl modl
4266
Valid (35ms) (colibri2)
4267
let
div_f_forward
(l1 l2:t) : t
4268
ensures { sound2 memt div_f_real l1 l2 result }
4269
= Make.ED.div_f_forward l1 l2
4270
Valid (28ms) (colibri2)
4271
let
mod_f_forward
(l1 l2:t) : t
4272
ensures { sound2 memt (fun (x y:real) -> Real.mod_f x y) l1 l2 result }
4273
= Make.ED.mod_f_forward l1 l2
4274
Valid (25ms) (colibri2)
4275
let
mod_f_backward_num
(num:t) (denl:t) (modl:t) : option t
4276
ensures { back2 memt (fun (x y:real) -> Real.mod_f x y) num denl modl result }
4277
= Make.ED.mod_f_backward_num num denl modl
4278
Valid (26ms) (colibri2)
4279
let
reduce_generic
[@requires:trusted "the caller in union.ml builds the reducer: red_min is ghost, it cannot be tested"] (op:reducer) (num:t) : option t
4280
requires { le_infr_bound op.red_min num.a }
4281
ensures { restrict memt op.red_is_in num result }
4282
= Make.reduce_generic op num
4283
Valid (31ms) (colibri2)
4284
let
map_fold
(fm:Make.Map.UnaryFold.fmap 'a) (l1:t) : 'a
4285
ensures { forall r1. mem r1 l1.a -> fm.Make.Map.UnaryFold.inv r1 result }
4286
= Make.Map.UnaryFold.map fm l1
4287
Valid (29ms) (colibri2)
4288
let
map_unary
(fm:Make.Map.Unary.fmap) (l1:t) : t
4289
ensures { sound1 memt fm.Make.Map.Unary.fr l1 result }
4290
= Make.Map.Unary.map fm l1
4291
end