[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Issue: DEFINE-OPTIMIZER (Version 2)
- To: CL-Compiler@SAIL.Stanford.EDU
- Subject: Issue: DEFINE-OPTIMIZER (Version 2)
- From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>
- Date: Fri, 10 Mar 89 16:21 EST
- Cc: 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.
Edit history: 28-Sep-88, Version 1 by Pitman
10-Mar-89, Version 2 by Pitman (clarifications, new example)
Status: For Internal Discussion
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.
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
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
;; 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)
(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-SUBTRACT EXP1 EXP2)))
(DEFOPT M- (EXP1 &OPTIONAL (EXP2 NIL EXP2P))
(IF (NOT EXP2P)
`(M--INTERNAL-SUBTRACT ,EXP1 ,EXP2)))
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.
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.
Some existing non-portable code could become portable.
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.
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.