leanprover / leanprover/lean4

exact? takes unreasonably long

Open
#12,754 1 comment 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

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

Description

In the following program, exact? takes unreasonably long (4 minutes):

structure S where
  data : List Nat
  ne : data ≠ []
  p1 : data.head ne = 0
  p2 : data.getLast ne = 42
  p3 : data.length > 1

def S.tl (s : S) : S where
  data := if s.data[1]'s.p3 = 0 then s.data.tail else s.data
  ne := sorry
  p1 := sorry
  p2 := sorry
  p3 := sorry

theorem S.ind {motive : S → Prop}
    (step : ∀ s, motive s.tl → motive s)
    (base : ∀ s, s.data[1]'s.p3 ≠ 0 → motive s)
    (s : S) : motive s := by
  rcases s with ⟨data, ne, p1, p2, p3⟩
  let s' : S := ⟨data, ne, p1, p2, p3⟩
  induction data
  case nil => simp at ne
  case cons head tail hi =>
    by_cases h : s'.data[1]'s'.p3 = 0
    · refine step s' ?_
      show motive ⟨if _ then _ else _, _, _, _, _⟩
      simp only [if_pos h, s', List.tail_cons]
      exact? -- takes 4 minutes, and produces a broken proof
      /- this works: `exact hi _ _ _ _` -/
    · exact base s' h

When it eventually does finish, it returns this error:

error: found a proof, but the corresponding tactic failed:
  (expose_names; exact ((fun a =>
        hi
          (Eq.trans
              (ite_congr (Eq.refl ((head :: tail)[1] = 0)) (fun a => Eq.refl tail) fun a => Eq.refl (head :: tail))
              ((fun x_0 x_1 x_2 x_3 => (fun x_0 x_1 x_2 x_3 => if_pos h) x_0 x_1 x_2 x_3)
                (instDecidableEqNat (head :: tail)[1] 0) (List Nat) tail (head :: tail)) ▸
            tl._proof_1 s')
          (Eq.trans
              (ite_congr (Eq.refl ((head :: tail)[1] = 0)) (fun a => Eq.refl tail) fun a => Eq.refl (head :: tail))
              ((fun x_0 x_1 x_2 x_3 => (fun x_0 x_1 x_2 x_3 => if_pos h) x_0 x_1 x_2 x_3)
                (instDecidableEqNat (head :: tail)[1] 0) (List Nat) tail (head :: tail)) ▸
            tl._proof_2 s')
          (Eq.trans
              (ite_congr (Eq.refl ((head :: tail)[1] = 0)) (fun a => Eq.refl tail) fun a => Eq.refl (head :: tail))
              ((fun x_0 x_1 x_2 x_3 => (fun x_0 x_1 x_2 x_3 => if_pos h) x_0 x_1 x_2 x_3)
                (instDecidableEqNat (head :: tail)[1] 0) (List Nat) tail (head :: tail)) ▸
            tl._proof_3 s')
          (Eq.trans
              (ite_congr (Eq.refl ((head :: tail)[1] = 0)) (fun a => Eq.refl tail) fun a => Eq.refl (head :: tail))
              ((fun x_0 x_1 x_2 x_3 => (fun x_0 x_1 x_2 x_3 => if_pos h) x_0 x_1 x_2 x_3)
                (instDecidableEqNat (head :: tail)[1] 0) (List Nat) tail (head :: tail)) ▸
            tl._proof_4 s')) ∘
      motive)
    s')

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

Run the supplied Lean reproducer and focus on the exact? invocation after simp only [if_pos h, s', List.tail_cons]. Compare its behavior with the explicit exact hi _ _ _ _ proof and the reported generated term; done means exact? completes promptly and produces a valid proof without the tactic failure.

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
Clearly specified
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.