Home / Learn / 5 Contracts and the verifier
5.4 What the verifier proves
Page 5 of 11
5.4.1 What an obligation is
Before a new shop opens, an inspector walks through it with a checklist: the fire exits, the wiring, the ramp at the door. Each item gets one mark: passed, failed, or could not be inspected. The shop opens only when every item has passed.
The verifier works through your program the same way. Its checklist is the list of proof obligations, or obligations for short: one question for each place where the program relies on a fact, as What the verifier is in section 5.1 says. "Is this divisor never 0?" "Does this call meet the callee's requires?" "Does this value fit the kind it enters?" Each question gets one mark, its status:
- proven: the fact holds for every input;
- refuted: some input breaks it, and the verifier shows that input;
- unknown: the solver could not decide.
A program checks only when every obligation is proven. You never write an obligation yourself: una derives them from what you wrote, the contracts, the refined kinds, the divisions and a few other constructs. This section shows how to see them, what each kind asks, and what to do when the solver cannot answer.
5.4.2 Why list the obligations
When una check . passes, it prints nothing. Silence is the right answer for a program that is correct, but it does not tell you what was proven. Was the guard you just added the thing that proved the division safe? Did the rule you care about become a question at all? A function with no contract has nothing to prove, and it passes in the same silence as a function whose every promise was proven.
A reviewer needs to see the checklist, not only the result. una obligations . prints it: every obligation of the package, proven or not, with where it comes from and what it asks.
5.4.3 How to list the obligations: una obligations
In the package's directory, run:
una obligations .It checks the package first. When the package has an error that is not an obligation, such as a syntax error or a missing uses, it reports that error instead of a list. Otherwise it prints one line per obligation. The step of this part has one small function for each kind of obligation, and it prints:
$ una obligations .
proven ob-b852e63daefa division src/stockroom.una:11:3 units != 0
proven ob-2a3920108dd8 postcondition src/stockroom.una:15:11 result <= 99
proven ob-0d6cd810c278 refinement src/stockroom.una:20:1 result >= 0
proven ob-011bffbfed9b division src/stockroom.una:23:72 people != 0
proven ob-7ed451ea7768 overflow src/stockroom.una:29:51 shelf + 1 in 0..255
proven ob-20fdd4197f66 precondition src/stockroom.una:34:31 4 >= 1
proven ob-82707e2c71ad refinement src/stockroom.una:34:101 1000 >= 0
proven ob-8ef0d001a88c refinement src/stockroom.una:35:61 12 in 0..999proven. The status. A list with onlyprovenlines is a package that checks.ob-b852e63daefa. The obligation's identity: a short name that stays the same while the obligation does not change.division. The kind of question, which the next part explains one by one.src/stockroom.una:11:3. Where it is: the file, the line and the column of the code that raised it.units != 0. The goal: the fact the solver must prove, written in Una with the names of your code.
Each line is one question, answered on its own. una --json obligations . prints the same list as JSON, for tools and agents.
5.4.4 The kinds of obligations
Edition 0.2 has six kinds, and each comes from one construct. This section shows five, with one function of the step for each. The sixth, exhaustive, comes from a when that chooses by a number, which section 8.2 teaches with its obligation.
5.4.4.1 precondition: at every call of a function with requires
--- The price of one unit of a pack. The clause gives each call a precondition obligation, and
--- the division gives the body a division obligation.
unit_price(pack_cents: Int, units: Int) -> Int
requires units >= 1
=
pack_cents / unitsproven ob-20fdd4197f66 precondition src/stockroom.una:34:31 4 >= 1The goal is the callee's clause, units >= 1, with the caller's argument in place of the parameter. main calls unit_price(1990, units: 4), so the goal is 4 >= 1. The line points at the call, in main, not at the clause.
5.4.4.2 division: at every / and mod by a value that is not a literal
The same function divides by units, which gives a second obligation, in the body:
proven ob-b852e63daefa division src/stockroom.una:11:3 units != 0The precondition proves it: inside the body, units >= 1 is a fact, so units is never 0. share proves its division with a guard instead:
--- A share of a bill. The guard proves the division obligation.
share(total: Int, people: Int) -> Int = if people == 0 then total else total / peopleproven ob-011bffbfed9b division src/stockroom.una:23:72 people != 0In the else branch, people == 0 is false. A division by a literal, such as total / 100, raises no obligation: the divisor is visibly not 0.
5.4.4.3 postcondition: at every return of a function with ensures
--- At most 99 units on one line. The clause gives the body a postcondition obligation.
capped(units: Int) -> Int
ensures result <= 99
=
if units > 99 then 99 else unitsproven ob-2a3920108dd8 postcondition src/stockroom.una:15:11 result <= 99One obligation covers every path that returns: both branches of the if. The line points at the clause.
5.4.4.4 refinement: wherever a value enters a refined kind
--- A price with the shipping fee. The result enters `Cents`: a refinement obligation.
with_fee(price: Cents) -> Cents = price + 495proven ob-0d6cd810c278 refinement src/stockroom.una:20:1 result >= 0
proven ob-82707e2c71ad refinement src/stockroom.una:34:101 1000 >= 0
proven ob-8ef0d001a88c refinement src/stockroom.una:35:61 12 in 0..999The first line is the result entering Cents: result >= 0. The other two are arguments entering the refined parameters of their functions in main: 1000 entering Cents, and 12 entering Int in 0..999, the type of the parameter of fill(units: Int in 0..999), the step's function that says how full a bin is. The goal is the kind's condition with the value in place of it.
5.4.4.5 overflow: at arithmetic on a fixed-width integer, and at a conversion to a narrower one
--- The next shelf of a rack of 201 shelves. `U8` holds 0 to 255: an overflow obligation.
next_shelf(shelf: U8) -> U8 = if shelf < 200 then shelf + 1 else 0proven ob-7ed451ea7768 overflow src/stockroom.una:29:51 shelf + 1 in 0..255A U8 holds the whole numbers 0 to 255 (section 2.3). shelf + 1 must stay in that range, and the guard shelf < 200 proves it does. A conversion of a value to a narrower fixed-width type raises the same kind of obligation: the value must fit.
5.4.4.6 Two more kinds in edition 0.3
Edition 0.3, a preview, adds two kinds, which come from the limits on authority of chapter 13: effect_condition and contract_lock. Packages on edition 0.2, as every step of this chapter is, never see them.
5.4.4.7 Running the step
unit price 497, capped 99, with fee 1495
share 333, bin stocked, next shelf 85.4.5 The obligations of a cart
Now the list for a real module: the cart of Cents, quantities and free shipping, in section 5.3. It has no division and no when on numbers, so its obligations are refinements and one postcondition:
$ una obligations .
proven ob-91854e18e0ff refinement src/cart.una:19:1 result >= 0
proven ob-993bde8df1da postcondition src/cart.una:20:11 ships_free(total) implies result == 0
proven ob-7cd127341d91 refinement src/cart.una:22:17 total >= 0
proven ob-4fcc7418858d refinement src/cart.una:28:37 line.unit_cents >= 0
proven ob-2a5905c8f53d refinement src/cart.una:28:64 (line.quantity + 1) in 1..99
proven ob-7397ad5ab9ad refinement src/cart.una:35:47 1990 >= 0
proven ob-827f34a7ed20 refinement src/cart.una:35:63 2 in 1..99
proven ob-0ebf927b2507 refinement src/cart.una:38:38 3980 >= 0
proven ob-cb89b59f2358 refinement src/cart.una:38:61 5970 >= 0Read it against the code, line by line:
19:1 result >= 0.shippingreturnsCents, so its result must not be negative, on both branches. The line points at the function.20:11 ships_free(total) implies result == 0. Theensuresofshipping.22:17 total >= 0.shippingcallsships_free(total), whose parameter isCents.28:37 line.unit_cents >= 0and28:64 (line.quantity + 1) in 1..99.one_morebuilds aLine, so each refined field proves its kind. The second is the one the guardif line.quantity < 99proves.35:47to38:61.mainbuilds a line and callsshippingwith literals. Each literal entering a refined kind is a question, and an easy one.
Every rule of the cart that matters is on this list, and so is every place where a value could break one. When a line you expected is missing, the rule did not become a question: look for a contract or a kind that is not there.
5.4.6 How an obligation is answered
5.4.6.1 With the facts of its path
The solver answers each obligation with the facts known at its place in the code, and only those: the function's requires, the conditions of the if branches and when arms on the way, the refined kinds of the values in scope, and the ensures of the functions called before it. It never uses what a callee's body does. So a guard proves an obligation only inside its branch, and a fact proven in one function reaches another only through a header.
5.4.6.2 Statuses
- proven: nothing to report. The obligation costs nothing when the program runs.
- refuted: U5001, with a counterexample, which section 5.2 shows how to read.
- unknown: U5002, with the reason. This is an error too:
unanever passes a program with a missing proof.
5.4.6.3 Identities
The identity, such as ob-2a5905c8f53d, comes from the module, the function, the kind and the goal. An edit that does not change the obligation keeps its identity, so a reviewer can follow one obligation across versions of the code. The same goal of the same kind twice in one function shares one identity.
5.4.6.4 A pinned solver
The answers come from the solver Z3 at the version verification.lock names, with a fixed step budget, the most work it may do on one question. Within the step budget, the same program and the same lock give the same answers on every machine.
5.4.7 When the solver cannot decide: U5002
5.4.7.1 What the solver decides
The solver decides linear arithmetic: sums and differences of values, products where one side is a literal, such as price * 3, and quotients and remainders by a literal that is not zero. A question in that language is one it can answer, given enough steps. A product of two values that are not literals, such as a unit price times a quantity, is beyond it: the solver treats the product as an unknown number.
When it then finds values that break a rule, una checks them with real multiplication. If they agree, the rule really breaks, and you get U5001 with those values as a counterexample. If every case the solver found needs a product that real arithmetic does not give, the values are no run of the program, and you get U5002.
5.4.7.2 A product the solver cannot read
An invoice line costs its unit price times its quantity, and both are at least 0. Written as one expression, the solver cannot prove that the cost is not negative:
--- a/src/invoice.una
+++ b/src/invoice.una
@@ -18,8 +18,4 @@
---- What one line costs. The guard handles a case that cannot happen, since both factors
---- are at least 0; the solver cannot see that for itself.
-line_total(line: Line) -> Cents
-=
- let total = line.unit_cents * line.quantity
- if total < 0 then 0 else total
+--- What one line costs.
+line_total(line: Line) -> Cents = line.unit_cents * line.quantity
[U5002] Error: refinement `result >= 0` could not be proven (the refutation depends on a product, quotient or remainder of two values, which the encoding of `spec/12 §2` leaves uninterpreted)Read the message in two parts. The first is the obligation: the refinement result >= 0, the result entering Cents, "could not be proven". The part in parentheses is the reason: the only refutation the solver found "depends on a product, quotient or remainder of two values". It names the section of the specification that defines what the solver decides (Reference links it). There is no counterexample, because the solver found no real one.
5.4.7.3 Giving the solver the fact: bind and guard
The version before the change, on the - side of the diff, is the repair. It names the product with let, then guards it with if: if total < 0 then 0 else total. The solver still cannot tell that total is not negative, but it does not need to: in the else branch, total < 0 is false, so the value returned there is at least 0, and the other branch returns 0. The guard handles a case that cannot happen, and costs one comparison when the program runs. Section 8.3 shows more of what a branch proves.
5.4.8 Check yourself: obligations
Here is the whole invoice step, with the guard:
module invoice
--- An amount of money in cents. It is never negative.
kind Cents = Int where it >= 0
--- One line of an invoice.
kind Line
sku: Text
unit_cents: Cents
quantity: Int in 1..99
--- Loyalty points: one for each whole 1.00 spent.
points(total: Cents) -> Int
ensures result >= 0
ensures result * 100 <= total
=
total / 100
--- What one line costs. The guard handles a case that cannot happen, since both factors
--- are at least 0; the solver cannot see that for itself.
line_total(line: Line) -> Cents
=
let total = line.unit_cents * line.quantity
if total < 0 then 0 else total
pub main() -> Unit
uses @console: Console[print]
=
let desk = Line(sku: "DESK-02", unit_cents: 14900, quantity: 2)
let total = line_total(desk)
@console.print("{total} cents, {points(total)} points")How many obligations does una obligations . list for it, and of which kinds?
Show the answer
Six: two postconditions and four refinements.
$ una obligations .
proven ob-00d161d86eb3 postcondition src/invoice.una:14:11 result >= 0
proven ob-a14e2a20a58d postcondition src/invoice.una:15:11 result * 100 <= total
proven ob-d6433d56c573 refinement src/invoice.una:21:1 result >= 0
proven ob-200f35c3fccb refinement src/invoice.una:29:47 14900 >= 0
proven ob-b453dd62cb76 refinement src/invoice.una:29:64 2 in 1..99
proven ob-f82fc95c6633 refinement src/invoice.una:31:42 total >= 0The postconditions are the two ensures of points. The refinements are the result of line_total entering Cents, the two refined fields of the Line that main builds, and total entering points, whose parameter is Cents. The product in line_total raises none of its own: the guard is what lets the refinement be proven. points divides by the literal 100, so there is no division obligation.
A second one. Is this function proven, refuted (U5001) or unknown (U5002)?
--- The floor area of a shelf, in square centimeters.
area(width: Int in 1..100, depth: Int in 1..100) -> Int
ensures result >= 1
=
width * depthShow the answer
Unknown:
[U5002] Error: postcondition of `area` could not be proven (the refutation depends on a product, quotient or remainder of two values, which the encoding of `spec/12 §2` leaves uninterpreted)width * depth is a product of two values, so the solver treats it as an unknown number, and every value that would break result >= 1 needs a product that real arithmetic does not give. The rule holds, since both factors are at least 1, but the proof is missing. Bind the product and guard it, as line_total does.