Home / Learn / 5 Contracts and the verifier

Release v0.4.0Edition 0.2

5.1 Preconditions: requires

Page 2 of 11

5.1.1 What a contract is

When a store hires a courier, the two sign an agreement. The store promises to hand over parcels that are packed, labeled and under 30 kilograms. The courier promises to deliver each one within two days. Each side knows what it must do and what it may count on, and neither has to watch how the other works.

A function and the code that calls it have the same kind of agreement. As chapter 1 showed, a function takes values, its parameters, and gives back a value, its result; the code that calls it is its caller, and the values the caller passes are the arguments. A contract is the agreement between the two, written into the function's header, the lines from its name down to =. The body, after =, is how the function keeps its side.

A contract has two halves:

A contract in Una is more than a comment: una checks both halves, for every caller and every input, before the program runs.

5.1.2 Why a function needs a precondition

Some functions only make sense for some arguments. Splitting a total into monthly installments divides it by the number of months, and a division by zero has no answer. Here is that function with nothing to say so:

steps/01-no-requires/src/installments.unauna
module installments

--- One of `count` equal monthly installments of `total` cents, rounded down.
installment(total: Int, count: Int) -> Int = total / count

--- What the customer pays each month. The checkout form allows 0 months, which means
--- paying everything now.
monthly(total: Int, months: Int) -> Int = if months < 1 then total else installment(total, count: months)

pub main() -> Unit
  uses @console: Console[print]
=
  @console.print("{installment(12000, count: 3)} a month for 3 months")
  @console.print("{monthly(12000, months: 0)} now, or {monthly(12000, months: 4)} a month for 4 months")

monthly uses if from section 3.4: a checkout form allows 0 months, which means paying everything now. In many languages this code runs, and works, until some call passes 0 to installment. Then the division fails while the program runs, and the checkout stops in front of a customer. A test finds the problem only if someone thought to try 0.

Una does not run it. una check . reports:

Diagnostic
[U5001] Error: division obligation `count != 0` is refuted
   ╭─[ src/installments.una:4:46 ]
   │
 4 │ installment(total: Int, count: Int) -> Int = total / count
   │                                              ──────┬──────
   │                                                    ╰──────── division obligation `count != 0` is refuted
   │
   │ Help: repair 1: guard the division with `if count != 0`
   │
   │ Note 1: obligation ob-69e79e4e9a3b (division) is refuted: count != 0
   │
   │ Note 2: counterexample: count = 0
   │
   │ Note 3: run `una explain U5001` for an explanation
───╯

You met this diagnostic in section 2.2: every division by a value that is not a literal is a proof obligation, a fact that must be proven before the program may run, here count != 0. Nothing tells una that count is never 0, and the line Note 2 gives the case that breaks it, count = 0: the counterexample. The Help line offers a guard, an if around the division, but a guard makes installment invent an answer for 0 installments, which has none. What installment needs is a way to say "never call me with 0", so that each caller, where the number comes from, makes sure of it. A precondition is that way.

Each example of this chapter is a package, made as chapter 2 explains, and the chapter's download, 05-contracts.tar.gz, holds them all.

5.1.3 What the verifier is

The verifier is the part of una check that proves facts about your program without running it. It runs after the other checks pass, in three steps:

  1. It lists what must be true. Every place where the program relies on a fact becomes a question: "is count != 0 here, whatever the inputs?" Such a question is a proof obligation. A division gives one, each requires gives one at every call, and each ensures gives one for the body.
  2. It asks a solver. A solver is a program that answers such questions by reasoning about every possible value at once, not by trying values one after another. Una uses the solver Z3, at the exact version that verification.lock names, so every machine gets the same answers.
  3. It reports the answer. An obligation is proven when it holds for every input, which needs no message. It is refuted when some input breaks it: that is U5001, and the input is the counterexample, on the line Note 2: counterexample: …. When the solver cannot decide, the obligation is unknown: that is U5002, an error too (section 5.4).

A test runs the code on the inputs someone wrote down. The verifier covers every input, before the program runs, and its proofs cost nothing when the program runs. In exchange, you write your conditions in a small language the solver can decide, the refinement language of section 5.3.

5.1.4 How to write requires

A requires clause is the word requires and a condition, on a line of its own under the header, indented two spaces, before =. A condition is an expression that is true or false, a Bool (section 3.3), such as units >= 1. A function with a clause is written in the long form of chapter 1: the header, the clauses, = alone on its line, then the body. A function may have any number of clauses, and every one must hold.

The step of this part shows every form a precondition takes. It works with two kinds of the store, a record and a sum (chapter 4):

steps/02-clauses/src/checkout.unathe kindsuna
--- One line of a cart: a SKU, how many units, and the price of one unit in cents.
kind CartLine
  sku: Text
  quantity: Int
  unit_cents: Int

--- Where a parcel goes.
kind Zone = Local | National | Abroad

5.1.4.1 One condition

The simplest precondition names one parameter:

