Zulip Chat Archive

Stream: lean4

Topic: Unification with free variables of structure type


Rish Vaishnav (Oct 03 2022 at 15:59):

I was wondering how Lean is going about unifying up (down b) and b in this definition from the prelude:

theorem PLift.up_down {α : Sort u} (b : PLift α) : Eq (up (down b)) b := rfl

My guess is that expands b to up (down b) (where it knows not to infinitely expand b in the LHS because it's already been projected), and more generally, if we have any structure

structure Test (α : Sort u) : Type u where
  a1 : α
  a2 : α
  ...
  an : α

and a free variable t : Test, unification will expand t wherever it occurs to Test.mk t.a1 t.a2 ... t.an. Is my suspicion correct? I'm trying to find where in the code this expansion happens, I found toCtorWhenStructure in src/Lean/Meta/WHNF.lean but it looks like that only applies to recursor applications.

Rish Vaishnav (Oct 03 2022 at 17:00):

Aha, I found try_eta_struct in src/kernel/typechecker.cpp. Is there an equivalent somewhere in the Lean codebase?

Kevin Buzzard (Oct 03 2022 at 17:05):

I don't think Lean will expand b to up (down b), it's more likely simplifying up (down b) back to b (probably using eta for structures).

Rish Vaishnav (Oct 03 2022 at 17:13):

Yeah from the typechecker code it looks like it's not actually doing any expansion, it's actually checking for specifically this case:

 /** \brief check whether \c s is of the form <tt>mk t.1 ... t.n</tt> */
bool type_checker::try_eta_struct_core(expr const & t, expr const & s) { ... }

bool try_eta_struct(expr const & t, expr const & s) {
     return try_eta_struct_core(t, s) || try_eta_struct_core(s, t);
}

(and try_eta_struct is called from is_def_eq)


Last updated: Dec 20 2023 at 11:08 UTC