Home / Learn / 5 Contracts and the verifier

Release v0.4.0Edition 0.2

5.2 Postconditions: ensures and counterexamples

Page 3 of 11

5.2.1 What a postcondition promises

A postcondition is the function's half of the contract: what holds of the result when the function returns. Inside the clause, result names the value returned. The verifier proves the clause on every path that returns, and every caller may then assume it without reading the body.

Think of a guarantee printed on a receipt: "this price never goes up after you pay". You do not need to know how the shop computes its prices to rely on it. A postcondition is that kind of promise, made by a function to every caller, and una holds the function to it.

5.2.2 Why callers need a promise

A caller knows a function only by its header. Here after_coupon has preconditions but promises nothing, and left_on_card, which calls it, promises that a gift card never ends below 0:

steps/06-no-promise/src/coupons.unauna
--- The price after a coupon worth `off` cents.
after_coupon(price: Int, off: Int) -> Int
  requires price >= 0
  requires off >= 0
=
  if off > price then 0 else price - off

--- What is left of a gift card after it pays for an order.
left_on_card(card: Int, price: Int) -> Int
  requires card >= 0
  requires price >= 0
  ensures result >= 0
=
  let due = after_coupon(price, off: card)
  card - (price - due)

Read the body of after_coupon, and the promise of left_on_card holds: the coupon never takes off more than the price. But una check . refutes it:

Diagnostic
[U5001] Error: postcondition of `left_on_card` is refuted
    ╭─[ src/coupons.una:17:3 ]
    │
 14 │   ensures result >= 0
    │           ─────┬─────
    │                ╰─────── ensures clause
    │
 17 │   card - (price - due)
    │   ──────────┬─────────
    │             ╰─────────── postcondition of `left_on_card` is refuted
    │
    │ Help 1: repair 1: add a guard or an arm so that the failing path returns a value for which `result >= 0` holds
    │
    │ Help 2: repair 2: adjust the `ensures` clause
    │
    │ Note 1: obligation ob-3376a2cf2fdd (postcondition) is refuted: result >= 0
    │
    │ Note 2: counterexample: card = 0, price = 0, result = -1
    │
    │ Note 3: run `una explain U5001` for an explanation
────╯

The verifier does not read the body of after_coupon when it checks left_on_card. It reads only its header, and the header says nothing about the result, so due could be any whole number. Note 2 shows a card of 0 and a price of 0 for which the result is −1. For that, due must be −1, which the counterexample leaves out. It is not a run: the real after_coupon never returns a negative due. It is what the header allows.

There is a reason the verifier works this way. If it read every body, a change to the body of after_coupon could silently break a proof in left_on_card, or in any of a hundred callers. By reading headers only, each function is checked once, against its own contract, and a caller depends on the promise, not on the code behind it. So a function promises in its header exactly what its callers need.

5.2.3 How to write ensures

An ensures clause is the word ensures and a condition, on its own line under the header, before =. It sits with the requires clauses, after them, and a function may have any number of each. The condition may read the parameters, as the caller passed them, and result, the value the function returns. Like requires, it is written in the refinement language.

5.2.3.1 A bound on the result

The rate of a parcel is never below 4.50, whatever it weighs:

steps/07-forms/src/fees.unauna
--- The rate of a parcel of `grams` grams: 450 cents for the first kilogram, and 250 more
--- for each kilogram or part of one after it. The clause states a lower bound.
pub parcel_rate(grams: Int) -> Int
  requires grams > 0
  ensures result >= 450
=
  let kilos = (grams + 999) / 1_000
  450 + (kilos - 1) * 250

ensures result >= 450 is a bound: it does not say what the rate is, only how low it can go. It needs the precondition. Take requires grams > 0 away:

src/fees.unadiff
--- a/src/fees.una
+++ b/src/fees.una
@@ -11,3 +11,2 @@
 pub parcel_rate(grams: Int) -> Int
-  requires grams > 0
   ensures result >= 450
