import Determinize.Spec.Syntaxnamespace Determinize.Proof.FiniteModelopen Spec.Papernamespace Binding/-- All free variables fit within the given number of available binders. -/def Scoped {α : Type} (depth : Nat) : Expr α → Prop | .bvar i => i < depth | .reject | .unit | .bool _ | .real _ | .nil => True | .lam body => Scoped (depth + 1) body | .fix body => Scoped (depth + 2) body | .fst body | .snd body | .inl body | .inr body | .neg body | .discrete _ body | .poisson _ body | .bernoulli _ body | .exponential _ body => Scoped depth body | .app a b | .pair a b | .cons a b | .add a b | .mul a b | .div a b | .lt a b | .uniform _ a b | .gaussian _ a b | .beta _ a b | .gamma _ a b => Scoped depth a ∧ Scoped depth b | .letE a b => Scoped depth a ∧ Scoped (depth + 1) b | .ite c a b => Scoped depth c ∧ Scoped depth a ∧ Scoped depth b | .matchSum c a b => Scoped depth c ∧ Scoped (depth + 1) a ∧ Scoped (depth + 1) b | .matchList c a b => Scoped depth c ∧ Scoped depth a ∧ Scoped (depth + 2) bdef scopedDecision {α : Type} : (depth : Nat) → (expression : Expr α) → Decidable (Scoped depth expression) | depth, .bvar i => inferInstanceAs (Decidable (i < depth)) | _, .reject | _, .unit | _, .bool _ | _, .real _ | _, .nil => isTrue True.intro | depth, .lam body => scopedDecision (depth + 1) body | depth, .fix body => scopedDecision (depth + 2) body | depth, .fst body | depth, .snd body | depth, .inl body | depth, .inr body | depth, .neg body | depth, .discrete _ body | depth, .poisson _ body | depth, .bernoulli _ body | depth, .exponential _ body => scopedDecision depth body | depth, .app left right | depth, .pair left right | depth, .cons left right | depth, .add left right | depth, .mul left right | depth, .div left right | depth, .lt left right | depth, .uniform _ left right | depth, .gaussian _ left right | depth, .beta _ left right | depth, .gamma _ left right => letI := scopedDecision depth left letI := scopedDecision depth right inferInstanceAs (Decidable (_ ∧ _)) | depth, .letE left right => letI := scopedDecision depth left letI := scopedDecision (depth + 1) right inferInstanceAs (Decidable (_ ∧ _)) | depth, .ite c x y => letI := scopedDecision depth c letI := scopedDecision depth x letI := scopedDecision depth y inferInstanceAs (Decidable (_ ∧ _ ∧ _)) | depth, .matchSum c x y => letI := scopedDecision depth c letI := scopedDecision (depth + 1) x letI := scopedDecision (depth + 1) y inferInstanceAs (Decidable (_ ∧ _ ∧ _)) | depth, .matchList c x y => letI := scopedDecision depth c letI := scopedDecision depth x letI := scopedDecision (depth + 2) y inferInstanceAs (Decidable (_ ∧ _ ∧ _))instance {α : Type} (depth : Nat) (expression : Expr α) : Decidable (Scoped depth expression) := scopedDecision depth expressiontheorem scoped_map {α β : Type} (expression : Expr α) (f : α → β) (depth : Nat) : Scoped depth (expression.map f id) ↔ Scoped depth expression := by induction expression generalizing depth <;> simp_all [Scoped, Expr.map]/-- Instantiate free variables with closed expressions; missing entries userejection. For scoped source expressions no missing entry is consulted. -/def close {α : Type} (environment : List (Expr α)) (depth : Nat) (expression : Expr α) : Expr α := expression.mapVars (fun depth i ↦ if i < depth then .bvar i else environment[i - depth]?.getD .reject) depththeorem scoped_mono {α : Type} (expression : Expr α) {a b : Nat} (bounded : Scoped a expression) (le : a ≤ b) : Scoped b expression := by induction expression generalizing a b with | bvar i => exact Nat.lt_of_lt_of_le bounded le | reject => trivial | unit => trivial | bool v => trivial | real v => trivial | nil => trivial | discrete k d ih => exact ih bounded le | lam body ih => exact ih bounded (Nat.add_le_add_right le 1) | fix body ih => exact ih bounded (Nat.add_le_add_right le 2) | fst body ih => exact ih bounded le | snd body ih => exact ih bounded le | inl body ih => exact ih bounded le | inr body ih => exact ih bounded le | neg body ih => exact ih bounded le | poisson k body ih => exact ih bounded le | bernoulli k body ih => exact ih bounded le | exponential k body ih => exact ih bounded le | app left right ihl ihr => exact ⟨ihl bounded.1 le, ihr bounded.2 le⟩ | pair left right ihl ihr => exact ⟨ihl bounded.1 le, ihr bounded.2 le⟩ | cons left right ihl ihr => exact ⟨ihl bounded.1 le, ihr bounded.2 le⟩ | add left right ihl ihr => exact ⟨ihl bounded.1 le, ihr bounded.2 le⟩ | mul left right ihl ihr => exact ⟨ihl bounded.1 le, ihr bounded.2 le⟩ | div left right ihl ihr => exact ⟨ihl bounded.1 le, ihr bounded.2 le⟩ | lt left right ihl ihr => exact ⟨ihl bounded.1 le, ihr bounded.2 le⟩ | uniform k left right ihl ihr => exact ⟨ihl bounded.1 le, ihr bounded.2 le⟩ | gaussian k left right ihl ihr => exact ⟨ihl bounded.1 le, ihr bounded.2 le⟩ | beta k left right ihl ihr => exact ⟨ihl bounded.1 le, ihr bounded.2 le⟩ | gamma k left right ihl ihr => exact ⟨ihl bounded.1 le, ihr bounded.2 le⟩ | letE value body ihv ihb => exact ⟨ihv bounded.1 le, ihb bounded.2 (Nat.add_le_add_right le 1)⟩ | ite c x y ihc ihx ihy => exact ⟨ihc bounded.1 le, ihx bounded.2.1 le, ihy bounded.2.2 le⟩ | matchSum c x y ihc ihx ihy => exact ⟨ihc bounded.1 le, ihx bounded.2.1 (Nat.add_le_add_right le 1), ihy bounded.2.2 (Nat.add_le_add_right le 1)⟩ | matchList c x y ihc ihx ihy => exact ⟨ihc bounded.1 le, ihx bounded.2.1 le, ihy bounded.2.2 (Nat.add_le_add_right le 2)⟩theorem mapVars_scoped {α : Type} (expression : Expr α) (depth : Nat) (replace : Nat → Nat → Expr α) (identity : ∀ d i, i < d → replace d i = .bvar i) (bounded : Scoped depth expression) : expression.mapVars replace depth = expression := by induction expression generalizing depth <;> simp_all [Scoped, Expr.mapVars]theorem shift_closed {α : Type} (expression : Expr α) (closed : Scoped 0 expression) (amount cutoff : Nat) : expression.shift amount cutoff = expression := by apply mapVars_scoped expression cutoff · intro d i lt simp [show ¬d ≤ i by omega] · exact scoped_mono expression closed (Nat.zero_le _)theorem subst_closed {α : Type} (expression : Expr α) (closed : Scoped 0 expression) (replacement : Expr α) (depth : Nat) : Expr.substAt depth replacement expression = expression := by apply mapVars_scoped expression depth · intro d i lt simp [show i ≠ d by omega, show ¬d < i by omega] · exact scoped_mono expression closed (Nat.zero_le _)theorem environment_lookup_scoped {α : Type} (environment : List (Expr α)) (closed : ∀ e ∈ environment, Scoped 0 e) (i depth : Nat) : Scoped depth (environment[i]?.getD .reject) := by cases h : environment[i]? with | none => simp [Scoped] | some e => simp only [Option.getD_some] exact scoped_mono e (closed e (List.mem_of_getElem? h)) (Nat.zero_le _)theorem close_scoped {α : Type} (expression : Expr α) (environment : List (Expr α)) (closed : ∀ e ∈ environment, Scoped 0 e) (depth : Nat) : Scoped depth (close environment depth expression) := by induction expression generalizing depth <;> simp_all only [close, Expr.mapVars, Scoped, and_self] split · assumption · exact environment_lookup_scoped environment closed _ depththeorem close_empty {α : Type} (expression : Expr α) (depth : Nat) (bounded : Scoped depth expression) : close [] depth expression = expression := by apply mapVars_scoped expression depth · intro d i lt simp [lt] · exact boundedtheorem close_cons_subst {α : Type} (expression : Expr α) (environment : List (Expr α)) (closed : ∀ e ∈ environment, Scoped 0 e) (value : Expr α) (valueClosed : Scoped 0 value) (depth : Nat) : Expr.substAt depth value (close environment (depth + 1) expression) = close (value :: environment) depth expression := by induction expression generalizing depth <;> simp_all only [close, Expr.mapVars, Order.lt_add_one_iff, Nat.add_assoc, Nat.reduceAdd] rename_i i by_cases below : i < depth · simp [below, show i ≤ depth by omega, Expr.substAt, Expr.mapVars, show i ≠ depth by omega, show ¬depth < i by omega] · by_cases equal : i = depth · subst i simp [Expr.mapVars, shift_closed value valueClosed] · have above : depth < i := by omega have notBelow : ¬i ≤ depth := by omega have diff : i - depth = (i - (depth + 1)) + 1 := by omega simp only [notBelow, ↓reduceIte, below, diff, List.getElem?_cons_succ] exact subst_closed _ (environment_lookup_scoped environment closed _ 0) value depththeorem close_two_subst {α : Type} (expression : Expr α) (environment : List (Expr α)) (closed : ∀ e ∈ environment, Scoped 0 e) (argument function : Expr α) (argumentClosed : Scoped 0 argument) (functionClosed : Scoped 0 function) : (close environment 2 expression).substTwo argument function = close (argument :: function :: environment) 0 expression := by unfold Expr.substTwo rw [show 2 = 1 + 1 from rfl, close_cons_subst expression environment closed function functionClosed 1] exact close_cons_subst expression (function :: environment) (by intro e he rcases List.mem_cons.mp he with rfl | he · exact functionClosed · exact closed e he) argument argumentClosed 0end Bindingend Determinize.Proof.FiniteModel