steps/02-clauses/src/checkout.unauna
--- The price of one unit when a pack of `units` costs `pack_cents`, rounded down.
unit_price(pack_cents: Int, units: Int) -> Int
  requires units >= 1
=
  pack_cents / units

The body divides by units. The clause makes that safe, and every caller must show that its units is at least 1.

5.1.4.2 Several conditions, several clauses

A precondition may relate parameters to each other. Write each condition as a clause of its own:

steps/02-clauses/src/checkout.unauna
--- The price after a coupon worth `off` cents. Three clauses, and all of them must hold.
after_coupon(price: Int, off: Int) -> Int
  requires price >= 0
  requires off >= 0
  requires off <= price
=
  price - off

The three clauses hold together, as if joined by and. Separate lines read better, and when a call breaks one, the message names that one. requires off <= price is a condition on two parameters: a coupon may not take off more than the price.

5.1.4.3 Fields and lengths

A condition may read the fields of a record parameter, and the length of a text with .len. It may join conditions with and; or and not work the same way:

steps/02-clauses/src/checkout.unauna
--- What one line costs. The clause reads two fields of the line.
line_cents(line: CartLine) -> Int
  requires line.quantity >= 1 and line.unit_cents >= 0
=
  line.quantity * line.unit_cents

--- The product family of a SKU: its first four characters, as `LAMP` in `LAMP-01`.
family(sku: Text) -> Text
  requires sku.len >= 4
=
  sku.slice(start: 0, end: 4)

family cuts the first four characters with slice, whose own precondition (section 3.2) says that the cut must lie inside the text. requires sku.len >= 4 is what lets family meet it.

5.1.4.4 A condition for one case: implies and is

a implies b reads "if a, then b". It holds whenever a is false, so it states a rule for one case only. zone is Abroad tests the variant of a sum, as in section 4.2:

steps/02-clauses/src/checkout.unauna
--- What shipping costs, in cents, for a parcel of `grams` grams. Abroad, a parcel weighs at
--- most 20 kilograms.
shipping_cents(zone: Zone, grams: Int) -> Int
  requires grams >= 1
  requires zone is Abroad implies grams <= 20000
=
  when zone
    is Local -> 495
    is National -> 795 + grams / 1000 * 100
    is Abroad -> 2500 + grams / 1000 * 300

A local or national parcel may weigh anything from 1 gram up. Only a parcel abroad must weigh at most 20,000 grams.

5.1.4.5 A named condition

When the same condition appears in many clauses, give it a name with a predicate, and write requires fits(off, price). Predicates, in section 5.3, show how.

5.1.4.6 Running the precondition forms

main calls each function once, with arguments that meet its precondition:

steps/02-clauses/src/checkout.unauna
pub main() -> Unit
  uses @console: Console[print]
=
  @console.print("one unit of a pack of 4: {unit_price(1990, units: 4)}")
  @console.print("after a coupon: {after_coupon(1990, off: 500)}")
  let one_line = line_cents(CartLine(sku: "LAMP-01", quantity: 2, unit_cents: 1990))
  @console.print("one line: {one_line}")
  let sku = "LAMP-01"
  @console.print("family of {sku}: {family(sku)}")
  @console.print("shipping: {shipping_cents(National, grams: 2300)} and {shipping_cents(Abroad, grams: 1500)}")
  @console.print("weekly price: {weekly_price(1990)} and {weekly_price(300)}")

una run . prints:

Output
one unit of a pack of 4: 497
after a coupon: 1490
one line: 3980
family of LAMP-01: LAMP
shipping: 995 and 2800
weekly price: 1490 and 0

Each call is proven before it runs. unit_price(1990, units: 4) gives the verifier the literal 4, and 4 >= 1 holds. family(sku) passes a text whose value the verifier knows, "LAMP-01", of length 7.

5.1.5 Installments that never divide by zero

Back to installments, now with the precondition:

steps/03-requires/src/installments.unacheckrununa
module installments

--- One of `count` equal monthly installments of `total` cents, rounded down.
installment(total: Int, count: Int) -> Int
  requires count >= 1
=
  total / count

--- What the customer pays each month. The checkout form allows 0 months, which means
--- paying everything now.
monthly(total: Int, months: Int) -> Int = if months < 1 then total else installment(total, count: months)

pub main() -> Unit
  uses @console: Console[print]
=
  @console.print("{installment(12000, count: 3)} a month for 3 months")
  @console.print("{monthly(12000, months: 0)} now, or {monthly(12000, months: 4)} a month for 4 months")
  1. requires count >= 1. The clause, under the header and before =.
  2. total / count. The division's obligation, count != 0, now follows from the precondition.
  3. if months < 1 then total else installment(total, count: months). months comes from a checkout form and can be 0. In the else branch, the verifier knows that months < 1 is false, so it proves months >= 1 for the call.
  4. installment(12000, count: 3). The verifier proves 3 >= 1 at the call. With a literal, the proof is immediate.

una run . prints:

Output
4000 a month for 3 months
12000 now, or 3000 a month for 4 months

5.1.6 How a precondition is checked

5.1.6.1 What the verifier knows at a call

