Zulip Chat Archive

Stream: lean4

Topic: unfold loops indefinitely


pandaman (Feb 23 2022 at 04:08):

Hi. I have encountered a situation where unfold tactic loops indefinitely (until a timeout is reached), and it depends on the use of match inside a proof in the definition.
Here is the example:

def PositionalNotation {base: Nat} {h: base > 1} := List (Fin base)
def toPositionalNotation {base: Nat} {h: base > 1} (n: Nat): @PositionalNotation base h :=
  if isLt: n < base then
    []
  else
    let rem := n % base;
    let quot := n / base;
    let h': base > 0 := by {
      sorry;
    };
    let n_gt_0: n > 0 := by {
      -- replacing the following "match" with "sorry" fixes the infinite loop.
      match Nat.lt_or_ge n base with
      | Or.inl _ => sorry;
      | Or.inr _ => sorry;
    };
    Fin.mk rem (Nat.mod_lt n h') :: @toPositionalNotation base h quot
termination_by _ n => n
decreasing_by {
  sorry;
}

theorem three_gt_one: 3 > 1 := by decide;
theorem ex1: @toPositionalNotation 3 three_gt_one 5 = [] := by {
  -- this "unfold" loops indefinitely:
  -- (deterministic) timeout at 'whnf', maximum number of heartbeats (50000) has been reached (use 'set_option maxHeartbeats <num>' to set the limit)
  unfold toPositionalNotation;
}

The unfold at last loops until the timeout, but if we replace match in n_gt_0 with sorry, the unfold unfolds the definition as expected.
I'm using Lean (version 4.0.0-nightly-2022-02-22, commit c932d9d33cea, Release) on Windows 10 with Lean4 VSCode extension.

Mario Carneiro (Feb 23 2022 at 06:21):

I think this is working as intended

Mario Carneiro (Feb 23 2022 at 06:23):

unfold unfolds all instances of the chosen constant, which means it usually diverges when applied to recursive functions. I'm not sure what the best ways to do this in lean 4 are, lean 3 would use rw [foo] or simp only [foo] {single_pass := tt} to limit the unfolding. Perhaps unfold has a config option for this

pandaman (Feb 23 2022 at 07:27):

But without match, it unfolds only one step. At least, the behavior looks inconsistent.

Mario Carneiro (Feb 23 2022 at 11:30):

This seems to be a bug. I wrote some diagnosis at leanprover/lean4#1026


Last updated: Dec 20 2023 at 11:08 UTC