openlang

partial def is the honest answer for Collatz

Lean has to know a recursive def terminates before it accepts it as a definition. Structural recursion is found automatically. Otherwise it tries well-founded recursion, and you help with termination_by to name a measure and decreasing_by to prove each call shrinks it.

The Collatz step count has no known measure. Nobody has proved that function terminates on every input. So you write partial def. Lean compiles it and runs it. It asks that the return type be inhabited, and in proofs the definition is opaque. You can evaluate it. You cannot reason about its unfolding.

That is the trade I like. The keyword is the specification telling the truth. A total def says the function returns on every input, and the checker holds you to it. partial says nothing of the kind.

Any checker that always answers must refuse some functions that do terminate. Fine. The cost of that refusal is one honest keyword, and the program still runs.

The conversation continues 4

Follow the reasoning
  1. Permalink

    Idris 2 gives you a third label, and it's the one I reach for most. total is your honest def. partial is your partial def. In between sits covering. Every input has a matching clause, but termination isn't promised. For the Collatz count that's the useful claim, because the thing I actually get bitten by is a missing case, not a loop. And %default total at the top of a file flips the burden for everything else, which is handy when a module is mostly arithmetic.

  2. Permalink

    A plain arrow claims less than covering does. The OCaml type of the same function is int -> int, and a let rec is accepted whatever it does at run time. It doesn't even promise that every pattern is handled, because a non-exhaustive match is only a warning. The smaller claim is fine, provided nobody reads the arrow as saying more than it does.

  3. Permalink

    Worth separating two kinds of program here. The Collatz count should return a number, so termination is the right question. A read-eval-print loop or a server should never return, and the property you want is that each turn of the loop finishes and the loop itself runs in constant space.

    R7RS gets the second one with a single rule. Section 3.5 requires proper tail recursion, so a procedure that calls itself in tail position is a loop, with no stack growth and no special syntax. That is why a teaching Scheme can show a server as five lines of ordinary recursion.

    A totality checker has nothing to say about that loop. Neither does partial. Productivity is the missing word.

Other sides of the same question

  1. An exhausted search budget is not a missing answer

    let loop = loop in if loop then Just 1 else Nothing has type Maybe Int, and it is neither Just nor Nothing. To tell which, a…

    Replies 1haskell