Issue COMPILER-LET-CONFUSION Writeup

Issue:		COMPILER-LET-CONFUSION

Forum:	        Compiler

References:	CLtL p. 112

		Issue DEFINE-OPTIMIZER

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)

		V5, 09 Jan 1989, Sandra Loosemore (discussion)

		V6, 08 Mar 1989, Sandra Loosemore (general updating)

		V7, 13 Mar 1989, Sandra Loosemore (fix bug from V6)

		V8, 23 Mar 1989, Sandra Loosemore (fix another bug, add

					to discussion)

Status:		Proposal ELIMINATE passed March 89.


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 has led to confusion about the intent of COMPILER-LET,

 and about its 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.


 One particular case where problems have resulted is a situation like

   (compiler-let ((*v* 1))

     #'(lambda () (m)))

 where M is a macro that refers to *V*.  In some implementations, M is

 not macroexpanded until the dynamic extent of the *V* binding has

 ended.

 

 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 "in parallel".

 

 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

 or SYMBOL-MACROLET.


 A typical use of COMPILER-LET 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))))

    


 The same thing could be accomplished using MACROLET:

  

  (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)))



 A further alternative would be to use SYMBOL-MACROLET (this particular

 implementation assumes that issue DEFINING-MACROS-NON-TOP-LEVEL passes):


  (let ((temp  (gensym)))

    (defmacro local-type-declare (declarations &body forms &environment env)

      `(symbol-macrolet ((,temp  ',(append declarations

					  (symbol-macro-value temp env))))

         ,@forms))

    (defmacro typed-var (var &environment env)

      (let ((type  (assoc var (symbol-macro-value temp env))))

	(if type `(the ,(cadr type) ,var) var)))

    )

			  

  (defun symbol-macro-value (symbol env &optional default)

    (multiple-value-bind (expansion macro-p) (macroexpand symbol env)

      (if macro-p (eval expansion) default)))


 

 Opinion is divided as to which is more understandable.  Some

 people find the COMPILER-LET idiom more understandable (assuming that

 it can be made to work consistently in compiled and interpreted

 code), while others find it just as natural to use MACROLET or 

 SYMBOL-MACROLET.


 The issues are these:


  - Is it possible to implement COMPILER-LET in a usefully consistent

    way in all implementations?


  - Are the benefits 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 argues that COMPILER-LET complicates the language

    and that providing this construct is not worth the associated 

    implementation cost.



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 it always makes special 

    bindings and makes those bindings visible only during 

    macroexpansion of forms in the body, not during the runtime

    execution of those forms.  


    If proposal DEFINE-OPTIMIZER:NEW-FACILITY is accepted, then

    optimizer functions are also executed in a dynamic environment

    in which COMPILER-LET bindings are visible.


    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, but nontrivial in some implementations.


    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 #'(LAMBDA (BINDING) (EVAL (CADR BINDING))) 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.


  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 shot at portability.


    Some users have indicated they dislike interpreters which do a semantic

    prepass, because they like to be able to dynamically redefine macros

    while debugging.



Proposal (COMPILER-LET-CONFUSION:ELIMINATE):


  Remove COMPILER-LET from the language.

  

  Rationale:


    Some people think that having one less special form would simplify the

    language.  The revised COMPILER-LET semantics, which require

    COMPILER-LET to make special bindings which are only visible during

    expansion of macros which appear lexically within its body, are

    not shared by any other feature in the language, and require a

    fairly complex implementation technique.  There are other

    constructs which are strictly lexical that can be readily used

    to solve the same kinds of problems that COMPILER-LET is intended to

    be used for.


  Cost to Implementors:

  

    Minimal.  Implementations could continue to support COMPILER-LET as

    an extension.

  

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


    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 or

    SYMBOL-MACROLET, though some perspicuity 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 whose interpreters include a preprocessor to

 expand all macros have already implemented something similar to proposal

 COMPILER-LET-CONFUSION:REPAIR.  Users of such 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:


 Pitman strongly favors COMPILER-LET-CONFUSION:REPAIR.  He argues 

 against the idea of using MACROLET instead of COMPILER-LET, saying:


  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.

 

 Sandra Loosemore responds:


  The argument that using MACROLET is more inefficient than COMPILER-LET

  is questionable.  Both of the suggested implementation techniques for

  COMPILER-LET involve considerable overhead.


  If COMPILER-LET were not part of the language, people wouldn't think in

  terms of rewriting COMPILER-LETs as MACROLETs; instead, they'd think of

  how to use MACROLET in the first place to solve their problems.  This

  is what people who now use implementations with broken COMPILER-LETs

  already do.  Since MACROLET is now used much more frequently than

  COMPILER-LET, that argues that people are much more familiar with 

  MACROLET idioms than COMPILER-LET idioms.


  Also, note that the intent of the revised COMPILER-LET definition is

  to make the binding only lexically visible within the body.  Using

  special binding for this purpose is troublesome.  Both the MACROLET

  and SYMBOL-MACROLET solutions are completely lexical and avoid all

  the problems associated with special binding.


Glenn Burke thinks it needs to be emphasized that the code-walker

mentioned in the REPAIR proposal does not need to be portable.  He

says:


  The present wording makes it sound like a piece of cake to do with

  portable code, when the reality is that a good fraction of CL cleanup

  effort has involved the lack of capability of producing such a beast.

  Without one or more of a number of proposals being accepted, a fully

  correct portable code walker cannot be built, in my belief.


  I object to the flippant attitude of just "presupposing" this

  "trivial" function which "we know how to do".


We have considered a number of other options on this issue, including

a variety of proposals that would redefine COMPILER-LET to store

information about the variable bindings in the lexical environment, and

either having MACROEXPAND-1 make the special bindings or provide a

function which could be used to access them directly.


Kent Pitman says:

  People have suggested that if it comes to making an incompatible change

  on this one, it's probably better to just remove the feature and let

  people continue to provide it compatibly where they think it's useful.

  Even though I think the COMPILER-SYMBOL-VALUE thing is technically

  doable, I find myself swayed by arguments that it's not the correct

  avenue for us to pursue at this time.


David Moon says:

  I think COMPILER-LET-CONFUSION:REPAIR should be split into four proposals.

  First, one that gives the general framework for repairing but doesn't

  say anything about how the interpreter implements COMPILER-LET, other

  than to say that an additional proposal is needed to cover that.  Then

  three proposals for how the interpreter implements COMPILER-LET:

   (1) The interpreter always does a "semantic pre-pass" like the compiler.

   (2) The interpreter expands all macros inside COMPILER-LET before

       evaluating any of the code inside COMPILER-LET.

   (3) COMPILER-LET passes the variable bindings to MACROEXPAND-1

       through the lexical environment, and the time when the interpreter

       expands macros is not changed.