Diagnostic
[U5001] Error: postcondition of `parcel_rate` is refuted
    ╭─[ src/fees.una:15:3 ]
    │
 12 │   ensures result >= 450
    │           ──────┬──────
    │                 ╰──────── ensures clause
    │
 15 │   450 + (kilos - 1) * 250
    │   ───────────┬───────────
    │              ╰───────────── postcondition of `parcel_rate` is refuted
    │ Note 2: counterexample: grams = -999, result = 200

The verifier found a weight that breaks the promise: grams = -999. A parcel of minus 999 grams makes kilos 0, and the rate 200. No parcel weighs less than nothing, but nothing in the function said so, and a caller could pass such a value. requires grams > 0 rules out every weight of zero or below, and with it the promise holds. This is how the two halves work together: the precondition limits the inputs, and the postcondition is proven for those inputs only.

5.2.3.2 The exact result

A clause can state the result exactly, with ==:

steps/07-forms/src/fees.unauna
--- The amount with the card fee of 50 cents added. The clause states the exact result.
pub with_card_fee(cents: Int) -> Int
  ensures result == cents + 50
=
  cents + 50

A caller then knows everything the function does from its header alone.

5.2.3.3 A promise for some cases: implies

A promise may cover only the cases a caller needs. status promises what an empty shelf and a full one give, and says nothing about the shelves in between. It returns a variant of a sum kind:

steps/09-promises/src/stockroom.unauna
--- How full a shelf is.
kind Shelf = Empty | Low | Stocked
steps/09-promises/src/stockroom.unauna
--- How full a shelf of `units` units is. The clauses state the two cases a caller relies on,
--- and leave the case between them to the body.
status(units: Int) -> Shelf
  requires units >= 0
  ensures units == 0 implies result is Empty
  ensures units >= 10 implies result is Stocked
=
  if units == 0 then Empty else if units < 10 then Low else Stocked

result is Empty tests the variant of the result. units == 0 implies result is Empty holds for every input: when units is not 0, it says nothing.

5.2.3.4 A Bool result

A clause can give the whole answer of a function that returns a Bool:

steps/09-promises/src/stockroom.unauna
--- Whether an order ships free. The clause gives the whole answer.
free_shipping(total: Int) -> Bool
  ensures result == (total >= 5000)
=
  total >= 5000

result == (total >= 5000) compares two Bool values: the result is true exactly when the total is at least 5000.

5.2.3.5 Fields of the result

A promise may speak of the fields of a record result:

steps/09-promises/src/stockroom.unauna
--- How `units` units pack in boxes of 6, and how many stay loose.
kind Packing
  boxes: Int
  loose: Int
steps/09-promises/src/stockroom.unauna
--- How `units` units pack in boxes of 6. The clauses speak of the fields of the result.
pack(units: Int) -> Packing
  requires units >= 0
  ensures result.boxes * 6 + result.loose == units
  ensures result.loose >= 0 and result.loose < 6
=
  Packing(boxes: units / 6, loose: units mod 6)

pack has two clauses, which hold together. The first relates the two fields: boxes of 6 and the loose units add up to units. The second bounds one field. result.boxes * 6 is allowed in a clause, since one side of the product is a literal.

5.2.3.6 The value before the call: old

A function can also change a value its caller passes in, with an edit parameter, which section 16.2 teaches; its ensures then names the value from before the call as old(name). Nothing in this chapter changes a parameter.

5.2.3.7 Running the promise forms

una run . in the two steps prints:

Output
with the card fee: 2040
500 g: 450, 2300 g: 950
1001 g: 700, 2000 g: 700
Output
Empty Low Stocked
free shipping at 4999: false, at 5000: true
20 units: 3 boxes and 2 loose

5.2.4 A coupon that never goes negative

A coupon is a good first case of a real rule. It takes some cents off a price, and two rules hold whatever the coupon: the price never becomes negative, and it never goes up.

steps/10-ensures/src/coupons.unacheckruntestuna
module coupons

--- The price after a coupon worth `off` cents. A coupon never makes a price negative, and
--- never raises it.
after_coupon(price: Int, off: Int) -> Int
  requires price >= 0
  requires off >= 0
  ensures result >= 0
  ensures result <= price
  ensures off <= price implies result == price - off
