KMP's CL References


This is the writeup of failed issue PROCLAIM-LEXICAL. Because it did not pass, it has no official standing other than as a historical document.

Click here to see my personal notes on this issue.
--Kent Pitman (10-Mar-2001)

References:   variables (p55), scope/extent (p37), global variables (p68),
	      declaration specifiers (p157)
Edit history: Version 2 by Rees 28-Apr-87
              Version 3 by Moon 16-May-87
              Version 4 by Masinter 27-Oct-87
              Version 5 by Masinter 14-Nov-87
              Version 6 by Pitman 15-Sep-88
	       (major revision, for review by Jonathan Rees and Jeff Dalton)
	      Version 7 by Pitman 24-Sep-88
   	       (minor revisions based on comments from Rees and Dalton)
	      Version 8 by Pitman 06-Oct-88 (merge recent discussion)
	      Version 9 by Masinter  8-Dec-88 (make JonL's changes)

Problem Description:

  Although local variables in Common Lisp may be `special' or `lexical,'
  global variables (with the exception of named constants) may currently
  only be `special.'

  The Scheme language permits free variable references to refer to global
  bindings. Their experience suggests that such usage would be useful to
  the Common Lisp community. The absence of such a facility in Common Lisp
  is a barrier both culturally (to the sharing of ideas) and technically
  (to the sharing of code).

  SPECIAL proclamations are uncontrollably pervasive. There is no way
  to locally override or globally undo a SPECIAL proclamation.


  Variable evaluation may be viewed in Common Lisp as a search through
  a set of environments to find a binding, and then the dereferencing of
  that binding. The environments with which Common Lisp deals are
  Lexical (L), Dynamic (D), and Global (G).

  A SPECIAL declaration for a variable amounts to a request that the
  variable be resolved by searching first the Dynamic and then the Global
  environment (DG).

  As currently described in CLtL, lexical variable reference searches
  only the Lexical environment (L).

  Because undeclared free variables in the interpreter are implicitly 
  declared SPECIAL by most (perhaps all) implementations, this amounts
  to a search of Lexical, Dynamic, and Global (LDG). However, the 
  accompanying warnings in many implementations make it clear that this
  behavior is not intended to be taken seriously.

  Constants are looked up solely in the Global environment (G). They
  have other properties as well, of course.

  In the Scheme language, the default lookup is first Lexical, then
  Global (LG). Providing compatibility for Scheme code is, and more
  generally for a Scheme working style is therefore difficult because
  Common Lisp does not provide the LG search style.

  The issue of whether a variable can be assigned is orthogonal.

  The issue of whether a variable can be bound and, if it can be, which
  environment is used for the new binding is orthogonal.


  Provide a new declaration (and proclamation) called LEXICAL which implies
  LG lookup. That is, variables declared LEXICAL would be looked up first
  in the lexical environment (L) and then in the global environment (G)
  if not found in the lexical.

  Clarify that a dynamic binding of a variable creates a new binding
  in the dynamic environment (D) leaving the global environment (G)

  Clarify that special variable access does DG lookup.  That is, 
  variables declared SPECIAL would be looked up first in the dynamic
  environment (D) and then in the global environment (G) if not found
  in the dynamic one. Further clarify that SYMBOL-VALUE does DG lookup.

  Define that a lexical binding of a variable creates a new binding
  in the lexical environment (L), leaving the global environment (G)
  and the dynamic environment (D) unaffected.

  Note that an assignment to a variable which is bound in the global 
  environment (G) will affect lexical (LG) lookups for which there is
  no lexical (L) binding and dynamic (DG) lookups for which there is
  no dynamic (D) binding.

  Note that these restrictions describe an abstract model, not a
  concrete implementation. An implementation may still choose to
  implement dynamic binding as either deep or shallow, but some
  searching may be necessary to find the global cell in shallow bound
  implementations [unless dynamic binding has been forbidden for
  that variable].

  Like SPECIAL declarations (and unlike type declarations),
  compilers and interpreters would be required to notice and 
  respect LEXICAL declarations.


 #1: (proclaim '(lexical x))
     (setq x 1)
     (defun f (fn) (list x (funcall fn)))
     (defun g (fn)
       (let ((x 2))
         (declare (special x))
	 (funcall fn #'(lambda () x))))
     (g #'f) => (1 2)

 #2: ; Warning: It is unlikely that any serious program would 
     ;  be written in so obscure a manner as this example.
     ;  This just tests the fringe cases.
     (proclaim '(lexical x))
     (proclaim '(special y))
     (setq x 1 y 2)
     (defun tst ()
       (let ((x 3) (y 4))
	 (locally (declare (special x) (lexical y))
		  (list x y
			(funcall (let ((x 5) (y 6))
				   #'(lambda () (list x y))))))))
     (tst) => (1 2 (5 4))

    If the results of this example confuse you, keep in mind
    that the results of code like this would be somewhat
    confusing no matter what the chosen semantics because the
    code itself is far from perspicuous.

    An explanation of this behavior, which some people find less
    than intuitive because of the bizarre choice of constructs:
      X gets bound lexically to 3 because X is [pervasively]
       proclaimed LEXICAL.
      Y gets bound specially to 4 because Y is [pervasively]
       proclaimed SPECIAL.
      Reference style for name X is changed to SPECIAL, making
       lexical X=3 invisible.
      Reference style for name Y is changed to LEXICAL, making
       dynamic Y=4 invisible.
      Global X=1 and global Y=2 are first two elements of list.
      X gets bound lexically to 5 because X is [pervasively]
       proclaimed LEXICAL.
      Y gets bound specially to 6 because Y is [pervasively]
       proclaimed SPECIAL.
      Closure is returned, capturing [lexical] X=5 but not
       [special] Y=6.
      Dynamic binding of Y to 6 disappears, dynamic binding
       of Y to 4 reverts.
      Closure is funcalled, returning captured X=5 and dynamically
       active Y=4 in a list which becomes third list element.


  This mechanism provides a simple and straightforward answer to
  the problems stated above.

Current Practice:

  Probably no one implements this.

Cost to Implementors:

  A fair amount compiler work would probably be needed. Some compilers
  may have hooks for most of this already laying around, but some may not.

  Note well that this proposal does not require separate global lexical
  and dynamic cells, so the data storage layout of Lisp need not change.

  Moon says...
   I have now thought of an efficient way to do this on Lisp machines,
   using invisible pointers, and another efficient way to do it on
   stock hardware, using one extra instruction on every global
   reference of one or the other sort, plus a few extra instructions
   in SPECIAL binding and unbinding.  Given that, I no longer object
   to the proposal as unimplementable.

   It doesn't just require a few compiler changes, it requires some
   reimplementation of the representation of global variables, with
   concomitant changes to the compiler, the loader, the interpreter,
   and probably the debugger. Every symbol now potentially has two
   values accessible from the interpreter (the current SPECIAL and
   the global LEXICAL) and you need the corresponding new data
   structure to keep track of that.

  Rees suggests...
   In shallow-bound implementations, implementors may have to add a
   small run-time routine that searches the dynamic saved-binding
   stack to look for the global value in the case where the variable
   has been dynamically bound.  One might want a bit (or a count)
   somewhere (perhaps in the symbol itself) to speed up the common
   case of access to a global binding of a variable that hasn't been
   dynamically bound; without some kind of optimization, you have to
   search the whole saved-binding stack on every reference to a 
   free [lexical] variable.
   While naively you might think you'd incur the cost of clearing the
   valid bit on every dynamic binding (not acceptable), in actuality
   the bit is a static property of programs (PROGV excepted).  So the
   only places you ever need to clear FOO's valid bit are in PROGV,
   in the interpreter, and when FASLOADing code that contains a compiled
   dynamic binding of FOO.

Cost to Users:

  For the most part, this change is upward compatible.
  Some code-walking tools would have to change.

Cost of Non-Adoption:

  It would continue to be difficult to share code with Scheme.

  New CL users coming from the Scheme community would be confused by
  their sometimes inability to map what they know about variable binding
  into the CL model of variable binding.

  Some interesting native CL applications would be impossible to write
  in a syntactically convenient style.


  Enhanced flexibility of expression.
  Rationalization of the semantics of dynamic variables.


  Improved appeal to a certain sector of the programming community.


  Rees points that it is an oversimplification to describe Scheme's
  binding simply as LG since they have no Dynamic environment and
  there is no way to distinguish LG and LDG. However, the reasons he
  prefers LG are:
   1. It's nice for readability and understandability to have a
      declaration which tells you that a variable will not be
      dynamically bound.
   2. It's nice for performance in deep-bound implementations to have a
      declaration that says that no search will be needed.
  Of course, he notes, there could be a counter-argument to item 2
  (in favor of LDG) in order to prefer shallow bound implementations,
  but that still would not defeat the argument in item 1. Rees believes
  that LG is slightly preferrable, but that LDG would be essentially
  adequate for most of his needs.

  Pitman supports PROCLAIM-LEXICAL:LG and believes that giving LDG the
  name LEXICAL would be a serious mistake, leaving open the door for
  program bugs due to accidental binding of variables presumed by the
  programmer not to be bound. If someone (Moon?) seriously wanted LDG
  type variables in addition to LG variables (under a name other than
  LEXICAL), Pitman would not object.

  Dalton expressed support for PROCLAIM-LEXICAL:LG (Version 6).
  He observes that another reason for opposing LDG is that it suggests
  the possibility that someone might want DLG. LG is simpler and still
  accomplishes the stated purpose. He adds ``I would like to be able
  to explain the global environment as a sort of giant, extensible
  LET abound everything.  This proposal seems to get fairly close.''

  It would be possible to submit a proposal for a GLOBAL (G) declaration
  under separate cover if anyone (Xerox?) was interested. Pitman thinks
  this would be an interesting idea. Dalton points out, however, that
  already with this proposal there is enough power to at least deal with
  globals -- albeit circuitously. For example, to reference a global
  variable X, one could write subroutines such as:
   (defun     global-x ()      (declare (lexical x)) x)
   (defun set-global-x (value) (declare (lexical x)) (setq x value))
  Eg, consider:
   (defun f (x) (+ (global-x) x))

  In principle, we could imaging saying that free variables should be
  lexical by default, but that would only reduce error checking to no
  good end. To be really useful, this proposal will need to be followed
  by a proposal for primitives analogous to DEFVAR and/or DEFPARAMETER
  but for lexical variables. However, since arguments over syntax are
  likely to have plenty of issues of their own, we've separated this
  proposal for primitive functionality from issues of syntax which
  can be dealt with separately once this is passed.

  Moon expressed concerns about the efficiency issues but after
  thinking about it for a while convinced himself that this is
  efficiently implementable both on stock and special purpose hardware.

  JonL expressed concerns about the last-minute nature of this change,
  which he sees as untested. This concern applies to the mixin of
  the dynamic environment implicit in the LDG proposal.

  Dalton suggests that an alternative solution to the speed issue
  might be possible to obtain by restricting a particular variable to
  be either LEXICAL or SPECIAL but not both.

  Dalton points that even if people don't like the details here, there
  must be a better fallback solution than "do nothing". Pitman agrees

HTML version Copyright 2001 by Kent M. Pitman. All Rights Reserved.