Home / Docs / Examples

toolshelf

Release v0.4.0

A community tool shelf: members check tools out for a number of days and bring them back, under two house rules.

The house rules are business rules of the kind that usually live in a wiki and in scattered if statements. Here each rule is a requirement, the limits are types, and the functions that apply the rules carry contracts that the solver proves for every input. The example also falls back from one shelf to another, which shows attempt and with working together.

What it demonstrates:

Run it

From this directory:

sh
una check .   # copy examples/toolshelf
una test .
una report .
una run .
una build .
./target/una/toolshelf-example

una run . and the native executable print:

una run .Output
Ana took the ladder for 14 days
returned 20 days later, it is 6 days late

The checkout is due 14 days after today, so a return 20 days after today is 6 days late. The output does not depend on the date, although main reads the clock. una test . runs the examples of both modules:

una test .Output
example toolshelf.desk "the backup shelf has what the main shelf lacks" ... ok
example toolshelf.desk "the main shelf is tried first" ... ok
example toolshelf.tools "a member with room takes a tool for a week" ... ok
example toolshelf.tools "a tool that is not on the shelf cannot be taken" ... ok
example toolshelf.tools "a shelf that is offline stops the checkout" ... ok
example toolshelf.tools "bringing a tool back frees a place" ... ok
example toolshelf.tools "a tool returned three days after its due day is three days late" ... ok

7 examples: 7 passed, 0 failed

How it works

The package has three modules: toolshelf.tools, the rules and the shelf; toolshelf.desk, the fallback between two shelves; and toolshelf.main, the program.

The rules

src/toolshelf/tools.unauna
requirement SHELF_1
  text "A member holds at most three tools at a time"
  source human
  owner front_desk
  status active

requirement SHELF_2
  text "A checkout lasts from one to twenty-eight days"
  source policy "Tool Shelf Rules 3"
  owner front_desk
  status active

Each rule then appears twice in the code: as a type that makes a wrong value impossible to build, and as a contract on the function that changes the value.

src/toolshelf/tools.unauna
pub kind KeepDays = Int in 1..28

...
pub kind Member
  name: Text
  holding: Int in 0..3

KeepDays is SHELF_2. A Member whose holding is 4 cannot exist, which is SHELF_1.

Predicates the solver can read

src/toolshelf/tools.unauna
pub predicate reflect can_check_out(m: Member) -> Bool = m.holding < 3

...
pub predicate reflect overdue(checkout: Checkout, today: Day) -> Bool = today > checkout.due

reflect makes the body visible to the solver, so it can reason with the predicate. The name still documents the intent: a contract that says requires can_check_out(member) reads as the rule, not as arithmetic.

Checking a tool out

src/toolshelf/tools.unauna
pub check_out(member: Member, name: Text, today: Day, days: KeepDays) -> Checkout
  requires can_check_out(member)
  ensures result.due == today + days
  ensures result.member.holding == member.holding + 1
  uses @shelf: Shelf[pick]
  fails CheckoutError
  derived from SHELF_1, SHELF_2
=
  let tool = @shelf.pick(name)
    if error fail ShelfDown
    if none fail NotOnShelf(tool: name)
  Checkout(tool, member: Member(name: member.name, holding: member.holding + 1), due: today + days)

The header is the whole story for a reviewer: what the function needs, what it promises, what it may touch, how it can fail, and which rules it implements. The requires is what makes member.holding + 1 fit in 0..3. bring_back is the mirror image: it requires checkout.member.holding > 0 and promises one tool less.

late_days shows how two ensures can pin a function down against a predicate: the result is positive exactly when the checkout is overdue, and zero otherwise.

Falling back to a second shelf

src/toolshelf/desk.unauna
pub check_out_anywhere(member: Member, name: Text, today: Day, days: KeepDays) -> Checkout
  requires can_check_out(member)
  ensures result.due == today + days
  uses @main_shelf: Shelf[pick]
  uses @backup_shelf: Shelf[pick]
  fails CheckoutError
=
  let first_try = attempt check_out(member, name, today, days) with @shelf = @main_shelf
  when first_try
    is Ok(checkout) -> checkout
    is Err ->
      check_out(member, name, today, days) with @shelf = @backup_shelf
        if error pass

