[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Issue: MACRO-CACHING (Version 1)
- To: CL-Compiler@SAIL.Stanford.EDU
- Subject: Issue: MACRO-CACHING (Version 1)
- From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>
- Date: Tue, 31 Jan 89 19:35 EST
Even if nothing ever comes of this proposal, at least the presence of
the issue name will give us a place to file any flaming on this topic so
that it doesn't have to get us side-tracked when we're really supposed
to be discussing some other issue...
References: 8.2 Macro Expansion (CLtL pp151-152),
Issues PACKAGE-CLUTTER, LISP-SYMBOL-REDEFINITION,
QUOTE-SEMANTICS (a.k.a. QUOTE-MAY-COPY),
Edit history: 31-Jan-89, Version 1 by Pitman
Status: For Internal Discussion
CLtL suggests that macro caching is a legitimate strategy.
Two particular kinds of caching are common:
Displacement. A macro expansion function displaces the actual macro in
order to avoid any later need for lookup.
Table. A macro expression is looked up in a cache (such as a hash table)
to avoid having to run the expander code.
While CLtL seems to expressly suggest these strategies to be legitimate,
linguistic constraints show that in most cases they are not. The problems
are things like:
- lexical scoping (MACROLET and SYMBOL-MACROLET, and FLET and LET to
the extent that they shadow the effect of MACROLET and SYMBOL-MACROLET,
- ``read only'' structure
To see the problem, consider the following examples:
(SETQ FOO1 '(FOO))
(EVAL `(LIST (MACROLET ((FOO (&WHOLE FORM) '(+ 1 1))) ,FOO1)
(MACROLET ((FOO (&WHOLE FORM) '(+ 1 2))) ,FOO1)))
=> (2 3)
Note that because the lexical contour may vary for an EQL expression,
however, displacing the expansion will cause confusion:
(DEFUN DISPLACE (X Y)
(SETF (CAR X) (CAR Y))
(SETF (CDR X) (CDR Y))
(DEFVAR FOO2 '(FOO))
(EVAL `(LIST (MACROLET ((FOO (&WHOLE FORM)
(DISPLACE FORM '(+ 1 1)))) ,FOO2)
(MACROLET ((FOO (&WHOLE FORM)
(DISPLACE FORM '(+ 1 2)))) ,FOO2)))
=> (2 2)
CLtL suggests that a displacement hook might be placed in
*MACROEXPANSION-HOOK*. The above example shows that to be an
If this were not enough, displacement is also inappropriate because
no Common Lisp primitive can tell the difference between regular list
structure and read-only list structure. Since a macro form being
expanded might have been read-only in some implementations (e.g., EVAL
of a quoted list), the macro cannot reliably side-effect the structure.
In the case of table-lookup, the problem is more complicated.
Table-lookup does not have a necessary effect beyond the particular
lookup being done at the moment. To do table-lookup correctly relies
on the key being not only the expression but also the lexical
environment object. Whether the cost of making and throwing away so
many tables was worth the savings over running the macro expander is
not at all clear. And the GC effects of caching every macro environment
ever seen may be extraordinary, however correctness could in principle
be preserved by doing such a two-dimensional lookup... at least unless
we decide that macro environments have only dynamic extent. [A separate
proposal, MACRO-ENVIRONMENT-EXTENT, addresses this issue. If it passed,
then there would really be no way for users to do reliable macro caching
without cooperation from the system to have the cache be part of the
Macro caching by displacement is provably not semantically valid.
Macro caching by table lookup is difficult for a user to do correctly,
and in any case is not possible to handle efficiently in user code.
1. a. Clarify that macro caching by displacement is not semantically
valid in user code.
b. Clarify that macro caching by displacement is semantically valid
for system macros and special forms, provided that such caching
does not prejudice the expansion of user-code contained in any
displaced code. For example:
(PROG () (FOO))
could displace to a BLOCK, but the (FOO) must appear un-expanded
in the BLOCK in case the BLOCK occurs in more than one lexical
2. a. Clarify that macro caching by table lookup is not semantically
valid in user code in order to correctly respect the lexical
Implementations are free to extend the language to permit such
lookup and to offer functions which support it in a more efficient
way, but code using such functions would, of course, not be portable.
b. Clarify that macro caching by table lookup is valid for the system,
but only if it correctly respects the lexical environment.
Like DISALLOW, but change 2a to:
Clarify that macro caching by table lookup is semantically valid only
if the lookup is keyed both on the form and the environment.
Implementations are free to extend the language to offer functions
which support it in a more efficient way, but code using such functions
would, of course, not be portable.
1. a. Displacement has effects which by their nature transcend
b. The system can assure that lexical boundaries are irrelevant in some
cases because users are not permitted to redefine or shadow definitions
in the initial LISP system. [See issues PACKAGE-CLUTTER and
2. a. Users can only associate an environment with a macro cache table
in a very clumsy way. Also, Permitting them to do so at all forces
macro environments to have indefinite extent, and works against
efficiency in compilers.
b. The system is capable of allocating space in an environment object
for a macro cache which can be reliably kept up in synch with the
lexical environment environment.
;; #1: File compiling this definition in some implementations will produce
;; a definition that returns read-only list structure. The call to EVAL
;; on the result must not try to modify the read-only structure during
;; macroexpansion. [See issue QUOTE-SEMANTICS.]
(DEFUN READ-ONLY-FOO () '(MACROLET ((FOO (&WHOLE FORM) (+ 1 1))) (FOO)))
;; #2: This constructs a form and then uses it in two places in another
;; constructed form. Each of the uses is in a different lexical
;; contour, so must be expanded differently.
(LET ((FOO (LIST 'FOO)))
(EVAL `(LIST (MACROLET ((FOO (&WHOLE FORM) '(+ 1 1))) ,FOO)
(MACROLET ((FOO (&WHOLE FORM) '(+ 1 2))) ,FOO))))
=> (2 3)
;; #3: This is effectively the same thing but involves a MACROLET
;; shadowing a DEFMACRO rather than two MACROLETs, since some
;; implementations might only be caching expansions that come
;; from DEFMACRO.
(DEFMACRO FOO (&WHOLE FORM) '(+ 1 1))
(LET ((FOO (LIST 'FOO)))
(EVAL `(LIST ,FOO (MACROLET ((FOO (&WHOLE FORM) '(+ 1 2))) ,FOO))))
=> (2 3)
Symbolics Genera does not use displacing or table caching in either
the interpreter or compiler.
Symbolics Cloe, a compiled only implementation, uses table caching
to boost compilation by a little. Running the test cases above turned
up a bug (in test case #3), which is now in the process of being fixed.
[The fact that a bug was turned up in code written by a CL implementor
is an existence proof that the potential for trouble was not imagined.]
Both Symbolics Cloe and Symbolics Genera support *MACROEXPANSION-HOOK*,
leaving open the possibility of users bringing disasters upon themselves.
Macro environment objects in Symbolics Genera are stack-allocated, so
have only dynamic extent.
Cost to Implementors:
This proposal is upward compatible with correct implementations.
Cost to Users:
There is no cost to users of the RESTRICT proposal, unless they were doing
semantically invalid caching.
The cost to users of the DISALLOW proposal is a loss of speed in some cases
which are semantically valid. In general, however, the efficiency and
usefulness of such caching is subject to question in code intended to be
ported. Given that implementations are not required to ever give the same
environment object twice, the caching may be all for naught in some
Cost of Non-Adoption:
Continued widespread confusion about whether displacement is a legitimate
implementation technique for user code.
Since *MACROEXPANSION-HOOK* is in the Lisp package, multiple applications
in the same environment share its effects. Often one application will
clobber another's hook, or introduce a hook that is not desirable to other
applications when none previously existed. Since a common use of
*MACROEXPANSION-HOOK* is to install a macro caching mechanism, clarifying
the situations in which *MACROEXPANSION-HOOK* should not be used will
decrease the likelihood of one program breaking, slowing down, or otherwise
adversely affecting another.
Most people agree that macro caching techniques are only supposed to improve
speed without affecting semantics. This proposal is only intended to
underscore that necessary truth. Insofar as this is only a clarification,
it presumably has no significant aesthetic impact.
Pitman thinks it's a good idea to clarify this issue because it's not really
spelled out now and it's the sort of thing programmers can waste a lot of
time bickering about to no good end. Either the functionality is reliable
and should be encouraged, or it is not reliable and should be discouraged
or forbidden. Pitman supports the DISALLOW proposal because it leaves open
the possibility of making macro environments have dynamic extent, but he
can live with the RESTRICT position, which he believes represents the
Bob Laddaga (a Cloe maintainer who reviewed a draft of this proposal)
supports the DISALLOW option as well.