Skip to content

Soundness: recfun accepts a measure whose < is not well-founded, proving false #1308

Open

Description

@jsiek

Soundness: a recfun's measure can have any type with a < in scope, including one where < isn't well-founded. A non-terminating function is then accepted, and its defining equation proves false.

Found while documenting recfun for #1306 (where clauses on recfun, #1298). The termination check is older than that PR.

Repro

recfun_false.pf, with the stdlib:

union Tick { tick }

fun operator < (a : Tick, b : Tick) { true }

recfun loop(n : UInt) -> UInt
  measure tick of Tick
{
  1 + loop(n)
}
terminates {
  arbitrary n:UInt
  evaluate
}

theorem oops: false
proof
  have eq: # loop(0) # = 1 + loop(0) by expand loop.
  have bad: loop(0) < # loop(0) # by replace eq.
  apply uint_less_irreflexive[loop(0)] to bad
end
$ python deduce.py recfun_false.pf
recfun_false.pf is valid

Observed vs. expected

  • Observed: the file is valid, including theorem oops: false.
  • Expected: the recfun is rejected, because its measure's type has no well-founded <.

A user-defined < isn't needed. A measure of type Int (or Rat) is accepted too: recfun h(n : Int) -> UInt measure n of Int { 1 + h(n - +1) } only asks for a proof of n - +1 < n, which is true, but h never terminates.

Cause

checker_pipeline.py, GenRecFun case of check_proofs: the obligation is that the measure decreases at each recursive call under stmt.less. That is whatever < uniquify finds in scope, which GenRecFun.uniquify records as less=list(env_map.get('<', [])). Nothing checks that the measure type, measure_ty, is one whose < is well-founded (Nat or UInt), or that less is the standard library's < for that type.

Possible fix

Restrict measure_ty to Nat and UInt, and resolve less to the standard library's < on that type rather than any < in scope. Other well-founded orders, such as lexicographic pairs, could be added later along with a proof that the order is well-founded.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions