Home / Learn / 7 Results and failures
7.5 When no proof can decide: checked and opaque predicates
Page 6 of 12
7.5.1 What checked is
Before a program runs, Una's verifier proves facts about it, such as the condition of a refined kind wherever a value enters the kind (section 5.3). Some facts depend on data that arrives only while the program runs, such as the text a person types, and on rules the verifier cannot read. For those, checked tests the fact when the program runs, once, and from then on the value carries the fact in its type.
Think of a ticket check at the door of a hall. Inside, nobody asks again: being inside means the ticket was checked. A value that has passed checked is like a guest inside. Its type says that the test passed, and every function that takes that type can rely on it.
7.5.2 Opaque predicates
7.5.2.1 Rules the verifier cannot read
A reflect predicate (section 5.3) has a body in the refinement language, which the verifier reads. Some rules cannot be written in it: "seven characters, a dash, then two digits" needs a test of each character of a text, which the solver does not decide. Such a rule goes in an opaque predicate, written predicate opaque in place of predicate reflect. The verifier sees only its name. Its body may be any pure expression that cannot fail, such as a call of is_digits, the prelude's test that every character of a text is a digit, and it runs when the program runs.
7.5.2.2 Where an opaque predicate may stand
An opaque predicate may be named in a kind's where clause, as kind Sku = Text where well_formed(it), which states the fact without proving it. It is called in only two places: as the condition of checked, and in the body of another opaque predicate. A call anywhere else, in an if or in a requires, is U2016, as How checked behaves shows.
7.5.3 Why a run-time test is needed
shelf_label takes a Sku, so it never prints a label for a malformed code. Pass it the text a person typed, and the verifier refuses:
--- a/src/sku.una
+++ b/src/sku.una
@@ -19,8 +19,3 @@
-show(raw: Text) -> Text
-=
- let outcome = attempt parse_sku(raw)
- when outcome
- is Ok(value) -> shelf_label(value)
- is Err -> "not a sku: {raw}"
+show(raw: Text) -> Text = shelf_label(raw)
una check . reports:
[U5001] Error: refinement `well_formed(raw)` is refuted
╭─[ src/sku.una:20:39 ]
│
7 │ kind Sku = Text where well_formed(it)
│ ───────┬───────
│ ╰───────── where clause
│
20 │ show(raw: Text) -> Text = shelf_label(raw)
│ ─┬─
│ ╰─── refinement `well_formed(raw)` is refuted
│
│ Help 1: repair 1: strengthen the type of the parameter `raw` to a refined kind that implies `well_formed(raw)`
│
│ Help 2: repair 2: add `requires well_formed(raw)` to the enclosing function; its callers then prove it
│
│ Help 3: repair 3: add a guard (`if` or a `when` arm) that handles the values where `well_formed(raw)` does not hold
│
│ Help 4: repair 4 (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, well_formed(raw)) else fail <Variant>`
│
│ Note 1: obligation ob-63f8dbd41c36 (refinement) is refuted: well_formed(raw)
│
│ Note 2: counterexample: raw = Text#0
│
│ Note 3: run `una explain U5001` for an explanation
────╯Read it from the top. The first line says that the refinement well_formed(raw) is refuted: the verifier cannot show the condition for this argument. The two marks show the where clause that asks for it and the argument that must meet it. Note 2 is the counterexample, Text#0, the verifier's name for some text it knows nothing about: raw could be any text. The help lines are the repairs, ranked. The first three need a proof, which no one can give for text typed by a person: the verifier cannot even read the rule. The fourth is checked.
7.5.4 How to write checked
checked(value, condition) else fail V has four parts:
value, the value to test, hereraw.trim.condition, written withitstanding for the value. It is a condition of the refinement language of section 5.3, or a call of an opaque predicate, so that it can run.else fail V, the variant your function fails with when the test does not hold. It is afaillike any other, soVbelongs to the function's error kind.- The result, when the test holds: the value, with a type refined by the condition. Given back where a
Skuis expected, it is aSku.
7.5.5 A checked SKU parser
The step's module turns outside text into a Sku with checked, then prints a shelf label for a well-formed SKU and not a sku: lamp 1 for the bad input:
module sku
--- A SKU as the warehouse prints it: seven characters, ending in a dash and two digits, as in `LAMP-01`.
--- The rule is checked when the program runs, so the predicate is opaque to proofs.
predicate opaque well_formed(t: Text) -> Bool = t.len == 7 and t.slice(start: 4, end: 5) == "-" and is_digits(t.slice(start: 5, end: 7))
kind Sku = Text where well_formed(it)
kind SkuError = | NotASku
--- Turns text from the outside into a `Sku`, or fails.
parse_sku(raw: Text) -> Sku
fails SkuError
=
checked(raw.trim, well_formed(it)) else fail NotASku
--- The label printed on a shelf. It takes a `Sku`, so it never sees unchecked text.
shelf_label(sku: Sku) -> Text = "sku {sku}"
show(raw: Text) -> Text
=
let outcome = attempt parse_sku(raw)
when outcome
is Ok(value) -> shelf_label(value)
is Err -> "not a sku: {raw}"
--- Shows four typed SKUs.
pub main() -> Unit
uses @console: Console[print]
=
@console.print(show("LAMP-01"))
@console.print(show("lamp 1"))
@console.print(show(" LAMP-02 "))
@console.print(show("RUG-07"))una run . prints:
sku LAMP-01
not a sku: lamp 1parse_sku trims the text, then checked tests well_formed(it) on it, with it standing for the trimmed text. When the test holds, the result has the kind Sku; when it does not, parse_sku fails with NotASku, like any fail. show keeps the outcome with attempt (section 7.4), and its is Err arm needs no name for the failure, since SkuError has one variant.
7.5.6 How a value gets an opaque fact
The verifier can never prove an opaque predicate, since it cannot read the body. So in code, a value gets its fact from checked, at run time. Here is a second rule of this kind, a barcode scanned at the till:
module barcodes
--- A barcode as the store prints it: 13 digits. Only a run can tell, so the verifier sees only
--- the predicate's name.
predicate opaque is_barcode(t: Text) -> Bool = t.len == 13 and is_digits(t)
--- A text that passed the barcode check.
kind Barcode = Text where is_barcode(it)
--- Why a scan was refused.
kind ScanError = | NotABarcode
--- Text from the scanner becomes a `Barcode` here, or the call fails.
read_barcode(raw: Text) -> Barcode
fails ScanError
=
checked(raw.trim, is_barcode(it)) else fail NotABarcode
--- A price tag. It takes a `Barcode`, so it never sees unchecked text.
price_tag(code: Barcode, cents: Int) -> Text = "{code}: {cents} cents"
--- What the till shows for a scan.
describe(raw: Text) -> Text
=
let outcome = attempt read_barcode(raw)
when outcome
is Ok(code) -> price_tag(code, cents: 1990)
is Err -> "not a barcode: {raw}"
--- Shows two scans.
pub main() -> Unit
uses @console: Console[print]
=
@console.print(describe("4006381333931"))
@console.print(describe("12-34"))4006381333931: 1990 cents
not a barcode: 12-34read_barcode is the only way to make a Barcode from a text, and price_tag takes a Barcode, so a price tag is never printed for a scan that failed the test. The predicate runs once, inside checked, and the type carries its answer from there.
7.5.7 The escape budget
Warning
checked replaces a proof with a test, so una.toml limits how many uses each module may have, and una report . counts them under escapes.
[package]
name = "sku"
version = "0.1.0"
edition = "0.2"
[run]
entry = "sku"
grants = ["console"]
[escape_budget]
checked_per_module = 1The table [escape_budget] is the escape budget: checked_per_module = 1 allows one use in each module. It is a line of the manifest, so raising it is a change a reviewer sees. una report . lists the use, next to the budget:
package sku 0.1.0
escapes:
sku: 1 checked, budget 1Without an [escape_budget] table the budget is 0. Remove the table, and the first checked in a module does not check:
[U7003] Error: module `sku` uses `checked` 1 time, and `[escape_budget] checked_per_module` allows 0
│ Help 1: repair 1: state the fact in a refined type or a `requires` clause, so that the solver proves it, and remove the `checked`
│
│ Help 2: repair 2: handle the values where the fact does not hold with a guard (`if` or a `when` arm), and remove the `checked`
│
│ Help 3: repair 3 (escape: escape_budget; the module may use more runtime tests in place of proofs; each one is listed in the build report and needs review): raise `checked_per_module` in `[escape_budget]` of `una.toml`The message counts the uses and the budget. The first two repairs remove the checked in favor of a proof or a guard; only the third raises the budget, and it says what that costs: each use is listed in the report and needs review.
7.5.8 How checked behaves
7.5.8.1 The test runs once
checked runs its condition once, when the program reaches it. A value that passed it carries its refined kind, so every function that takes a Sku relies on the fact with no second test.
7.5.8.2 A failed test is an ordinary failure
When the condition does not hold, the function fails with the variant after else fail, and its callers handle that failure with the clauses of section 7.3, or with attempt.
7.5.8.3 Calling an opaque predicate elsewhere
Call is_barcode in an if, and una check . refuses:
--- a/src/barcodes.una
+++ b/src/barcodes.una
@@ -22,8 +22,3 @@
--- What the till shows for a scan.
-describe(raw: Text) -> Text
-=
- let outcome = attempt read_barcode(raw)
- when outcome
- is Ok(code) -> price_tag(code, cents: 1990)
- is Err -> "not a barcode: {raw}"
+describe(raw: Text) -> Text = if is_barcode(raw) then "a barcode: {raw}" else "not a barcode: {raw}"
[U2016] Error: opaque predicate `is_barcode` is called outside `checked`, so its fact would bypass the escape budget
╭─[ src/barcodes.una:23:34 ]
│
23 │ describe(raw: Text) -> Text = if is_barcode(raw) then "a barcode: {raw}" else "not a barcode: {raw}"
│ ───────┬───────
│ ╰───────── opaque predicate `is_barcode` is called outside `checked`, so its fact would bypass the escape budget
│
│ Help 1: repair 1: if the code needs only the test and not the fact, test with a function, not a predicate, with the body of `is_barcode`
│
│ 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, is_barcode(it)) else fail <Variant>`
│
│ Note: run `una explain U2016` for an explanation
────╯The test itself is harmless, but a value that passed it would carry a fact the escape budget never counted. The first repair keeps the budget: when the code needs only a yes or no, write a plain function with the same body. The second makes the call a checked, which the budget counts.
7.5.8.4 reflect or opaque
predicate reflect |
predicate opaque |
|
|---|---|---|
| Body | in the refinement language, not recursive | any pure expression that cannot fail |
| What the verifier sees | the body | only the name |
| How a value gets the fact | proven, where it enters the kind | checked at run time |
| Called in code | anywhere | only inside checked and other opaque bodies |
7.5.9 A proof, a guard or checked
Which to use:
| The fact… | Use |
|---|---|
| Follows from what the code already knows | nothing: the verifier proves it |
| Is the caller's to keep, such as "never 0 months" | requires (section 5.1) |
| Holds of every value of a type, wherever it goes | a refined kind for the parameter or the result (section 5.3) |
| Can be tested with a condition of the refinement language | a guard: an if that handles the other values, as section 7.6 shows |
| Depends on outside data and a rule the verifier cannot read | checked with an opaque predicate, within the budget |
Prefer a guard to checked whenever the condition is in the refinement language: a guard needs no budget, and the verifier proves the code around it. Use checked when it is not: the test then runs, fails with a reason, and is listed for review.
7.5.10 Check yourself: checked
well_formed wants seven characters, a dash at position 4, and two digits. What do these two lines print?
@console.print(show(" LAMP-02 "))
@console.print(show("RUG-07"))Show the answer
sku LAMP-02
not a sku: RUG-07parse_sku tests the trimmed text, so the spaces around LAMP-02 do not matter, and the label shows the trimmed SKU, the value checked gave back. RUG-07 has six characters, so the test fails, parse_sku fails with NotASku, and show prints its Err arm.