issue MACRO-ENVIRONMENT-EXTENT, version 2

[sandra%defun@cs.utah.edu (Sandra J Loosemore)]

This writeup ended up getting more changes than I anticipated.  Here it
is in case anybody has any additional comments before I send it out
to X3J13.

Forum:		Compiler
Issue:		MACRO-ENVIRONMENT-EXTENT
References:	CLtL p. 145-146
		Issue COMPILER-LET-CONFUSION
		Issue MACRO-CACHING
		Issue EVAL-WHEN-NON-TOP-LEVEL
		Issue SYNTACTIC-ENVIRONMENT-ACCESS
		CLOS Chapter 3 (89-003)
Category:	CLARIFICATION,CHANGE
Edit History:   V1, 10 Jan 1989, Sandra Loosemore
		V2, 09 Mar 1989, Sandra Loosemore
Status:		Ready for release


Problem Description:

What is the extent of environment objects received as the &ENVIRONMENT
argument of a macro function?

CLtL says that &ENVIRONMENT is "useful primarily in the rare cases
where a macro definition must explicitly expand any macros in a
subform of the macro call before computing its own expansion".  While
this suggests that macro environment objects are typically used within
the dynamic scope of the macro function, the use of the word
"primarily" (rather than "only" or "exclusively" or some similarly
strong language) suggests that there may be other legitimate uses for
environment objects.  But, because CLtL is silent about what those
uses might be, many users and implementors are under the impression
that environment objects have only dynamic extent.

There are some situations where using environment objects as if they
had indefinite extent provides a very useful viewpoint from which to
solve a problem.  Consider the following example:

  (defmacro typed-var (var) var)

  (defmacro local-type-declare (declarations &body forms &environment env)
      `(macrolet ((typed-var (&whole w var)
		    (let ((type  (assoc var ',declarations)))
		      (if type 
		          `(the ,(cadr type) ,var)
                          (macroexpand w ',env)))))
	 ,@forms))

  (defun f (x y)
    (local-type-declare ((x fixnum) (y float))
      (+ (typed-var x) (typed-var y))))

Here, local macro TYPED-VAR is defined to look first in the innermost
lexical environment for information about the variable, and if there
isn't any then it recurses on the next outermost lexical environment.
The global definition of TYPED-VAR provides a terminal case to stop
the recursion.

There are other situations where the extent of macro environment
objects comes into play.  For example, if we allow caching of macro
expansions (issue MACRO-CACHING), environments must have indefinite
extent.  It is unclear whether CLOS would be affected by allowing
macro environments to have only dynamic extent.  (The descriptions of
the CLOS defining macros in document 89-003 seem to imply that the
value of the &ENVIRONMENT argument appears in the expansion of the
macro, but there now seems to be sentiment that the model of how the
defining macros work that is presented there is broken.)


Proposal MACRO-ENVIRONMENT-EXTENT:INDEFINITE:

State that macro environment objects received with the &ENVIRONMENT
argument of a macro function or as the argument to a *MACROEXPAND-HOOK*
function have indefinite extent.

Note that implementations are not permitted to destructively modify
environment objects once they have been passed to a macro function.

  Rationale:

  This legitimizes the use of idioms which depend on macro environments
  having indefinite extent.

  Since data objects in Lisp otherwise have indefinite extent, it is
  more consistent to give environment objects indefinite extent as
  well.


Proposal MACRO-ENVIRONMENT-EXTENT:DYNAMIC:

State that macro environment objects received with the &ENVIRONMENT
argument of a macro function or with a *MACROEXPAND-HOOK* function
have only dynamic extent; the consequences are undefined if they are
referred to outside the dynamic extent of that macro function or hook
function.

  Rationale:

  This allows implementations to use somewhat more efficient techniques
  for representing environment objects.  For example, the storage could
  be stack-allocated, or environments could be bashed destructively
  instead of always being freshly heap-allocated.


Proposal MACRO-ENVIRONMENT-EXTENT:DYNAMIC-WITH-COPIER:

State that macro environment objects received with the &ENVIRONMENT
argument of a macro function or with a *MACROEXPAND-HOOK* function
have only dynamic extent; the consequences are undefined if they are
referred to outside the dynamic extent of that macro function or hook
function.

Add a new function:

COPY-ENVIRONMENT environment				[function]

This function returns an environment object that is semantically
equivalent to "environment" (which must be an object of the type
received with an &ENVIRONMENT argument to a macro or as an argument to
a *MACROEXPAND-HOOK* function), but which may safely be referred to
outside the dynamic extent of the macro function.  This function is
permitted to return an object that is EQ to its argument if that 
object may be safely used.

  Rationale:

  This allows implementations to use somewhat more efficient techniques
  for representing environment objects.  For example, the storage could
  be stack-allocated, or environments could be bashed destructively
  instead of always being freshly heap-allocated.

  It also allows programmers to use idioms that rely on environment
  objects having indefinite extent.


Current Practice:

Macro environments appear to have indefinite extent in Lucid Common
Lisp, Kyoto Common Lisp, CMU Common Lisp (at least in the
interpreter), Utah Common Lisp, and A-Lisp.  A-Lisp internally uses
the kind of idiom shown in the example above to implement FLET,
LABELS, and FUNCTION as macros.

Macro environments are stack-allocated in Symbolics Genera.


Cost to implementors:

For proposal INDEFINITE, some implementations may need to change.  A
simple implementation of macro environments that would fit the
requirements of this proposal is to represent them as lists, pushing
information for inner contours onto the front of the list as the
contour is entered and popping the list when the contour is exited.
Implementations that now use some other representation, or that
stack-allocate environments, could make a copy of the environment
before expanding any macros.

For proposal DYNAMIC, there is no associated implementation cost.

For proposal DYNAMIC-WITH-COPIER, the implementation cost is unknown
but probably trivial in most implementations.


Cost to users:

For proposal INDEFINITE, there is no associated cost to users.

For proposal DYNAMIC, users would not be able to portably use a
simple and elegant approach to solving certain kinds of problems.

For proposal DYNAMIC-WITH-COPIER, users would have to remember to make
a copy of an environment object in some situations.


Benefits:

It is made clear whether treating environment objects as if they had
indefinite extent is portable usage.


Discussion:

Proposal SYNTACTIC-ENVIRONMENT-ACCESS:ADD-FUNCTIONAL-INTERFACE
includes adding a function called AUGMENT-ENVIRONMENT.  It's unclear
whether having this function would eliminate the need for
COPY-ENVIRONMENT under proposal DYNAMIC-WITH-COPIER.

Loosemore supports proposal MACRO-ENVIRONMENT-EXTENT:INDEFINITE.

Moon says:
  My opinion is that anything in CLOS that seems to depend on indefinite
  extent for macro environments is broken and needs to be fixed.  It's not
  broken because of the environment extent, but for other reasons.
  Thus I believe in dynamic extent for environments.

Neil Goldman says:
  In my code walker I have a pretty ugly way of dealing with MACROLET
  that would have been trivial if I could have counted on the
  ENVIRONMENT having indefinite extent.  There may be some cleaner way
  than what I did, but I just looked at PCL's code walker, and it also
  is much more complex than would be necessary if environments had
  indefinite extent.
-------