Lean2Js.Sound
Type soundness: a value eval returns satisfies the type the compiler read #
Type soundness: if the compiler judged an expression to have type T and eval returns a value for it,
that value satisfies T.
Compiler correctness needs this because the generated code branches on the type of its operands: a + b
is __i53(a + b) for Int53 and string concatenation for String. Without a statement tying the type
the compiler read out of its context to the value the environment actually holds, that case split cannot
be closed.
What this covers #
TypeChecked names the expression forms the proof reaches. call is not among them: a call's type is
the callee's declared return type, so covering it means covering every form any declaration's body can
use, and the induction would have to carry the whole program's well-typedness. Outside TypeChecked,
Agree.checkAgreement checks the shipped artifact at run time.
Which key a constructor is carried under does not reach a type: the statements below are about
eval and the types the compiler read, and hold for whatever reading the program declares.
Lean2Js.EnvTyped
sourceEvery name the compiler's context has typed holds, if the environment binds it at all, a value of that type, and every name it binds is one the context has.
The second half is what a call and a function reference need. eval reads the callee out of the
environment while the generated code was compiled against the context, so a name the context did not
have would send the two sides to different declarations.
Instances For
Used by
Lean2Js.TypeChecked
sourceThe expression forms type soundness reaches.
- arrayLit : (∀ (e : Core.Expr), e ∈ items → TypeChecked e) → TypeChecked (Core.Expr.arrayLit elem items)
- ctor : (∀ (e : Core.Expr), e ∈ args → TypeChecked e) → TypeChecked (Core.Expr.ctor typeName tyArgs ctorName args)
- dictLit : (∀ (e : String × Core.Expr), e ∈ entries → TypeChecked e.snd) → TypeChecked (Core.Expr.dictLit value obj entries)
- reduceE : TypeChecked arr → TypeChecked init → TypeChecked body → TypeChecked (arr.reduceE init accName elemName body)
- matchE : TypeChecked scrut → (∀ (alt : Core.Alt), alt ∈ alts → TypeChecked alt.body) → TypeChecked (scrut.matchE alts)
- foldE : TypeChecked scrut → (∀ (alt : Core.Alt), alt ∈ alts → TypeChecked alt.body) → TypeChecked (scrut.foldE typeName tyArgs result alts)
Instances For
Used by
Lean2Js.TypeChecked.all
sourceEvery shape of the subset type checks. The judgement covers the syntax, so the induction it drives reads as a case analysis on the expression.
Used by
Lean2Js.TypeChecked.allList
sourceUsed by
Lean2Js.TypeChecked.allValues
sourceUsed by
Lean2Js.TypeChecked.allAlts
sourceUsed by
Lean2Js.Ty.beq_refl
sourceUsed by
Lean2Js.Ty.beqList_refl
sourceUsed by
Lean2Js.tyList_beq_refl
sourceReflexivity for the plain list comparison the entry check and the signatures use, which goes through
List's own BEq rather than Ty.beqList.
Used by
Lean2Js.Ty.eq_of_beq
sourceUsed by
Lean2Js.Ty.eq_of_beqList
sourceUsed by
Lean2Js.Ty.eq_of_not_bne
sourceUsed by
Lean2Js.hasTy_bool_inv
sourceUsed by
Lean2Js.hasTy_int53_inv
sourceUsed by
Lean2Js.hasTy_uint32_inv
sourceUsed by
Lean2Js.hasTy_string_inv
sourceUsed by
Lean2Js.hasTy_array_inv
sourceUsed by
Lean2Js.hasTy_bigint_inv
sourceUsed by
Lean2Js.hasTy_named_inv
sourceUsed by
Lean2Js.hasTy_option_inv
sourceUsed by
Lean2Js.hasTy_result_inv
sourceUsed by
Lean2Js.hasTy_dict_inv
sourceUsed by
Lean2Js.hasTy_dictObj_inv
sourceUsed by
Lean2Js.hasTy_of_dictValueTy
sourceA receiver a dictionary operation accepted holds exactly what the Map spelling asks for, whichever
of the two the author declared. This is what lets the four cases below read either receiver through the
.dict lemmas rather than through two copies of each.
Used by
Lean2Js.hasTy_fn_inv
sourceUsed by
Lean2Js.tyList_eq_of_beq
sourceSoundness of the plain list comparison, matching tyList_beq_refl.
Used by
Lean2Js.hasTy_fnValue_inv
sourceThe converse direction: a function value satisfies no type but a function type. What a call needs,
since eval reads the callee out of the environment.
Used by
Lean2Js.hasTy_var_inv
sourceUsed by
Lean2Js.hasTy_named_fields
sourceUsed by
Lean2Js.hasTy_option_fields
sourceUsed by
Lean2Js.hasTy_result_fields
sourceUsed by
Lean2Js.mkInt53_hasTy
sourceUsed by
Lean2Js.applyUn_not_hasTy
sourceUsed by
Lean2Js.applyUn_toString_hasTy
sourceUsed by
Lean2Js.applyUn_neg_int53
sourceUsed by
Lean2Js.applyUn_neg_bigint
sourceUsed by
Lean2Js.applyUn_abs_int53
sourceUsed by
Lean2Js.applyUn_abs_bigint
sourceUsed by
Lean2Js.int53_ty
sourceUsed by
Lean2Js.uint32_ty
sourceUsed by
Lean2Js.bigint_ty
sourceUsed by
Lean2Js.str_ty
sourceUsed by
Lean2Js.arr_ty
sourceUsed by
Lean2Js.hasElemTy_append
sourceUsed by
Lean2Js.hasElemTy_iff
sourceReading the check element by element, so that every list operation that only ever keeps elements it was given inherits it from a membership lemma about that operation.
Used by
Lean2Js.hasElemTy_of_subset
sourceUsed by
Lean2Js.applyUn_range_int53
sourceThe count has to be the typed value rather than a bare Int: what keeps every element inside
Int53 is that the count already is, and the elements are all below it.
Used by
Lean2Js.hasElemTy_getElem?
sourceUsed by
Lean2Js.hasElemTy_string_inv
sourceUsed by
Lean2Js.hasTy_string_array_inv
sourceUsed by
Lean2Js.hasElemTy_map_str
sourceUsed by
Lean2Js.sliceArr_hasTy
sourceUsed by
Lean2Js.sortPairs_hasTy
sourceUsed by
Lean2Js.reverse_hasTy
sourceUsed by
Lean2Js.applyArith_hasTy
sourceUsed by
Lean2Js.applyMinMax_hasTy
sourceUsed by
Lean2Js.compareValues_hasTy
sourceUsed by
Lean2Js.applyBin_concat_hasTy
sourceUsed by
Lean2Js.binResultTy
sourceThe type the compiler gives a binary operation whose operands both have type t.
Equations
- Lean2Js.binResultTy Lean2Js.Core.BinOp.add t = t
- Lean2Js.binResultTy Lean2Js.Core.BinOp.sub t = t
- Lean2Js.binResultTy Lean2Js.Core.BinOp.mul t = t
- Lean2Js.binResultTy Lean2Js.Core.BinOp.div t = t
- Lean2Js.binResultTy Lean2Js.Core.BinOp.mod t = t
- Lean2Js.binResultTy Lean2Js.Core.BinOp.min t = t
- Lean2Js.binResultTy Lean2Js.Core.BinOp.max t = t
- Lean2Js.binResultTy Lean2Js.Core.BinOp.concat t = t
- Lean2Js.binResultTy op t = Lean2Js.Core.Ty.bool
Instances For
Used by
Lean2Js.applyBin_hasTy
sourceUsed by
Lean2Js.applyStrUn_hasTy
sourceUsed by
Lean2Js.applyStrBin_hasTy
sourceUsed by
Lean2Js.sliceStr_hasTy
sourceUsed by
Lean2Js.asBool_hasTy
sourceUsed by
Lean2Js.EnvTyped.cons
sourceUsed by
Lean2Js.EnvTyped.fnScoped
sourceA function value in the environment is one the context typed as a function: it is bound, so the context has a type for it, and only a function type is satisfied by a function value.
Used by
Lean2Js.litValue_hasTy
sourceUsed by
Lean2Js.keysDistinct_iff
sourceUsed by
Lean2Js.keysDistinct_of_validateDistinct
sourceUsed by
Lean2Js.keysDistinct_of_sublist
sourceUsed by
Lean2Js.hasEntryTys_iff
sourceUsed by
Lean2Js.hasTy_dict_filter
sourceUsed by
Lean2Js.hasTy_dict_with
sourceWriting a key already present leaves the key list alone, and writing a new one appends a key the
list did not have. Either way a Map still holds every key once.
Used by
Lean2Js.dictLookup_hasTy
sourceUsed by
Lean2Js.hasElemTy_dict_keys
sourceUsed by
Lean2Js.hasElemTy_dict_values
sourceUsed by
Lean2Js.findAt?_eq
sourceThe constructors a use of the type at args sees are the declared ones with their field types
substituted, so a lookup by name lands on the same constructor either way.
Used by
Lean2Js.hasFieldTys_find
sourceUsed by
Lean2Js.ty_of_foldKindOf_self
sourceA field the fold walks into is the type coming round, at the arguments the fold names. foldKindOf
is read by the evaluator and by the emitter alike, so what it answers is what both walk.
Used by
Lean2Js.ty_of_foldKindOf_list
sourceUsed by
Lean2Js.hasTy_of_lookupFieldV
sourceReading a field out of a value by name gives the type the declaration puts at that name. hasFieldTys
lines the value's fields up with the declared ones in order, and the names being apart is what makes the
lookup land on the same one.
Used by
Lean2Js.hasFieldTys_find_some
sourceUsed by
Lean2Js.find?_field_ty
sourceUsed by
Lean2Js.scrutName_reserved
sourceUsed by
Lean2Js.ne_scrutName_of_unreserved
sourceUsed by
Lean2Js.ne_scrutName_of_validateIdent
sourceNo name the compiler lets through can be the one match gives its scrutinee: validateIdent
rejects the __ prefix, and scrutName starts with it.
Used by
Reading a traversal off the compiler #
Not private, unlike the inversions above: the correctness proof reads the same three parts out of a traversal — the array, the body under the binder, and the shape the compiler emitted.
Lean2Js.compileExpr_mapE_inv
sourceUsed by
Lean2Js.compileExpr_sortByKeyE_inv
sourceUsed by
Lean2Js.compileExpr_filterE_inv
sourceUsed by
Lean2Js.compileExpr_findE_inv
sourceUsed by
Lean2Js.compileExpr_quantE_inv
sourceUsed by
Lean2Js.compileExpr_reduceE_inv
sourceUsed by
Lean2Js.zipAll_of_map
sourceA call checks its arguments against the types of the callee's parameters. The names come from the same parameter list, so the check the compiler wrote over types alone reads as one over parameters.
Used by
Lean2Js.ParamsTyped
sourceEvery argument has the type its parameter declared.
Equations
- Lean2Js.ParamsTyped p [] [] = True
- Lean2Js.ParamsTyped p (param :: ps) (a :: as) = (Lean2Js.Value.hasTy p a param.ty = true ∧ Lean2Js.ParamsTyped p ps as)
- Lean2Js.ParamsTyped p x✝¹ x✝ = False
Instances For
Used by
Lean2Js.envTyped_bindParams
sourceThe compiler's context and the reference environment are built from the same parameter list in the same order, so the name each lookup lands on is the same one.
Used by
Lean2Js.paramsTyped_of_args
sourceThe arguments of a call, carrying the induction hypothesis of typeSound along them: the environment
the callee's body runs in is typed by the context that body was compiled against.
Used by
Reading a match off the compiler #
An arm is compiled against the context its pattern binds, and eval runs it in the environment the same
pattern bound, so type soundness for match is the statement that those two line up.
Lean2Js.BindsAgree
sourceWhat a pattern bound, against what the arm was compiled against: the same names in the same order, each value satisfying the type the compiler read.
Equations
Instances For
Used by
Lean2Js.ValuesTyped
sourceEquations
- Lean2Js.ValuesTyped p [] [] = True
- Lean2Js.ValuesTyped p (v :: vs) (t :: ts) = (Lean2Js.Value.hasTy p v t = true ∧ Lean2Js.ValuesTyped p vs ts)
- Lean2Js.ValuesTyped p x✝¹ x✝ = False
Instances For
Used by
Lean2Js.BindsAgree.append
sourceUsed by
Lean2Js.EnvTyped.append
sourceUsed by
Lean2Js.valuesTyped_of_hasFieldTys
sourceUsed by
Lean2Js.hasFieldTys_of_signature
sourceThe fields a constructor pattern reads, as the type checker sees them and as the value holds them.
signature is the compiler's view of a type's constructors; Value.hasTy is the reference semantics'.
Used by
Lean2Js.matchPat_binds
sourceA pattern that matched bound exactly what the compiler compiled the arm against.
Used by
Lean2Js.matchPats_binds
sourceUsed by
Lean2Js.foldPatParts_binds
sourceA fold's alternative binds what the compiler compiled its arm against. The rebuilt node carries the
answer for every field that came round, so the types the binders take are foldFieldTys' and not the
declared ones; everything nested inside a field reads through patPartsList unchanged.
Used by
Lean2Js.firstMatch_mem
sourceUsed by
Lean2Js.compileAlts_firstMatch
sourceUsed by
Lean2Js.compileFoldAlts_firstMatch
sourceThe arm a fold's rebuilt node fell to is one the compiler compiled, against the context the pattern's
binders give it. compileAlts_firstMatch over foldPatParts.
Used by
Lean2Js.compileExpr_matchE_inv
sourceUsed by
Lean2Js.compileExpr_foldE_inv
sourceWhat the compiler had in hand where it built a fold: a scrutinee at the type the fold names, a type with at least one constructor to read the key off, arms it compiled, and every one of them answering at the fold's result type.
Used by
Walking a traversal #
A traversal evaluates its body under an environment that changes from element to element, so these take
the induction hypothesis of typeSound over every environment rather than the one at the traversal.
filter, find and all / any need no hypothesis at all: what they return is an element they were
given, or a Bool they decided.
Lean2Js.hasElemTy_of_mapItems
sourceUsed by
Lean2Js.ProgramTyped
sourceWhat the compiler establishes about every declaration of a program it accepted: each body compiles, under the context its parameters give, at the type the declaration is declared to return.
A call is where a proof about one expression reaches into another declaration, so this is the shape the
whole program has to be handed in, names included: the generated code calls a declaration by its name,
which has to be one the environment cannot be holding. Decl.programTyped_of_compileProgram reads both
off the module.
- fieldNames(n : String) (args : List Core.Ty) (t : Core.TypeDef) : p.findType? n = some t → ∀ (c : Core.CtorDef), c ∈ t.ctorsAt args → (List.map (fun (x : Core.Field) => x.name) c.fields).Nodup
Instances For
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. The arms run at the fold's own fuel, so the fuel induction's hypothesis is what types their bodies.
Lean2Js.typeSound
sourceIf the compiler judged an expression to have type T and eval returns a value, the value satisfies
T.
Used by
Lean2Js.hasFieldTys_of_evalFoldFields
sourceThe node a fold's walk rebuilt carries the fields Compile.foldFieldTys names: each one that came
round holds the fold's answer for it, and the rest hold what they held. A fold's alternatives are
compiled against exactly that, so it is what a proof about the arms needs of the node they run on —
hasTy_of_fold's fourth walker, at the fuel typeSound was proved for.