Theorem: HMem.Trace.CostedProgram.splitTimeCost
Proof state before:
case h₁.a
α : Type u_1
inst✝⁷ : Complexity.Coding α Memory
β : Type u_2
inst✝⁶ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝⁵ : Complexity.Coding γ Memory
inst✝⁴ : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝³ : Complexity.Computable Encoding.Model fs
inst✝² : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
γ✝ δ✝ : Type
inst✝¹ : Complexity.Coding γ✝ Memory
inst✝ : Complexity.Encoding δ✝ Memory
fs✝ : γ✝ → δ✝
cs✝ : Complexity.CostFunction γ✝ ℕ
hcost : Complexity Encoding.Model fs✝ cs✝
next : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (subroutine' dst✝ src✝ inst✝¹ inst✝ fs✝ cs✝ hcost next)) fm
a : α
m : Memory
hm : m ∈ fm a
⊢ Memory.setms m dst✝
      (Complexity.encode
        (fs✝
          (Option.get (Complexity.decode γ✝ (Memory.getms m src✝))
            (_ : Option.isSome (Complexity.decode γ✝ (Memory.getms m src✝)) = true)))) ∈
    ((flip Option.bind fun m =>
          Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ fs✝) (Complexity.decode γ✝ (Memory.getms m src✝))) ∘
        fm)
      ?h₁.a

case h₁.a
α : Type u_1
inst✝⁷ : Complexity.Coding α Memory
β : Type u_2
inst✝⁶ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝⁵ : Complexity.Coding γ Memory
inst✝⁴ : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝³ : Complexity.Computable Encoding.Model fs
inst✝² : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
γ✝ δ✝ : Type
inst✝¹ : Complexity.Coding γ✝ Memory
inst✝ : Complexity.Encoding δ✝ Memory
fs✝ : γ✝ → δ✝
cs✝ : Complexity.CostFunction γ✝ ℕ
hcost : Complexity Encoding.Model fs✝ cs✝
next : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (subroutine' dst✝ src✝ inst✝¹ inst✝ fs✝ cs✝ hcost next)) fm
a : α
m : Memory
hm : m ∈ fm a
⊢ α

α : Type u_1
inst✝⁷ : Complexity.Coding α Memory
β : Type u_2
inst✝⁶ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝⁵ : Complexity.Coding γ Memory
inst✝⁴ : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝³ : Complexity.Computable Encoding.Model fs
inst✝² : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
γ✝ δ✝ : Type
inst✝¹ : Complexity.Coding γ✝ Memory
inst✝ : Complexity.Encoding δ✝ Memory
fs✝ : γ✝ → δ✝
cs✝ : Complexity.CostFunction γ✝ ℕ
hcost : Complexity Encoding.Model fs✝ cs✝
next : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (subroutine' dst✝ src✝ inst✝¹ inst✝ fs✝ cs✝ hcost next)) fm
a : α
m : Memory
hm : m ∈ fm a
⊢ (subroutineTimeCost
                (_ :
                  TracedProgram.sound' f size (toTracedProgram next)
                    ((flip Option.bind fun m =>
                        Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ fs✝)
                          (Complexity.decode γ✝ (Memory.getms m src✝))) ∘
                      fm)) +
              recurseTimeCost hf
                (_ :
                  TracedProgram.sound' f size (toTracedProgram next)
                    ((flip Option.bind fun m =>
                        Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ fs✝)
                          (Complexity.decode γ✝ (Memory.getms m src✝))) ∘
                      fm)) +
            localTimeCost
              (_ :
                TracedProgram.sound' f size (toTracedProgram next)
                  ((flip Option.bind fun m =>
                      Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ fs✝)
                        (Complexity.decode γ✝ (Memory.getms m src✝))) ∘
                    fm)))
          ?h₁.a +
        Complexity.ALE.bound Complexity.cost_ale
          (Option.get (Complexity.decode γ✝ (Memory.getms m src✝))
            (_ : Option.isSome (Complexity.decode γ✝ (Memory.getms m src✝)) = true)) +
      1 ≤
    (subroutineTimeCost h + recurseTimeCost hf h + localTimeCost h) a
