Issue: COMPILER-LET-CONFUSION (Version 4)

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

Ok, per your request, here's a total reworking of this issue based on my
view of what COMPILER-LET is about. I've changed nearly every section, so
read carefully.

In the process, the presentation of the ELIMINATE option changed
somewhat.  Although I don't personally support that option, I've tried
to still cast it as something people could reasonably decide to vote for
once they understand the issues. If some part of the presentation
doesn't seem fair, either submit a correction or let me know and I will.

Statements of support (for either option) for inclusion in the
Discussion are solicited anew from anyone with an opinion on this topic.

-----
Issue:		COMPILER-LET-CONFUSION
Forum:	        Compiler
References:	CLtL p. 112
Category:	CHANGE
Edit History:   V1, 27 Sep 1988, Sandra Loosemore (initial version)
                V2, 04 Oct 1988, Sandra Loosemore (add another example)
		V3, 31 Oct 1988, Sandra Loosemore (only proposal ELIMINATE)
	        V4, 08 Jan 1989, Kent M. Pitman (new alternative)

Problem Description:

 The description of the COMPILER-LET special form in CLtL is confusing
 to many people.  There are no examples provided to make it clear how it
 is supposed to be used. The only description which is offered is overly
 concrete, which have led to confusion about the intent of COMPILER-LET,
 and about it's implementability.
 
 The intent of COMPILER-LET was to permit information to be communicated
 between macros by use of dynamic variables at macroexpansion time.
 It was not necessary to the intended uses of COMPILER-LET that such
 variables ever be bound at execution time.  
 
 Unfortunately, probably because some implementations did not primitively
 support COMPILER-LET at the time CLtL was written, an exception was 
 permitted to make COMPILER-LET `more or less work' in interpreters: 
 the COMPILER-LET variables were permitted to be bound at execution time.
 The problem was further compounded by the fact that CLtL presented this
 exception as part of COMPILER-LET's contract rather than as an 
 implementation note, and by the fact that no examples of actually using
 COMPILER-LET correctly are provided.
 
 Subtle bugs can be introduced because of the different handling of the
 variable bindings in the interpreter and the compiler.  In compiled
 code, the bindings are only lexically visible during the expansion of
 macros at compile time, while in interpreted code the bindings have
 dynamic scope and may also be seen during ordinary evaluation if
 evaluation and macroexpansion happen concurrently.
 
 Further compatibility problems can result from the value forms being
 evaluated in a null lexical environment in the compiler and the ordinary
 lexical environment in the interpreter.
 
Background and Analysis:

 It should be clear up front that COMPILER-LET is not computationally
 essential. Most (if not all) uses of it can be rewritten using MACROLET.

 However, this is a little misleading because it's like saying you can
 do without LET given that you have FLET. You can, but you lose some things
 in the process:

 Just as rewriting a LET using FLET might slow your computation, so too
 a rewrite of COMPILER-LET using MACROLET might slow things down. However,
 compilation speed is generally not weighted as heavily as execution speed
 by many people, so the loss of speed here may not be as important.

 Just as rewriting a LET using FLET might obscure the simplicity of your
 intent, so too rewriting COMPILER-LET using MACROLET might obscure your
 intent. You'd probably get used to recognizing idioms if you used it often
 enough. Certainly this would be true if you didn't have LET. However,
 COMPILER-LET is used less often, so not having it would mean that the
 code you wrote instead would be much harder to read because people
 wouldn't have the necessary familiarity with the idioms involved and so
 wouldn't always understand them.

 Just as rewriting a LET using FLET is harder to do (if not impossible) in
 the presence of side-effects to the LET variables, so too rewriting
 COMPILER-LET in terms of MACROLET is harder to do (if not impossible) in
 the presence of side-effects.

 A typical use of COMPILER-LET (without side-effects) might be:

  (defvar *local-type-declarations* '())
     
  (defmacro local-type-declare (declarations &body forms)
    `(compiler-let ((*local-type-declarations* 
		      (append ',declarations *local-type-declarations*)))
       ,@forms))
     
  (defmacro typed-var (var)
    (let ((type (assoc var *local-type-declarations*)))
      (if type `(the ,(cadr type) ,var) var)))
     
  (defun f (x y)
    (local-type-declare ((x fixnum) (y float))
      (+ (typed-var x) (typed-var y))))
    
 This can be rewritten straightforwardly by someone familiar with doing so,
 but the result is not as readable to those not familiar with the idioms:
  
  (defmacro local-type-declare (declarations &body forms)
    (local-type-declare-aux declarations forms))
    
  (defmacro typed-var (var) var)

  (eval-when (eval compile load)
    (defun local-type-declare-aux (declarations forms)
      `(macrolet ((typed-var (var)
		    (let ((type  (assoc var ',declarations)))
		      (if type `(the ,(cadr type) ,var) var)))
		  (local-type-declare (new-declarations &body new-forms)
		    (local-type-declare-aux
		      (append new-declarations ',declarations)
		      new-forms)))
	 ,@forms)))

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

 The issues are these:

  - Is it possible to implement COMPILER-LET in a usefully consistent
    way in all implementations?

  - Is the cost of providing a useful and compatible implementation of
    COMPILER-LET worth any associated cost?

 Two proposals are presented below:

  - Option REPAIR argues that COMPILER-LET provides interesting
    functionality that can be implemented in a manner that is usefully
    consistent across implementations, and that the associated cost
    is low enough for it to be worthwhile to do so.

  - Option ELIMINATE presents a fall-back position for those who 
    either find that COMPILER-LET is not possible to implement in
    a usefully consistent way in all implementations, or for those who
    agree that although technically possible to do so, the cost is too 
    high.

Proposal (COMPILER-LET-CONFUSION:REPAIR):

  Strike the existing definition of COMPILER-LET. Redefine it as follows:
  
  COMPILER-LET						  [Special form]
  
    COMPILER-LET is similar to LET, but its bindings are visible only
    during macroexpansion of forms in the body, not during the runtime
    execution of those forms. 

    The intent is that some macros might macroexpand into calls to
    COMPILER-LET in which the body would the contain references to
    macros which access the variables in the COMPILER-LET.
  
    The initial value forms of the bindings, if any, are always 
    evaluated in a null lexical context, regardless of whether the
    COMPILER-LET expression is being interpreted or compiled.
  
    The initial value forms of the bindings, if any, are evaluated in
    a dynamic context where the bindings of any lexically enclosing
    COMPILER-LET are visible, and where dynamic execution-time 
    environment may or may not be visible.
  
    Implementation Note: Permitting the execution-time dynamic
    environment to be visible when initializing COMPILER-LET variables
    is a concession to some interpreters which may have to do this in
    order to keep the cost down. Where feasible, implementors should
    try not to make the runtime environment visible.

  Rationale:

    This gives a consistent description of COMPILER-LET which separates
    issues of intent from those of implementation in a way that makes it
    possible for portable code to make serious use of it, and which does
    not force gratuitous incompatibilities between interpreters and
    compilers.

    This description of COMPILER-LET can be implemented without undue
     cost by all implementations. See "Cost to Implementors" for details.

  Cost to Implementors:

    Modest to small:

    In compiled code, and in interpreters doing a one-time semantic
    prepass, it should be fairly easy for COMPILER-LET to cause the 
    variables to get bound (using PROGV) during semantic analysis.

    In interpreters which do not do a semantic-prepass, it is necessary
    to fully macroexpand the body. Assuming the presence of a
    SYSTEM::MACROEXPAND-ALL primitive, the definition of COMPILER-LET
    could look like:
      (DEFMACRO COMPILER-LET (BINDINGS &BODY FORMS &ENVIRONMENT ENV)
        (SETQ BINDINGS ;; Assure no non-atom bindings
	      (MAPCAR #'(LAMBDA (BINDING) 
		          (IF (ATOM BINDING) (LIST BINDING) BINDING))
		      BINDINGS))
        (PROGV (MAPCAR #'CAR BINDINGS)
	       (MAPCAR #'CDR BINDINGS)
	  (SYSTEM::MACROEXPAND-ALL `(PROGN ,@FORMS) ENV)))
    This reduces the problem of writing a program capable of doing a
    full macroexpansion. Many systems already have such a facility.
    Pitman wrote such a facility in Cloe Runtime in order support 
    SYMBOL-MACROLET (before it was christened a special form); it was
    about 750 lines of relatively straightforward, well-commented code.

    Another approach, which has not been fully explored, but which seems
    plausible, is for COMPILER-LET to annotate the environment with the
    bindings, and then to instantiate the bindings for the duration of
    each call to MACROEXPAND-1. To accomodate SETQ of COMPILER-LET
    variables, some care would be needed to assure that assignments to
    these variables were recorded at the end of such a binding context
    in order to correctly affect subsequent macroexpansions in the same
    COMPILER-LET scope. This technique might be slightly slower, but
    could avoid the need for a special code-walker. Also, the slowness
    would generally only be incurred when a COMPILER-LET was actually 
    being processed, which (depending on the application) might not be
    the common case.

  Cost to Users:

    Code currently depending on this feature is either non-existent or
    already not portable (due to wide variation in implementation 
    strategy for COMPILER-LET).

    Most users will probably be happy for any interpretation which offers
    them a future short at portability.

Proposal (COMPILER-LET-CONFUSION:ELIMINATE):

  Remove COMPILER-LET from the language.
  
  Rationale:
  
    This is a fallback position for those who believe that COMPILER-LET
    is not implementable in consistently useful way across implementations,
    or for those who believe that a consistently useful implementation
    would be prohibitively expensive.
  
    Some people think that having one less special form would simplify the
    language.

  Cost to Implementors:
  
    Minimal.  Implementations could continue to support COMPILER-LET as
    an extension.
  
  Cost to Users:
  
    People who use COMPILER-LET would have to rewrite their programs to use
    some other construct.  As discussed above, most uses of COMPILER-LET
    for communication between macros can be handled using MACROLET, though
    some perspecuity may be lost in the process.

Current Practice:
  
 Some implementations have implemented the description in CLtL. 
 Users of those implementations (quite reasonably) can't figure how to 
 use COMPILER-LET and so don't use it much.

 Some implementations (the onces from which COMPILER-LET originally came)
 continue to use their pre-CLtL semantics. These semantics are useful, though
 incompatible with CLtL (which they largely consider to simply be in error).
 Users of those implementations probably use COMPILER-LET somewhat more 
 often since it has an intelligible behavior, but their code is not portable
 since it relies on behaviors which are either contrary to or not guaranteed
 by CLtL.

Benefits:

 Either way, a potential area of incompatibility between compiled and
 interpreted code would be eliminated.

 Either way, a potential area of portability trouble would be very
 drastically reduced (in the case of the REPAIR option) or eliminated
 (in the case of the ELIMINATE option).

Discussion:

 [Most opinions previously expressed on this topic were given before
 a balanced set of options were provided. Since I hope some people
 may want to change their votes now that two "reasonable" options
 are presented, I've removed statements of preference and hope that
 people will state a position anew based on this new writeup. -kmp]

 Pitman strongly favors COMPILER-LET-CONFUSION:REPAIR.