Strings as a value domain #
The worked examples read a relation of strings, and a sum of two of them
is their decimal reading added. The reading is strToNat?, which walks
the characters of the string structurally rather than calling
String.toNat?: the latter goes through the slice API, which is defined
by well-founded recursion and does not reduce in the kernel, so an
equation about a computed relation over this domain could not be closed
by decide. Everything here reduces, which is what makes
Provenance.Example's checks theorems.
Whether every character of a list is a decimal digit.
Equations
Instances For
Dependency graph
The value of a decimal numeral, read most significant digit first into an accumulator.
Equations
- ValueTypeString.digitsVal [] x✝ = x✝
- ValueTypeString.digitsVal (c :: t) x✝ = ValueTypeString.digitsVal t (x✝ * 10 + (c.toNat - 48))
Instances For
Dependency graph
The decimal reading of a string: its value where it is a
non-empty run of digits, and nothing otherwise. This is String.toNat?
read off the characters, so that the kernel reduces it.
Equations
- ValueTypeString.strToNat? s = match s.toList with | [] => none | l => if ValueTypeString.allDigits l = true then some (ValueTypeString.digitsVal l 0) else none
Instances For
Dependency graph
Dependency graph
Printing a number #
The domain prints numbers with its own copy of Nat.repr. The core
printer is not exposed to other modules, so a computation through it
does not reduce there; this one is, which keeps the worked examples
decidable.
The decimal digit d, for d < 10.
Equations
- ValueTypeString.digitChar d = Char.ofNat (48 + d)
Instances For
Dependency graph
Nat.toDigitsCore in base ten: prepend to ds the decimal digits of
n, most significant first, within fuel steps.
Equations
- One or more equations did not get rendered due to their size.
- ValueTypeString.toDigitsCore 0 x✝¹ x✝ = x✝
Instances For
Dependency graph
The decimal numeral of n, as Nat.repr prints it.
Equations
- ValueTypeString.numeral n = String.ofList (ValueTypeString.toDigitsCore (n + 1) n [])
Instances For
Dependency graph
A number reads back as itself. This is Nat.toNat?_repr for the
structural reading and the printer above.
Dependency graph
The value domain #
Zero is the numeral 0, a sum is the sum of the two readings printed
back, and a string that is not a numeral reads as nothing – which makes
the sum the empty string, as the domain's own arithmetic has it.
Equations
Dependency graph
Equations
- One or more equations did not get rendered due to their size.
Dependency graph
Dependency graph
Dependency graph
Dependency graph
Equations
- ValueTypeString.instSubString_provenance = { sub := fun (x x_1 : String) => "" }
Dependency graph
Equations
- ValueTypeString.instMulString_provenance = { mul := fun (x x_1 : String) => "" }
Dependency graph
Equations
- One or more equations did not get rendered due to their size.