=
  if off > price then 0 else price - off

--- What is left of a gift card after it pays for an order.
left_on_card(card: Int, price: Int) -> Int
  requires card >= 0
  requires price >= 0
  ensures result >= 0
=
  let due = after_coupon(price, off: card)
  card - (price - due)

pub main() -> Unit
  uses @console: Console[print]
=
  @console.print("{after_coupon(1990, off: 500)} {after_coupon(300, off: 500)}")
  @console.print("{left_on_card(5000, price: 1990)} {left_on_card(1000, price: 1990)}")

example "a coupon worth more than the price gives 0"
  do after_coupon(0, off: 1)
  expect result == 0
  1. ensures result >= 0 and ensures result <= price. The two rules. They hold on both branches of the if, and the verifier proves each one.
  2. ensures off <= price implies result == price - off. A third clause says what the result is when the coupon fits. It says nothing when off > price.
  3. left_on_card. A caller. It knows after_coupon only by its header. With the first two clauses alone, it knows only that due is between 0 and price, which is not enough to prove result >= 0. The third clause gives it what it needs.
  4. example "a coupon worth more than the price gives 0". The example. It pins down the case where the coupon is worth more than the price. From a counterexample to an example shows where it comes from.

una run . prints:

Output
1490 0
3010 0

5.2.5 Reading a counterexample

Now write the body most people write first, price - off, and check:

src/coupons.unadiff
--- a/src/coupons.una
+++ b/src/coupons.una
@@ -11,3 +11,3 @@
 =
-  if off > price then 0 else price - off
+  price - off
 
Diagnostic
[U5001] Error: postcondition of `after_coupon` is refuted
    ╭─[ src/coupons.una:12:3 ]
    │
  8 │   ensures result >= 0
    │           ─────┬─────
    │                ╰─────── ensures clause
    │
 12 │   price - off
    │   ─────┬─────
    │        ╰─────── postcondition of `after_coupon` is refuted
    │
    │ Help 1: repair 1: add a guard or an arm so that the failing path returns a value for which `result >= 0` holds
    │
    │ Help 2: repair 2: adjust the `ensures` clause
    │
    │ Note 1: obligation ob-3bf1d4af758b (postcondition) is refuted: result >= 0
    │
    │ Note 2: counterexample: off = 1, price = 0, result = -1
    │
    │ Note 3: run `una explain U5001` for an explanation
────╯

Read it in four steps:

  1. The first line names the promise that failed: the postcondition of after_coupon.
  2. The two marks point at the clause it breaks, ensures result >= 0 on line 8, and at the returned expression, price - off on line 12.
  3. Help 1 and Help 2 are the two repairs: change the body, or change the clause. The verifier cannot tell which one is wrong. That is your decision.
  4. Note 2 is the counterexample, off = 1, price = 0, result = -1: a coupon of 1 cent on a free item. Run the body by hand on those values and the result is −1, so the rule is broken.

The solver often picks the smallest numbers that break the rule, such as 0 and 1, so a case that looks artificial usually stands for a real one: here, any coupon worth more than its order.

5.2.5.1 When the body calls other functions

When the body has no calls, as here, a counterexample is a case you can run by hand. When the body calls other functions, the verifier knows each call only by the callee's header, so a call's result in the counterexample can be any value that header allows, even one the callee never returns, as in Why callers need a promise. Then the values are not a run, but they still point at the problem: the body relies on something the callee does not promise.

5.2.6 From a counterexample to an example

Two things to do with a counterexample:

  1. Fix the code or the contract. Here the code is wrong: a coupon larger than the price must give 0. Sometimes the contract promises more than you meant.
  2. Keep the case as an example, when it is a run, as this one is. The example in coupons.una, written as in chapter 1, is this counterexample. The proof already covers it, but the example documents the case for a reader and shows it in una test .:
Output
example coupons "a coupon worth more than the price gives 0" ... ok

1 example: 1 passed, 0 failed

5.2.7 How a postcondition is checked

