Documentation

Determinize.Proof.Semantics.Typing

Type safety for the paper semantics #

Substitution and successful reduction preserve typing. ActionTyped also allows stuck actions; the public DomainSafe assumption excludes them almost surely.

theorem Determinize.Proof.Paper.Typing.hasVar_prepend {suffix : List Spec.Paper.Ty} {index : ℕ} {ty : Spec.Paper.Ty} {inserted : List Spec.Paper.Ty} (h : Spec.Paper.HasVar suffix index ty) :
Spec.Paper.HasVar (inserted ++ suffix) (index + inserted.length) ty
theorem Determinize.Proof.Paper.Typing.hasVar_shift {before suffix : List Spec.Paper.Ty} {index : ℕ} {ty : Spec.Paper.Ty} {inserted : List Spec.Paper.Ty} (h : Spec.Paper.HasVar (before ++ suffix) index ty) :
Spec.Paper.HasVar (before ++ inserted ++ suffix) (if before.length ≤ index then index + inserted.length else index) ty
theorem Determinize.Proof.Paper.Typing.typed_shift {before suffix : List Spec.Paper.Ty} {expression : Spec.Paper.Expr} {ty : Spec.Paper.Ty} {inserted : List Spec.Paper.Ty} (h : Spec.Paper.Typed (before ++ suffix) expression ty) :
Spec.Paper.Typed (before ++ inserted ++ suffix) (Spec.Paper.Expr.shift inserted.length before.length expression) ty
theorem Determinize.Proof.Paper.Typing.hasVar_subst {before : List Spec.Paper.Ty} {binder : Spec.Paper.Ty} {suffix : List Spec.Paper.Ty} {index : ℕ} {ty : Spec.Paper.Ty} (h : Spec.Paper.HasVar (before ++ binder :: suffix) index ty) :
index = before.length ∧ ty = binder ∨ index ≠ before.length ∧ Spec.Paper.HasVar (before ++ suffix) (if before.length < index then index - 1 else index) ty
theorem Determinize.Proof.Paper.Typing.typed_substAt {before : List Spec.Paper.Ty} {binder : Spec.Paper.Ty} {suffix : List Spec.Paper.Ty} {expression : Spec.Paper.Expr} {ty : Spec.Paper.Ty} {replacement : Spec.Paper.Expr} (h : Spec.Paper.Typed (before ++ binder :: suffix) expression ty) (replacementTyped : Spec.Paper.Typed suffix replacement binder) :
Spec.Paper.Typed (before ++ suffix) (Spec.Paper.Expr.substAt before.length replacement expression) ty
theorem Determinize.Proof.Paper.Typing.typed_substHead {binder : Spec.Paper.Ty} {suffix : List Spec.Paper.Ty} {body : Spec.Paper.Expr} {ty : Spec.Paper.Ty} {replacement : Spec.Paper.Expr} (bodyTyped : Spec.Paper.Typed (binder :: suffix) body ty) (replacementTyped : Spec.Paper.Typed suffix replacement binder) :
Spec.Paper.Typed suffix (body.substHead replacement) ty
theorem Determinize.Proof.Paper.Typing.typed_substTwo {argumentTy functionTy : Spec.Paper.Ty} {suffix : List Spec.Paper.Ty} {body : Spec.Paper.Expr} {resultTy : Spec.Paper.Ty} {argument function : Spec.Paper.Expr} (bodyTyped : Spec.Paper.Typed (argumentTy :: functionTy :: suffix) body resultTy) (argumentTyped : Spec.Paper.Typed suffix argument argumentTy) (functionTyped : Spec.Paper.Typed suffix function functionTy) :
Spec.Paper.Typed suffix (body.substTwo argument function) resultTy
Instances For
    theorem Determinize.Proof.Paper.Typing.ActionTyped.wrap {childTy : Spec.Paper.Ty} {action : Spec.Paper.Action} {context : Spec.Paper.Expr → Spec.Paper.Expr} {resultTy : Spec.Paper.Ty} (actionTyped : ActionTyped childTy action) (wrapTyped : ∀ (expression : Spec.Paper.Expr), Spec.Paper.Typed [] expression childTy → Spec.Paper.Typed [] (context expression) resultTy) :
    ActionTyped resultTy (Spec.Paper.Action.wrap context action)
    theorem Determinize.Proof.Paper.Typing.typed_arr_value {context : List Spec.Paper.Ty} {expression : Spec.Paper.Expr} {argument result : Spec.Paper.Ty} (typed : Spec.Paper.Typed context expression (argument.arr result)) (value : expression.isValue = true) :
    (∃ (a : Spec.Paper.Ty) (r : Spec.Paper.Ty) (body : Spec.Paper.Expr), expression = body.lam ℝ Spec.Paper.DistributionAction ∧ argument.Sub a ∧ r.Sub result ∧ Spec.Paper.Typed (a :: context) body r) ∨ ∃ (a : Spec.Paper.Ty) (r : Spec.Paper.Ty) (body : Spec.Paper.Expr), expression = body.fix ℝ Spec.Paper.DistributionAction ∧ argument.Sub a ∧ r.Sub result ∧ Spec.Paper.Typed (a :: a.arr r :: context) body r
    theorem Determinize.Proof.Paper.Typing.typed_prod_value {context : List Spec.Paper.Ty} {expression : Spec.Paper.Expr} {leftTy rightTy : Spec.Paper.Ty} (typed : Spec.Paper.Typed context expression (leftTy.prod rightTy)) (value : expression.isValue = true) :
    ∃ (left : Spec.Paper.Expr) (right : Spec.Paper.Expr), expression = left.pair ℝ Spec.Paper.DistributionAction right ∧ Spec.Paper.Typed context left leftTy ∧ Spec.Paper.Typed context right rightTy
    theorem Determinize.Proof.Paper.Typing.typed_sum_value {context : List Spec.Paper.Ty} {expression : Spec.Paper.Expr} {leftTy rightTy : Spec.Paper.Ty} (typed : Spec.Paper.Typed context expression (leftTy.sum rightTy)) (value : expression.isValue = true) :
    (∃ (body : Spec.Paper.Expr), expression = body.inl ℝ Spec.Paper.DistributionAction ∧ Spec.Paper.Typed context body leftTy) ∨ ∃ (body : Spec.Paper.Expr), expression = body.inr ℝ Spec.Paper.DistributionAction ∧ Spec.Paper.Typed context body rightTy
    theorem Determinize.Proof.Paper.Typing.typed_list_value {context : List Spec.Paper.Ty} {expression : Spec.Paper.Expr} {element : Spec.Paper.Ty} (typed : Spec.Paper.Typed context expression element.list) (value : expression.isValue = true) :
    expression = Spec.Paper.Expr.nil ∨ ∃ (head : Spec.Paper.Expr) (tail : Spec.Paper.Expr), expression = head.cons ℝ Spec.Paper.DistributionAction tail ∧ Spec.Paper.Typed context head element ∧ Spec.Paper.Typed context tail element.list
    theorem Determinize.Proof.Paper.Typing.typed_bool_value {context : List Spec.Paper.Ty} {expression : Spec.Paper.Expr} (typed : Spec.Paper.Typed context expression Spec.Paper.Ty.bool) (value : expression.isValue = true) :
    ∃ (result : Bool), expression = Spec.Paper.Expr.bool ℝ Spec.Paper.DistributionAction result
    theorem Determinize.Proof.Paper.Typing.typed_real_value {context : List Spec.Paper.Ty} {expression : Spec.Paper.Expr} {affinity : Spec.Paper.Affinity} (typed : Spec.Paper.Typed context expression (Spec.Paper.Ty.float affinity)) (value : expression.isValue = true) :
    ∃ (result : ℝ), expression = Spec.Paper.Expr.real ℝ Spec.Paper.DistributionAction result
    theorem Determinize.Proof.Paper.Typing.typed_realList_value {context : List Spec.Paper.Ty} {expression : Spec.Paper.Expr} {affinity : Spec.Paper.Affinity} (typed : Spec.Paper.Typed context expression (Spec.Paper.Ty.float affinity).list) (value : expression.isValue = true) :
    ∃ (values : List ℝ), Spec.Paper.realListValue? expression = some values
    theorem Determinize.Proof.Paper.Typing.domainSafeAt_of_value {expression : Spec.Paper.Expr} (fuel : ℕ) (value : expression.isValue = true) :
    Spec.Paper.DomainSafeAt fuel expression