recursive definitions fail if recursive calls appear in the types of matchers
Nobody has claimed this yet.
- 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
- 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
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- 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