Home / Docs / Specification / 29. Numerics

29.8 Verification

Release v0.4.0
  1. The encoding is exact. An F64 is the SMT-LIB sort (_ FloatingPoint 11 53), Float64, with the rounding mode RNE. The theory has one NaN and two zeros, as F64 has, so the encoding is the run-time semantics, not an approximation of it:

    Una SMT-LIB
    a float literal, nan(), infinity() (fp #b<sign> #b<exponent> #b<significand>), the exact bits
    +, -, *, /, unary - fp.add RNE, fp.sub RNE, fp.mul RNE, fp.div RNE, fp.neg
    sqrt, abs fp.sqrt RNE, fp.abs
    == SMT =, identity
    <, <= the defined functions i!lt!F64, i!le!F64: totalOrder
    ieee_eq, ieee_lt, ieee_le, ieee_gt, ieee_ge, ieee_ne fp.eq, fp.lt, fp.leq, fp.gt, fp.geq, (not (fp.eq a b))
    is_nan, is_finite, is_infinite, is_sign_negative fp.isNaN; (not (or (fp.isNaN x) (fp.isInfinite x))); fp.isInfinite; (and (fp.isNegative x) (not (fp.isNaN x)))
    is_zero, is_positive_zero, is_negative_zero fp.isZero; with fp.isPositive; with fp.isNegative
    n.to_f64(), n of a fixed-width type of width w (ite (in range) ((_ to_fp 11 53) RNE ((_ int2bv w) n)) <the form of Int>), to_fp_unsigned for an unsigned type: the narrow form only where n lies in its type's range, since a term computed exactly (a reflect body, a clause) may lie beyond it; a conversion in ordinary code keeps the narrow form unguarded, since its operand is a value of its type by construction (a parameter, a field, a result with an overflow obligation)
    n.to_f64(), n of Int the same at width 64 for -2^63 <= n < 2^63, and the uninterpreted i!to_f64!Int beyond
  2. The refinement language (spec/03 §3) gains, over F64: float literals other than in the forms of §5 rules 5 and 6, nan() and infinity(), +, -, *, / and unary - between any two F64 terms, ==, !=, <, <=, >, >=, the IEEE comparisons, abs(), sqrt(), the classifications, is_zero(), is_positive_zero(), is_negative_zero(), and to_f64() of an integer term. Every operation rounds as the code's does: ensures result == a + b states the rounded sum. The other methods are code only: U2014 in a clause.

  3. Which queries change. A query without an F64 term is unchanged, byte for byte, in QF_UFLIA. A query with one declares the logic ALL and is sent with the step budget 5,000,000, a constant of the encoding una-smt-1, whatever step_budget the lock sets. verification.lock keeps logic = "QF_UFLIA", the logic of every query without an F64 term.

  4. The cone. The hypotheses of an obligation are split into their conjuncts. A conjunct without an F64 term is kept. A conjunct with one is kept when it is connected to the goal's F64 terms through shared F64 binders, transitively (a union-find, O(|Π| α(|Π|))). Of the others, a selfified let with an F64 term, a definition, is dropped, and every other one, a constraint (a branch condition, a refinement, an ensures, a field equation of a construction), is kept with each float atom, a maximal Bool subterm with an F64 argument, replaced by a fresh Bool. Each step only weakens Π.

  5. Order. The pipeline of spec/12 §5 runs on the cone query. proven and unknown are final. refuted is final when nothing was dropped, or when only definitions were dropped whose binders occur in no kept hypothesis and not in the goal, and no ground fact of a dropped term is left out. Otherwise the pipeline runs again on the full query, the obligation's query with every hypothesis of Π, whose status is the obligation's; when it is unknown, the reason says that the refutation holds unless floating-point facts make the path unreachable. The weighted bound below applies to every query sent, re-solves included.

  6. The weighted bound. The weight of a query is taken over its distinct terms: fp.mul, fp.div, fp.sqrt and a conversion of a value that is not a literal weigh 4 (the two forms of one integer's conversion together), fp.add and fp.sub weigh 1, everything else nothing; each distinct application of a reflect predicate weighs its body's weight, as if inlined. A query of weight more than 4 is not sent: it is U5002, with the reason "this obligation needs floating-point reasoning of weight N, more than the 4 the verifier decides" and its repairs (a checked boundary, a split contract, a weaker property). An unknown on a float query is U5002 with the float reason.

  7. What is expected to verify: a bound by constants on the result of one operation over inputs bounded by constants; finiteness and not-NaN of one operation; up to four additions; a conversion from an integer of modest range; comparison-only facts over a handful of binders. Not expected, and U5002: a result compared with an input of the same operation, two multiplications in a chain, dot products, norms, a fact about the result of a loop.

  8. Counterexamples (spec/12 §7). An F64 binding shows its rendering of §7, as a JSON string ("0.1", "-0.0", "nan"). A refutation whose query uses i!to_f64!Int, in its hypotheses or in the facts of a loop's first iteration, is solved once more with every argument of the conversion in -2^63 <= n < 2^63, where the encoding is exact: a model of that query is an execution, and the obligation stays refuted with it; a conversion in a reflect predicate's definition is pinned at each application, its argument instantiated; otherwise it is unknown (U5002), with a reason that asks for a range refinement or a fixed-width type. So no counterexample ever rests on a value of the uninterpreted conversion.

  9. Generic code. A comparison of a type parameter instantiated with F64 in a callee's contract is i!lt!F64 and i!le!F64.