Zulip Chat Archive

Stream: general

Topic: unfolding structural recursion


Satoshi Kura (Dec 03 2022 at 12:03):

I am trying to define denotational semantics of simply typed lambda calculus using lean 3.49.1 with mathlib (commit 22feff54d70f45fe7f4dfdd7770e32e13f1aa3d4).
However, lean fails to prove an obvious equation about structural recursion at the bottom of the following code.
What do you think is the reason?

import category_theory.closed.cartesian

section

inductive Member {α : Type} : α  list α  Type
| head :  {a as}, Member a (a::as)
| tail :  {a b bs}, Member a bs  Member a (b::bs)

inductive Ty (β : Type)
| base : β  Ty
| fn : Ty  Ty  Ty

inductive Term {β : Type} : list (Ty β)  Ty β  Type
| var   :  {ty ctx}, Member ty ctx  Term ctx ty
| app   :  {ctx dom ran}, Term ctx (Ty.fn dom ran)  Term ctx dom  Term ctx ran
| lam   :  {ctx dom ran}, Term (dom :: ctx) ran  Term ctx (Ty.fn dom ran)

end

section

open category_theory category_theory.category

universes v u w

variables {C : Type u} [category.{v} C] [limits.has_finite_products C] [category_theory.cartesian_closed C]

variables {β : Type} (a : β  C)

noncomputable def Ty.denote : Ty β  C
| (Ty.base b) := a b
| (Ty.fn t1 t2) := t1.denote  t2.denote

noncomputable def ctx_denote : list (Ty β)  C
| [] := limits.terminal C
| (x::xs) := limits.prod (Ty.denote a x) (ctx_denote xs)

noncomputable def term_var_proj {ty : Ty β} : Π {ctx : list (Ty β)}, Member ty ctx  (ctx_denote a ctx  Ty.denote a ty)
| _ Member.head := limits.prod.fst
| (h::tl) (Member.tail m) := begin dsimp [ctx_denote], exact limits.prod.snd end  term_var_proj m

noncomputable def Term.denote : Π {ctx : list (Ty β)} {ty : Ty β}, Term ctx ty  (ctx_denote a ctx  Ty.denote a ty)
| ctx ty (Term.var m) := term_var_proj a m  --  Term.denote a (Term.var m) is defined here.
| ctx cod (Term.app m n) := limits.prod.lift n.denote m.denote  begin dsimp [Ty.denote], exact ((exp.ev _).app _) end
| ctx (Ty.fn dom cod) (Term.lam m) := begin
    dsimp [Ty.denote],
    apply cartesian_closed.curry,
    have m_denote := Term.denote m,
    dsimp [ctx_denote] at m_denote,
    exact m_denote,
end

example {ctx : list (Ty β)} {ty : Ty β} (m : Member ty ctx) : Term.denote a (Term.var m) = term_var_proj a m := rfl
-- type mismatch, term
--   rfl
-- has type
--   ?m_2 = ?m_2
-- but is expected to have type
--   Term.denote a (Term.var m) = term_var_proj a m

end

Last updated: Dec 20 2023 at 11:08 UTC