Home / Learn / 9 Repeating: for

Release v0.4.0Edition 0.2

9.3 What a loop keeps and what the verifier knows

Page 4 of 9

9.3.1 What the verifier knows inside a loop

The verifier proves the rules of a program before it runs: preconditions, postconditions and refined kinds (chapter 5). For a loop it faces a problem: the body runs once for each value of a range that it may only learn when the program runs. So the verifier does not follow a loop turn by turn. It checks the body once, for any turn at all.

Think of a rule for the clerk who counts the aisles: "after each aisle, the count on your sheet is not negative". You can check that rule for one aisle without knowing which aisle it is or how many came before: if the count was not negative before the aisle, and the aisle only adds, it is not negative after it. That is how the verifier reads a loop. What it knows at the start of a turn is only what holds at the start of every turn.

9.3.2 When a loop forgets a fact

Here demand gives back Units, a number that is never negative, and its total is a plain Int:

steps/19-loop-forgets/src/demand.unauna
--- A number of units. It is never negative.
kind Units = Int where it >= 0

--- The units customers ask for over `weeks` weeks, at `per_week` units a week.
pub demand(weeks: Int, per_week: Units) -> Units
=
  let edit total = 0
  for week in 1..weeks
    total = total + per_week
  total

una check . reports:

Diagnostic
[U5002] Error: refinement `result >= 0` could not be proven (the loop forgets every fact about `total` but the refinements of its type, so the counterexample sets `total` freely; guard the use with an `if`, or move the update into a helper with an `edit` parameter whose `ensures` states what the use needs)

The total starts at 0 and only adds per_week, which is never negative, so it is never negative either. But the proof is missing, and the reason in parentheses says why: "the loop forgets every fact about total but the refinements of its type". A refinement is the rule a refined kind adds to its base type, such as it >= 0 for Units (section 5.3). total is a plain Int, which has none. So at the start of a turn, as far as the verifier knows, total could be any whole number, and after the loop too: the result might be negative. The code is not wrong; the fact is not where the verifier looks for it. It is U5002, "could not be proven", not U5001, "refuted" (section 5.4), since no real run breaks the rule.

9.3.3 Keeping a fact through the loop: a refined type

The fact the result needs, "not negative", can be the type of the accumulator:

src/demand.unadiff
--- a/src/demand.una
+++ b/src/demand.una
@@ -8,3 +8,3 @@
 =
-  let edit total = 0
+  let edit total: Units = 0
   for week in 1..weeks

Now total is a Units, and the step checks and prints:

Output
20 units

Two proofs make this work. First, each assignment to total must give it a Units, as every value of a refined type must be. total + per_week is a sum of two numbers that are not negative, so the verifier proves it at every turn. Second, since every assignment keeps total a Units, the verifier knows at the start of every turn, and after the loop, that total >= 0. A type written on an editable name is a rule that holds at every turn: in other books, a loop invariant.

9.3.4 What the body knows

Inside the body, the verifier knows more than the types of the names the loop changes.

9.3.4.1 The loop variable lies in its range

In a loop over a range, the loop variable lies between the range's ends at every turn: in for position in 0..<sku.len, the verifier knows that 0 <= position and position < sku.len. That proves a cut of the text at the position:

steps/21-body-facts/src/signs.unauna
--- A SKU with a space after each character, for a sign that is read from afar. Each turn
--- cuts one character out of the SKU, at a position the range keeps inside it.
pub spaced(sku: Text) -> Text
=
  let edit sign = ""
  for position in 0..<sku.len
    sign = "{sign}{sku.slice(start: position, end: position + 1)} "
  sign.trim

slice requires its positions to lie inside the text (section 3.2): here position + 1 <= sku.len, which follows from position < sku.len. Change the range to 0..sku.len, which also visits the position sku.len, one past the last character:

Diagnostic
[U5001] Error: precondition `0 <= position and position <= (position + 1) and (position + 1) <= sku.len` of this call is refuted
   ╭─[ src/signs.una:9:20 ]
   │
 9 │     sign = "{sign}{sku.slice(start: position, end: position + 1)} "
   │                    ──────────────────────┬──────────────────────
   │                                          ╰──────────────────────── precondition `0 <= position and position <= (position + 1) and (position + 1) <= sku.len` of this call is refuted
   │ Help 1: repair 1: add a guard (`if` or a `when` arm) that handles the values where `0 <= position and position <= (position + 1) and (position + 1) <= sku.len` does not hold
   │ Note 2: counterexample: position = 0, sign = "", sku = Text#1, sku.len = 0

This one is U5001, refuted, with a real counterexample: an empty SKU, whose length is 0. The range 0..0 visits the position 0, and the text has no character there. The marks point at the call of slice. The Help line proposes a guard around the call, which would work, but the mistake is in the range: ..< is the fix, and every position it visits is inside the text.

9.3.4.2 Facts from before the loop stay

