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)
:
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)
:
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
- stuck {ty : Spec.Paper.Ty} : ActionTyped ty Spec.Paper.Action.stuck
- next {ty : Spec.Paper.Ty} {expression : Spec.Paper.Expr} : Spec.Paper.Typed [] expression ty → ActionTyped ty (Spec.Paper.Action.next expression)
- sample {ty : Spec.Paper.Ty} {continuation : ℝ → Spec.Paper.Expr} {site : Spec.Paper.DistributionAction × Spec.Paper.Op} {fiber : MeasureTheory.Measure ℝ} : (∀ (value : ℝ), Spec.Paper.Typed [] (continuation value) ty) → ActionTyped ty (Spec.Paper.Action.sample site fiber continuation)
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)
@[simp]
theorem
Determinize.Proof.Paper.Typing.noVar_nil
{index : ℕ}
{ty : Spec.Paper.Ty}
:
¬Spec.Paper.HasVar [] index ty
theorem
Determinize.Proof.Paper.Typing.ActionTyped.sub
{a : Spec.Paper.Ty}
{action : Spec.Paper.Action}
{b : Spec.Paper.Ty}
(typed : ActionTyped a action)
(h : a.Sub b)
:
ActionTyped b 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.reduce_typed_closed
{expression : Spec.Paper.Expr}
{ty : Spec.Paper.Ty}
(typed : Spec.Paper.Typed [] expression ty)
:
ActionTyped ty (Spec.Paper.reduce expression)
theorem
Determinize.Proof.Paper.Typing.domainSafeAt_of_value
{expression : Spec.Paper.Expr}
(fuel : ℕ)
(value : expression.isValue = true)
:
Spec.Paper.DomainSafeAt fuel expression