SyntaxIR Proofs

The runtimes reuse results to bound the cost of a parse, and they stop a parse that a limit or a cancellation interrupts. Each mechanism is stated in the Parser and Runtime Specification. A reuse is correct only if it gives the result that evaluating again would give. An interruption is atomic only if it returns no partial value and leaves no state that a later parse could read. The proofs here show that, and the cost bounds that the mechanisms claim, as lemmas over the definitions of the specifications that they cite.

Each proof names its author and the date of its last revision under its title. A change to a statement or a proof updates the date. From the first release on, each proof also lists the releases that changed it. To cite a proof, cite SyntaxIR and name the proof.

Contents

Proof Shows Status
Skip Runs A reused record of a skip run gives what the rest of the walk would, and the walks of a site evaluate its element a linear number of times Proved
Run Sites A reused record of a run site gives what the rest of the walk would, in the environment of the walk that reuses it, and once a site keeps records its walks evaluate its element a number of times linear in the input plus a constant per walk Proved for the engine backends; the cost of placing the values of a walk is not bounded
Memoization Answering a call from a memo entry, including the members of a left-recursion cycle and results that depend on the order of evaluation, gives the outcome that evaluating it again would give Proved from the rules of the specification that it cites
Left-Recursion Growth The growth of a left-recursive rule at a position ends after at most two more steps than the input it consumes, and gives one result, which every parse gives, including the members of a cycle, several leaders at one position and the dependency memo Proved from the rules of the specification that it cites and the Memoization proof
Documents A parse of a Document after edits, reusing carried memo entries and recorded runs, gives the result of a fresh parse of its text Proved from the rules of the specification that it cites and the Memoization proof
Interruptions A cancellation or exhausted limit is atomic: a reservation proceeds whole or interrupts before its work, nothing absorbs an interruption, a parse returns no partial value and leaves no state that a later parse could read, a stream keeps what it delivered, and the point where a limit stops a parse repeats on every run of a backend Proved from the rules of the specification that it cites
Linear Cost How the Conditions for Linear Cost bound the cost of a parse Lemmas 1, 3, 7, 8, 9 and 14 proved; Lemma 11 proved apart from the values of variables (step 5); Lemma 16 on the number of recovered errors of an outcome proved given the Memoization and Documents theorems; Lemmas 2 and 10 proved apart from the tries of an Operators Rule outside its activations (step 3); Lemmas 13 and 15 proved for the cost view; Lemma 12 on what a Document parse charges beyond the cost proved given Lemmas 4 and 5, step 3 and the bounds of Work of a Document Parse, and its corollary given Lemmas 4 to 6, step 3 and those bounds, both in terms of what the Document retains; Lemma 6 proved given the count of activations of Lemma 4; Lemmas 4 and 5 outlined, with proved claims, among them the bounds of Lemma 4 on the repetitions of an activation at one position, on the activations that do not succeed apart from the tries of an Operators Rule outside its activations, and on the activations that memoized links lead to, in either lookahead state and either variant and through the growths that a link makes again, for the links that its step 1 does not leave open and apart from the repetitions after a dropped step of a growth or a path that enters the growth again, which Lemma 5 counts first (step 4), and the steps still open; the theorem proved given Lemmas 4, 5 and 6 and step 3; the checks of the classifier mapped to the conditions and lemmas; the bounds on the cost view hold of the written grammar by Cost View, except for the values that actions build from reshaped values and their run-time errors (step 7, open)
Cost View The grammar as written costs at most a constant times the cost view that the classifier reads, on every input and in the compute units of each backend, so the bounds of the Linear Cost proof hold of the written grammar Proved for every rewrite of the view, on the cost less the values that actions build from a value that the view reshapes, on inputs where no such action stops a parse with a run-time error; those values and errors are open (Linear Cost, step 7)
Constant-Cost Text Taking the text of a node is a step of constant cost given the guarantee of Cost, so the conditions need not count it as a copy, and a comparison of strings may count only one operand Proved
Grammar Laws Which rewrites of Rule Expressions preserve matching, values, syntax errors and cost, under which conditions, and a normal form that decides several of them Draft: laws proved as stated; confluence of the normalization and the free-variable law unproved
Conditional Laws Which transformations and declarations make the laws hold where the syntax does not show their conditions, how each is checked, and which reasons of the classification each removes Draft