Skip to content

recfun terminates proofs print internal unique names in .thm files #1307

Open

Description

@jsiek

A recfun's terminates proof prints in .thm files with internal unique names for its binders, so the printed recfun doesn't parse back.

Refs #1284 (print proofs that round-trip), which fixed the same kind of thing for arbitrary in other proofs. Noticed while implementing #1298 (recfun with a where clause, draft PR #1306).

Repro

python deduce.py test/should-validate/uint_replicate.pf

test/should-validate/uint_replicate.thm then contains:

recfun replicate<T>(n:UInt, x:T) -> List<T>
  measure n of UInt
{
  ...
}
terminates {
  arbitrary n.s64_4 : UInt,
  x.s64_5 : T
uint_monus_one_less[n]
}

The library has the same problem: lib/NatDiv.thm, which the site publishes as NatDiv.thm.html, shows arbitrary a.s1_s2_s8_s40_4 : Nat, ... and assume prem.s1_s2_s8_s40_7.

Pasting that recfun back into a .pf file (with import UInt and import List) fails to parse:

  arbitrary n.s64_4 : UInt,
             ^^^^^^
Missing type annotation. Expected ':' followed by a type.

Observed vs. expected

  • The binders print with their unique names (n.s64_4, prem.s1_s2_s8_s40_7), while uses of them print with base names (uint_monus_one_less[n]). Expected: base names, as in the source (arbitrary n:UInt, x:T).
  • The body of the terminates block after arbitrary isn't indented (uint_monus_one_less[n] starts at column 1, and so does add_both_sides_of_less[...] in NatDiv.thm).

.thm files aren't parsed when importing (checker_types.is_modified only compares their timestamps), so this doesn't break checking. It affects the published stdlib pages and any attempt to reparse a .thm.

Where

GenRecFun.pretty_print in abstract_syntax/declarations.py prints self.terminates.pretty_print(indent + 2), which is the uniquified proof. .thm files show only the statements of theorems, so a recfun's terminates block may be the only proof they print. The fix is probably to print the binders with their base names, as other names in .thm output already are, or to keep the source proof for printing.

Activity

  1. jsiek commented on Nov 20, 2026

    @jsiek
    OwnerAuthor

    A related .thm printing problem, found while answering Codex on #1310 (#1310 (comment)).

    A recursive function that recurses through a view, for example

    recursive count(JCons) -> N {
      count(JViewNil) = Z
      count(JViewCons(x, rest)) = S(count(rest))
    }
    

    with the JCons view from test/should-validate/viewrec_join_list.pf, is converted to a trusted GenRecFun by type_check_view_recursive_fun. The .thm then prints the converted form:

    recfun count(view_arg:JCons) -> N
      measure view_arg of JCons
    {
      switch join_view(view_arg) { ... }
    }
    terminates {
    sorry
    }
    

    Observed: the .thm shows a recfun with an internal parameter name (view_arg) and a sorry, which reads as an unproved termination.

    Expected: the .thm shows the declaration as written: recursive count(JCons) -> N with its view cases.

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