Zulip Chat Archive
Stream: lean4
Topic: Maximum recursion depth error
Pim Otte (Jul 21 2023 at 21:06):
In the following example, the last line gives a maximum recursion depth error. Increasing the depth just causes a crash. Any pointers on what I'm doing wrong/how to debug this? (Context: I'm trying to hack a UInt24ish format)
import Mathlib.Data.Nat.Basic
import Mathlib.Tactic.Linarith
def le_sub_one_of_lt (h : n < m) : n ≤ m - 1 := by
induction h with
| refl => simp_arith
| step h ih => {
simp_arith
exact Nat.le_trans ih (by simp_arith)
}
def mwe (a b c : Fin 256) : a.val * 2^16 + b.val * 2^8 + c.val ≤ 2^24 := by
have h1 : b.val * 2^8 ≤ (2^8-1)*2^8 :=
Nat.mul_le_mul_of_nonneg_right (le_sub_one_of_lt b.isLt)
have h2 : a.val * 2^16 ≤ (2^8-1)*2^16 :=
Nat.mul_le_mul_of_nonneg_right (le_sub_one_of_lt a.isLt)
have rhs : 2^24 = (2^8-1)*2^16 + (2^8-1)*2^8 + 2^8 := by simp_arith
simp [ UInt8.toNat, rhs, Nat.add_assoc]
set_option maxRecDepth 4096 in
exact Nat.add_le_add (Nat.add_le_add h2 h1) (c.isLt)
Kyle Miller (Jul 21 2023 at 21:56):
It looks like this works:
theorem mwe (a b c : Fin 256) : a.val * 2^16 + b.val * 2^8 + c.val ≤ 2^24 := by
have h1 : b.val * 2^8 ≤ (2^8-1)*2^8 :=
Nat.mul_le_mul_of_nonneg_right (le_sub_one_of_lt b.isLt)
have h2 : a.val * 2^16 ≤ (2^8-1)*2^16 :=
Nat.mul_le_mul_of_nonneg_right (le_sub_one_of_lt a.isLt)
have h3 := Nat.add_le_add (Nat.add_le_add h2 h1) c.isLt.le
exact h3
Kyle Miller (Jul 21 2023 at 21:56):
Changing have h3 :=
to exact
causes it to do a maximum recursion depth error.
Pim Otte (Jul 22 2023 at 08:22):
Thanks! A little experimentation lead me to:
def ineq_uint24 (a b c : Fin 256) : a.val * 2^16 + b.val * 2^8 + c.val < 2^24 := by
linarith [a.isLt, b.isLt, c.isLt]
which just works.
Do you have any idea why this causes recursion in the first place? Is it trying to unpack the inequality all the way or something?
Last updated: Dec 20 2023 at 11:08 UTC