THEORIES

sets of runes to enable/disable in concert 
Major Section:  ACL2 Documentation


Example: '((:definition app)
           (:executable-counterpart app)
           rv
           (rv)
           assoc-of-app)
See:

A theory is a list of ``runic designators'' as described below. Each runic designator denotes a set of ``runes'' (see rune) and by unioning together the runes denoted by each member of a theory we define the set of runes corresponding to a theory. Theories are used to control which rules are ``enabled,'' i.e., available for automatic application by the theorem prover. There is always a ``current'' theory. A rule is enabled precisely if its rune is an element of the set of runes corresponding to the current theory. At the top-level, the current theory is the theory selected by the most recent in-theory event, extended with the rule names introduced since then. Inside the theorem prover, the :in-theory hint (see hints) can be used to select a particular theory as current during the proof attempt for a particular goal.

Theories are generally constructed by ``theory expressions.'' Formally, a theory expression is any term, containing at most the single free variable world, that when evaluated with world bound to the current ACL2 world (see world) produces a theory. ACL2 provides various functions for the convenient construction and manipulation of theories. These are called ``theory functions'' (see theory-functions). For example, the theory function union-theories takes two theories and produces their union. The theory function universal-theory returns the theory containing all known rule names as of the introduction of a given logical name. But a theory expression can contain constants, e.g., 

'(assoc (assoc) (:rewrite car-cons) car-cdr-elim)
and user-defined functions. The only important criterion is that a theory expression mention no variable freely except world and evaluate to a theory.

More often than not, theory expressions typed by the user do not mention the variable world. This is because user-typed theory expressions are generally composed of applications of ACL2's theory functions. These ``functions'' are actually macros that expand into terms in which world is used freely and appropriately. Thus, the technical definition of ``theory expression'' should not mislead you into thinking that interestng theory expressions must mention world; they probably do and you just didn't know it!

One aspect of this arrangement is that theory expressions cannot generally be evaluated at the top-level of ACL2, because world is not bound. To see the value of a theory expression, expr, at the top-level, type 

ACL2 !>(LET ((WORLD (W STATE))) expr).
However, because the built-in theories are quite long, you may be sorry you printed the value of a theory expression!

A theory is a true list of runic designators and to each theory there corresponds a set of runes, obtained by unioning together the sets of runes denoted by each runic designator. For example, the theory constant 

   '(assoc (assoc) (:rewrite car-cons) car-cdr-elim)
corresponds to the set of runes 
   {(:definition assoc)
    (:induction assoc)
    (:executable-counterpart assoc)
    (:elim car-cdr-elim)
    (:rewrite car-cons)} .
Observe that the theory contains four elements but its runic correspondent contains five. That is because some designators denote sets of several runes. If the above theory were selected as current then the five rules named in its runic counterpart would be enabled and all other rules would be disabled.

We now precisely define the runic designators and the set of runes denoted by each.

o A rune is a runic designator and denotes the singleton set containing that rune.

o If symb is a function symbol introduced with a defun (or defuns) event, then symb is a runic designator and denotes the set containing the runes (:definition symb) and (:induction symb), omitting the latter if no such induction rule exists (presumably because the function's definition is not singly recursive).

o If symb is a function symbol introduced with a defun (or defuns) event, then (symb) is a runic designator and denotes the singleton set containing the rune (:executable-counterpart symb).

o If symb is the name of a defthm (or defaxiom) event that introduced at least one rule, then symb is a runic designator and denotes the set of the names of all rules introduced by the named event.

o If str is the string naming some defpkg event and symb is the symbol returned by (intern str "ACL2"), then symb is a runic designator and denotes the singleton set containing (:rewrite symb), which is the name of the rule stating the conditions under which the symbol-package-name of (intern x str) is str.

o If symb is the name of a deftheory event, then symb is a runic designator and denotes the runic theory corresponding to symb.

These conventions attempt to implement the Nqthm-1992 treatment of theories. For example, including a function name, e.g., assoc, in the current theory enables that function but does not enable the executable counterpart. Similarly, including (assoc) enables the executable counterpart (Nqthm's *1*assoc) but not the symbolic definition. And including the name of a proved lemma enables all of the rules added by the event. These conventions are entirely consistent with Nqthm usage. Of course, in ACL2 one can include explicitly the runes naming the rules in question and so can avoid entirely the use of non-runic elements in theories.

Because a rune is a runic designator denoting the set containing that rune, a list of runes is a theory and denotes itself. We call such theories ``runic theories.'' To every theory there corresponds a runic theory obtained by unioning together the sets denoted by each designator in the theory. When a theory is selected as ``current'' it is actually its runic correspondent that is effectively used. That is, a rune is enabled iff it is a member of the runic correspondent of the current theory. The value of a theory defined with deftheory is the runic correspondent of the theory computed by the defining theory expression. The theory manipulation functions, e.g., union-theories, actually convert their theory arguments to their runic correspondents before performing the required set operation. The manipulation functions always return runic theories. Thus, it is sometimes convenient to think of (non-runic) theories as merely abbreviations for their runic correspondents, abbreviations which are ``expanded'' at the first opportunity by theory manipulation functions and the ``theory consumer'' functions such as in-theory and deftheory.