The proved library of Colibri2

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 the library

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.

Floating-point numbers

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

Numbers and basic properties

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

Domains and their propagation

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

Wiring with the e-graph

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

Tools

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)

What is proved

What is trusted

The proofs rely on:

The sources are in common/colibrilib/.