Common — library colibrilib.dom_ring — module Ring

The normal forms, proved

183
module Ring
184
use int.Int
185
use real.RealInfix
186
use list.List
187
use list.Mem
188
use list.Length
189
use option.Option
190
use colibrilib.ring.Atom
191
use colibrilib.ring.Mono
192
use colibrilib.ring.Poly as P
193
use colibrilib.stda.StdA as A
194
use colibrilib.ring.Export as R
195
use colibrilib.polynome.Assoc
196
use colibrilib.polynome.PT
197
use colibrilib.polynome.Lin as L
198
use colibrilib.env.Env
199
use colibrilib.env.Interval
200
use colibrilib.env.Linear
201
use colibrilib.spec.Opt
202
use Env

The linear form of the terms l of a normal form, with product nodes

  Valid (602ms) (colibri2 5) (split_vc) (depth 1)
205
let rec
linear_terms
(d:env) (l:P.poly) : L.t
206
variant { l }
207
ensures { live d -> L.eval d.m result = P.eval d.m l }
208
= match l with
209
| Nil -> L.zero ()
210
| Cons (m, c) r ->
211
let rest = linear_terms d r in
212
match m with
213
| Nil -> L.add_cst rest c
214
| Cons x Nil -> L.add (L.monome c x) rest
215
| _ ->
216
let pn = product_node m in
217
watch_product d pn;
218
L.add (L.monome c pn) rest
219
end
220
end

The linear form of a normal form

  Valid (16ms) (colibri2)
223
let
linear
(d:env) (p:R.t) : L.t
224
ensures { live d -> L.eval d.m result = R.eval d.m p }
225
= linear_terms d (R.get p)

The normal form of a free node y in the linear form of x: not used when it contains x (a cycle)

  Valid (28ms) (colibri2)
229
let
free
(d:env) (x y:Atom.t) : R.t
230
ensures { is_nf d y result }
231
= match find_nf d y with
232
| Some p -> if P.occ_p x (R.get p) = 0 then p else R.var y
233
| None -> R.var y
234
end

The product of the normal forms of the atoms of m

  Valid (307ms) (colibri2)
237
let rec
free_mono
(d:env) (x:Atom.t) (m:mono) : R.t
238
variant { m }
239
ensures { live d -> R.eval d.m result = evalm d.m m }
240
= match m with
241
| Nil -> R.cst (A.of_int 1)
242
| Cons a r -> R.mul (free d x a) (free_mono d x r)
243
end

The normal form of the bindings of a linear form

  Valid (597ms) (colibri2)
246
let rec
free_bindings
(d:env) (x:Atom.t) (l:list binding) : R.t
247
variant { l }
248
ensures { live d -> R.eval d.m result = evall d.m l }
249
= match l with
250
| Nil -> R.zero ()
251
| Cons (y, k) r ->
252
let my = match monomial y with
253
| None -> free d x y
254
| Some m -> free_mono d x m
255
end in
256
R.add (R.scale k my) (free_bindings d x r)
257
end

The normal form of the linear form of x (a node or a product node), if x is eliminated by Dom_polynome

  Valid (169ms) (cvc4)
261
let
eliminated
(d:env) (x:Atom.t) : option R.t
262
ensures { when_some (is_nf d x) result }
263
= match Linear.get_repr d x with
264
| Some l ->
265
if is_self l x then None
266
else Some (R.add (R.cst (L.cst_of l)) (free_bindings d x (L.atoms l)))
267
| None -> None
268
end

The normal form of the atom x

  Valid (22ms) (colibri2)
271
let
atom
(d:env) (x:Atom.t) : R.t
272
ensures { is_nf d x result }
273
= match find_nf d x with
274
| Some p -> p
275
| None ->
276
match eliminated d x with
277
| Some p -> p
278
| None -> R.var x
279
end
280
end

The atoms of a normal form replaced by their normal forms

  Valid (316ms) (colibri2)
283
let rec
subst_mono
(d:env) (m:mono) : R.t
284
variant { m }
285
ensures { live d -> R.eval d.m result = evalm d.m m }
286
= match m with
287
| Nil -> R.cst (A.of_int 1)
288
| Cons a r -> R.mul (atom d a) (subst_mono d r)
289
end
290
Valid (111ms) (colibri2)
291
let rec
subst_terms
(d:env) (l:P.poly) : R.t
292
variant { l }
293
ensures { live d -> R.eval d.m result = P.eval d.m l }
294
= match l with
295
| Nil -> R.zero ()
296
| Cons (m, c) r -> R.add (R.scale c (subst_mono d m)) (subst_terms d r)
297
end

x is used by n for each atom x of the terms l

  Valid (23ms) (colibri2)
300
let rec
add_used_terms
(d:env) (n:Atom.t) (l:P.poly) : unit
301
variant { l }
302
= match l with
303
| Nil -> ()
304
| Cons (m, _) r ->
305
let rec add_mono (m:mono) : unit variant { m } =
306
match m with Nil -> () | Cons x r -> add_used d x n; add_mono r end in
307
add_mono m;
308
add_used_terms d n r
309
end

The factorization

p = c * q, with the first coefficient of q equal to one

  Valid (406ms) (colibri2 5) (split_vc 4) (depth 4)