At each call, the verifier proves the callee's precondition with the arguments in place of the parameters. It can use every fact it has at that line:

It never uses what a function's body does, only what its header says. So a precondition is part of the function's public face: change it, and every call is checked again.

5.1.6.2 Inside the body

Inside the function, each requires is a fact. The verifier assumes it, and uses it to prove the obligations of the body: the division in installment, the slice in family. The body never tests the condition itself, and the condition costs nothing when the program runs.

5.1.6.3 A call that does not meet the precondition

Remove the guard from monthly, and call installment directly:

src/installments.unadiff
--- a/src/installments.una
+++ b/src/installments.una
@@ -10,3 +10,3 @@
 --- paying everything now.
-monthly(total: Int, months: Int) -> Int = if months < 1 then total else installment(total, count: months)
+monthly(total: Int, months: Int) -> Int = installment(total, count: months)
 

una check . now refutes the call, and says why:

Diagnostic
[U5001] Error: precondition `months >= 1` of this call is refuted
    ╭─[ src/installments.una:11:43 ]
    │
  5 │   requires count >= 1
    │            ─────┬────
    │                 ╰────── requires clause
    │
 11 │ monthly(total: Int, months: Int) -> Int = installment(total, count: months)
    │                                           ────────────────┬────────────────
    │                                                           ╰────────────────── precondition `months >= 1` of this call is refuted
    │
    │ Help 1: repair 1: strengthen the type of the parameter `months` to a refined kind that implies `months >= 1`
    │
    │ Help 2: repair 2: add `requires months >= 1` to the enclosing function; its callers then prove it
    │
    │ Help 3: repair 3: add a guard (`if` or a `when` arm) that handles the values where `months >= 1` does not hold
    │
    │ Help 4: repair 4 (escape: checked; a runtime test replaces the static proof: the program fails at run time where the proof would have rejected it; it counts against [escape_budget] and is listed in the build report): check the value with `checked(value, months >= 1) else fail <Variant>`
    │
    │ Note 1: obligation ob-b0ef023087ff (precondition) is refuted: months >= 1
    │
    │ Note 2: counterexample: months = 0
    │
    │ Note 3: run `una explain U5001` for an explanation
────╯

Read the diagnostic from the top. The first line names the obligation, a precondition, and its goal, months >= 1, written with the caller's argument in place of count. The two marks show the clause that asked for it, on line 5, and the call that does not meet it, on line 11. Note 2 is the counterexample: with months = 0, the goal is false. The Help lines are the repairs, best first:

  1. a stronger type for months, a refined kind (section 5.3);
  2. a requires on monthly, which moves the obligation to its callers;
  3. a guard, as the if was;
  4. last, checked, a test at run time, which section 7.5 covers.

5.1.6.4 What a requires clause may say

5.1.7 A precondition or a guard

A precondition and a guard both protect the same division. They differ in who handles the bad case:

Which to use:

You want to… Use
Make a bad argument the caller's mistake, checked at every call requires
Handle every argument, with an answer for the bad case a guard, if in the body (section 3.4)
State a rule that holds of every value of a type a refined kind (section 5.3)
Pass an obligation on to your own callers requires, with the same condition

monthly uses a guard because 0 months has a meaning: pay now. installment uses a precondition because 0 installments has none.

5.1.8 Check yourself: preconditions

weekly_price takes the weekly coupon of 5.00 off a price, and turns a price below 5.00 into 0:

steps/02-clauses/src/checkout.unauna
--- The price on a product page after the weekly coupon of 5.00. A price below 5.00 becomes 0.
weekly_price(price: Int) -> Int
  requires price >= 0
=
  if price < 500 then 0 else after_coupon(price, off: 500)

It calls after_coupon from Several conditions, several clauses, with its three clauses. Now drop the if, and write the body as after_coupon(price, off: 500). Does it still check? If not, which clause fails, and for which price?

Show the answer

It does not check. price >= 0 holds by weekly_price's own precondition, and 500 >= 0 holds for the literal. 500 <= price is the clause no fact supports:

Diagnostic
[U5001] Error: precondition `500 <= price` of this call is refuted
    │ Note 2: counterexample: price = 0

Any price below 500 breaks it, and the counterexample shows one. The if was what proved the clause: in the else branch, price < 500 is false.

One more, without code. unit_price requires units >= 1. Which of these calls check?

  1. unit_price(1990, units: 4).
  2. unit_price(1990, units: 0).
  3. unit_price(cents, units: packs), inside a function that has requires packs >= 2.
  4. unit_price(cents, units: packs), inside a function that says nothing about packs.
Show the answer

Calls 1 and 3 check. In call 1 the literal 4 is at least 1. In call 3 the caller's own precondition, packs >= 2, implies packs >= 1. Call 2 is refuted: 0 is not at least 1, and the literal itself is the case. Call 4 is refuted too, with a value of packs below 1 as the counterexample: nothing tells the verifier what packs holds. A guard, a requires on the caller, or a refined kind must supply the fact.

Next:5.2 Postconditions: ensures and counterexamples