Issue: DEFINE-OPTIMIZER (Version 4)

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

[A revised proposal (v4) follows at the end of my reply to Cris.]

    Date: Fri, 10 Mar 89 14:35:06 PST
    From: cperdue@Sun.COM (Cris Perdue)
    
    ... I support Kent's proposal, with the following suggestions:
    
    An additional function that corresponds to MACRO-FUNCTION for ordinary
    macros.  I include the proposed definition for this, which follows the
    definition of MACRO-FUNCTION in CLtL, p144.  This provides 
    primitive-level access, including the ability to undefine an
    optimizer.

The current definition is agnostic about whether built-in system
optimizers are implemented using DEFINE-OPTIMIZER or vice versa.
This is important for two reasons:
 - System optimizations may be type dispatched, as mentioned
   in earlier discussions. In such cases, the general mechanism
   proposed here could effectively define optimizations on type T
   and not override more specific optimizations.
 - Some systems may permit multiple optimizers for the same
   function. In such a case, the optimizer set up by DEFINE-OPTIMIZER
   may be only one of several.
Adding your OPTIMIZER-FUNCTION would expose the implementation, by
forcing us to say whether all the optimizers were captured, or only
the ones defined by DEFINE-OPTIMIZER. The interface I chose tries
deliberately to hide this issue in order to keep us from getting
bogged down in those other issues.

Similar arguments apply to the issue of undefining optimizers.

In both cases, I think you're describing very useful features and
I encourage you to (a) extend your implementation, (b) propose those
interfaces on the next standardization cycle.

The issue for now is that this proposal is essentially unchanged since
the last time I brought it up, but last round I made the mistake of
hinting that other issues might get involved so everyone immediately
went off in a million different directions and Sandra marked the
proposal as without clear support. I think she was right, and I think
what makes this time different is that the focus is just enough
different that we can all agree that this much functionality is ok.

    Add to the problem description that sometimes an "operator" is defined
    as a macro purely because its performance would be inadequate if
    implemented as a function.
    
Good idea.

    Also, I believe it would be best to state that in environments where
    the compiler is prohibited from treating a function as INLINE,
    optimizers are deactivated.  In particular, the functions
    OPTIMIZE-EXPRESSION and OPTIMIZE-EXPRESSION-1 do not transform their
    expression argument if given an environment in which the function must
    not be treated as INLINE.  (I recognize that this is a bit of
    a judgment call.)

    The point here is to make user-defined optimizers follow the behavior
    of optimizers built-in to compilers in their response to NOTINLINE.

I agree this is a problem, but I don't want to solve it this way because,
as you say, it's a judgment call, and I don't want to jeopardize the
whole thing if someone gets nervous. I will add wording saying that the
effects of having an OPTIMIZER on a function which is also proclaimed 
INLINE are ``unspecified but harmless'' (in that both optimizations and
inlining are intended to be semantics-preserving operations).

-----
Forum:	      Compiler
Issue:        DEFINE-OPTIMIZER
References:   Issue SYNTACTIC-ENVIRONMENT-ACCESS
Category:     ADDITION
Edit history: 28-Sep-88, Version 1 by Pitman
	      10-Mar-89, Version 2 by Pitman (clarifications, new example),
	      10-Mar-89, Version 3 by Pitman & Loosemore
Status:	      Ready for release

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, or
  else that some operators that should be implemented as functions end
  up getting implemented as macros to assure needed efficiency.

Proposal (DEFINE-OPTIMIZER:NEW-FACILITY):

  Introduce a facility for declaring compiler optimizations.

  DEFINE-OPTIMIZER name arglist {declaration}* {form}*		[Macro]

   Defines a compiler optimizer for a function named NAME. The ARGLIST,
   DECLARATIONS, and FORMS are treated exactly like the arglist, 
   declarations, and forms in a DEFMACRO. (The arglist may include
   &ENVIRONMENT and &WHOLE.)

   The argument NAME must name a function which has been previously
   defined. The effects of defining an optimizer for a locally or
   globally defined macro, a locally defined function, or a special 
   form are undefined.

   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.

   If a call to DEFINE-OPTIMIZER appears at top-level in a file
   being processed by the file compiler, it also makes the optimizer 
   known at compile-time (similar to the way DEFMACRO makes a macro 
   definition known to the compiler).

  OPTIMIZE-EXPRESSION-1 form env				[Function]

   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					[Function]

   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.

  Using FLET and MACROLET shadow not only functions and their SETF methods,
  but also their optimizers.  No portable facility is provided for creating
  locally defined optimizers.

  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.

  The effect of using DEFINE-OPTIMIZER on a function declared to be
  INLINE is ``unspecified but harmless'' (per new Error Terminology).
  That is, since both operations (optimization and inlining) are intended
  to be semantics-preserving, no functional difference should be observed.
  However, in some implementations the presence of an optimizer may thwart
  the ability to inline, or vice versa. Writers of portable are encouraged
  to use either DEFINE-OPTIMIZER or (PROCLAIM '(INLINE ...)) but not both.

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)))

  (DEFINE-OPTIMIZER 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)))

  (DEFINE-OPTIMIZER 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.
  For example, Lucid provides "compiler macros" which serve the same
  purpose.

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
  (SYNTACTIC-ENVIRONMENT-ACCESS) 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.

  Loosemore says:
    Although I don't really think this is an essential feature to include
    in the standard, I don't have any strong objection to adding it.  If
    people think it's a good idea to provide a standard interface for this
    kind of thing, this is a good proposal for doing it -- it's fairly
    simple, doesn't introduce any radically new ideas, and is general
    enough to allow alternate interfaces (such as the pattern matcher) to
    be layered on top of it.