check_out uses a capability called @shelf. The desk holds two shelves under other names, and binds @shelf to one of them for each call with with. attempt keeps the first outcome as a Result, so a failure of the main shelf leads to the backup instead of out of the function. if error pass lets a failure of the backup leave the function unchanged, as a CheckoutError. The ensures follows from check_out's own, on both paths.

The program

main reads the clock and turns milliseconds into days with now / 86_400_000. It is the only function that touches the host, and una.toml grants it the console and the clock: grants = ["console", "clock"]. The shelf in main is the shelf_with handler over a fixed catalog.

What una check proves

una obligations . lists 42 obligations, all proven:

una trace SHELF_1 shows the rule with what implements it:

una trace SHELF_1Output
requirement SHELF_1 (active)
  text "A member holds at most three tools at a time"
  source human
  owner front_desk
toolshelf.tools.bring_back
  requires checkout.member.holding > 0
  ensures result.holding == checkout.member.holding - 1
  proven   ob-2ecf6008288c postcondition result.holding == checkout.member.holding - 1
  proven   ob-938f9eb8fced refinement    (checkout.member.holding - 1) in 0..3
toolshelf.tools.check_out
  requires can_check_out(member)
  ensures result.due == today + days
  ensures result.member.holding == member.holding + 1
  proven   ob-46cea04ba61e postcondition result.due == today + days
  proven   ob-f7b9f3eae75c postcondition result.member.holding == member.holding + 1
  proven   ob-c04f1a76c228 refinement    (member.holding + 1) in 0..3

Common mistakes

Applying a rule without checking it

Delete the requires can_check_out(member) line of check_out. A member who already holds three tools could take a fourth:

Diagnostic
[U5001] Error: refinement `(member.holding + 1) in 0..3` is refuted
    ╭─[ src/toolshelf/tools.una:62:61 ]
    │
 27 │   holding: Int in 0..3
    │                   ──┬─
    │                     ╰─── range
    │
 62 │   Checkout(tool, member: Member(name: member.name, holding: member.holding + 1), due: today + days)
    │                                                             ─────────┬────────
    │                                                                      ╰────────── refinement `(member.holding + 1) in 0..3` is refuted
    │
    │ Help 1: repair 1: add a guard (`if` or a `when` arm) that handles the values where `(member.holding + 1) in 0..3` does not hold
    │
    │ Help 2: repair 2 (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, (member.holding + 1) in 0..3) else fail <Variant>`
    │
    │ Note 1: obligation ob-c04f1a76c228 (refinement) is refuted: (member.holding + 1) in 0..3
    │
    │ Note 2: counterexample: days = 1, member = Member#0, member.holding = 3, member.name = Text#0, tool = Tool#0
    │
    │ Note 3: run `una explain U5001` for an explanation
────╯

The counterexample names the case: member.holding = 3.

A caller that breaks the rule

Put the requires back, and in the first example of tools.una give Ana three tools, Member(name: "Ana", holding: 3). The call in the example is now refuted:

Diagnostic
[U5001] Error: precondition `can_check_out(Member(name: "Ana", holding: 3))` of this call is refuted
    ╭─[ src/toolshelf/tools.una:96:6 ]
    │
 53 │   requires can_check_out(member)
    │            ──────────┬──────────
    │                      ╰──────────── requires clause
    │
 96 │   do check_out(Member(name: "Ana", holding: 3), name: "drill", today: 100, days: 7)
    │      ───────────────────────────────────────┬──────────────────────────────────────
    │                                             ╰──────────────────────────────────────── precondition `can_check_out(Member(name: "Ana", holding: 3))` of this call is refuted
    │
    │ Help 1: repair 1: add a guard (`if` or a `when` arm) that handles the values where `can_check_out(Member(name: "Ana", holding: 3))` does not hold
    │
    │ Help 2: repair 2 (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, can_check_out(Member(name: "Ana", holding: 3))) else fail <Variant>`
    │
    │ Note 1: obligation ob-1ce6f94f8309 (precondition) is refuted: can_check_out(Member(name: "Ana", holding: 3))
    │
    │ Note 2: run `una explain U5001` for an explanation
────╯

A checkout that is too long

In main, ask for the ladder for 30 days, days: 30:

