Lectures onType Theory
Grade checking
appendix sectiontutorials

Grade checking

Exercise 54.12.

Problem, calculus, invariant, result, and acceptance. The finite calculus is t::=FXApply r t u. Evaluate its two-coordinate context demand and compare it with the direct translation’s unchanged annotations. The invariant is usage(Apply r t u)=usage(t)+rusage(u). The concrete result is usage(f(fx))=(3,4) at r=2, with the same translated pair and Boolean pair (true,true). Acceptance means the four named passes, the completion line, and audit [] printed in appendix E.

Representation choice. The constructors F, X, and Apply r t u retain exactly the data needed for the Graded Base application rule. A pair of naturals stores the demands for f and x. The separate Linear Base datatype has application and an explicit r-graded box; its evaluator scales at the box, not at application. These trees make the correspondence oracle discriminating, but adding a third variable changes the demand representation. A finite map from variable names to grades scales to arbitrary contexts, at the cost of normalization and equality code that obscures the calculation.

Minimal end-to-end version. Variables contribute unit demand in one coordinate. Application adds the function demand to r times the argument demand. Check f(fx)=(1+r,r2) at r=2. Translate each application to an application whose argument is an explicit box carrying the same grade, evaluate the Linear Base tree by scaling at boxes, and compare both results with (3,4).

Remaining cases, in metatheory order. First check the direct translation equality. Second add the Boolean semiring evaluator and re-run the source syntax. Third compare fx, with natural usage (1,1), against f(fx), with usage (3,4): their Boolean usages coincide. Only after those oracles pass should another term be added.

Incorrect version. Replace multiplication at application by addition. The code typechecks, but the nested grade at r=2 is no longer 4. As a separate mutation, omit the argument box in translation and require the translation oracle to fail.

Run and theorem boundary. Execute the four commands for this artifact in appendix E and compare accepted-output.txt with the named transcript. Restore the multiplication and replay after the mutant fails. The chapter’s correspondence theorem is proved by induction on typing and source reduction; this program checks only finite arithmetic and does not prove that theorem, combined-grading soundness, or fractional borrow safety.

Search the book

Type to search the local edition.