Documentation

Provenance.Util.ValueTypeString

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
    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
      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
        Instances For
          Dependency graph

          Nat.toDigitsCore in base ten: prepend to ds the decimal digits of n, most significant first, within fuel steps.

          Equations
          Instances For
            Dependency graph

            The decimal numeral of n, as Nat.repr prints it.

            Equations
            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.

              Dependency graph
              @[instance_reducible]
              Equations
              • One or more equations did not get rendered due to their size.
              Dependency graph
              Dependency graph
              theorem ValueTypeString.add_of_right_none {a b : String} {n : ℕ} (ha : strToNat? a = some n) (hb : strToNat? b = none) :
              a + b = ""
              Dependency graph
              theorem ValueTypeString.add_eq_repr {a b : String} {n m : ℕ} (ha : strToNat? a = some n) (hb : strToNat? b = some m) :
              a + b = numeral (n + m)
              Dependency graph
              @[instance_reducible]
              Equations
              Dependency graph
              @[instance_reducible]
              Equations
              Dependency graph
              @[instance_reducible]
              Equations
              • One or more equations did not get rendered due to their size.
              Dependency graph

              The string domain has no null: WithNull String is how a nullable column of strings is modeled.

              Dependency graph