Zulip Chat Archive

Stream: lean4

Topic: How does constructor interact with inequalities.


Shreyas Srinivas (Apr 05 2023 at 14:46):

I have an #mwe for something that I find weird. I am trying to understand whatconstructor is doing here.

def N (m : ) := {n :  // n  m}

def incr_m {m : } (n : N m) : N (m+1) := by
  constructor
  constructor

#print incr_m

Explanation : N m is the set of natural numbers greater than or equal to m. incr_m is supposed to be something like below:

def incr_m {m : } (n : N m) : N (m+1) := by
  constructor
  case val => exact n.val + 1
  case property => linarith [n.property]

printing this yields

def incr_m : {m : }  N m  N (m + 1) :=
fun {m} n => { val := n + 1, property := (_ : m + 1  n + 1) }

which is fine.

But I have been playing around with repeat' in the last few days. In the #mwe just applying repeat' constructor closed all goals. Then I manually repeated it and in two applications it claimed that all goals were met. So I printed it out

def incr_m : {m : }  N m  N (m + 1) :=
fun {m} n => { val := m + 1, property := (_ : Nat.le (m + 1) (m + 1)) }

How did constructor magically infer the function I wanted to compute (incorrectly of course)?

Shreyas Srinivas (Apr 05 2023 at 14:47):

I thought constructor was lean4's equivalent of lean 3's split

Alex J. Best (Apr 05 2023 at 15:14):

(your mwe is missing imports)
constructor is the lean 4 equivalent of the lean 3 tactic constructor which tries all constructors of an inductive type in turn, split on the other hand is a special case of this when the type has only one constructor (e.g. an and statement, where applying this constructor splits the goal into two).
I think whats happening here is that the definition of le on naturals is an inductive type docs4#Nat.le with two constructors, i.e. lean knows that there are only two ways (possibly chained) to prove a natural is le another.
The constructor tactic simply to tries to apply each of these in turn, so it applies apply Nat.le.refl (every natural number is le itself) which unifies the metavariable (the value of the function) with the lower bound, then once that is assigned there is nothing else to prove.
This is one reason why people don't use tactics to make defs!
so your code really does this

import Mathlib.Data.Nat.Basic
def N (m : ) := {n :  // n  m}

def incr_m {m : } (n : N m) : N (m+1) := by
  apply Subtype.mk
  apply Nat.le.refl

btw do you know the tactic show_term its very helpful for unpacking what tactics are doing under the hood (and often easier than reading the source code)

Shreyas Srinivas (Apr 05 2023 at 15:38):

Sorry about the imports. I wrote this inside a large file. About show_term thanks for recommending it. I tried to search the docs for it. It doesn't seem to be in the docs

Shreyas Srinivas (Apr 05 2023 at 15:39):

If I understand your explanation correctly, if the goal is a value (rather than a prop), then in tactic mode, there is a risk that it will be filled with the wrong hypothesis. In this case constructor found le.refl and an appropriate filler for the meta variable for the val goal.

Patrick Massot (Apr 05 2023 at 15:41):

https://leanprover-community.github.io/mathlib4_docs/Std/Tactic/ShowTerm.html

Shreyas Srinivas (Apr 05 2023 at 15:42):

oh right. lean4 naming conventions.

Alex J. Best (Apr 05 2023 at 15:48):

Shreyas Srinivas said:

If I understand your explanation correctly, if the goal is a value (rather than a prop), then in tactic mode, there is a risk that it will be filled with the wrong hypothesis. In this case constructor found le.refl and an appropriate filler for the meta variable for the val goal.

Yeah the real issue is that tactics are very smart (sometimes) and fill in whatever they can, a goal whose type is a type is no different to most tactics. When proving things it doesn't matter most of the time if a tactic solves a goal in a way you weren't anticipating as any proof is just as good. But with defs/data there may be multiple ways to fill a goal that are distinct


Last updated: Dec 20 2023 at 11:08 UTC