Home / Learn / 5 Contracts and the verifier
5.3 Refined kinds and predicates
Page 4 of 11
5.3.1 A rule on the kind
A type says what sort of value a name holds: Int holds whole numbers, Text holds texts, and a kind declares a type of your own (chapter 4). A refined kind is a type with a condition attached: a base type, and a rule that every value of the kind obeys. kind Cents = Int where it >= 0 is the whole numbers that are not negative. In the condition, it stands for the value.
Think of a parcel locker that only takes parcels below a size. A parcel that got in fits, and nobody measures it again. A refined kind is that locker: a value is checked once, when it enters the kind, and everyone who receives a Cents knows it is not negative.
5.3.2 Why put a rule on a kind
A price in cents is never negative. With preconditions alone, every function that takes a price must say so, and every function that returns one must promise it:
module prices
--- The price after a coupon worth `off` cents. A price is never negative, so the clauses say
--- so.
after_coupon(price: Int, off: Int) -> Int
requires price >= 0
requires off >= 0
ensures result >= 0
=
if off > price then 0 else price - off
--- The price with a shipping fee added. The same rule, written again.
with_fee(price: Int, fee: Int) -> Int
requires price >= 0
requires fee >= 0
ensures result >= 0
=
price + fee
--- The price after a markdown of `cut` cents. This function forgot the rule.
marked_down(price: Int, cut: Int) -> Int = price - cut
pub main() -> Unit
uses @console: Console[print]
=
@console.print("after a coupon: {after_coupon(1990, off: 500)}")
@console.print("with a fee: {with_fee(1990, fee: 495)}")
@console.print("on the shelf label: {marked_down(1990, cut: 2500)} cents")una run . prints:
after a coupon: 1490
with a fee: 2485
on the shelf label: -510 centsThe program checks, and the last line prints a negative price on a shelf label. The rule "a price is never negative" lives in the clauses of each function, written again each time, and marked_down forgot it. Nothing connects the three functions: they all take an Int, and an Int may be anything.
Put the rule on a kind, Cents, and make it the type of every price. Then the rule is written once, a function that returns Cents must prove it on every path, and a function that receives Cents gets it for free. marked_down with a result of type Cents would not check: price - cut is negative whenever the cut is larger than the price, and the verifier would refute it with such a case.
5.3.3 How to write a refined kind
A refined kind is a kind declaration with three parts: its name, = and the base type, then the condition after where. The condition reads the value as it, and is written in the refinement language, like requires and ensures. The step of this part shows every form:
--- An amount of money in cents. It is never negative.
kind Cents = Int where it >= 0
--- A discount in whole percent, from 0 to 100: `..` keeps both ends.
kind Percent = Int in 0..100
--- A slot on a shelf of 12 slots, numbered from 0: `..<` leaves 12 out.
kind Slot = Int in 0..<12
--- A staff discount: a `Percent` of at most 50. It holds both conditions.
kind StaffDiscount = Percent where it <= 50
--- A SKU, such as `LAMP-01`: at least four characters.
kind Sku = Text where it.len >= 4
--- One line of a delivery. The quantity is refined in place, with `in`.
kind Line
sku: Text
quantity: Int in 1..99
--- A line of at least 10 units, which earns free units.
kind BulkLine = Line where it.quantity >= 105.3.3.1 A condition with where
kind Cents = Int where it >= 0 is the general form. The prelude, the names every module can use without declaring them, already has a kind like Cents: Nat, which is Int where it >= 0. Any condition of the refinement language works: comparisons, and, or, not, implies, and calls of the predicates of this section.
5.3.3.2 A range with in
Int in 0..100 is short for Int where 0 <= it and it <= 100: .. keeps both ends. Int in 0..<12 leaves the end out, which fits a count of positions: 12 slots numbered 0 to 11. next_slot moves to the next slot and wraps around:
--- The next slot of the shelf, back to 0 after the last one.
next_slot(slot: Slot) -> Slot = if slot < 11 then slot + 1 else 0The result is a Slot, so the verifier proves both branches: slot + 1 is below 12 when slot < 11, and 0 is in range.
5.3.3.3 Refinements of refinements, and type arguments
A refinement of a refined kind adds its condition to the first: kind Small = Cents where it < 100 is both >= 0 and < 100. In the step, a staff discount is a Percent of at most 50, so a value of it holds both conditions:
--- What a staff member pays, in percent of the price: always at least half.
staff_pays(rate: StaffDiscount) -> Percent
ensures result >= 50
=
100 - rate100 - rate is a Percent, and at least 50, because rate is between 0 and 50.
Important
In editions 0.1 and 0.2, which this book uses, a refined kind cannot be the type argument of a generic kind (section 4.4): with kind Change[T], the type Change[Cents] is ill-formed (U2002), and the diagnostic asks for the base type, Change[Int]. Put the refinement on a field of a record instead, as Line does with quantity. Edition 0.3 allows refined type arguments (chapter 19).
5.3.3.4 Texts and records
The base can be any type. A condition on a text usually reads its length, and a condition on a record reads its fields:
--- The product family of a SKU: its first four characters.
family(sku: Sku) -> Text = sku.slice(start: 0, end: 4)
--- The free units of a bulk line: one for every 10 units.
free_units(line: BulkLine) -> Int
ensures result >= 1
=
line.quantity / 10Skuis a text of at least four characters, sofamilycan cut four characters withslicewith no clause of its own: the kind carries the fact.BulkLineis aLinewhose quantity is at least 10, sofree_unitscan promise at least one free unit.
5.3.3.5 A range in place
A range can also be written right where a type goes, without a kind: on a field, as quantity: Int in 1..99 in Line, or on a parameter:
--- Where to put a box: a row from 1 to 5, refined in place, and a slot.
place(row: Int in 1..5, slot: Slot) -> Text = "row {row}, slot {slot}"A where cannot be written in place: a condition other than a range needs a named kind.
5.3.3.6 Running the kind forms
main calls each function. Among its lines:
after slot 4: 5, after slot 11: 0
family of LAMP-01: LAMP
row 2, slot 75.3.4 Cents, quantities and free shipping
Now the kinds at work in a cart, with a predicate, a named condition that Predicates explains in full:
module cart
--- An amount of money in cents. It is never negative.
kind Cents = Int where it >= 0
--- How many units of one SKU a line may order.
kind Quantity = Int in 1..99
--- One line of a cart.
kind Line
sku: Text
unit_cents: Cents
quantity: Quantity
--- An order ships free from 50.00.
predicate reflect ships_free(total: Cents) -> Bool = total >= 5000
--- What shipping costs for an order of `total` cents.
shipping(total: Cents) -> Cents
ensures ships_free(total) implies result == 0
=
if ships_free(total) then 0 else 495
--- The line with one more unit, up to the limit of a line.
one_more(line: Line) -> Line
=
if line.quantity < 99
Line(sku: line.sku, unit_cents: line.unit_cents, quantity: line.quantity + 1)
else
line
pub main() -> Unit
uses @console: Console[print]
=
let lamp = Line(sku: "LAMP-01", unit_cents: 1990, quantity: 2)
let more = one_more(lamp)
@console.print("{more.quantity} x {more.sku}")
@console.print("shipping {shipping(3980)}, then {shipping(5970)}")kind Cents = Int where it >= 0. A function that takesCentsmay assume it; one that returnsCentsmust prove it.quantity: Quantity. A field of a refined kind. Building aLineproves the field's condition, and readingline.quantitygives the fact back.predicate reflect ships_free(total: Cents) -> Bool = total >= 5000. A named condition. Code may call it like any function, asshippingdoes.ensures ships_free(total) implies result == 0. A contract that names a business rule reads as the rule.if line.quantity < 99. Anifover several lines (section 3.4).line.quantity + 1entersQuantityagain, and the guard proves that it fits. Without the guard, the verifier refutes it with a line of 99 units, as A value that does not fit shows.
una run . prints:
3 x LAMP-01
shipping 495, then 05.3.5 How a refined kind is checked
5.3.5.1 Where a value enters the kind
The verifier proves the condition at every place a value enters the kind: an argument, a returned value, a field of a record, and a let with the kind written, such as let total: Cents = gross - off. The other way needs no proof: a Cents goes wherever an Int goes.
So the work happens at the edges. shipping returns 0 or 495, and the verifier proves each is a Cents. Line(sku: "LAMP-01", unit_cents: 1990, quantity: 2) proves 1990 >= 0 and 2 in 1..99. A function that only passes a Cents along has nothing new to prove.
5.3.5.2 What a value of the kind gives back
Wherever a value of a refined kind is read, its condition is a fact: a parameter of the kind, a field, the result of a call that returns the kind. family cuts a Sku without a clause, because the condition comes with the value.
5.3.5.3 A value that does not fit
Take the guard out of one_more, and add a unit whatever the quantity:
--- a/src/cart.una
+++ b/src/cart.una
@@ -23,9 +23,4 @@
---- The line with one more unit, up to the limit of a line.
-one_more(line: Line) -> Line
-=
- if line.quantity < 99
- Line(sku: line.sku, unit_cents: line.unit_cents, quantity: line.quantity + 1)
- else
- line
+--- The line with one more unit.
+one_more(line: Line) -> Line = Line(sku: line.sku, unit_cents: line.unit_cents, quantity: line.quantity + 1)
[U5001] Error: refinement `(line.quantity + 1) in 1..99` is refuted
╭─[ src/cart.una:25:91 ]
│
7 │ kind Quantity = Int in 1..99
│ ──┬──
│ ╰──── range
│
25 │ one_more(line: Line) -> Line = Line(sku: line.sku, unit_cents: line.unit_cents, quantity: line.quantity + 1)
│ ────────┬────────
│ ╰────────── refinement `(line.quantity + 1) in 1..99` is refuted
│
│ Help 1: repair 1: add `requires (line.quantity + 1) in 1..99` to the enclosing function; its callers then prove it
│
│ Help 2: repair 2: add a guard (`if` or a `when` arm) that handles the values where `(line.quantity + 1) in 1..99` does not hold
│
│ Help 3: repair 3 (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, (line.quantity + 1) in 1..99) else fail <Variant>`
│
│ Note 1: obligation ob-2a5905c8f53d (refinement) is refuted: (line.quantity + 1) in 1..99
│
│ Note 2: counterexample: line = Line#0, line.quantity = 99, line.sku = Text#0, line.unit_cents = 0
│
│ Note 3: run `una explain U5001` for an explanation
────╯The goal is the condition of Quantity with the new value in place of it: (line.quantity + 1) in 1..99. The mark on 1..99 is labeled range, the declaration it comes from. The counterexample is a line of 99 units, the most a line may hold: one more would be 100. Line#0 and Text#0 stand for a line and a text the solver chose, and line.unit_cents = 0 is one value it picked; only line.quantity matters here.
5.3.6 Predicates: named conditions
A predicate is a named condition: a function that returns a Bool, which contracts and kinds may call. It turns a rule of the business into a word, so requires fits(off, price) reads as the rule it states.
5.3.6.1 Why name a condition
The same condition tends to appear in many places: "an order ships free from 50.00" in a precondition, a postcondition, a kind and a branch of code. Written out each time, the places can drift apart, and a change of the threshold must find them all. A predicate states the rule once, under a name, and every clause that uses it changes with it.
5.3.6.2 How to write a predicate
predicate reflect name(parameters) -> Bool = condition: the word predicate, the word reflect, a name, typed parameters, the result type Bool, and a body of one condition after =. reflect means the verifier sees the body: when a clause calls the predicate, the verifier reads it as its body with the arguments in place.
A reflect predicate uses no capabilities, cannot fail, and returns a value for every input. Its body is written in the refinement language. It may call other reflect predicates, but never itself, directly or through another predicate (U2015). The other kind, an opaque predicate, whose body the verifier does not see, comes with the run-time tests of section 7.5.
5.3.6.3 Where a predicate is used
The step declares three predicates and uses them in every place a condition goes:
--- An amount of money in cents. It is never negative.
kind Cents = Int where it >= 0
--- An order ships free from 50.00.
predicate reflect ships_free(total: Cents) -> Bool = total >= 5000
--- A coupon fits a price when it takes off no more than the price.
predicate reflect fits(off: Cents, price: Cents) -> Bool = off <= price
--- An order ready to ship as a gift: it ships free, and no coupon was used. One predicate
--- may call another.
predicate reflect gift_ready(total: Cents, off: Cents) -> Bool = ships_free(total) and off == 0
--- An order total that ships free: a predicate in a `where` clause.
kind FreeTotal = Cents where ships_free(it)
--- The price after a coupon: a predicate in `requires`.
after_coupon(price: Cents, off: Cents) -> Cents
requires fits(off, price)
=
price - off
--- What shipping costs: a predicate in `ensures`, and in code.
shipping(total: Cents) -> Cents
ensures ships_free(total) implies result == 0
=
if ships_free(total) then 0 else 495
--- The note on a packing slip: a predicate of two arguments, called in code.
slip_note(total: Cents, off: Cents) -> Text = if gift_ready(total, off) then "gift wrap" else "standard"
--- The thank-you line of an order that ships free. It takes a `FreeTotal`, so it needs no
--- check of its own.
thank_you(total: FreeTotal) -> Text = "{total} cents, shipped free"- In
requires:after_couponrequiresfits(off, price), so its body may computeprice - offand return aCents. The verifier readsfitsasoff <= price. - In
ensures:shippingpromisesships_free(total) implies result == 0. - In a
whereclause:FreeTotalis theCentsthat ship free.thank_youtakes one, so it is never called for an order that pays for shipping. - In code:
shippingandslip_notecall predicates in anif, like ordinary functions. - In another predicate:
gift_readycallsships_free.
una run . prints:
after a coupon: 1490
shipping 495, then 0
gift wrap, standard
6200 cents, shipped freethank_you(6200) proves that 6200 is a Cents and that ships_free(6200) holds, which the verifier computes from the body of ships_free.
5.3.7 The refinement language
The condition of a refinement, and every requires and ensures clause, is written in the refinement language, the part of Una the solver decides:
- whole number,
Booland text literals, the parameters,result,it, fields, and.len; +,-and unary-;*when one side is a literal;/andmodby a literal that is not zero;- the comparisons
==,!=,<,<=,>,>=, andina range,isa variant; and,or,not,implies;- calls of
reflectpredicates.
Anything else in a clause, such as the product of two parameters, is U2014 (a contract outside the refinement language). Some things look allowed and are not: ordering two texts with <, comparing with a variant by == (write is), and calls of ordinary functions. A clause that needs one of these needs a different statement of the rule.
5.3.8 A precondition, a refined kind or a predicate
Several tools state a rule about a value. Choose by where the rule belongs:
Which to use:
| The rule… | Use |
|---|---|
| Holds of every value of a type, wherever it goes, such as "a price is never negative" | a refined kind |
| Is about one function's arguments together, such as "the coupon is no larger than the price" | requires |
| Relates the result to the arguments | ensures |
| Has a name in the business, and appears in several clauses | a reflect predicate, used in them |
| Can only be decided by running code, such as the format of a barcode | a test at run time (section 7.5) |
| Concerns data from outside the program | a check where it enters (section 7.6) |
A refined kind is usually the strongest choice: one declaration, checked at every way in, and a fact at every use. A precondition fits rules that tie several parameters together, which no single type can carry.
5.3.9 Check yourself: refined kinds and predicates
staff_pays takes a StaffDiscount, a Percent of at most 50, and promises a result of at least 50:
--- A staff discount: a `Percent` of at most 50. It holds both conditions.
kind StaffDiscount = Percent where it <= 50What does staff_pays(30) return? Which of these calls check: staff_pays(0), staff_pays(50), staff_pays(60)?
Show the answer
staff pay 70% and 50%staff_pays(30) is 70. staff_pays(0) and staff_pays(50) check: both values are in 0..100 and at most 50. staff_pays(60) does not: 60 is a Percent, but not a StaffDiscount, and the refinement is refuted at the call.
A bulk line is a Line of at least 10 units. What does free_units(Line(sku: "RUG-07", quantity: 24)) return, and what would happen with a quantity of 9?
Show the answer
free units: 224 units give two free units: 24 / 10 rounds down to 2. With 9 units the call does not check: free_units takes a BulkLine, and the verifier refutes the condition of BulkLine where the line enters the kind. The program never runs with a bulk line of 9 units.