Issue: DEFINE-OPTIMIZER

[jrose@Sun.COM (John Rose)]

   Date: Wed, 28 Sep 88 15:32:23 PDT
   From: Jim McDonald <jlm@lucid.com>

   I would prefer to see a rule-based approach, at least as the normal
   way of declaring optimizations.  A more programmable approach would
   be used only when the rule processor is inadequate.

   E.g., I find it much easier to read rules of the form:

    ((<arg-type>*) <result-type> <rewrite-pattern>)
    or
    ((<arg-type>*) (<result-type>*) <rewrite-pattern>)

  ....
Hear, hear.  (See below.)


   Date: Wed, 28 Sep 88 17:07:21 MDT
   From: sandra%defun@cs.utah.edu (Sandra J Loosemore)

   ...while I think that just about all
   compilers do some kind of pattern-matching transformations, everybody
   seems to use a different technique and syntax for specifying them, and
   we'd probably get into religious wars if we tried to standardize one
   or another of them.  (I know of at least a half-dozen different ones
   that have been used in the various compilers developed here at Utah
   within the past 2 or 3 years!)
Perhaps CLOS can eventually supply a partial consensus on how to organize
these things.  (See below.)

   Date: Thu, 29 Sep 88 11:20 EDT
   From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>

   I think the way Symbolics does its optimizers (I haven't looked recently) is
   to allow multiple optimizers on a function and to give each a name, so that
   you can selectively redefine each. In effect, it defines

    INTERNAL-DEFINE-OPTIMIZER function optimizer-name bvl &BODY forms

   so that (effectively) you could define DEFINE-OPTIMIZER as 

    (DEFMACRO DEFINE-OPTIMIZER (NAME BVL &BODY FORMS)
      `(INTERNAL-DEFINE-OPTIMIZER ,NAME ANSI-CL-INTERFACE ,BVL ,@FORMS))

  ....
CLOS has a mechanism for named function parts; see below.


   Date: Fri, 30 Sep 88 12:07:09 PDT
   From: Jim McDonald <jlm@lucid.com>
  ...

   I should note that Lucid's compiler-macro facility allows one to
   define a symbol to be treated as a function at eval-time but a macro 
   at compile-time.  One obvious use of compiler-macros is to implement
   optimizers.  The drawback is the one I alluded to earlier -- there is
   just one compiler-macro for a symbol, so you run the risk of a
   brain-dead dotimes if you try to optimize it as in my example above.

   (I'd be tempted to suggest a compiler-macro-time analog to defadvice,
    but that seems too hairy, too dependent on the whole idea of
    compiler-macros, and too fraught with the dangers I railed against
    earlier.)
Yes it's hairy, but maybe we can lean on CLOS.

  ....

Attaching multiple transformation rules on one function seems superior
to having to express all the logic in a monolithic optimizer function.
After all, some Lisp functions will be complex enough to admit several
independent optimization strategies, each encodable by a different rule.
Perhaps two vendors or programmers want to add strategies to the same
function; it's unclear how to do this through a monolithic optimizer.

One might object that only the function's author should get to optimize
it, but that's not the case when the function is well-known and the
occasion for optimizing it arises when some specialized __argument__
appears for it.  E.g., (SQRT (MY-EXPONENTIAL X)) => (MY-EXPONENTIAL (/ X
2)), or perhaps something like (SEARCH WORD (MY-INDEXED-STRING X)) =>
(MY-INDEXED-SEARCH WORD X).

Even if it's agreed that we want multiple optimization rules on a single
function, there is still the problem of (1) arranging for the separate
compilation and eventual combination of the rules, and (2) specifying
the language(s) used to write the  patterns which guard the rules.

I believe CLOS supplies excellent answers to (1), and eventually will
enable an answer to (2).

It seems to me that, in the interests of economy, whenever there is a
situation in Common Lisp where multiple, separately compilable program
fragments are being combined into single functions (e.g., DEFADVICE,
optimizer rules), that service should be if at all possible supplied
by CLOS.  Using CLOS has a number of advantages:

 * Implementors have less work, since they use CLOS method combination
   machinery.  In some cases, they may only need to write a
   DEFINE-METHOD-COMBINATION which organizes the program fragments
   the way they want.

 * Users have a standard interface for defining, undefining, and
   querying for program fragments.

 * Any CLOS program management tools (e.g., browsers) are immediately
   applicable.

To summarize, you get the usual advantages of integration.

Classes per se needn't enter the picture at all.  I'm thinking of
something like this, for starters:

	(defmethod compiler:transform sqrt-exp ((fn (eql 'sqrt)) &rest args)
	  (backquote-case args
	    (`((my-exp ,x)) `(my-exp (/ ,x 2)))
	    (otherwise (call-next-method))))

(In place of the hypothetical BACKQUOTE-CASE, put your own favorite
pattern matcher.)  The key is using the method qualifier syntax
(SQRT-EXP, here) for differentiating fragments of code.  If the CLOS
specializer syntax is usable ((EQL 'SQRT), here), that's great, but
unspecialized methods are perfectly valid too.

[Parenthetical Note:  To implement advice this way, you'd probably want
 to introduce a new function specifier syntax, analogous (SETF FOO):
	(defmethod (advise foo) :before ensure-open-foo-files (&rest ignore)
	  (declare (ignore ignore))
	  (unless (foo-files-open-p) (open-foo-files)))
 Note that use of two method qualifiers.  That's OK, and the abstraction's
 DEFINE-METHOD-COMBINATION declaration gets to assign the appropriate
 meaning to them.]

That should show how CLOS addresses problem (1), of managing code
fragments.

Problem (2), the construction of rule guard patterns, may be partially
addressible in CLOS, some day.  The key is realizing that your favorite
pattern language for Lisp forms probably has enough structure to impose a
type/subtype structure on the universe of Lisp forms.  In other words,
it makes sense to pretend that patterns in your language (e.g.,
`((my-exp ,x)) above) define form types, and that there is an inclusion
structure on these types, with less specific patterns being supertypes.
(When talking about these issues to the CLOS people, I have referred to
such a system of patterns or predicates as a "description language".)

If CLOS provides enough extensibility of specializer syntax (and that's
a big if, actually), it will be possible to express optimizer rules
even more cleanly, using CLOS.  Here's a final example, in which
a form-discriminating specializer is used (with a syntax pulled
out of a hat, I admit):

	(defmethod compiler:transform ((:form `(sqrt (my-exp ,x))))
	  `(my-exp (/ ,x 2)))

Note that since the specializers suffice to differentiate the rules,
there is less need for qualifiers (e.g., the symbol SQRT-EXP above).

The CLOS spec. does not discuss extensibility of specializers, yet.
For this, we await the famous but mysterious third chapter of the spec,
the Meta-Object Protocol.

By the way, a useful second argument to COMPILER:OPTIMIZE
would be an environment, to allow for type checking or macroexpansion.

I've used list structure patterns in the examples above, but I
could equally well have used patterns which discriminated things
like declared type, if I understood enough about Lisp compiler
type inference to construct a plausible example.

As Sandra says, there are any number of pattern languages out there.
I'm certainly not suggesting it's easy to settle on one, but I am
saying that using CLOS would help us settle some of the simpler issues
(like separate compilation of rules), allowing us to devote more energy
to the hard ones (like pattern languages).  In fact, I don't see why
several pattern languages couldn't be used in the same Lisp.  After all,
EQL and class specializers co-exist now, and they could be viewed as two
different languages.

The bottom line is that CLOS has a lot of services to offer, and Common
Lisp should take advantage of them where possible.

				-- John