Since version 0.7, the core reasoning of Colibri2 is written in
WhyML, proved with Why3 and
why3find, and extracted to OCaml: the
library colibrilib. The OCaml code of Colibri2 around it connects the
proved domains to the e-graph, the daemons and the options.
The documentation below is the one generated by why3find doc: the
specifications, the code, and the proof status of each function.
The files of colibrilib by part, with their documentation in colibrilib
0.7.
🐫: the file has a module Export,
the functions that the OCaml code of Colibri2 calls (total, without
preconditions).
🔌: the file has functions (val)
implemented by OCaml code given in an extraction driver, which is trusted.
🐓: the file has theories realized in
Rocq.
The domain of the floats and its implementation on concrete binary floats. Their rounding is the one of Flocq: the theories of flocq are realized in Rocq and checked against Flocq.
fp |
the interface of the floats seen by the domain: the order where -0 < +0, the index of the floats | |
fbin |
🐫 | its implementation: binary floats with the format as data, the rounding computed on dyadic numbers |
fp_facts |
the facts derived from the interface, for the users of the floats | |
fp_interval |
🐫 | the domain of the floats: unions of intervals, and the rules on the sign and the magnitude |
dyadic |
🐫 | the powers of 2 that divide a real (the FIX and FLT of Gappa) |
fp_dyadic |
the dyadic domain on the floats: rounding forward and backward, exact roundings | |
zinterval |
🐫 | intervals of integers: the relations between the indices of two floats |
pow2r |
the powers of 2 as reals, for every integer exponent | |
flocq |
🐓 | the rounding of Flocq and the binary floats, as WhyML theories |
fbin_ieee |
the rounding of fbin is the rounding of Flocq |
The trusted interfaces of Zarith and Flint, models showing their axioms consistent, and the facts the other proofs use.
zarith |
🔌 | the trusted specification of the Zarith functions used |
flint |
🔌 | the trusted bindings to Calcium, the exact reals of Flint |
int63 |
🔌 | the bit operations of the OCaml integers |
models |
models of the trusted interfaces: their axioms are consistent | |
zbit_model |
a model of the bit operations of Zarith | |
q |
🔌 | the interface of the rationals |
q_model |
a model of it: normalized fractions | |
stdq |
🐫 | the rationals of colibri2 (Std.Q) |
stda |
🐫 | the real algebraic numbers of colibri2 (Std.A): a rational or an exact real |
qa |
the Euclidean remainder on the reals and the rationals | |
dv |
divisibility on the reals | |
modulo |
rounding to a multiple of a rational | |
generic_divrem_rewrite |
x = y * div x y + mod x y, for the divisions of SMT-LIB and Why3 | |
lowbits |
the low bits of the integers | |
zbit |
total bit operations, for any index | |
safe_bits |
🐫 | bit fields of the integers: extract, sign extension, update |
The abstract domains of the theories, with the transfer functions that propagate the constraints between them.
bound |
🐫 | strict and large bounds |
union |
🐫 | unions of intervals |
congruence |
🐫 | congruence classes of the reals |
union_congr |
🐫 | the domain of the reals: a union of intervals and a congruence class |
known_bits |
🐫🔌 | the known bits of an integer |
kb_interval |
🐫 | the known bits of an interval domain, and back; the bitwise operators on intervals |
ring |
🐫🔌 | polynomials in expanded normal form |
polynome |
🐫🔌 | linear polynomials |
product |
🐫🔌 | the products |x|^q and their solver |
sign_product |
🐫🔌 | the products of signs |
negcycle |
🐫 | incremental detection of negative cycles (the acyclicity of the datatypes) |
bdd |
🔌 | binary decision diagrams (layers BDD and VBDD) |
sbdd |
the layer SBDD of the BDD domain | |
pbdd |
the layer PBDD | |
ibdd |
the layer IBDD: the bitwise operations, specified on the integers | |
bddbitv |
🐫 | the bit-vector domain on BDDs |
bv_sem |
🐫 | the interpretation of the bit-vector operators by the model check, equal to SMT-LIB |
The code that connects the domains to the e-graph of colibri2, proved for one model of its specification (env).
env |
🔌 | the specification of the e-graph and of the domains, for one model (trusted) |
fp_conv |
🐫🔌 | the propagators of the floating-point theory |
dom_ring |
🐫🔌 | the ring theory: normal forms of +, -, * |
dom_modrw |
🐫🔌 | the rewriting of the Euclidean remainders |
bitwise_rules |
🐫🔌 | the bit-level terms of the integer bitwise operators and of the bit-vector operators |
bv_dolmen |
🐫🔌 | the Dolmen builtins of these terms |
The shapes of the specifications and generic data structures.
spec |
the shapes of the specifications of the abstract domains | |
tagtbl |
tables indexed by tags | |
summarize |
🐫 | a value by steps over sorted intervals, and its join over a union (for the floats) |
mod, the products |x|^q.The proofs rely on:
The sources are in
common/colibrilib/.