Lean2Js.Correct
Compiler correctness for a fragment of the subset #
Compiler correctness. Proves "if the reference semantics returns a value, the generated JS returns the same value" for a fragment of the subset.
The target is limited to a fragment so that the reach of the proof stays unambiguous. Outside the
fragment, Agree.checkAgreement checks agreement at run time against the shipped artifact.
Why the fragment stops here #
Every binary operator is in, so the next form to reach for is the call, and that needs
Sound.TypeChecked over the whole subset: the callee's body is arbitrary syntax.
Lean2Js.Correct.InFragment
sourceThe syntax the proof reaches.
- ctor : (∀ (e : Core.Expr), e ∈ args → InFragment e) → InFragment (Core.Expr.ctor typeName tyArgs ctorName args)
- arrayLit : (∀ (e : Core.Expr), e ∈ items → InFragment e) → InFragment (Core.Expr.arrayLit elem items)
- dictLit : (∀ (e : String × Core.Expr), e ∈ entries → InFragment e.snd) → InFragment (Core.Expr.dictLit value obj entries)
- reduceE : InFragment arr → InFragment init → InFragment body → InFragment (arr.reduceE init accName elemName body)
- matchE : InFragment scrut → (∀ (alt : Core.Alt), alt ∈ alts → InFragment alt.body) → InFragment (scrut.matchE alts)
- foldE : InFragment scrut → (∀ (alt : Core.Alt), alt ∈ alts → InFragment alt.body) → InFragment (scrut.foldE typeName tyArgs result alts)
Instances For
Used by
Lean2Js.Correct.InFragment.all
sourceEvery shape of the subset is in the fragment. The proof reaches the whole syntax, so the induction the judgement drives reads as a case analysis on the expression.
Used by
Lean2Js.Correct.InFragment.allList
sourceUsed by
Lean2Js.Correct.InFragment.allValues
sourceUsed by
Lean2Js.Correct.InFragment.allAlts
sourceUsed by
Lean2Js.Correct.InFragment.typeChecked
sourceEverything the correctness proof reaches is also reached by type soundness, which the arithmetic cases need to know that the values in the environment match the types the compiler read.
Used by
Lean2Js.Correct.encodeEnv
sourceEquations
- Lean2Js.Correct.encodeEnv env = List.map (fun (x : String × Lean2Js.Value) => match x with | (name, v) => (name, Lean2Js.encodeValue v)) env
Instances For
Used by
Lean2Js.Correct.Eventually
sourceThe relation "given enough fuel, the generated code returns this value". Quantifying the fuel existentially lets subexpressions compose even when each needs a different amount.
Equations
Instances For
Used by
Lean2Js.Correct.lookup_encodeEnv
sourceUsed by
Lean2Js.Correct.eventually_lit
sourceUsed by
Lean2Js.Correct.eventually_num
sourceUsed by
Lean2Js.Correct.eventually_big
sourceUsed by
Lean2Js.Correct.eventually_str
sourceUsed by
Lean2Js.Correct.eventually_bool
sourceUsed by
Lean2Js.Correct.eventually_arrowCall
sourceUsed by
Lean2Js.Correct.eventually_not
sourceUsed by
Lean2Js.Correct.eventually_neg_num
sourceUsed by
Lean2Js.Correct.eventually_neg_big
sourceUsed by
Lean2Js.Correct.eventually_call1
sourceUsed by
Lean2Js.Correct.eventually_objLit0
sourceA constructor value is an object literal whose first field is the tag.
Used by
Lean2Js.Correct.eventually_objLit1
sourceUsed by
Lean2Js.Correct.EventuallyList
sourceThe list an object, array or dictionary literal evaluates before it builds the value.
Equations
Instances For
Used by
Lean2Js.Correct.eventuallyList_nil
sourceUsed by
Lean2Js.Correct.eventuallyList_cons
sourceUsed by
Lean2Js.Correct.eventually_arrayLit
sourceUsed by
Lean2Js.Correct.eventually_objLit
sourceUsed by
Lean2Js.Correct.eventually_dictLit
sourceUsed by
Lean2Js.Correct.eventually_call3
sourceUsed by
Lean2Js.Correct.encodeList_map_str
sourceUsed by
Lean2Js.Correct.hasInfix_eq
sourceUsed by
Lean2Js.Correct.int53_range
sourceUsed by
Lean2Js.Correct.strToInt_eq
sourceUsed by
Lean2Js.Correct.helper_strUn
sourceThe string helpers the compiler emits compute what applyStrUn and applyStrBin compute; the two
sides are written as the same functions on the code points.
Used by
Lean2Js.Correct.indexOfChars_eq
sourceUsed by
Lean2Js.Correct.joinFrom_eq
sourceUsed by
Lean2Js.Correct.joinStr_eq
sourceUsed by
Lean2Js.Correct.repeatFrom_eq
sourceUsed by
Lean2Js.Correct.helper_strBin
sourceUsed by
Lean2Js.Correct.strBin_err_indexOf
sourceindexOf is the one string pair that can fail: a position past the safe integers traps the way a
length does.
Used by
Lean2Js.Correct.strBin_err_repeat
sourcerepeat is the other one: a result longer than the safe integers traps before the string is
built.
Used by
Lean2Js.Correct.applyStrUn_str
sourceUsed by
Lean2Js.Correct.strSlice_of_sliceStr
sourcesubstring counts code points on both sides. The model's extra guard against a bound outside the
safe integers is the one the reference semantics gets from the argument being an Int53 at all.
Used by
Lean2Js.Correct.strSlice_trap
sourceUsed by
Lean2Js.Correct.eventually_member
sourceUsed by
Lean2Js.Correct.eventually_length_arr
sourceUsed by
Lean2Js.Correct.eventually_size_dict
sourceUsed by
Lean2Js.Correct.helper_strlen
sourceUsed by
Lean2Js.Correct.encodeFields_find
sourceThe dictionary helpers read and write the encoded entries the way the reference semantics reads and writes the entries themselves; the encoding only touches the values.
Used by
Lean2Js.Correct.encodeFields_any
sourceUsed by
Lean2Js.Correct.encodeFields_filter
sourceUsed by
Lean2Js.Correct.encodeFields_map_set
sourceUsed by
Lean2Js.Correct.encodeFields_append
sourceUsed by
Lean2Js.Correct.encodeFields_with
sourceUsed by
Lean2Js.Correct.encodeValue_dictLookup
sourceUsed by
Lean2Js.Correct.helper_dget
sourceUsed by
Lean2Js.Correct.helper_dhas
sourceUsed by
Lean2Js.Correct.helper_dset
sourceUsed by
Lean2Js.Correct.helper_dkeys
sourceUsed by
Lean2Js.Correct.helper_dvalues
sourceUsed by
Lean2Js.Correct.helper_ddelete
sourceUsed by
Lean2Js.Correct.member_encodeObj
sourceA field read finds the field, not the constructor's name the value carries in front of it. The two cannot collide: a type may not declare a field named the key it carries that name under, and the fragment reads no such name.
Used by
Lean2Js.Correct.encodeFields_eq
sourceUsed by
Lean2Js.Correct.encodeList_eq
sourceUsed by
Lean2Js.Correct.encodeList_rangeValues
sourceUsed by
Lean2Js.Correct.at?_ok
sourceThe array reads count elements on both sides. The model's extra guard against an index outside the
safe integers is the one the reference semantics gets from the index being an Int53 at all.
Used by
Lean2Js.Correct.at?_err
sourceUsed by
Lean2Js.Correct.arrSlice_of_sliceArr
sourceUsed by
Lean2Js.Correct.arrSlice_trap
sourceUsed by
Lean2Js.Correct.helper_at
sourceUsed by
Lean2Js.Correct.helper_aslice
sourceUsed by
Lean2Js.Correct.helper_areverse
sourceUsed by
Lean2Js.Correct.helper_i53
sourceUsed by
Lean2Js.Correct.helper_abs_num
sourceUsed by
Lean2Js.Correct.helper_abs_big
sourceUsed by
Lean2Js.Correct.helper_str
sourceUsed by
Lean2Js.Correct.helper_range
sourceUsed by
Lean2Js.Correct.i53_of_mkInt53
sourceUsed by
Lean2Js.Correct.absInt
sourceUsed by
Lean2Js.Correct.eventually_call2
sourceUsed by
Lean2Js.Correct.eventually_andL
sourceUsed by
Lean2Js.Correct.eventually_andR
sourceUsed by
Lean2Js.Correct.eventually_orL
sourceUsed by
Lean2Js.Correct.eventually_orR
sourceUsed by
Lean2Js.Correct.eval_binary_plus
sourceUsed by
Lean2Js.Correct.eval_binary_minus
sourceUsed by
Lean2Js.Correct.eval_binary_times
sourceUsed by
Lean2Js.Correct.eval_binary_shr
sourceUsed by
Lean2Js.Correct.eventually_binary
sourceUsed by
Lean2Js.Correct.u32_lt
sourceUsed by
Lean2Js.Correct.u32_add
sourceUsed by
Lean2Js.Correct.u32_sub
sourceUsed by
Lean2Js.Correct.u32_mul
sourceUsed by
Lean2Js.Correct.u32_of_lt
sourceUsed by
Lean2Js.Correct.eventually_plus_str
sourceUsed by
Lean2Js.Correct.encodeList_append
sourceUsed by
Lean2Js.Correct.helper_aconcat
sourceUsed by
Lean2Js.Correct.helper_i53div
sourceUsed by
Lean2Js.Correct.helper_i53mod
sourceUsed by
Lean2Js.Correct.helper_u32div
sourceUsed by
Lean2Js.Correct.helper_u32mod
sourceUsed by
Lean2Js.Correct.helper_bigdiv
sourceUsed by
Lean2Js.Correct.helper_bigmod
sourceUsed by
Lean2Js.Correct.u32_of_natCast
sourceUsed by
Lean2Js.Correct.u32_tdiv
sourceUsed by
Lean2Js.Correct.u32_tmod
sourceUsed by
Lean2Js.Correct.helper_u32mul
sourceUsed by
Lean2Js.Correct.helper_min_num
sourceUsed by
Lean2Js.Correct.helper_min_big
sourceUsed by
Lean2Js.Correct.helper_max_num
sourceUsed by
Lean2Js.Correct.helper_max_big
sourceUsed by
Lean2Js.Correct.string_compare_toList
sourceUsed by
Lean2Js.Correct.helper_strcmp
sourceUsed by
Lean2Js.Correct.strcmp_compare
sourceUsed by
Lean2Js.Correct.u32_compare
sourceUsed by
Lean2Js.Correct.eval_binary_lt
sourceUsed by
Lean2Js.Correct.eval_binary_le
sourceUsed by
Lean2Js.Correct.eval_binary_gt
sourceUsed by
Lean2Js.Correct.eval_binary_ge
sourceUsed by
Lean2Js.Correct.arith_lt
sourceUsed by
Lean2Js.Correct.arith_le
sourceUsed by
Lean2Js.Correct.arith_gt
sourceUsed by
Lean2Js.Correct.arith_ge
sourceUsed by
Lean2Js.Correct.order_num
sourceUsed by
Lean2Js.Correct.order_big
sourceUsed by
Lean2Js.Correct.u32_beq
sourceUsed by
Lean2Js.Correct.beq_encodeValue
sourceEncoding preserves equality, but only between values of one type. Untyped the statement is false:
Int53 0 and UInt32 0 are different values that both encode to .num 0.
Used by
Lean2Js.Correct.beq_encodeFields
sourceUsed by
Lean2Js.Correct.beq_encodeList
sourceUsed by
Lean2Js.Correct.beq_encodeEntries
sourceUsed by
Lean2Js.Correct.eval_binary_eqq
sourceUsed by
Lean2Js.Correct.eval_binary_neqq
sourceUsed by
Lean2Js.Correct.arith_eqq
sourceUsed by
Lean2Js.Correct.arith_neqq
sourceUsed by
Lean2Js.Correct.helper_eq
sourceUsed by
Lean2Js.Correct.sameValue_encodeValue
source=== compares scalars by value, so the model's sameValue reaches Value.beq only where the
compiler has already decided the operands are scalars.
Used by
Lean2Js.Correct.cond_true
sourceUsed by
Lean2Js.Correct.cond_false
sourceUsed by
Failing, at every large enough amount of fuel #
The mirror of Eventually. Where that carries a value across the boundary, this carries a thrown code,
and each shape the compiler emits has to be shown to pass one along.
Lean2Js.Correct.EventuallyErr
sourceEquations
- Lean2Js.Correct.EventuallyErr m env je code = ∃ (g : Nat), ∀ (g' : Nat), g ≤ g' → Lean2Js.Js.eval m g' env je = Except.error code
Instances For
Used by
Lean2Js.Correct.eventuallyErr_not
sourceUsed by
Lean2Js.Correct.eventuallyErr_neg
sourceUsed by
Lean2Js.Correct.eventuallyErr_binaryL
sourceUsed by
Lean2Js.Correct.eventuallyErr_binaryR
sourceUsed by
Lean2Js.Correct.eventuallyErr_andR
sourceUsed by
Lean2Js.Correct.eventuallyErr_orR
sourceUsed by
Lean2Js.Correct.eventuallyErr_condC
sourceUsed by
Lean2Js.Correct.eventuallyErr_condT
sourceUsed by
Lean2Js.Correct.eventuallyErr_condE
sourceUsed by
Lean2Js.Correct.eventuallyErr_arrowArg
sourceUsed by
Lean2Js.Correct.eventuallyErr_arrowBody
sourceUsed by
Lean2Js.Correct.eventuallyErr_objLit1
sourceUsed by
Lean2Js.Correct.eventuallyErr_member
sourceUsed by
Lean2Js.Correct.encodeFields_zip
sourceUsed by
Lean2Js.Correct.eventually_ctorObj
sourceA constructor value is the tag followed by the fields, zipped back onto the names the type declares them under.
Used by
Lean2Js.Correct.eventually_dictLitZip
sourceUsed by
Lean2Js.Correct.EventuallyListErr
sourceEquations
- Lean2Js.Correct.EventuallyListErr m env jes code = ∃ (g : Nat), ∀ (g' : Nat), g ≤ g' → Lean2Js.Js.evalList m g' env jes = Except.error code
Instances For
Used by
Lean2Js.Correct.eventuallyListErr_head
sourceUsed by
Lean2Js.Correct.eventuallyListErr_tail
sourceUsed by
Lean2Js.Correct.eventuallyErr_arrayLit
sourceUsed by
Lean2Js.Correct.eventuallyErr_objLit
sourceUsed by
Lean2Js.Correct.eventuallyErr_dictLit
sourceUsed by
Lean2Js.Correct.eventuallyErr_ctorObj
sourceUsed by
Lean2Js.Correct.eventuallyErr_dictLitZip
sourceUsed by
Lean2Js.Correct.eventuallyErr_call1
sourceUsed by
Lean2Js.Correct.eventuallyErr_call1_helper
sourceUsed by
Lean2Js.Correct.eventuallyErr_call3_1
sourceUsed by
Lean2Js.Correct.eventuallyErr_call3_2
sourceUsed by
Lean2Js.Correct.eventuallyErr_call3_3
sourceUsed by
Lean2Js.Correct.eventuallyErr_call3_helper
sourceUsed by
Lean2Js.Correct.eventuallyErr_call2L
sourceUsed by
Lean2Js.Correct.eventuallyErr_call2R
sourceUsed by
Lean2Js.Correct.eventuallyErr_call2_helper
sourceUsed by
One shape, whichever operand failed #
Every shape compileExpr emits for a binary node evaluates the left operand and then the right, so a
thrown code from either travels out. Reading it off the compiler's tables once keeps the induction from
repeating the argument sixteen times.
Lean2Js.Correct.numericHelper_errL
sourceUsed by
Lean2Js.Correct.numericHelper_errR
sourceUsed by
Lean2Js.Correct.compileExpr_bin_errL
sourceUsed by
Lean2Js.Correct.compileExpr_bin_errR
sourceUsed by
Lean2Js.Correct.compileArgs_length
sourceThe dictionary operations: the operand the compiler read as a Dict, the expression it emitted, and
the type it gave back.
Used by
Lean2Js.Correct.compileValues_length
sourceUsed by
Lean2Js.Correct.evalArgs_length
sourceUsed by
Lean2Js.Correct.JsEnvAgrees
sourceThe generated environment binds everything the reference one does, to the encoding of the same value. It may bind more: a public function's entry check leaves the raw parameters in scope, and the compiled body never names them.
scrutFree is the other half, and match is why it is here: the generated arm chain runs under the
scrutinee bound to scrutName, so a reference environment that bound that name too would be read on one
side and shadowed on the other. Every name a program can bind went through validateIdent, which
rejects the __ prefix.
bodyFree is why a call the compiler redirects to a declaration's body lands on the module's function
of that name: calleeName lets a binding holding a function shadow the module's own, and nothing the
generated code binds is spelled under the body prefix.
- binds(name : String) (v : Value) : env.lookup? name = some v → Option.map (fun (x : String × Js.JsValue) => x.snd) (List.find? (fun (x : String × Js.JsValue) => x.fst == name) jenv) = some (encodeValue v)
- fresh(name : String) (jv : Js.JsValue) : isReserved name = false → Option.map (fun (x : String × Js.JsValue) => x.snd) (List.find? (fun (x : String × Js.JsValue) => x.fst == name) jenv) = some jv → ∃ (v : Value), env.lookup? name = some v
- bodyFree(name : String) (jv : Js.JsValue) : Option.map (fun (x : String × Js.JsValue) => x.snd) (List.find? (fun (x : String × Js.JsValue) => x.fst == name) jenv) = some jv → isBodyName name = false
Instances For
Used by
Lean2Js.Correct.JsEnvAgrees.scrutFree
sourceThe reference environment binds no reserved name, so in particular not the scrutinee's.
Used by
Lean2Js.Correct.lookup_cons_none
sourceUsed by
Lean2Js.Correct.JsEnvAgrees.cons
sourceUsed by
Lean2Js.Correct.lookup_of_encodeEnv
sourceThe names of encodeEnv env are the names of env, so an unreserved one found there is bound.
Used by
Lean2Js.Correct.jsEnvAgrees_encodeEnv
sourceUsed by
Traversals #
The reference semantics and the model walk an array with one auxiliary function each, written to the same shape, so a traversal needs a lemma that walks the two together. The body's induction hypothesis is taken over every environment, which is what lets it apply one element at a time.
Lean2Js.Correct.isNumKey_encode
sourceUsed by
Lean2Js.Correct.isStrKey_encode
sourceUsed by
Lean2Js.Correct.key_of_keysOk
sourceUsed by
Lean2Js.Correct.keyLe_encode
sourceThe two sides order the keys the same way. uint32 is why this asks for the key to be one of the two
key shapes rather than holding for every value: it encodes to a number the model would compare, and the
reference semantics refuses it.
Used by
Lean2Js.Correct.sortPairs_encode
sourceUsed by
Lean2Js.Correct.keysOk_of_hasElemTy
sourceThe key type the compiler insists on is what says the sort never refuses the keys it was handed.
Used by
Lean2Js.Correct.eventually_sortByJs
sourceUsed by
Lean2Js.Correct.eventually_mapJs
sourceUsed by
Lean2Js.Correct.eventually_filterJs
sourceUsed by
Lean2Js.Correct.eventually_findJs
sourceUsed by
Lean2Js.Correct.eventually_quantJs
sourceUsed by
Lean2Js.Correct.eventually_reduceJs
sourceUsed by
Arms #
match compiles to an arrow that binds the scrutinee to scrutName and then to a chain of conditionals,
one per arm: the arm's tests conjoined with &&, its body applied to the values its pattern reads. The
last arm carries no test — exhaustiveness was checked at compile time, so falling through to it is what
the compiler decided is safe.
Three things therefore have to line up with firstMatch: a matching pattern makes its tests true, a
pattern that does not match makes the conjunction false without evaluating past the test that failed, and
the values the arm reads out of the scrutinee are the ones the pattern bound.
Lean2Js.Correct.eventually_eqq
sourceUsed by
Lean2Js.Correct.eventually_and_false
sourceUsed by
Lean2Js.Correct.eventually_and_true
sourceUsed by
Lean2Js.Correct.eventually_andFold_false
sourceUsed by
Lean2Js.Correct.eventually_andFold_true
sourceUsed by
Lean2Js.Correct.TestsFail
sourceThe tests of an arm the scrutinee does not take: the one that decides it evaluates to false, and
every test before it to true. Nothing is said about the tests after it — && short-circuits, and an
inner test that reads a field the value does not carry is exactly what that protects.
Equations
- One or more equations did not get rendered due to their size.
- Lean2Js.Correct.TestsFail m jenv [] = False
Instances For
Used by
Lean2Js.Correct.TestsFail.append_right
sourceUsed by
Lean2Js.Correct.TestsFail.append_left
sourceUsed by
Lean2Js.Correct.eventually_andFold_of_fail
sourceUsed by
Lean2Js.Correct.eventually_arrowCallN
sourceUsed by
Lean2Js.Correct.LookupsAgree
sourceEach declared field name reads back the value the reference semantics has at that position. The two
sides line up by name on the generated side and by position on the reference side, which is why the names
have to be distinct and none of them may be tag.
Equations
- One or more equations did not get rendered due to their size.
- Lean2Js.Correct.LookupsAgree obj [] [] = True
- Lean2Js.Correct.LookupsAgree obj x✝¹ x✝ = False
Instances For
Used by
Lean2Js.Correct.lookupsAgree_of_hasFieldTys
sourceUsed by
Lean2Js.Correct.PathsAgree
sourceThe values an arm's paths read, against the values its pattern bound: the same names in the same order, and no name the scrutinee binding could shadow.
Equations
- One or more equations did not get rendered due to their size.
- Lean2Js.Correct.PathsAgree m jenv [] [] = True
- Lean2Js.Correct.PathsAgree m jenv x✝¹ x✝ = False
Instances For
Used by
Lean2Js.Correct.EventuallyEach
sourceEquations
- Lean2Js.Correct.EventuallyEach m jenv [] [] = True
- Lean2Js.Correct.EventuallyEach m jenv (e :: es) (v :: vs) = (Lean2Js.Correct.Eventually m jenv e (Lean2Js.encodeValue v) ∧ Lean2Js.Correct.EventuallyEach m jenv es vs)
- Lean2Js.Correct.EventuallyEach m jenv x✝¹ x✝ = False
Instances For
Used by
Lean2Js.Correct.ValuesTyped.length
sourceUsed by
Lean2Js.Correct.eventuallyEach_members
sourceUsed by
Lean2Js.Correct.SignatureOk
sourceWhat the arm chain needs from the program's type declarations: a constructor's fields are named apart
from each other and from the key its name is carried under, and every value the type admits carries its
own constructor under that same key — an arm tests one key, and the value it is tested against wrote the
key of whatever constructor it was built with. Compile.validateType checks both and compileProgram
runs it over every declared type, so Decl.decl_correct discharges this from the module it was handed.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
Lean2Js.Correct.signatureOk_fields
sourceUsed by
Lean2Js.Correct.signatureOk_key
sourceThe key an arm tests is the key the value it is tested against wrote its constructor under.
Used by
Lean2Js.Correct.obj_of_signature_ctor
sourceA constructor pattern only compiles against a type whose values are objects. bool has a signature
too, but its heads are literals, so the lookup by constructor name fails before this is reached.
Used by
Lean2Js.Correct.sameValue_comm
sourceUsed by
Lean2Js.Correct.litJs_ok
sourceUsed by
Lean2Js.Correct.eventually_litTest
sourceUsed by
Lean2Js.Correct.eventually_tagTest
sourceUsed by
Lean2Js.Correct.PathsAgree.append
sourceUsed by
Lean2Js.Correct.patParts_matched
sourceA pattern that matched makes every test the compiler emitted true, and the paths the arm reads land on the values the pattern bound.
Used by
Lean2Js.Correct.patParts_unmatched
sourceA pattern that did not match makes the conjunction false: the test that decides it evaluates to
false, and the ones before it to true.
Used by
Lean2Js.Correct.patPartsList_matched
sourceUsed by
Lean2Js.Correct.patPartsList_unmatched
sourceUsed by
Lean2Js.Correct.eventually_ident
sourceUsed by
Lean2Js.Correct.JsEnvAgrees.consScrut
sourceUsed by
Lean2Js.Correct.PathsAgree.names
sourceUsed by
Lean2Js.Correct.PathsAgree.eventuallyList
sourceUsed by
Lean2Js.Correct.PathsAgree.jsEnvAgrees
sourceUsed by
Lean2Js.Correct.compileAlts_cons_inv
sourceUsed by
A fold's arms, and the node the walk rebuilt #
A fold reads its alternatives exactly as a match does, but against a node that is not a value of the
declared type: every field that came round carries the fold's answer for it rather than the field. These
are the twins of patParts_matched, patParts_unmatched and eventually_chain against that node. Only
the top level differs — what a folded field binds is an ordinary type, so everything nested inside goes
to patPartsList_matched and its partner unchanged.
Lean2Js.Correct.head_ctor_beq
sourceUsed by
Lean2Js.Correct.heads_find_of_findAt
sourceA constructor the declaration names is the head the signature carries, with the fields it declares.
Both sides read ctorsAt, so the lookup that finds one finds the other.
Used by
Lean2Js.Correct.specOf_find_aux
sourceThe spec the emitter wrote names each constructor with the fields that come round. foldSpecOf and
TypeDef.findAt? both read ctorsAt, so the entry for a constructor is the declaration's.
Used by
Lean2Js.Correct.foldSpecOf_find
sourceUsed by
Lean2Js.Correct.foldKey_eq
sourceThe key a fold's alternative tests is the key the value it walks wrote its constructor under. Both
constructors belong to the type the fold names, and SignatureOk settles the key for every value that
type admits — which is what makes the one key Helper.fold is handed right for every node.
Used by
Lean2Js.Correct.mapSetAll_of_nodup
sourceA node rebuilt with a set-all is the node written out: what the walk was handed comes first and each
field is appended after it. Every mapSet is an append because the fields are named apart from each
other and from the key, which is what SignatureOk gives.
Used by
Lean2Js.Correct.foldFields_names
sourceA fold's rebuilt node carries its fields named apart from each other and from the key its constructor
is written under. foldFieldTys leaves the declared names alone, and SignatureOk is what says those are
apart — the same fact a match reads, at the same constructor.
Used by
Lean2Js.Correct.foldEach_members
sourceEvery path a fold's alternative reads lands on the field the rebuilt node carries there.
Used by
Lean2Js.Correct.foldPatParts_matched
sourceA fold's alternative that matched makes every test the compiler emitted true, and the paths the arm reads land on the values the pattern bound.
The twin of patParts_matched, against the node the walk rebuilt. What is asked of that node is not that
it is a value of the declared type — it is not one, the fields that came round carry the fold's answers —
but that its fields are the ones foldFieldTys names.
Used by
Lean2Js.Correct.foldPatParts_unmatched
sourceA fold's alternative that did not match makes the conjunction false: the test that decides it
evaluates to false, and the ones before it to true. The twin of patParts_unmatched.
Used by
Lean2Js.Correct.compileFoldAlts_cons_inv
sourcecompileAlts_cons_inv over compileFoldAlts: the arms are the alternatives one for one, each with
the tests and binders its pattern gave and its body compiled against them.
Used by
Lean2Js.Correct.eventually_foldJs
sourceA fold evaluates its scrutinee and then walks it, which is what evalFoldJs does. The twin of
eventually_mapJs.
Used by
Lean2Js.Correct.ctorFields_not_key
sourceA constructor's fields are named apart from the key its own name is carried under, so a field is read past the tag entry the node carries first.
Used by
Lean2Js.Correct.encodeFields_map_fst
sourceUsed by
Lean2Js.Correct.fst_of_hasFieldTys
sourceA value's fields are named by the types it was checked against, in the same order.
Used by
Lean2Js.Correct.lookupField_encodeFields
sourceUsed by
Lean2Js.Correct.findAt_first
sourceThe type the fold names has a first constructor, so the key Helper.fold is handed is a key some
constructor of that type is carried under.
Used by
Lean2Js.Correct.mapSetAll_encodeFields
sourceThe node evalFoldJs rebuilds with a set-all is the node encodeValue writes for the fold's answer
at that constructor: the key comes first and the walked fields follow it in the order they were walked.
Every mapSet is an append because SignatureOk names the fields apart from each other and from the
key, and foldFieldTys left those names alone.
Used by
Walking a fold #
A fold recurses on the value rather than on the expression, so its four walkers need an induction of
their own: one strong induction on a bound for the value's size, carrying all four at once because they
call each other. Sound.hasTy_of_fold is that induction for the types; this is it for the values.
The fuel is existential at every level and a node's arms run at the fuel its own walk was handed, so
each level takes the max of what its subwalks asked for. A finite value asks for a finite amount.
Calls #
A call is the one shape that leaves the expression it sits in: the callee's body is not a subterm, and the name it lands on is settled at run time by the environment. These read the generated side of that.
Lean2Js.Correct.helper_of_unreserved
sourceNo name a program can write is a runtime helper: validateIdent rejects the reserved prefix and the
helper dispatch is guarded by it.
Used by
Lean2Js.Correct.find?_name
sourceA declaration found by name carries that name.
Used by
Lean2Js.Correct.eventually_fnRef
sourceA function reference in the generated code: the name is not bound, so it reads the module's own function of that name.
Used by
Lean2Js.Correct.calleeName_agrees
sourceThe generated code and the reference semantics pick the same callee. A function value in the reference environment is one the generated environment holds under the same name; anything else leaves both sides with the name they were given.
Used by
Lean2Js.Correct.calleeName_bodyName
sourceA call the compiler redirected to a declaration's body lands on the module's function of that name. Nothing the generated code binds carries the body prefix, so no binding shadows it.
Used by
Lean2Js.Correct.eventually_call
sourceA call in the generated code: the arguments evaluate, the name is no helper, and the callee returns what the reference semantics returned.
Stated with "no helper answers this call" rather than with the reserved prefix, because the two callees the compiler writes sit on opposite sides of that prefix: a declaration's own name is outside it and a declaration's body is inside it, and neither is a row of the table.
Used by
Lean2Js.Correct.eventually_check
sourceA call through a function value crosses the boundary, so what comes back is read the way an argument is: where the check accepts it, the caller holds what the normalisation makes of it.
Used by
Lean2Js.Correct.eventuallyErr_check
sourceThe same when what it reads threw: the check never runs, so the code the callee raised is the code the caller sees.
Used by
Lean2Js.Correct.eventuallyErr_call
sourceThe same when the callee throws.
Used by
Lean2Js.Correct.eventuallyErr_call_args
sourceAnd when an argument throws before the call is made.
Used by
Lean2Js.Correct.ModuleHasDecls
sourceEvery declaration has a function of its own name in the module. Decl reads it off the compiled
program; a function reference evaluates to the name, and the generated code resolves it there.
Equations
- Lean2Js.Correct.ModuleHasDecls p m = ∀ (d : Lean2Js.Core.Decl), d ∈ p.decls → (List.find? (fun (x : Lean2Js.Js.Func) => x.name == d.name) m.funcs).isSome = true
Instances For
Used by
Lean2Js.Correct.DeclAgrees
sourceWhat a call through a function value needs about the declaration it lands on: at this much reference fuel, the module's function of that name returns what the body returns. The body runs at exactly the fuel the call is left with, so this is the same fuel the expression-level statement is at.
The entry and not the body, because a function reference evaluates to the declared name: passing a
declaration by name calls it the way a consumer would, entry check and all. A call the compiler can see
the callee of goes to DeclBodyAgrees instead.
What the entry hands back is read through the declared return type, so this does not say the caller is
holding encodeValue v: it says the caller is holding something the descriptor accepts, and that
reading it back in is what the body built. That is what the compiled call does with it — a call through
a function value is a crossing in both directions.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
Lean2Js.Correct.DeclBodyAgrees
sourceThe same for the body function, which is where a call whose callee the compiler read off the program goes. The arguments are already the encoding of values of the declared types, which is exactly what the entry check would have handed back, so the check is the one thing this statement does without.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
Lean2Js.Correct.AgreesAt
sourceExpression-level agreement at one amount of the reference semantics' fuel.
The induction runs on this rather than on the fragment derivation: a call evaluates the callee's body, which is not a subterm of the call, at one less fuel.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
Lean2Js.Correct.fragment_correct_succ
sourceOne step of the induction behind fragment_correct_in, carrying agreement from f to f + 1.
The induction is on fuel rather than on the fragment derivation because a call runs the callee's body,
which is not a subterm of the call. Every shape evaluates its subterms with one less fuel, so the
hypothesis at f reaches subterms and callee bodies alike.
Used by
Lean2Js.Correct.Mirrorable
sourceThe failures the trap direction carries across: every one but the reference side's own.
outOfFuel is what makes eval total, and the claim about the generated code is stated at every large
enough amount of the model's, so a run only eval ran out of has nothing to match. Every other failure
is carried, noMatchingAlternative included — the generated chain takes its last arm without a test,
and Exhaustive.firstMatch_isSome is what says the reference semantics takes an arm too.
Equations
- Lean2Js.Correct.Mirrorable err = (err ≠ Lean2Js.Err.outOfFuel)
Instances For
Used by
Refusing what the reference semantics refuses #
The other direction of fragment_correct_in. Agree compares two failures by their thrown code, so
that is what this carries across too: not "both fail" but "both fail the same way".
Lean2Js.Correct.i53_err_of_mkInt53
sourceUsed by
Lean2Js.Correct.i53_guard_trap
sourceUsed by
Lean2Js.Correct.numericHelper_trap
sourceUsed by
Lean2Js.Correct.EnvCovers
sourceEvery name the compiler has in scope is bound in the reference environment. EnvTyped says only
that the two agree where both have the name, which leaves eval free to fail on a lookup the generated
code answers.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
Lean2Js.Correct.EnvCovers.cons
sourceUsed by
Lean2Js.Correct.evalExpr_zero
sourceUsed by
Lean2Js.Correct.compareValues_ok
sourceUsed by
Lean2Js.Correct.compileExpr_bin_trap
sourceUsed by
Lean2Js.Correct.eventuallyErr_mapJs
sourceUsed by
Lean2Js.Correct.eventuallyErr_sortByJs
sourceUsed by
Lean2Js.Correct.eventuallyErr_sortByJs_items
sourceUsed by
Lean2Js.Correct.eventuallyErr_mapJs_items
sourceUsed by
Lean2Js.Correct.eventuallyErr_foldJs
sourceA fold evaluates its scrutinee and then walks it, so a scrutinee that throws throws out of the
fold. The twin of eventuallyErr_mapJs.
Used by
Lean2Js.Correct.eventuallyErr_foldJs_walk
sourceThe same for a walk that throws once the scrutinee is in hand. The twin of
eventuallyErr_mapJs_items.
Used by
Lean2Js.Correct.eventuallyErr_filterJs
sourceUsed by
Lean2Js.Correct.eventuallyErr_filterJs_items
sourceUsed by
Lean2Js.Correct.eventuallyErr_findJs
sourceUsed by
Lean2Js.Correct.eventuallyErr_findJs_items
sourceUsed by
Lean2Js.Correct.eventuallyErr_quantJs
sourceUsed by
Lean2Js.Correct.eventuallyErr_quantJs_items
sourceUsed by
Lean2Js.Correct.eventuallyErr_reduceJs
sourceUsed by
Lean2Js.Correct.eventuallyErr_reduceJs_init
sourceUsed by
Lean2Js.Correct.eventuallyErr_reduceJs_items
sourceUsed by
Lean2Js.Correct.EnvCovers.append
sourceUsed by
Lean2Js.Correct.eventuallyErr_arrowCallN
sourceUsed by
Walking a fold that throws #
The mirror of eventuallyFold_of_fold, on the same strong induction over a bound for the value's size
and carrying the same four walkers at once. Where that one carries a value across, this carries the
thrown code, and the walk has one more shape to account for at every level: a subwalk that throws, with
the walks before it having answered.
noMatchingAlternative is not one of those shapes. Exhaustive.foldFirstMatch_isSome says an
alternative matches the rebuilt node, which is what the compiler's usefulFold check bought.
Lean2Js.Correct.DeclTraps
sourceThe same for a callee that throws.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
Lean2Js.Correct.DeclBodyTraps
sourceThe same for the body function.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
Lean2Js.Correct.TrapsAt
sourceExpression-level trap agreement at one amount of the reference semantics' fuel.
Equations
- One or more equations did not get rendered due to their size.
Instances For
Used by
Lean2Js.Correct.fragment_traps_succ
sourceOne step of the induction behind fragment_traps_in, carrying the thrown code from f to f + 1.
On fuel for the same reason as fragment_correct_succ: the callee's body is not a subterm of the call.