Diagnostic
[U5001] Error: refinement `30 in 1..28` is refuted
    ╭─[ src/toolshelf/main.una:15:90 ]
    │
 15 │   let checkout = check_out(Member(name: "Ana", holding: 0), name: "ladder", today, days: 30) with @shelf = shelf_with(tools: catalog())
    │                                                                                          ─┬
    │                                                                                           ╰── refinement `30 in 1..28` is refuted
    │
    ├─[ src/toolshelf/tools.una:16:28 ]
    │
 16 │ pub kind KeepDays = Int in 1..28
    │                            ──┬──
    │                              ╰──── range
    │
    │ Note 1: obligation ob-6d88845711a7 (refinement) is refuted: 30 in 1..28
    │
    │ Note 2: run `una explain U5001` for an explanation
────╯

The rule is enforced where the value enters, in another module, with a pointer back to the type that states it.

Extend it

  1. Both shelves down. Add an example to desk.una where both shelves are offline_shelf(), and expect fails ShelfDown. Hint: import offline_shelf from toolshelf.tools.
  2. A late fee. Add pub late_fee(checkout: Checkout, today: Day) -> Nat, three units for each late day, with ensures not overdue(checkout, today) implies result == 0. Hint: reuse late_days. Add an example: a checkout due on day 10 and returned on day 16 costs 18.
  3. A fee the solver cannot prove. Make the fee a tenth of the tool's deposit for each late day: late_days(checkout, today) * (checkout.tool.deposit / 10). una check . now reports U5002, not U5001: the obligations are unknown, because the encoding of the solver's arithmetic (spec/12 §2) leaves a product of two values uninterpreted, as the diagnostic says. Unknown is not refuted. It means that the proof needs a different shape, such as a fee per day that is a constant, or a fee table chosen with when.

Learn more

Edition

Edition 0.1 (edition).

Files

una.tomltoml
[package]
name = "toolshelf-example"
version = "0.1.0"
edition = "0.1"

[run]
entry = "toolshelf.main"
grants = ["console", "clock"]
src/toolshelf/desk.unauna
module toolshelf.desk

import toolshelf.tools (Checkout, CheckoutError, Day, KeepDays, Member, Shelf, Tool, can_check_out, check_out, shelf_with)

--- Checks out from the main shelf, or from the backup shelf when the main one cannot.
pub check_out_anywhere(member: Member, name: Text, today: Day, days: KeepDays) -> Checkout
  requires can_check_out(member)
  ensures result.due == today + days
  uses @main_shelf: Shelf[pick]
  uses @backup_shelf: Shelf[pick]
  fails CheckoutError
=
  let first_try = attempt check_out(member, name, today, days) with @shelf = @main_shelf
  when first_try
    is Ok(checkout) -> checkout
    is Err ->
      check_out(member, name, today, days) with @shelf = @backup_shelf
        if error pass

example "the backup shelf has what the main shelf lacks"
  given @main_shelf = shelf_with(tools: [])
  given @backup_shelf = shelf_with(tools: [Tool(name: "saw", deposit: 15)])
  do check_out_anywhere(Member(name: "Bo", holding: 2), name: "saw", today: 10, days: 3)
  expect result.tool.name == "saw"
  expect result.due == 13
  expect performed @backup_shelf.pick

example "the main shelf is tried first"
  given @main_shelf = shelf_with(tools: [Tool(name: "drill", deposit: 20)])
  given @backup_shelf = shelf_with(tools: [])
  do check_out_anywhere(Member(name: "Ana", holding: 0), name: "drill", today: 10, days: 3)
  expect result.tool.name == "drill"
  expect not performed @backup_shelf.pick
src/toolshelf/main.unauna
module toolshelf.main

import toolshelf.tools (CheckoutError, Member, Tool, check_out, late_days, shelf_with)

--- The tools of the community shelf.
catalog() -> List[Tool] = [Tool(name: "drill", deposit: 20), Tool(name: "ladder", deposit: 35), Tool(name: "saw", deposit: 15)]

pub main() -> Unit
  uses @console: Console[print]
  uses @clock: Clock[now]
  fails CheckoutError
=
  let now = @clock.now()
  let today = now / 86_400_000
  let checkout = check_out(Member(name: "Ana", holding: 0), name: "ladder", today, days: 14) with @shelf = shelf_with(tools: catalog())
    if error pass
  @console.print("{checkout.member.name} took the {checkout.tool.name} for 14 days")
  let late = late_days(checkout, today: today + 20)
  @console.print("returned 20 days later, it is {late} days late")