314
let
to_monic
(p:R.t) : (A.t, R.t)
315
returns { (c, q) -> A.real c <> 0.0 /\
316
forall env. R.eval env p = A.real c *. R.eval env q }
317
= match R.get p with
318
| Cons (_, c) _ ->
319
if A.equal c (A.of_int 1) then (A.of_int 1, p)
320
else (c, R.scale (A.div (A.of_int 1) c) p)
321
| Nil -> (A.of_int 1, p)
322
end

The pending factorizations of n = c * q

  Valid (385ms) (colibri2 7) (cvc5 2) (split_vc 2) (depth 2)
325
let rec
products_pending
(d:env) (n:Atom.t) (c:A.t) (q:R.t)
326
(l:list (Atom.t, A.t, mono)) : unit
327
requires { A.real c <> 0.0 }
328
requires { live d -> d.m n = A.real c *. R.eval d.m q }
329
requires { live d -> pending_ok d.m q l }
330
variant { l }
331
= match l with
332
| Nil -> ()
333
| Cons (n', k, g) r ->
334
let k' = A.div k c in
335
{proof…}
336
assert { live d -> d.m n' = A.real k' *. evalm d.m (Cons n g)
337
by d.m n' = A.real k *. evalm d.m g *. R.eval d.m q
338
so evalm d.m (Cons n g) = d.m n *. evalm d.m g };
339
{qed}
340
product d n' k' (Cons n g);
341
products_pending d n c q r
342
end

n = k * g * q: given to Dom_product when q is a constant or the normal form of a node, else waits for this node

  Valid (570ms) (colibri2 10) (split_vc) (depth 1)
346
let
factorize
(d:env) (n:Atom.t) (p:R.t) : unit
347
requires { is_nf d n p }
348
= let k, g, q = R.factor p in
349
match g, R.get q with
350
| Nil, _ -> ()
351
| Cons _ Nil, Cons (Nil, _) Nil -> (* linear *) ()
352
| _, Cons (Nil, c) Nil -> (* a monomial *) product d n (A.mul k c) g
353
| _ ->
354
match find_monic d q with
355
| Some (m, c) -> product d n (A.div k c) (Cons m g)
356
| None -> set_pending d q (Cons (n, k, g) (find_pending d q))
357
end
358
end

p is the normal form of n: the factorization of the first node of normal form p (the others are merged with it by Dom_polynome)

  Valid (30ms) (colibri2 14) (split_vc) (depth 1)
362
let
table_set
(d:env) (n:Atom.t) (p:R.t) : unit
363
requires { is_nf d n p }
364
= match R.get p with
365
| Nil | Cons (Nil, _) Nil -> ()
366
| _ ->
367
if not (table_mem d p) then begin
368
table_add d p n;
369
let c, q = to_monic p in
370
(match find_monic d q with
371
| None ->
372
set_monic d q n c;
373
let l = find_pending d q in
374
remove_pending d q;
375
products_pending d n c q l
376
| Some _ -> ()
377
end);
378
factorize d n p
379
end
380
end

The normal forms

p is the normal form of n

  Valid (29ms) (colibri2 7) (split_vc 4) (depth 2)
385
let rec
set
(d:env) (n:Atom.t) (p:R.t) : unit
386
requires { is_nf d n p }
387
diverges
388
= let same_nf = match find_nf d n with
389
| Some p' -> same p p'
390
| None -> false
391
end in
392
if length (R.get p) <= max_terms d && not same_nf then begin
393
if P.occ_p n (R.get p) > 0 then begin
394
(* [n = p(n)] is an equation, not a definition *)
395
remove_nf d n;
396
assume_linear d n (linear d p)
397
end else begin
398
set_nf d n p;
399
add_used_terms d n (R.get p);
400
table_set d n p;
401
assume_linear d n (linear d p)
402
end;
403
changed d n
404
end

The normal form of x changed: the normal forms that use it are updated

408
with
changed
(d:env) (x:Atom.t) : unit
409
diverges
410
= changed_list d x (used d x)
411
Valid (27ms) (colibri2)
412
with
changed_list
(d:env) (x:Atom.t) (l:list Atom.t) : unit
413
diverges
414
= match l with
415
| Nil -> ()
416
| Cons n r ->
417
(match find_nf d n with
418
| Some p -> if P.occ_p x (R.get p) > 0 then set d n (subst_terms d (R.get p))
419
| None -> ()
420
end);
421
changed_list d x r
422
end

Dom_polynome eliminates the product node pm of the monomial m with the linear form l: the equation m = l is solved in the ring, for an atom alone in its monomial.

  Valid (485ms) (cvc4)
427
let
solve_product
(d:env) (pm:Atom.t) : unit
428
diverges
429
= match monomial pm with
430
| Some m ->
431
match eliminated d pm with
432
| Some l ->
433
let pm' = subst_mono d m in
434
match R.solve (R.sub pm' l) with
435
| R.Zero | R.NotSolved -> ()
436
| R.Contra -> contradiction d
437
| R.Solved x q -> set d x q
438
end
439
| None -> ()
440
end
441
| None -> ()
442
end
443
end