Editable values and loops
Release v0.4.0
Values stay immutable and there are no references; what changes is which value a binding holds (spec/17).
let edit x = edeclares an editable binding, andx = eorx.field = erebinds it. Assigning anything else is U2019. An editable binding keeps its declared type, refinement and label at every rebind.- Without an annotation, the positions that its initial value leaves open, as the key and value of
empty_map()or the element of[], take the labels of everything assigned there, so a generictally[T: Ord](xs: List[T]) -> Map[T, Int]built withlet edit m = empty_map()checks, and its counts carry the labels ofT(ADR 0075). The binding's own top label stays the one its initial value gives it. - A parameter declared
edit p: Tis passed in and out: the caller writesedit placeand gets the final value back;old(p)inensuresis its value on entry.oldtakes the parameter itself, so writeold(xs).len, notold(xs.len)(U2012). A method receiver is marked before it:edit tally.record(amount). - A parameter declared
take p: Tconsumes its argument: the caller writestake x, andxcannot be used afterwards (U2017) until it is assigned again. - Markers match declarations exactly (U2020); an
editargument and another use of the same binding in one call is U2018; a function witheditortakeparameters cannot be used as a value (U2021). A call with a marker is the whole expression of its statement. for x in xsvisits a list in order, andfor i in a..bora..<bthe integers of a range; the bounds are evaluated once, before the first iteration. The loop variable has the element type, or the integer type of the bounds. There is nobreakorcontinue. The refinements of the bindings a loop updates are its invariant; no other fact about them survives the loop.if cwith an indented block and noelseis a statement.edit xs.set(index: i, item: v)replaces a list element.- A loop keeps the length of a list it changes only with
set, or with a helper whoseensuresis exactlyxs.len == old(xs).len, sofor i in 0..<xs.lenwithedit xs.set(index: i, item: v)verifies. After anappendor any other change, the loop forgets the length, and a check that needs it is U5002, "the loop forgets every fact about the listxs...": guard it withif i < xs.len. - A contract about what a loop builds goes on the helper one iteration calls. The loop forgets every fact about the bindings it updates but their refinements, so an
ensuresthat needs one after the loop, such ascounts.has(key: vote)after a loop ofcounts.set, is U5002, and neither anifguard norcheckedproves it. Move the update into a helper with aneditparameter and give the helper the contract, asadd_votebelow: the solver proves it once, for every call, and a caller has it right after each call. The helper'sensuresnames the parameter's value on entry asold(p), ascounts.len <= old(counts).len + 1. The loop's ownensuresabout everything it built, such asresult.len <= votes.len, still cannot be proven, since the loop keeps no fact from one iteration to the next: state what callers need on the helper. - A call that fails leaves its
editarguments unchanged for the caller; operations it performed stay performed. - Cost. A list, map or text that nothing else holds is updated in place, so
acc = acc.append(item: x)in a loop, or through helpers that takeaccand return it, is linear (ADR 0072). - Known limit: keeping the old value on failure.
acc = step(acc, item: x)followed byif error use accreadsaccafter the call, so the call cannot take it over and copies it: every iteration copies the whole list, and the loop is quadratic. The old value is kept because a failed call changes nothing for its caller (spec/17). For a linear loop, check first and then update, or make the update unable to fail and return a status with the new value.
una
module demo
pub kind Tally
count: Int
total: Int
--- An `edit` parameter goes in and comes back out; `old(t)` is its value on entry.
pub record(edit t: Tally, amount: Int) -> Unit
ensures t.count == old(t).count + 1
=
t.count = t.count + 1
t.total = t.total + amount
pub summarize(amounts: List[Int]) -> Tally
=
let edit tally = Tally(count: 0, total: 0)
for amount in amounts
edit tally.record(amount)
tally
pub sum_to(n: Nat) -> Int
=
let edit total = 0
for i in 1..n
total = total + i
total
--- `set` keeps the length, so every index of the range stays valid (ADR 0071).
pub zeroed(xs: List[Int]) -> List[Int]
ensures result.len == xs.len
=
let edit ys = xs
for i in 0..<ys.len
edit ys.set(index: i, item: 0)
ys
pub cleared(xs: List[Int], index: Int) -> List[Int]
requires 0 <= index and index < xs.len
ensures result.len == xs.len
=
let edit copy = xs
edit copy.set(index: index, item: 0)
copyuna
module tally
--- One vote counted. The key is in the map afterwards: a fact a loop would forget, which
--- each call of the helper keeps.
add_vote(edit counts: Map[Text, Int], vote: Text) -> Unit
ensures counts.has(key: vote)
=
let n = counts.get(key: vote)
if none use 0
edit counts.set(key: vote, value: n + 1)
--- The votes counted, one call of the helper per vote.
pub tally(votes: List[Text]) -> Map[Text, Int]
=
let edit counts: Map[Text, Int] = empty_map()
for vote in votes
add_vote(edit counts, vote)
counts
--- A vote counted on top of the others: its key is there, by the helper's contract.
pub with_vote(votes: List[Text], vote: Text) -> Map[Text, Int]
ensures result.has(key: vote)
=
let edit counts = tally(votes)
add_vote(edit counts, vote)
countsuna
module demo
pub kind Limit = | Full
pub kind Added
items: List[Int]
full: Bool
--- Fails when the list is full.
pub bounded(acc: List[Int], item: Int) -> List[Int]
fails Limit
=
if acc.len >= 100
fail Full
acc.append(item: item)
--- Quadratic: `if error use acc` reads `acc` after the call, so each call copies it.
pub kept(items: List[Int]) -> List[Int]
=
let edit acc: List[Int] = []
for item in items
acc = bounded(acc, item: item)
if error use acc
acc
--- Linear: check first, then update.
pub checked_first(items: List[Int]) -> List[Int]
=
let edit acc: List[Int] = []
for item in items
if acc.len < 100
acc = acc.append(item: item)
acc
--- Never fails: the new list, and whether it was full.
pub add(acc: List[Int], item: Int) -> Added
=
if acc.len >= 100
Added(items: acc, full: true)
else
Added(items: acc.append(item: item), full: false)
--- Linear: the update cannot fail, and returns its status with the new value.
pub with_status(items: List[Int]) -> List[Int]
=
let edit acc: List[Int] = []
for item in items
let added = add(acc, item: item)
acc = added.items
acc
example "the three keep the first 100 items"
do kept([1, 2, 3]) == checked_first([1, 2, 3]) and checked_first([1, 2, 3]) == with_status([1, 2, 3])
expect result == trueuna
-- fails with U2019
module demo
pub count_up(n: Int) -> Int
=
let total = 0
total = n
total