Issue: DEFINE-OPTIMIZER (Version 2)

[Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>]

Most of the discussion which came from the previous draft came from the
following two points:

 1. Some people were very confused by the use of STRING-APPEND as an
    example, apparently because so many implementations offer 
    STRING-APPEND as an extension that everyone thought I was suggesting
    that users could and should write optimizers for CL built-in functions,
    something which I don't think is a good idea.

 2. Some people wanted a pattern matching facility intertwined with this.

I addressed these problems in the following ways:

 1. I removed the STRING-APPEND example and replaced it with a couple
    of small examples taken directly from the Common Lisp Macsyma (R)
    sources, since it was Macsyma that motivated this issue in the first
    place.  Macsyma actually has some considerably more elaborate 
    optimizers, but it would have been a lot more trouble for me to get
    someone to authorize me to release the sources for them than for 
    these simple examples, so I hope these will suffice.

 2. I added a note to the Discussion mentioning that this was a nice idea,
    but that we don't have time to develop such a thing. However, as I
    hope the examples illustrate, there is still quite a bit that can be
    done even with the simpler facility proposed here, and I hope people
    will seriously consider this without getting bogged down in a bunch
    of really orthogonal issues.

-----
Issue:        DEFINE-OPTIMIZER
References:   None
Category:     ADDITION
Edit history: 28-Sep-88, Version 1 by Pitman
	      10-Mar-89, Version 2 by Pitman (clarifications, new example)
Status:	      For Internal Discussion

Problem Description:

  Often a general functional interface could be bypassed given explicit
  knowledge of the arguments passed. This may happen when the arguments
  are constant (or otherwise inferrable), an argument type is known (eg,
  due to use of THE or DECLARE), or when some particular pattern of
  optional, rest or keyword arguments is apparent.

  Most implementations provide internally for optimization of generalized
  function call interfaces to more specialized ones, but such an
  optimization facility is not provided to Common Lisp users.

  The absence of this facility in a portable fashion means that some
  CL programs run slower than they need to in some implementations.

Proposal (DEFINE-OPTIMIZER:NEW-FACILITY):

  Introduce a facility for declaring compiler optimizations.

  DEFINE-OPTIMIZER name arglist &body forms

   Defines a compiler optimizer for a function named NAME. The arglist
   is treated exactly like the arglist to DEFMACRO, and may include
   &ENVIRONMENT and &WHOLE.

   When the optimizer is invoked, the forms are executed in the context
   of bindings specified by the arglist, and two values are yielded,
   RESULT and VALID-P. (If either of the first or second return value
   is non-NIL, then the first return value is considered valid).

   If the result is valid, it is a form which is preferrable to evaluate
   instead of the indicated call.

  OPTIMIZE-EXPRESSION-1 form env

   Similar to MACROEXPAND-1. Invokes the optimizers for the top level of
   FORM, but does not iterate on the result. Returns two values:
   RESULT and CHANGED-P. 

   Note: If an optimizer returns a result which is not valid,
    OPTIMIZE-EXPRESSION-1 hides the fact by returning FORM,NIL
    rather than NIL,NIL.

  OPTIMIZE-EXPRESSION form env

   Iterates calling OPTIMIZE-EXPRESSION-1 until the CHANGED-P result
   is NIL.

  An implementation must save optimizer definitions created by
  DEFINE-OPTIMIZER in case OPTIMIZE-EXPRESSION is attempted, but is
  not actually required to call OPTIMIZE-EXPRESSION itself. Interpreters,
  for example, may choose to just call the unoptimized form.

  The effect of defining optimizations for functions on the LISP package
  is not defined. (In some implementations, this would clobber or conflict
  with existing advice that may be of higher quality.)

  The editor is advised that a non-binding style note such as the
  following would also be appropriate:

   In general, it is poor style for a programmer to define optimizers for
   functions that he does not maintain. This is because the correct
   implementation of an optimizer for a function usually depends on an
   understanding of the internals of that function. As such, a function 
   definition and any optimizers should be maintained as a unit so that
   they can changes in either can be synchronized as appropriate with the
   other.