Tactic:
apply Option.mem_bind_of_mem hm
Proof state after:
case h₁.a
α : Type u_1
inst✝⁷ : Complexity.Coding α Memory
β : Type u_2
inst✝⁶ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝⁵ : Complexity.Coding γ Memory
inst✝⁴ : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝³ : Complexity.Computable Encoding.Model fs
inst✝² : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
γ✝ δ✝ : Type
inst✝¹ : Complexity.Coding γ✝ Memory
inst✝ : Complexity.Encoding δ✝ Memory
fs✝ : γ✝ → δ✝
cs✝ : Complexity.CostFunction γ✝ ℕ
hcost : Complexity Encoding.Model fs✝ cs✝
next : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (subroutine' dst✝ src✝ inst✝¹ inst✝ fs✝ cs✝ hcost next)) fm
a : α
m : Memory
hm : m ∈ fm a
⊢ Memory.setms m dst✝
      (Complexity.encode
        (fs✝
          (Option.get (Complexity.decode γ✝ (Memory.getms m src✝))
            (_ : Option.isSome (Complexity.decode γ✝ (Memory.getms m src✝)) = true)))) ∈
    Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ fs✝) (Complexity.decode γ✝ (Memory.getms m src✝))

α : Type u_1
inst✝⁷ : Complexity.Coding α Memory
β : Type u_2
inst✝⁶ : Complexity.Encoding β Memory
f : α → β
tp : TracedProgram
γ δ : Type
inst✝⁵ : Complexity.Coding γ Memory
inst✝⁴ : Complexity.Encoding δ Memory
fs : γ → δ
cs : Complexity.CostFunction γ ℕ
inst✝³ : Complexity.Computable Encoding.Model fs
inst✝² : Complexity Encoding.Model fs cs
size : α → ℕ
fm : α → Option Memory
fcp : CostedProgram
hf : Program.sound (TracedProgram.toProgram (toTracedProgram fcp)) f size
dst✝ src✝ : Source
γ✝ δ✝ : Type
inst✝¹ : Complexity.Coding γ✝ Memory
inst✝ : Complexity.Encoding δ✝ Memory
fs✝ : γ✝ → δ✝
cs✝ : Complexity.CostFunction γ✝ ℕ
hcost : Complexity Encoding.Model fs✝ cs✝
next : CostedProgram
h : TracedProgram.sound' f size (toTracedProgram (subroutine' dst✝ src✝ inst✝¹ inst✝ fs✝ cs✝ hcost next)) fm
a : α
m : Memory
hm : m ∈ fm a
⊢ (subroutineTimeCost
                (_ :
                  TracedProgram.sound' f size (toTracedProgram next)
                    ((flip Option.bind fun m =>
                        Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ fs✝)
                          (Complexity.decode γ✝ (Memory.getms m src✝))) ∘
                      fm)) +
              recurseTimeCost hf
                (_ :
                  TracedProgram.sound' f size (toTracedProgram next)
                    ((flip Option.bind fun m =>
                        Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ fs✝)
                          (Complexity.decode γ✝ (Memory.getms m src✝))) ∘
                      fm)) +
            localTimeCost
              (_ :
                TracedProgram.sound' f size (toTracedProgram next)
                  ((flip Option.bind fun m =>
                      Option.map (Memory.setms m dst✝ ∘ Complexity.encode ∘ fs✝)
                        (Complexity.decode γ✝ (Memory.getms m src✝))) ∘
                    fm)))
          a +
        Complexity.ALE.bound Complexity.cost_ale
          (Option.get (Complexity.decode γ✝ (Memory.getms m src✝))
            (_ : Option.isSome (Complexity.decode γ✝ (Memory.getms m src✝)) = true)) +
      1 ≤
    (subroutineTimeCost h + recurseTimeCost hf h + localTimeCost h) a