Issue: PROCLAIM-LEXICAL (Version 7)

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

Jonathan Rees gave me a dump of a bunch of thinking he'd been doing
about PROCLAIM-LEXICAL and based on my understanding of that, I
decided to rewrite the existing proposals and revive this issue.
The focus and presentation is changed substantially -- I hope
for the better.

-----
Issue:        PROCLAIM-LEXICAL
References:   variables (p55), scope/extent (p37), global variables (p68),
	      declaration specifiers (p157)
Category:     CLARIFICATION/ADDITION
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)
Status:	      For Internal Discussion

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.

Background/Analysis:

  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.

Proposal (PROCLAIM-LEXICAL:LG):

  Provide a new declaration (and proclamation) called LEXICAL which does
  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 dynamic binding 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 lexical. Further clarify that SYMBOL-VALUE does DG lookup.

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

  Define that a lexical binding of a variable creates a new binding
  in the lexical environment (L), leaving the global environment (G)
  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 this declaration.

Test Case:

  #1: (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 4))
				    #'(lambda () (list x y))))))))
      (tst) => (1 4 (5 4))

 #2: (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)

Rationale:

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

Current Practice:

  Probably no one implements this.

Cost to Implementors:

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

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.

Benefits:

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

Aesthetics:

  [I'll leave this open to discussion.]  

Discussion:

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