All proofs
Project-declaredLean 4.31.0 · null

Partial eval preserves well typed

Cedar.Thm.partial_eval_preserves_well_typed

Plain-language statement

Theorem: Partial evaluation preserves well-typedness of residuals. If a residual is well-typed in some type environment, then partially evaluating it with a partial request and partial entities produces another well-typed residual in the same type environment. This is a fundamental property ensuring that the partial evaluation process maintains type safet...

Exact Lean statement

theorem partial_eval_preserves_well_typed
  {env : TypeEnv}
  {res : Residual}
  {req : Request}
  {preq : PartialRequest}
  {es : Entities}
  {pes : PartialEntities} :
  InstanceOfWellFormedEnvironment req es env →
  RequestAndEntitiesRefine req es preq pes →
  Residual.WellTyped env res →
  Residual.WellTyped env (TPE.evaluate res preq pes)

Formal artifact

Lean source

Canonical source
Full Lean sourceLean 4
theorem partial_eval_preserves_well_typed  {env : TypeEnv}  {res : Residual}  {req : Request}  {preq : PartialRequest}  {es : Entities}  {pes : PartialEntities} :  InstanceOfWellFormedEnvironment req es env   RequestAndEntitiesRefine req es preq pes   Residual.WellTyped env res   Residual.WellTyped env (TPE.evaluate res preq pes):= by  intro h_wf h_ref h_wt  unfold RequestAndEntitiesRefine at h_ref  rcases h_ref with h_rref, h_eref  have h_ref : RequestAndEntitiesRefine req es preq pes := h_rref, h_eref   cases hᵣ : res <;> rw [hᵣ] at h_wt  case val v ty =>    simp only [TPE.evaluate]    exact h_wt  case error ty =>    simp only [TPE.evaluate]    exact h_wt  case var v ty =>    exact partial_eval_well_typed_var h_wf h_ref h_wt  case and a b ty =>    let h_wt₂ := h_wt    cases h_wt₂ with    | and h_a h_b h_ty_a h_ty_b =>      have ih_a : Residual.WellTyped env (TPE.evaluate a preq pes) := partial_eval_preserves_well_typed h_wf h_ref h_a      have ih_b : Residual.WellTyped env (TPE.evaluate b preq pes) := partial_eval_preserves_well_typed h_wf h_ref h_b      exact partial_eval_well_typed_and ih_a ih_b h_wf h_ref h_wt  case or a b ty =>    let h_wt₂ := h_wt    cases h_wt₂ with    | or h_a h_b h_ty_a h_ty_b =>      have ih_a : Residual.WellTyped env (TPE.evaluate a preq pes) := partial_eval_preserves_well_typed h_wf h_ref h_a      have ih_b : Residual.WellTyped env (TPE.evaluate b preq pes) := partial_eval_preserves_well_typed h_wf h_ref h_b      exact partial_eval_well_typed_or ih_a ih_b h_wf h_ref h_wt  case ite c t e ty =>    let h_wt₂ := h_wt    cases h_wt₂ with    | ite h_c h_t h_e h_ty_c h_ty_t =>      have ih_c : Residual.WellTyped env (TPE.evaluate c preq pes) := partial_eval_preserves_well_typed h_wf h_ref h_c      have ih_t : Residual.WellTyped env (TPE.evaluate t preq pes) := partial_eval_preserves_well_typed h_wf h_ref h_t      have ih_e : Residual.WellTyped env (TPE.evaluate e preq pes) := partial_eval_preserves_well_typed h_wf h_ref h_e      exact partial_eval_well_typed_ite ih_c ih_t ih_e h_wf h_ref h_wt  case unaryApp op expr ty =>    let h_wt₂ := h_wt    cases h_wt₂ with    | unaryApp h_expr h_op =>      have ih_expr : Residual.WellTyped env (TPE.evaluate expr preq pes) := partial_eval_preserves_well_typed h_wf h_ref h_expr      exact partial_eval_well_typed_unaryApp ih_expr h_wf h_ref h_wt  case binaryApp op expr1 expr2 ty =>    simp [TPE.evaluate]    have h_wt₂ := h_wt    cases h_wt with    | binaryApp h_expr1 h_expr2 h_op =>      have ih1 : Residual.WellTyped env (TPE.evaluate expr1 preq pes) := partial_eval_preserves_well_typed h_wf h_ref h_expr1      have ih2 : Residual.WellTyped env (TPE.evaluate expr2 preq pes) := partial_eval_preserves_well_typed h_wf h_ref h_expr2      apply partial_eval_well_typed_app₂ ih1 ih2 h_wf h_ref h_wt₂  case set ls ty =>    let h_wt₂ := h_wt    cases h_wt₂    rename_i ty₁ h₀ h₁ h₂    have ih_ls :  r  ls, Residual.WellTyped env (TPE.evaluate r preq pes) := by      intros r h_mem      specialize h₀ r h_mem      exact partial_eval_preserves_well_typed h_wf h_ref h₀    exact partial_eval_well_typed_set ih_ls h_wf h_ref h_wt  case record ls ty =>    let h_wt₂ := h_wt    cases h_wt₂    rename_i ty₁ h₀ h₁    have ih_ls :  k v, (k, v)  ls  Residual.WellTyped env (TPE.evaluate v preq pes) := by      intros k v h_mem      specialize h₀ k v h_mem      have termination : sizeOf v <= sizeOf ls := by        -- Use the existing lemma for list member size        have h_snd_lt : sizeOf (k, v).snd < 1 + sizeOf ls := List.sizeOf_snd_lt_sizeOf_list h_mem        simp at h_snd_lt        omega       have termination₂ : sizeOf ls < sizeOf (Residual.record ls (CedarType.record ty₁)) := by        simp only [Residual.record.sizeOf_spec, CedarType.record.sizeOf_spec]        omega      exact partial_eval_preserves_well_typed h_wf h_ref h₀    exact partial_eval_well_typed_record ih_ls h_wf h_ref h_wt  case getAttr expr attr ty =>    let h_wt₂ := h_wt    cases h_wt₂    case getAttr_entity ety rty h₄ h₅ h₆ h₇ =>      have ih_expr : Residual.WellTyped env (TPE.evaluate expr preq pes) := partial_eval_preserves_well_typed h_wf h_ref h₅      exact partial_eval_well_typed_getAttr ih_expr h_wf h_ref h_wt    case getAttr_record rty h₄ h₅ h₆ =>      have ih_expr : Residual.WellTyped env (TPE.evaluate expr preq pes) := partial_eval_preserves_well_typed h_wf h_ref h₄      exact partial_eval_well_typed_getAttr ih_expr h_wf h_ref h_wt  case hasAttr expr attr ty =>    let h_wt₂ := h_wt    cases h_wt₂    case hasAttr_entity ety h₅ h₆ =>      have ih_expr : Residual.WellTyped env (TPE.evaluate expr preq pes) := partial_eval_preserves_well_typed h_wf h_ref h₅      exact partial_eval_well_typed_hasAttr ih_expr h_wf h_ref h_wt    case hasAttr_record rty h₆ h₇ =>      have ih_expr : Residual.WellTyped env (TPE.evaluate expr preq pes) := partial_eval_preserves_well_typed h_wf h_ref h₆      exact partial_eval_well_typed_hasAttr ih_expr h_wf h_ref h_wt  case call xfn args ty =>    let h_wt₂ := h_wt    cases h_wt₂    rename_i h₁ h₂    have ih_args :  r  args, Residual.WellTyped env (TPE.evaluate r preq pes) := by      intros r h_mem      specialize h₁ r h_mem      exact partial_eval_preserves_well_typed h_wf h_ref h₁    exact partial_eval_well_typed_call ih_args h_wf h_ref h_wt
Project
Cedar Specification
License
Apache-2.0
Commit
3f093947b8ae
Source
cedar-lean/Cedar/Thm/TPE/WellTyped.lean:59-174

Reuse this declaration

Bring the exact result into your workflow

The import identifies the source module. Your project still needs the pinned package dependency shown on this page.

What this badge means

This completion status comes from the project or community source. It has not yet been represented here as an independent rebuild and axiom audit.

Continue in this project

Related declarations

Project-declaredLean 4.31.0

Find? ext

Cedar.Data.Map.find?_ext

Plain-language statement

Two well-formed maps are equal if they have the same find? for every key.

authorizationprogram verificationsemantics

Source project: Cedar Specification

Person-level attribution pending.

View proof record
Project-declaredLean 4.31.0

Find? notmem keys

Cedar.Data.Map.find?_notmem_keys

Plain-language statement

Inverse of find?_mem_toList, except that this requires wf

authorizationprogram verificationsemantics

Source project: Cedar Specification

Person-level attribution pending.

View proof record
Project-declaredLean 4.31.0

Find? some iff in values

Cedar.Data.Map.find?_some_iff_in_values

Plain-language statement

The mp direction of this does not need the wf precondition and, in fact, is available separately as find?_some_implies_in_values above

authorizationprogram verificationsemantics

Source project: Cedar Specification

Person-level attribution pending.

View proof record