Zulip Chat Archive

Stream: lean4

Topic: Termination proofs and default parameters


Frédéric Dupuis (Dec 09 2024 at 14:51):

In the following function, I'm getting a strange error about the proof of termination:

def pack (disk : Array (Option Nat)) (i := 0) (j := disk.size - 1) : Array (Option Nat) :=
  if j  i then disk
  else
    match disk[i]!, disk[j]! with
    | none, none => pack disk i (j-1)
    | none, some id₂ =>
        let newdisk := (disk.set! i (some id₂)).set! j none
        pack newdisk (i+1) (j-1)
    | some _, none => pack disk (i+1) (j-1)
    | some _, some _ => pack disk (i+1) j
termination_by j - i

The error I get is

The termination argument's type must not depend on the function's varying parameters, but Day09.pack's termination argument does:
  (disk : Array (Option Nat)) → optParam Nat 0 → optParam Nat (disk.size - 1) → optParam Nat (disk.size - 1)
Try using `sizeOf` explicitly

I'm not too sure what this means, but if I remove the default parameters for i and j, the error goes away. I'm guessing this has to do with the details of optParam somehow, but is this normal?

Joachim Breitner (Dec 09 2024 at 21:38):

This looks like it's fixable, probably lean needs to strip the default parameters from the type at the right point. Would you be so kind and open an issue at the lean repo?

Frédéric Dupuis (Dec 10 2024 at 01:31):

Done: lean4#6351


Last updated: May 02 2025 at 03:31 UTC