Names that the loop does not change keep what the verifier knew about them before it. A requires on a parameter holds in every turn:

steps/21-body-facts/src/signs.unauna
--- The boxes needed over `weeks` weeks, when each week `units` units arrive in boxes of
--- `per_box`. The division is proved in every turn by the `requires`, a fact from before the
--- loop.
pub boxes(weeks: Int, units: Int, per_box: Int) -> Int
  requires per_box >= 1
=
  let edit count = 0
  for week in 1..weeks
    count = count + (units + per_box - 1) / per_box
  count

The division by per_box, a value that is not a literal, must be proven safe (section 2.2). No turn changes per_box, so per_box >= 1 from the requires holds in each one, and the division checks. main prints both results:

Output
[R U G - 0 7]
9 boxes

The rule: what the body knows is the facts of the code around the loop, the range of the loop variable, and the refined types of the names the loop changes. What it does not know is the value those names had at the end of the turn before.

9.3.5 Each assignment is proved

Every assignment to an editable name of a refined type must give it a value of that type, and the verifier proves it at the line of the assignment. A shelf that sells the same amount every week:

steps/23-stock-below-zero/src/shelf.unauna
--- The units left on a shelf after `weeks` weeks of sales, at `per_week` units a week.
pub left_after(start: Units, weeks: Int, per_week: Units) -> Units
=
  let edit stock: Units = start
  for week in 1..weeks
    stock = stock - per_week
  stock

una check . reports:

Diagnostic
[U5001] Error: refinement `(stock - per_week) >= 0` is refuted
    ╭─[ src/shelf.una:11:13 ]
    │
  4 │ kind Units = Int where it >= 0
    │                        ───┬───
    │                           ╰───── where clause
    │
 11 │     stock = stock - per_week
    │             ────────┬───────
    │                     ╰───────── refinement `(stock - per_week) >= 0` is refuted
    │ Help 1: repair 1: add a guard (`if` or a `when` arm) that handles the values where `(stock - per_week) >= 0` does not hold
    │ Note 2: counterexample: per_week = 1, start = 0, stock = 0, stock (assigned) = -1, week = 1, weeks = 1

Here the rule really breaks, so it is U5001 with a counterexample: a shelf with start = 0 and per_week = 1, for one week. The line stock (assigned) = -1 is the value the assignment would give, below zero. The repair is the guard that the Help line proposes (section 8.3): a shelf cannot sell more than it holds.

src/shelf.unadiff
--- a/src/shelf.una
+++ b/src/shelf.una
@@ -10,3 +10,3 @@
   for week in 1..weeks
-    stock = stock - per_week
+    stock = if stock >= per_week then stock - per_week else 0
   stock

In the branch where stock >= per_week holds, the difference is not negative, and the other branch gives 0. The step checks, and prints:

Output
8 units left
0 units left

A shelf of 5 units that sells 4 a week has 1 left after the first week, and 0 after the second and third.

9.3.6 How the loop check behaves

The reason of a U5002 from a loop names one more repair: "move the update into a helper with an edit parameter whose ensures states what the use needs". The postcondition of such a helper tells the verifier what one call did to the name, in the turn that makes the call; section 16.2 covers edit parameters.

9.3.7 A refined type, a guard or a helper

Which to use:

The fact the code after the loop needs… Use
Holds of every value the name takes, such as "never negative" a refined type on the name: let edit total: Units = 0
Could break at one assignment, such as a stock that sells more than it holds a guard at that assignment: if stock >= per_week then … else 0
Is about the loop variable and the range nothing: the body knows it, if the range is right (..< for positions)
Is about a name the loop does not change nothing: it stays
Depends on the number of turns, such as "exactly 5 units per week" an example (section 9.5): the verifier forgets how many turns ran

9.3.8 Check yourself: what a loop keeps

This function counts the days the store stays open late:

src/hours.unauna
--- How many days of the week the store stays open late, from day `first_day` on, counting
--- Monday as day 1.
pub late_days(first_day: Int) -> Int in 0..7
=
  let edit count: Int in 0..7 = 0
  for day in 1..7
    if day >= first_day
      count = count + 1
  count

Does una check . pass, and if not, is it U5001 or U5002?

Show the answer

No, and it is U5002:

Diagnostic
[U5002] Error: refinement `(count + 1) in 0..7` could not be proven (the loop forgets every fact about `count` but the refinements of its type, so the counterexample sets `count` freely; guard the use with an `if`, or move the update into a helper with an `edit` parameter whose `ensures` states what the use needs)

The verifier checks the body for any turn, with count holding any value of its type, Int in 0..7. For count = 7, count + 1 is 8, outside the range. No real run gets there, since the loop takes 7 turns and adds at most one per turn, but that fact depends on the number of turns, which the verifier forgets. So the proof is missing, not refuted. A guard is the repair: count = if count < 7 then count + 1 else 7.

Next:9.4 Day-to-day: a weekly restock plan