openlang

partial def: #eval gives 111, but rfl and decide fail. Any checked route without ofReduceBool?

I have a small audit tool, toolchain leanprover/lean4:v4.15.0. The step counter is a partial def, since nobody has a termination proof:

partial def collatzSteps (n : Nat) (acc : Nat := 0) : Nat :=
  if n ≤ 1 then acc
  else if n % 2 == 0 then collatzSteps (n / 2) (acc + 1)
  else collatzSteps (3 * n + 1) (acc + 1)

def withinBudget (n : Nat) : Bool :=
  decide (collatzSteps n ≤ budget)

lake build is clean and #eval Audit.collatzSteps 27 gives 111. But in a separate file:

example : collatzSteps 6 = 8 := by rfl
theorem w27 : withinBudget 27 = true := by decide

Both are rejected. The message says the term does not reduce to the expected value. I suspected the default argument and the Inhabited instance. Writing acc explicitly and adding an instance changed nothing.

native_decide accepts both, but #print axioms then shows Lean.ofReduceBool, which I do not accept.

Two questions:

  1. Why can the compiled code evaluate this while the kernel and decide cannot?
  2. Is there any way to get a kernel-checked fact about this function, short of rewriting it, for instance with fuel?

The conversation continues 2

Follow the reasoning
  1. Permalink

    For me, partial def is compiled as an opaque constant, so the kernel has nothing to unfold. That is why rfl and decide fail even though #eval runs the compiled code. The reference manual says something about this, I think: https://lean-lang.org/doc/reference/latest/

    Maybe write the fuel version, prove facts about it, then put @[extern] on it to use the fast one in the compiled code? Did you try this?

Other sides of the same question

  1. -race reports DATA RACE even though ack is an unbuffered receive. Is time.After to blame?

    Is it possible that the race detector is wrong here, or that I misunderstand what the ack gives me? This is pushgate, a small…

    Replies 4Latest activity go
  2. HMAC mismatch on one webhook only (the one with accents in the name)

    I wrote a small Node checker (plain JS, no build step) that replays saved webhook deliveries and verifies the HMAC-SHA256 bef…

    Replies 7Latest activity typescriptjavascript
  3. memset before free passes at default flags, fails with OPT=-O2

    I'm working on a small C credential holder called vault, built in WSL. vault_release() is supposed to wipe the secret and the…

    Replies 6Latest activity c