SUBVERSIVE-RECURSIONS

Major Section:  MISCELLANEOUS

Subtleties arise when one of the ``constrained'' functions, f, introduced in the signature of an encapsulate event, is involved in the termination argument for a non-local recursively defined function, g, in that encapsulate. During the processing of the encapsulated events, f is locally defined to be some witness function, f'. Properties of f' are explicitly proved and exported from the encapsulate as the constraints on the undefined function f. But if f is used in a recursive g defined within the encapsulate, then the termination proof for g may use properties of f' -- the witness -- that are not explicitly set forth in the constraints stated for f.

Such recursive g are said be ``subversive'' because if naively treated they give rise to unsound induction schemes or (via functional instantiation) recurrence equations that are impossible to satisfy. We illustrate what could go wrong below.

Subversive recursions are not banned outright. Instead, they are treated as part of the constraint. That is, in the case above, the definitional equation for g becomes one of the constraints on f. This is generally a severe restriction on future functional instantiations of f. In addition, ACL2 removes from its knowledge of g any suggestions about legal inductions to ``unwind'' its recursion.

What should you do? Often, the simplest response is to move the offending recursive definition, e.g., g, out of the encapsulate. That is, introduce f by constraint and then define g as an ``independent'' event. You may need to constrain ``additional'' properties of f in order to admit g, e.g., constrain it to reduce some ordinal measure. However, by separating the introduction of f from the admission of g you will clearly identify the necessary constraints on f, functional instantiations of f will be simpler, and g will be a useful function which suggests inductions to the theorem prover.

Note that the functions introduced in the signature should not even occur ancestrally in the termination proofs for non-local recursive functions in the encapsulate. That is, the constrained functions of an encapsulate should not be reachable in the dependency graph of the functions used in the termination arguments of recursive functions in encapsulate. If they are reachable, their definitions become part of the constraints.

The following event illustrates the problem posed by subversive recursions.

(encapsulate (((f *) => *))
  (local (defun f (x) (cdr x)))
  (defun g (x)
    (if (consp x) (not (g (f x))) t)))

Then it would be possible to prove the theorem:

(defthm f-not-identity
  (not (equal (f '(a . b)) '(a . b)))
  :rule-classes nil
  :hints (("Goal" :use (:instance g (x '(a . b))))))

But then we could functionally instantiate f-not-identity, replacing f by the identity function, to prove nil! This is bad.

(defthm bad
  nil
  :rule-classes nil
  :hints
  (("Goal" :use (:functional-instance f-not-identity (f identity)))))

This sequence of events was legal in versions of ACL2 prior to Version 1.5. When we realized the problem we took steps to make it illegal. However, our steps were insufficient and it was possible to sneak in a subversive function (via mutual recursion) as late as Version 2.3.

We now turn to the plausibility of the bogus argument above. Why might one even be tempted to think that the definition of g above poses no constraint on f? Here is a very similar encapsulate.

(encapsulate (((f *) => *))
  (local (defun f (x) (cdr x)))
  (defun map (x)
    (if (consp x)
        (cons (f x) (map (cdr x)))
      nil)))

As a ``user-friendly'' gesture, ACL2 implicitly moves map-like functions out of encapsulations; logically speaking, they are introduced after the encapsulation. This simplifies the constraint. When the constraint cannot be thus simplfied the user is advised, via the ``infected'' warning, to phrase the encapsulation in the simplest way possible.

The lingering bug between Versions 1.5 and 2.3 mentioned above was due to our failure to detect the g-like nature of some functions when they were defined in mutually recursively cliques with other functions. The singly recursive case was recognized. The bug arose because our detection ``algorithm'' was based on the ``suggested inductions'' left behind by successful definitions. We failed to recall that mutually-recursive definitions do not, as of this writing, make any suggestions about inductions and so did not leave any traces of their subversive natures.

We conclude by elaborating on the criterion ``involved in the termination argument'' mentioned at the outset. Suppose that function f is recursively defined in an encapsulate, where the body of f has no ``ancestor'' among the functions introduced in the signature of that encapsulate, i.e.: the body contains no call of a signature function, no call of a function whose body calls a signature function, and so on. Then ACL2 treats f as though it is defined in front of that encapsulate form; so f is not constrained by the encapsulate, and its definition is hence certainly not subversive in the sense discussed above. But suppose to the contrary that some function introduced in the signature is an ancestor of the body of f. Then the definition of f is subversive if moreover, its termination proof obligation has an ancestor among the signature functions. Now, that proof obligation involves terms from the first argument of selected calls of IF, as well as recursive calls; for a detailed discussion, see ruler-extenders. The important point here is that for the recursive calls, only the arguments in ``measured'' positions are relevant to the termination proof obligation. Consider the following example.

  (encapsulate
   (((h *) => *))
   (local (defun h (n) n))
   (defun f (i n)
     (if (zp i)
         n
       (f (1- i) (h n)))))