Issue: MACRO-CACHING (Version 1)

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

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

-----
Issue:        MACRO-CACHING
Forum:	      Compiler
References:   8.2 Macro Expansion (CLtL pp151-152),
	      Issues PACKAGE-CLUTTER, LISP-SYMBOL-REDEFINITION, 
 	      QUOTE-SEMANTICS (a.k.a. QUOTE-MAY-COPY),
	      and MACRO-ENVIRONMENT-EXTENT
Category:     Clarification
Edit history: 31-Jan-89, Version 1 by Pitman
Status:	      For Internal Discussion

Background:

  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,
	respectively).

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

   (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
  unreliable technique.

  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
  environment itself.]

Problem Description:

  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.

Proposal (MACRO-CACHING:DISALLOW):

  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
	environment.

  2. a. Clarify that macro caching by table lookup is not semantically
	valid in user code in order to correctly respect the lexical
        environment.

	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.

Proposal (MACRO-CACHING:RESTRICT):

  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.

Rationale:

 1. a. Displacement has effects which by their nature transcend
       lexical boundaries.

    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 
       LISP-SYMBOL-REDEFINITION.]

 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.

Test Case:

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

 (EVAL (READ-ONLY-FOO))
 => 2

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

Current Practice:

 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
 implementations.

Cost of Non-Adoption:

 Continued widespread confusion about whether displacement is a legitimate
 implementation technique for user code.

Benefits:

 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.

Aesthetics:

 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.

Discussion:

 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
 status quo.

 Bob Laddaga (a Cloe maintainer who reviewed a draft of this proposal) 
 supports the DISALLOW option as well.