src/toolshelf/tools.unauna
module toolshelf.tools

requirement SHELF_1
  text "A member holds at most three tools at a time"
  source human
  owner front_desk
  status active

requirement SHELF_2
  text "A checkout lasts from one to twenty-eight days"
  source policy "Tool Shelf Rules 3"
  owner front_desk
  status active

--- The number of days a member keeps a tool.
pub kind KeepDays = Int in 1..28

--- A day, counted from the Unix epoch.
pub kind Day = Int

pub kind Tool
  name: Text
  deposit: Nat

pub kind Member
  name: Text
  holding: Int in 0..3

pub kind Checkout
  tool: Tool
  member: Member
  due: Day

pub kind CheckoutError = NotOnShelf(tool: Text) | ShelfDown

pub kind ShelfError = | Offline

--- The shelf the tools are kept on.
pub capability Shelf
  op pick(name: Text) -> Option[Tool]
    fails ShelfError
  op bring_back(tool: Tool) -> Unit
    fails ShelfError

--- A member may take one more tool.
pub predicate reflect can_check_out(m: Member) -> Bool = m.holding < 3

--- A checkout is overdue after its due day.
pub predicate reflect overdue(checkout: Checkout, today: Day) -> Bool = today > checkout.due

--- Checks a tool out from the shelf for `days` days from `today`.
pub check_out(member: Member, name: Text, today: Day, days: KeepDays) -> Checkout
  requires can_check_out(member)
  ensures result.due == today + days
  ensures result.member.holding == member.holding + 1
  uses @shelf: Shelf[pick]
  fails CheckoutError
  derived from SHELF_1, SHELF_2
=
  let tool = @shelf.pick(name)
    if error fail ShelfDown
    if none fail NotOnShelf(tool: name)
  Checkout(tool, member: Member(name: member.name, holding: member.holding + 1), due: today + days)

--- Brings a taken tool back to the shelf.
pub bring_back(checkout: Checkout) -> Member
  requires checkout.member.holding > 0
  ensures result.holding == checkout.member.holding - 1
  uses @shelf: Shelf[bring_back]
  fails CheckoutError
  derived from SHELF_1
=
  @shelf.bring_back(checkout.tool)
    if error fail ShelfDown
  Member(name: checkout.member.name, holding: checkout.member.holding - 1)

--- The days a returned tool is late, zero when it is on time.
pub late_days(checkout: Checkout, today: Day) -> Nat
  ensures overdue(checkout, today) implies result > 0
  ensures not overdue(checkout, today) implies result == 0
=
  if today > checkout.due then today - checkout.due else 0

--- A shelf holding `tools`.
pub handler shelf_with(tools: List[Tool]) for Shelf
  op pick(name) = tools.first_where(keep: fn(t) -> t.name == name)
  op bring_back(tool) = unit

--- A shelf that cannot be reached.
pub handler offline_shelf() for Shelf
  op pick(name) = fail Offline
  op bring_back(tool) = fail Offline

example "a member with room takes a tool for a week"
  given @shelf = shelf_with(tools: [Tool(name: "drill", deposit: 20)])
  do check_out(Member(name: "Ana", holding: 1), name: "drill", today: 100, days: 7)
  expect result.due == 107
  expect result.member.holding == 2
  expect performed @shelf.pick

example "a tool that is not on the shelf cannot be taken"
  given @shelf = shelf_with(tools: [])
  do check_out(Member(name: "Ana", holding: 0), name: "saw", today: 100, days: 7)
  expect fails NotOnShelf

example "a shelf that is offline stops the checkout"
  given @shelf = offline_shelf()
  do check_out(Member(name: "Bo", holding: 0), name: "saw", today: 100, days: 3)
  expect fails ShelfDown

example "bringing a tool back frees a place"
  given @shelf = shelf_with(tools: [])
  do bring_back(Checkout(tool: Tool(name: "saw", deposit: 15), member: Member(name: "Bo", holding: 3), due: 10))
  expect result.holding == 2
  expect performed @shelf.bring_back

example "a tool returned three days after its due day is three days late"
  do late_days(Checkout(tool: Tool(name: "saw", deposit: 15), member: Member(name: "Bo", holding: 1), due: 10), today: 13)
  expect result == 3