leanprover / leanprover/lean4

recursive definitions fail if recursive calls appear in the types of matchers

Open
#1,694 5 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

P-low
Dominant language
Lean
Stars
9.2k
Forks
990
Avg merge
1d 17h
Merged PRs (30d)
175

Description

Prerequisites
  • Put an X between the brackets on this line if you have done all of the following:
    • Checked that your issue isn't already filed.
    • Reduced the issue to a self-contained, reproducible test case.
Description

In the following code (sorry, tried to make it even smaller, but couldn't), a "failed to prove
termination" error shows up in the definition of variable asdf, despite that the
statement proving well-foundedness of the call is directly above in hereIAm.

The error disappears when the line containing aaLtA is commented out,
or extracted to another function, which provides a workaround.

As probably a separate issue, when I try to inline asdf, Lean won't even notice
the variable hereIAm (it won't be shown among other defined variables in
the error description).

open Classical

def least (s: T → Prop) (nonempty: { t: T // s t }): T := sorry

structure WellOrder where
  T: Type
  lt: T → T → Prop
  wf: WellFounded lt

instance (w: WellOrder): WellFoundedRelation w.T where
  rel := w.lt
  wf := w.wf

namespace WellOrder
  @[reducible] def succ.lt (w: WellOrder): (a b: Option w.T) → Prop
    | none, _ => False
    | some _, none => True
    | some a, some b => w.lt a b
  
  def succ (w: WellOrder): WellOrder :=
    {
      T := Option w.T,
      lt := succ.lt w,
      wf := sorry
    }
  
  noncomputable def Morphism.initial.helper
    {wa wb: WellOrder}
    (aSucc: wa.succ.T)
    (fA: wa.T)
  :
    wb.T
  :=
    -- If I inline this, Lean won't even notice the variable
    -- `hereIAm` at all.
    let asdf (aa: { aa: wa.T // wa.succ.lt (some aa) aSucc }) :=
      let hereIAm: wa.succ.lt (some aa.val) aSucc := aa.property
      initial.helper (some aa)
    
    if hEq: some fA = aSucc then
      least
        (fun b =>
          ∀ aa: { aa: wa.T // wa.succ.lt (some aa) aSucc },
            (asdf aa) aa.val ≠ b)
        ⟨
          sorry,
          fun aa eq =>
            -- If the next line is commented out, or extracted
            -- to a separate function, the error disappears.
            let aaLtA: wa.lt aa fA := hEq.symm ▸ aa.property
            sorry
        ⟩
      else sorry
    termination_by initial.helper a fA => a
end WellOrder
Steps to Reproduce
  1. Paste the above code to VS Code.

Expected behavior: Termination is proven.

Actual behavior: An error shows up.

Reproduces how often: Always.

Versions

Both Lean 4 stable and nightly
Lean (version 4.0.0-nightly-2022-09-14, commit fccb60fb69be, Release),
Lean (version 4.0.0, commit 7dbfaf9b7519, Release)

Ubuntu 22.04.1 LTS

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Start by pasting the self-contained example into VS Code and compare the behavior with the aaLtA line present, commented out, or extracted. Investigate the termination-checking behavior for recursive calls in matcher types, then verify that the definition succeeds without the workaround and that hereIAm is recognized.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.