termhints

(in-package "ACL2")

(defstub hq (x) nil)

(defxdoc hq
  :parents (use-termhint)
  :short "Stands for Hint-Quote. Used in @(see use-termhint), delimits terms
that go inside hints from the hint boilerplate surrounding them.")

(defxdoc process-termhint
  :parents (use-termhint)
  :short "Processes termhint objects into regular hint objects."
  :long "<p>Essentially this function is an interpreter for terms containing
calls of cons and binary-append, as well as quoted and pseudo-quoted
objects (see below), which are both treated the same.  If any other functions or any
variable atoms are present, it produces an error.</p>

<p>This capability is intended to be enough to process backtick expressions
where all the commas are accompanied by hq (or other pseudoquote) calls; e.g.:</p>
@({
 (let ((my-a (foo bar baz)))
   (process-termhint `'(:use my-theorem (a ,(hq my-a)))))
=>
 (:USE MY-THEOREM (A (FOO BAR BAZ)))
 })

<p>Process-termhint is always called with @('quote') and @('hq') present in
quotesyms, but there may also be others according to the termhint quotesyms
list, which is stored in a table:</p>
@({
 (table termhint 'quotesyms)   ;; show the list of quotesyms
 (cdr (assoc 'quotesyms (table-alist termhint world))) ;; access the list of quotesyms
 (termhint-add-quotesym my-quotesym) ;; add a new quotesym
 })

")

(table termhint
  nil
  nil
  :guard (or (not (eq key 'quotesyms)) (subsetp-eq '(hq quote) val)))

(table termhint 'quotesyms '(hq quote))

(set-tau-auto-mode nil)

(set-tau-auto-mode t)

(defxdoc use-termhint
  :parents (hint-utils)
  :short "Compute hints based on a term that gets simplified along with the rest of the goal."
  :long "<p>When a theory doesn't lend itself well to rewriting, you might just
use a lot of hints to get through a proof.  But this can become brittle and
unwieldy: you might get through the proof by piling on :use hints, but if that
proof later fails it can be very difficult to debug.  An unstructured pile of
hints doesn't give many clues for how the proof is supposed to work and how to
fix it if it breaks.  Use-termhint provides a different way to structure proofs
that require a lot of hints.  Also see @(see termhint-seq) for a way to give
hints in sequence throughout a termhint term.</p>

<h2>Demo</h2>

<p>As a very simple example, suppose that we have axioms ax1 through ax3, and
we want to prove th:</p>

@({
 (defstub p1 (x) t)
 (defstub p2 (x y z) t)
 (defstub p3 (x y) t)
 (defstub p4 (x) t)
 (defstub b (x) t)
 (defstub c (x) t)
 (defstub d (x) t)

 (defaxiom t1
   (implies (p1 a)
            (p2 a (b a) (c a))))

 (defaxiom t2
   (implies (p2 a b c)
            (p3 a (d c))))

 (defaxiom t3
   (implies (p3 a d)
            (p4 a)))

 (defthm th
   (implies (p1 a)
            (p4 a)))
})

<p>We could do this using some unstructured :use hints (in this case perhaps
only one would suffice).  But we can be more explicit about how the proof
precedes by using use-termhint, as follows.</p>

<p>First, we write a function that follows the process of the proof and
provides hints at certain endpoints:</p>

@({
 ;; A computed hint to use later -- see below.
 (defun my-use-t3-inst-hint (d)
    `(:use ((:instance t3 (d ,d)))))

 (defun hint-for-th (a)
   (b* ((b (b a))
        (c (c a))
        ;; The first thing that we want to conclude is (p2 a b c) for some b, c,
        ;; namely, the ones given by t1.
        ((unless (p2 a b c))
         ;; The unless here causes a case split.  In one case, we assume (p2 a
         ;; b c).  In the other case, we arrive here, and we return a hint that
         ;; proves the subgoal by proving (p2 a b c).  This hint is
         ;; double-quoted because in general we return the quotation of a
         ;; computed hint expression; in this case, the computed hint we want
         ;; is '(:use t1).
         ''(:use t1))
        ;; Now we can assume (p2 a b c).  Next we want to show (p3 a d) for some d,
        ;; by t2.
        (d (d c))
        ((unless (p3 a d))
         ;; In the case where we're assuming (not (p3 a d)), prove it by using t2.
         ;; Notice the uses of (hq ...) below: these are specially processed by
         ;; use-termhint, so that (hq b) will be replaced by whatever the term
         ;; bound to b has been rewritten to.  This will produce the hint:
         ;;    :use ((:instance t2
         ;;           (b (b a))
         ;;           (c (c a))))
         ;; But notice that we don't have to write out (b a) and (c a); instead we
         ;; use the (hq ...) of variables bound to those terms.
         `'(:use ((:instance t2
                   (b ,(hq b))
                   (c ,(hq c)))))))
     ;; Finally, we have (p3 a d), so we just use t3 to get our conclusion.
     ;; We could use the following:
     ;; `'(:use ((:instance t3 (d ,(hq d)))))
     ;; but instead we'll do this, just to show that you can use arbitrary
     ;; computed hints:
     `(my-use-t3-inst-hint ',(hq d))))
})

<p>Now, we submit th with the following hints:</p>
@({
 (defthm th
    (implies (p1 a)
             (p4 a))
    :hints (("goal" :in-theory (disable t1 t2 t3))
            (use-termhint (hint-for-th a))))
})
<p>which suffices to prove it.</p>

<h2>Mechanism</h2>

<p>Use-termhint produces a sequence of two computed hints: an initial :use hint
that adds a @('use-termhint-hyp') hypothesis to the goal, and another computed
hint evaluated when stable under simplification, which looks for the simplified
@('use-termhint-hyp') literal and and extracts a hint from that term.</p>

<p>In the above example, the hypothesis added to the goal is
@('(use-termhint-hyp (hint-for-th a))').
This term is processed and simplified like any other.
In particular, the hint-for-th function is opened (because it is an
enabled, non-recursive function) and, because it contains IFs, causes some case
splits.  In each of the three cases, once everything settles down, the
use-termhint-hyp literal remains and contains a term specifying the hint to
give for that case.  This hint is taken care of by the later computed hint,
which strips that hypothesis from the clause and then gives a hint
corresponding to what was in the use-termhint-hyp hypothesis.</p>

<h2>Details</h2>

<p>The @('hq') trick, or something like it, is necessary to allow the hint
object to contain terms that are simplified and beta-reduced by the prover as
well as hint boilerplate that is not.  The function @(see process-termhint) is
used to produce normal hint objects from these; it interprets calls of
@('cons') and @('append') and treats calls of @('hq') like @('quote').</p>

<p>Other quote-like symbols can be added to this list.  In particular, it may
be useful to add symbols that have certain congruences or rewriting properties.
For example, if you want to expand a certain function call and that function
has a congruence on its first argument, you may want to introduce an HQ-like
symbol that has the same congruence:</p>

@({
 (defun my-hq (x) (my-fix x))
 (defcong my-equiv equal (my-hq x) 1)
 (in-theory (disable my-hq (my-hq) (:t my-hq)))
 (termhint-add-quotesym my-hq)

 (defthm ...
   :hints ((use-termhint
            (let ((arg ...))
               `(:expand ((my-fn ,(my-hq arg))))))))
 })
")

(def-b*-binder termhint-seq
  :decls ((declare (xargs :guard (and (consp args) (not (cdr args)) (not forms)))
     (ignorable forms)))
  :body `(termhint-seq ,(CAR ARGS) ,REST-EXPR))

(defxdoc termhint-seq
  :parents (use-termhint)
  :short "Sequence hints within a @(see use-termhint) term."
  :long "<p>Termhint-seq is both a standalone macro and a B* binder that allows
hints to be sequenced within a @(see use-termhint) term.  For example:</p>

@({
 (defun my-sequenced-hints (x)
   (declare (xargs :normalize nil))
   (termhint-seq
     `'(:use ((:instance foo (a ,(hq x)))))
      (if (bar x)
          `'(:use ((:instance foo-when-bar (q ,(hq x)))))
        `'(:expand ((bar ,(hq x)))))))
})

<p>Here, the hint form @('(use-termhint (my-sequenced-hints x))') will (when
stable under simplification) first issue a hint using an instance of @('foo'),
then cause a case split on @('(bar x)') and when stable under simplification
again, use an instance of @('foo-when-bar') in the case where @('(bar x)') is
assumed true and expand @('(bar x)') in the other case.</p>

<p>Note the @(':normalize nil') declaration: this is useful for functions that
use @('termhint-seq'), because it makes use of @('hide') to keep the second set
of hints from causing case splits before the first set of hints is in play;
normalization tends to disrupt this.</p>

<p>A @('b*') binder form of termhint-seq also exists; the following function is
equivalent to the one above:</p>

@({
 (defun my-sequenced-hints (x)
   (declare (xargs :normalize nil))
   (b* (((termhint-seq `'(:use ((:instance foo (a ,(hq x)))))))
        ((when (bar x))
         `'(:use ((:instance foo-when-bar (q ,(hq x)))))))
      `'(:expand ((bar ,(hq x))))))
})

<p>The argument to the @('termhint-seq') binder is the first hint and the rest
of the @('b*') form after that binder is the second hint.</p>")

(set-tau-auto-mode nil)

(set-tau-auto-mode t)

(def-b*-binder hintcontext
  :decls ((declare (xargs :guard (not forms))
     (ignore forms)))
  :body `(hintcontext ,(CAR ARGS) ,REST-EXPR))

(def-b*-binder hintcontext-bind
  :decls ((declare (xargs :guard (not forms))
     (ignore forms)))
  :body `(hintcontext-bind ,(CAR ARGS) ,REST-EXPR))

(defxdoc hintcontext
  :parents (function-termhint)
  :short "Name a context within a function definition for later use in @(see function-termhint)."
  :long "
<p>Usage:</p>
@({
 (hintcontext name body)
 })
<p>is logically equivalent to body, and should execute as body with no
overhead, but sets a name for the current context that can be referenced by
@(see function-termhint).</p>

<p>The following @(see b*) binder form is equivalent:</p>
@({
 (b* (((hintcontext name))
      ...)
    ...)
 })")

(defxdoc hintcontext-bind
  :parents (function-termhint)
  :short "Bind variables for use in @(see function-termhint)."
  :long "
<p>Usage:</p>
@({
 (hintcontext-bind bindings body)
 })
<p>is logically equivalent to body, and should execute as body with no
overhead, but sets up variable bindings that can be used in @(see function-termhint).</p>

<p>The following @(see b*) binder form is equivalent:</p>
@({
 (b* (((hintcontext-bind bindings))
      ...)
    ...)
 })

<p>The main reason to use this is to allow hints to refer to different stages
of a stobj's modifications.  For example:</p>

@({
 (b* (((hintcontxt-bind ((st0 st))))
      (st (update-st-foo x st))
      ((hintcontext-bind ((st1 st))))
      (st (update-st-bar y st))
      ((hintcontext-bind ((st2 st))))
      (st (update-st-baz z st))
      ((hintcontext :after-updates)))
   ...)
 })

<p>If a @(see function-termhint) gives a hint for the @(':after-updates')
context, it will have the following bindings available for use in the hint:</p>
@({
 ((st0 st)
  (st1 (update-st-foo x st))
  (st2 (update-st-bar y (update-st-foo x st)))
  (st  (update-st-baz z (update-st-bar y (update-st-foo x st)))))
 })

")

(defxdoc function-termhint
  :parents (use-termhint)
  :short "Give termhints according to the structure of a function with @(see hintcontext) annotations."
  :long "

<p>Usage (as a computed hint):</p>
@({
 (function-termhint function-name case1 case2 ...)
})
<p>where each case is of one of the following two forms, and each ctxname is the
name given by some @(see hintcontext) annotation in the named function:</p>
@({
 ;; provides termhint at the ctxname hintcontext
 (ctxname termhint)

 ;; provides termhint at the ctxname1 and ctxname2 hintcontexts
 ((ctxname1 ctxname2 ...) termhint)
 })

<h3>Rationale</h3>
<p>Sometimes when using @(see use-termhint) an otherwise sensible hint might
require replicating much of the body of a function.  This utility offers an
alternative.  First, place @(see hintcontext) annotations in the body of the
function in contexts where it makes sense to give a hint.  Then use @(see
function-termhint), which transforms the body of the function to place
user-provided termhint fragments in those contexts.  For example, if @('foo')
is defined as follows:</p>

@({
 (defun foo (x)
   (if (test1 x)
       (let ((y (foo-y x)))
         (if (test2 y)
             (hintcontext :test2-true (foo-ans1 y x))
           (hintcontext :test2-false (foo-ans2 y x))))
     (hintcontext :test1-false (foo-ans3 x))))
  })

<p>then @('function-termhint') can be invoked as follows:</p>

@({
 (defthm foo-prop
     (prop (foo x))
     :hints ((function-termhint foo
              (:test2-true `(:expand ((foo-ans ,(hq y) ,(hq x)))))
              ((:test1-false :test2-false)
               '(:use ((:instance my-lemma (z x))))))))
 })

<p>This is equivalent to:</p>

@({
 (defthm foo-prop
   (prop (foo x))
   :hints ((use-termhint
             (if (test1 x)
                 (let ((y (foo-y x)))
                   (if (test2 y)
                       `(:expand ((foo-ans ,(hq y) ,(hq x)))) ;; :test2-true
                     '(:use ((:instance my-lemma (z x)))))) ;; :test2-false
              '(:use ((:instance my-lemma (z x)))))))) ;; :test1-false
 })

<p>But note that in the latter form, we replicate the IF and LET structure of
the original function, whereas in the former, we only make reference to the
hintcontext labels and bound variables of that function.</p>

<p>An additional utility, @(see hintcontext-bind), can be used to add variable
bindings that don't actually exist in the function but may be used by the
hints.  This is convenient for reasoning about stobjs: each binding of a stobj
in an executable function must shadow all of its previous bindings, but
@('hintcontext-bind') can make previous bindings also available to termhints.</p>

<h3>Operation</h3>

<p>Function-termhint analyzes the (unnormalized) body of the given function and
transforms it into a termhint term by replacing each @('hintcontext')
annotation with the corresponding hint from the user-provided case list.  This
transformation is done by the function @('term-replace-hintcontexts'), which we
describe below.  It uses an operator @('hintcontext-join') which produces the
first non-NIL hint out of its arguments.  In the following description, we call
this joining two potential hints.  The function
@('term-replace-hintcontexts') behaves as follows:</p>

<ul>
<li>If term is a variable or quote, return NIL.</li>

<li>If term is a hintcontext annotation, find the corresponding hint from the
case list and join this with the result of recurring on the body (third
argument).</li>

<li>If term is a hintcontext-bind annotation, create a @(see b*) term whose
bindings are the (unquoted) second argument and whose body is the result of
recurring on the third argument.</li>

<li>If term is any other kind of RETURN-LAST call, return the result of
recurring on the last argument.  (Note: this means we only process the
@(':logic') part of MBE forms.)</li>

<li>If term is an IF, recur on the then and else branches; if either returns a
non-nil result, return @('(if original-test then-result else-result'),
otherwise NIL.</li>

<li>If term is a function call, join the results of recurring on all the
function arguments.</li>

<li>If term is a lambda call, join the results of recurring on all the
arguments as well as, if the recursive call on the lambda body returns a
non-NIL result, the term @('((lambda formals body-result) . original-args)').</li>

</ul>

")