Example:

  ;; These examples are taken literally from the Macsyma sources,
  ;; modified only to change DEFOPT to DEFINE-OPTIMIZER. The comments
  ;; were specially written for the X3J13 audience.

  ;; M+ is adds a Macsyma expression to another Macsyma expression.
  ;; The Macsyma internal representation for the sum of X and Y is
  ;; ((MPLUS) X Y). A all the real work is done by SIMPLIFY, which
  ;; reduces the expression as needed necessary. However, SIMPLIFY
  ;; is very complicated, and considerable speed can be gained by
  ;; entering it at specific known places.

  (DEFUN M+ (&REST TERMS)
    (PROTECT-&REST-VARIABLE TERMS)
    (SIMPLIFY `((MPLUS) ,@TERMS)))

  (DEFOPT M+ (&REST TERMS)
    (COND ((= (LENGTH TERMS) 2) `(ADD2* ,@TERMS))
	  (T `(ADDN (LIST ,@TERMS) NIL))))

  ;; M- negates a Macsyma expression, or substracts two Macsyma
  ;; expressions. Once you figure out which of the two operations is
  ;; to be done, the problem is similar to that of M+ above. However,
  ;; often the decision can be made at compile time. In this case,
  ;; INLINE functions would have worked ok, except that not all
  ;; implementations do inlining, and even those that do may fail to
  ;; recognize that EXP2 being NIL means that a test can be eliminated
  ;; or dead code can be eliminated. Using optimizers is far more
  ;; likely to be useful in practice.

  (DEFUN M- (EXP1 &OPTIONAL (EXP2 NIL EXP2P))
    (IF (NOT EXP2P)
	(M--INTERNAL-NEGATE EXP1)
	(M--INTERNAL-SUBTRACT EXP1 EXP2)))

  (DEFOPT M- (EXP1 &OPTIONAL (EXP2 NIL EXP2P))
    (IF (NOT EXP2P)
	`(M--INTERNAL-NEGATE ,EXP1)
	`(M--INTERNAL-SUBTRACT ,EXP1 ,EXP2)))

Rationale:

  Many large portable applications expect such a facility on an 
  implementation-specific basis. Others would use one if available.

  Even if implementations don't use the provided optimizers primitively,
  user macros and code-walkers can invoke them, so the facility wouldn't
  be completely useless even in those implementations.

Current Practice:

  Symbolics Genera provides an optimizer facility which is more elaborate
  but not fundamentally incompatible with this facility.

  Many (if not most) serious implementations provide a similar facility.

Cost to Implementors:

  Since the implementation is not required to use this facility, the
  cost of providing the proposed support is very small.

Cost to Users:

  None. This change is upward compatible.

Cost of Non-Adoption:

  Portable code would be slower than necessary in some situations.

Benefits:

  Some existing non-portable code could become portable.

Aesthetics:

  Providing a separate optimizer definition from a main function definition
  makes a possibility that the optimizer and main function could drift out
  of synch. However, most places where this gets used in the first place
  are places where speed is of paramount importance and the programmer is
  willing to invest effort in maintaining things correctly and to accept the
  risk of lossage if s/he fails.

  This is a fairly clean and simple extension which adds significant
  power to the compiler.

Discussion:

  Pitman strongly supports this proposal, the design of which is modeled
  directly after that which has been used in Macsyma for many years.

  Information about argument type can come from two different sources:
  THE and declarations (via PROCLAIM or DECLARE). The former information
  is portably accessible, the latter is not. While a separate proposal
  for allowing program access to type declarations would be make this
  facility more useful, it is still quite useful without it, as the
  examples from Macsyma illustrate.

  Some implementations provide a way to provide more than one optimizer
  for the same function. A multiple optimizer facility can be written
  in terms of this simpler facility and vice versa, so the simpler of
  the two facilities is proposed here.

  Some people have suggested that they would like to see a pattern
  matching facility integrated into this facility. The design of a
  facility that would satisfy everyone would take a lot of time and
  effort. At this point, there is no chance that the design of such a
  facility would occur in time for acceptance into the standard.
  The choice is this or nothing. Pitman thinks the language is much
  better off with some form of optimization support than none.