5.2.7.1 Every path that returns

A body can return in several places: each branch of an if, each arm of a when. The verifier proves each ensures clause on every one of them, with the facts of that path: the function's requires, the condition of the branch, and the promises of the calls made on the way. One path that breaks the clause is enough for U5001, and the diagnostic points at that path's returned expression.

5.2.7.2 What a caller gets

After a call, the caller may assume every ensures clause of the callee, with its own arguments in place of the parameters. After let due = after_coupon(price, off: card), left_on_card knows due >= 0, due <= price, and card <= price implies due == price - card. Promises add up: each function's ensures is a fact for the next one, and in the day-to-day program a chain of them proves that no total is negative.

The standard library has contracts too, and the verifier trusts them without reading their bodies. min, the smaller of two whole numbers (section 2.2), as in min(total / 100, b: 100), promises a result no larger than either argument, and equal to one of them.

5.2.7.3 A promise the body does not keep

Raise the promised minimum of parcel_rate to 500:

src/fees.unadiff
--- a/src/fees.una
+++ b/src/fees.una
@@ -13 +13 @@
-  ensures result >= 450
+  ensures result >= 500
Diagnostic
[U5001] Error: postcondition of `parcel_rate` is refuted
    ╭─[ src/fees.una:16:3 ]
    │
 13 │   ensures result >= 500
    │           ──────┬──────
    │                 ╰──────── ensures clause
    │
 16 │   450 + (kilos - 1) * 250
    │   ───────────┬───────────
    │              ╰───────────── postcondition of `parcel_rate` is refuted
    │ Note 2: counterexample: grams = 1000, result = 450

The counterexample is a parcel of 1000 g, for which the body returns 450. Either the body or the clause is wrong, and here it is the clause: the rate of the first kilogram is 4.50.

5.2.7.4 What ensures does not cover

Note

ensures describes normal returns only. A function that fails, which section 7.2 teaches, returns no value on that path, and its postcondition says nothing about it. Contracts also do not prove that a function ends: they hold if it returns.

5.2.7.5 What an ensures clause may say

result is allowed only in ensures, and in the expect lines of examples (U2012 elsewhere). The rest of the rules of a requires clause apply: the parameters, the refinement language, and no calls but of the predicates of section 5.3.

5.2.8 A contract or an example

A postcondition and an example both say something about the result, but not the same thing:

Which to use:

You want to… Use
State a rule that holds for every input, such as "never negative" ensures
Give callers a fact they need to prove their own contracts ensures
Pin down one exact answer, such as "10% of 188.85 is 18.88" an example
Keep a counterexample as a case a reader can see an example
Describe what the function is for, in words a doc comment (---)

How much to promise is a choice. Promise what the callers need and what will stay true. A promise that states the exact result, as free_shipping's does, gives callers the most, and ties the body to it for good. A bound, such as result <= price, leaves the body free to change, for example to round differently.

5.2.9 Check yourself: postconditions

points gives a customer one loyalty point for each whole 1.00, and at most 100 points for one order:

steps/09-promises/src/stockroom.unauna
--- The loyalty points of an order: one for each whole 1.00, and at most 100.
points(total: Int) -> Int
  requires total >= 0
  ensures result >= 0
  ensures result <= 100
=
  min(total / 100, b: 100)

Does it check? And what does points(25000) return?

Show the answer

It checks. The body is a call of min, whose contract promises a result no larger than b, which is 100, and equal to one of its two arguments. total / 100 is at least 0, since total is, and 100 is too, so the result is at least 0. Both clauses follow from the promise of min, without a branch in the body.

Output
points for 250.00: 100

25000 cents is 250 whole units of 1.00, and min keeps it at 100.

A second one: what may a caller assume about status(5)?

Show the answer

Nothing but its type: the result is a Shelf. Both clauses of status speak of other inputs, 0 and from 10 up, so for 5 they say nothing. The body returns Low, but a caller cannot rely on that, since the header does not promise it. To let callers rely on it, add ensures units >= 1 and units < 10 implies result is Low.

Next:5.3 Refined kinds and predicates