blob: 8af1ad63ea8b562a6d28aeab5dd2bef592d877b7 [file] [edit]
module
public axiom P : Nat → Prop
public axiom P.intro : P n
public inductive AckFuel : (n m : Nat) → Type where
| step1 : AckFuel 0 m
| step2 : AckFuel n 1 → AckFuel (n + 1) 0
| step3 : (∀ m', P m' → AckFuel n m') → AckFuel (n + 1) m → AckFuel (n+1) (m + 1)
namespace Test1
/--
info: Try this:
[apply] termination_by structural x _ x => x
-/
#guard_msgs in
public def ackermann_fuel : (n m : Nat) → (fuel : AckFuel n m) → Nat
| 0, m, .step1 => m+1
| n + 1, 0, .step2 f => ackermann_fuel n 1 f
| n + 1, m + 1, .step3 f1 f2 =>
ackermann_fuel n (ackermann_fuel (n + 1) m f2) (f1 _ (by exact P.intro))
termination_by?
end Test1
namespace Test2
/--
info: Try this:
[apply] termination_by structural x _ x => x
-/
#guard_msgs in
public def ackermann_fuel : (n m : Nat) → (fuel : AckFuel n m) → Nat
| 0, m, .step1 => m+1
| n + 1, 0, .step2 f => ackermann_fuel n 1 f
| n + 1, m + 1, .step3 f1 f2 =>
ackermann_fuel n (ackermann_fuel (n + 1) m f2) (f1 _ (by as_aux_lemma => exact P.intro))
termination_by?
end Test2
namespace Test3
/--
info: Try this:
[apply] termination_by structural x _ x => x
-/
#guard_msgs in
@[expose] public def ackermann_fuel : (n m : Nat) → (fuel : AckFuel n m) → Nat
| 0, m, .step1 => m+1
| n + 1, 0, .step2 f => ackermann_fuel n 1 f
| n + 1, m + 1, .step3 f1 f2 =>
ackermann_fuel n (ackermann_fuel (n + 1) m f2) (f1 _ (by exact P.intro))
termination_by?
end Test3
namespace Test4
-- This checks that when unfolding abstracted proofs, we do not unfold function calls
-- that were actually there, like the one to `Function.cons` below
/--
error: failed to infer structural recursion:
Cannot use parameter #3:
unexpected occurrence of recursive application
ackermann_fuel
-/
#guard_msgs in
public def ackermann_fuel : (n m : Nat) → (fuel : AckFuel n m) → Nat
| 0, m, .step1 => m+1
| n + 1, 0, .step2 f => ackermann_fuel n 1 f
| n + 1, m + 1, .step3 f1 f2 =>
Function.const _
( ackermann_fuel n (ackermann_fuel (n + 1) m f2) (f1 _ (by exact P.intro))
)
ackermann_fuel
termination_by structural _ _ fuel => fuel
end Test4