Skip to content

0.2.653

Choose a tag to compare

@TimoKramer TimoKramer released this 19 Nov 23:16
49ebd8f
Clojure model: conformance proofs for recursive models (#445)

* Clojure model: conformance proofs for recursive models

`(a/conforms f)` now proves conformance of recursive modelled functions
without a script (ansatz.clj-model.recursion).

- CljM.fix<k>.induct, proved once per k on demand: for an invariant I on
  arguments, a measure μ and a property Q of results, if one step of F
  establishes Q whenever its recursive calls on arguments in I of smaller
  measure do, then Q (fix<k> F fuel t x…) for every fuel above μ t x….
  The step is proved with `self` abstract, so the fixpoint is never unfolded
  at a symbolic fuel.
- Default choice: Q is the entry's context (the goal with the group call
  abstracted); I a disjunction of templates `∃ v…, x = A[v…]`, starting from
  the entry's arguments and closed under one step (a call on arguments that
  match no template adds one; a case split on the template's lists when an
  argument is left undetermined); μ the summed CljM.weight of the arguments,
  or the weight of one argument - 1 + (members - 1 - tag) for accumulator
  loops and an arity calling the next. `clj_model_inv` closes `I y…` by
  matching a template.
- Lemma generation (proof.clj): recursive ops contribute their equation
  lemmas (eq_<n>) instead of evaluated constructor lemmas, whose right side
  was the brecOn encoding (stuck? did not look through projections); an op
  that wraps another (`CljM.first`) is unfolded once when its pattern cannot
  be refined further; continuations are normalized under their binder.

Co-Authored-By: Claude <noreply@anthropic.com>

* Clojure model: document the measure candidates

---------

Co-authored-by: Claude <noreply@anthropic.com>