Issue: DEFINE-OPTIMIZER

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

Issue:        DEFINE-OPTIMIZER
References:   None
Category:     ADDITION
Edit history: 28-Sep-88, Version 1 by Pitman
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.

Example:

  (PROCLAIM '(INLINE STRING-APPEND-REAL-STRINGS))
  (DEFUN STRING-APPEND-REAL-STRINGS (STRING1 STRING2)
    (CONCATENATE 'STRING (THE STRING STRING1) (THE STRING STRING2)))

  (DEFUN STRING-APPEND (NAME1 NAME2)
    (STRING-APPEND-REAL-STRINGS (STRING NAME2) (STRING NAME2)))

  (DEFUN DECLARED-TYPEP (THING TYPE)
    (AND (NOT (ATOM THING))
	 (EQ (CAR  THING) 'THE)
	 (EQ (CADR THING) TYPE)))

  (DEFUN QUOTED-TYPEP (THING TYPE)
    (AND (NOT (ATOM THING))
	 (EQ (CAR THING) 'QUOTE)
	 (TYPEP (CADR THING) TYPE)))

  (DEFINE-OPTIMIZER STRING-APPEND (NAME1 NAME2)
    (LET ((OPTIMIZE NIL))
      (FLET ((OPTIMIZE-ARGUMENT (ARG)
	       (COND ((OR (TYPEP ARG 'STRING)
			  (DECLARED-TYPEP ARG 'STRING))
		      (SETQ OPTIMIZE T)
		      ARG)
		     ((QUOTED-TYPEP ARG 'STRING)
		      (SETQ OPTIMIZE T)
		      (EVAL ARG))
		     ((DECLARED-TYPEP ARG 'SYMBOL)
		      (SETQ OPTIMIZE T)
		      `(SYMBOL-NAME ,ARG))
		     ((QUOTED-TYPEP ARG 'SYMBOL)
		      (SETQ OPTIMIZE T)
		      (STRING (EVAL ARG)))
		     (T
		      `(STRING ,ARG)))))
	(LET ((ARG1 (OPTIMIZE-ARGUMENT NAME1))
	      (ARG2 (OPTIMIZE-ARGUMENT NAME2)))
	  (WHEN OPTIMIZE
	    (IF (AND (STRINGP ARG1) (STRINGP ARG2))
		(STRING-APPEND-REAL-STRINGS ARG1 ARG2)
		`(STRING-APPEND-REAL-STRINGS ,ARG1 ,ARG2)))))))

  (STRING-APPEND 'FOO 'BAR) => "FOOBAR"

  (LET ((X 'FOO) (Y 'FOO))
    (STRING-APPEND (THE SYMBOL X) (THE SYMBOL Y)))
   => "FOOBAR"

  (OPTIMIZE-EXPRESSION '(STRING-APPEND 'FOO 'BAR))
   => "FOOBAR"

  (OPTIMIZE-EXPRESSION '(STRING-APPEND (THE SYMBOL X) 'BAR))
   => (STRING-APPEND-REAL-STRINGS (SYMBOL-NAME (THE SYMBOL X)) "BAR")

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:

  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.

  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 compilers provide other optimization facilities which allow
  direct optimization to assembly code or machine instructions. I hope
  this wouldn't conflict with that but since I'm not familiar with the
  details of those implementations, I'm not 100% sure. If anyone familiar
  with such systems wants to comment on that, I'd be interested. -kmp]

  Pitman supports this proposal.