Issue: PROCLAIM-LEXICAL

[David A. Moon <Moon@STONY-BROOK.SCRC.Symbolics.COM>]

I finally found the time to read this huge pile of mail carefully and think
clearly about it.  Here's my considered opinion, but before telling you
which proposal I support I'd like to clear away some underbrush.  I
apologize for the 200 line length, but I can't make all the concepts
unambiguously clear with a briefer speech.

We speak of cells, which are conceptual locations that remember a value and
can be read and written.  Sometimes these conceptual locations are
implemented by actual memory locations, and sometimes they aren't, but
that's an implementation detail and is irrelevant here.  (Sometimes these
are called variables, but other times the word "variable" means something
else, so for the sake of clarity I'm not going to use the word "variable".)

Right now, Common Lisp has two kinds of cells: global cells and local
cells.  Local cells have lexical extent, while global cells have global
extent and can be referenced from anywhere except where they are shadowed
by a local cell referenced by the same name.

Right now, Common Lisp has two kinds of binding:  Lexical binding creates a
new local cell.  Special binding saves the value of a global cell, gives it
a new value during the extent of the binding, and later restores the old
value.  We know that special binding saves and restores because of what
other functions see when they read the cell.  Please don't get confused
with issues of shallow-bound versus deep-bound implementation, which are
irrelevant here: I said cells are not the same thing as memory locations.

Note that I am carefully using different words for the two kinds of cells
 from the words for the two kinds of binding; lack of differentiation here
has led to a lot of confusion, I think.

Right now, Common Lisp has a fairly complicated set of rules for how to
determine what cell is referenced when a program mentions a variable name.
(When I say "lexically free", I mean outside of all bindings of that name,
regardless of whether those bindings are special or lexical.)
  1. If the reference is lexically free, use the global cell.
  2. Otherwise, in the absence of a SPECIAL declaration use the cell that
     was affected by the innermost binding; if that binding was special,
     use the global cell; if it was lexical, use the local cell created
     by that binding.
  3. Otherwise, the SPECIAL declaration forces use of the global cell.

We certainly do not want to introduce a third kind of cell, because that
would lead to a great deal of confusion.  Nor do we want to introduce a
third kind of binding.  What we -are- trying to accomplish is to make the
primitive concepts orthogonally available.  An example of a problem we have
right now that needs to be fixed is that there is no way to say that a name
is not misspelled without simultaneously saying that bindings of that name
should be special rather than lexical.  These concepts should be available
as separate constructs.

There are four things that we would like to be able to proclaim about
a variable name (aside from TYPE):
 - the default kind of binding if no declaration specifies which kind
 - the name is not misspelled so don't warn about free references
 - it is illegal to specially bind the global cell, because it is
   a constant or because we want to optimize the performance of a
   deep-binding implementation
 - it is illegal to store into the global cell, because it is a constant

It is already possible in Common Lisp to proclaim all four of these things,
but some of them are mixed up with other concepts and not separately
available.  Let's pick names for the four kinds of proclamations, and let's
also agree that any proclamation serves the "not misspelled" purpose.  Let's
further agree that these four proclamations are mutually exclusive.

  LEXICAL  -- does nothing other than "not misspelled"
  SPECIAL  -- changes the default kind of binding from lexical to special
  GLOBAL   -- makes it illegal to specially bind the global cell
  CONSTANT -- makes it illegal to store into the global cell
              CONSTANT implies GLOBAL because special-binding is storing

SPECIAL exists now.  LEXICAL is Rees's proposal.  CONSTANT exists now
but only buried inside the DEFCONSTANT macro.  GLOBAL exists now but
only when implied by DEFCONSTANT.  I propose to make CONSTANT and
GLOBAL explicitly available.

It appears to be appropriate to make CONSTANT and GLOBAL proclamations
change the default kind of binding to "illegal", rather than leaving
it lexical.

Now we have to ask what these proclamations mean as declarations.
Let us agree that they have the same scoping rules as the SPECIAL
declaration, i.e. they can be attached to a binding and they can
also be wrapped around references, which they pervasively affect
until shadowed by the next declaration or binding.

LEXICAL attached to a binding forces the binding to be lexical even
if there is a SPECIAL, GLOBAL, or CONSTANT proclamation.  LEXICAL
shadows the effect of a special binding on references; therefore we
must add another rule to the "complicated set":
  4. Otherwise, a LEXICAL declaration forces use of the local cell
     created by the innermost lexical binding of the name, or if there
     is none, use of the global cell.

SPECIAL means the same as it has always meant in Common Lisp.

GLOBAL or CONSTANT attached to a binding makes the binding illegal.
GLOBAL or CONSTANT affects a reference by forcing it to use the global
cell, thus rule 3 in the "complicated set" must be modified to treat GLOBAL
and CONSTANT the same as SPECIAL.  We could also just make GLOBAL and
CONSTANT illegal as declarations.  Another idea would be to make CONSTANT
as a declaration allow you to create a new lexical constant.  I'm going to
take the path of least addition to the language and make them illegal.

Note that PROCLAIM-LEXICAL:RESTRICTED conflates LEXICAL and GLOBAL, which
seems undesirable to me.  We want to make each primitive concept separately
available.

Okay, so which proposal do I support?  Well, I support a slight modification
of PROCLAIM-LEXICAL:GENERAL, which I will now explicate (text mostly
copied from Rees):

Proposal (PROCLAIM-LEXICAL:GENERAL+GLOBAL):

  Introduce new declaration specifiers, LEXICAL, GLOBAL, and CONSTANT, which
  are mutually exclusive with the SPECIAL declaration specifier.  All four
  may be used as proclamations; only SPECIAL and LEXICAL may be used as
  declarations.

  A name may be proclaimed only one of LEXICAL, SPECIAL, GLOBAL, or
  CONSTANT.  A name is said to be unproclaimed if it has not been
  proclaimed to be any of these four.

  A free reference or assignment to a name is an error if it is
  unproclaimed and undeclared.

  A LAMBDA-binding in the absence of a declaration or proclamation binds
  the lexical variable.

  SPECIAL proclamations and declarations behave as defined in CLtL.

  LEXICAL proclamations have no effect other than to make the name
  cease to be unproclaimed.  LEXICAL declarations shadow all enclosing
  declarations and proclamation of any of these four types.  LEXICAL
  declarations have the same scoping rules as SPECIAL declarations.

  GLOBAL proclamations make it an error to bind the name.

  CONSTANT proclamations make it an error to bind the name and an
  error to assign to the name.

  DEFCONSTANT is defined in terms of SETQ and the CONSTANT proclamation.
  All keyword symbols are automatically proclaimed CONSTANT.

  A free reference or assignment accesses the same value regardless
  of the declaration or proclamation.  This is called the global value.
  SPECIAL binding alters the global value within its extent.
  (Multiple process and multiple processor systems will have to make
  their own definitions of the extent of a SPECIAL binding, as noted
  on p.38 of CLtL--this proposal is not a proposal to standardize that.)

  The preceding paragraph should be understood carefully.  There is only
  one global value for a name and it is used by all free references, all
  free assignments, and all SPECIAL bindings.

  Example:

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

Note that the second element of the list is different from
the value, 2, it would have in PROCLAIM-LEXICAL:GENERAL.
That is because the special binding of y changes the global
value to 4, and the declared-lexical reference to y accesses
the global value, since there is no surrounding lexical binding.

Cost of adopting change:

  I believe this is the same as current practice as specified by CLtL,
  except that all of the primitive concepts have been made visible instead
  of being hidden inside other concepts.  Compilers and interpreters
  will need to support LEXICAL as a declaration.

  Referencing or assigning to an unproclaimed and undeclared name
  "is an error", not "signals an error", which allows but does not
  require an implementation to issue a warning.  This is a change from
  current language but does not mandate a change from current practice.

Benefits:

  LEXICAL proclamation enhances compatibility with Scheme.
  GLOBAL proclamation allows more efficient deep-bound implementations
  and enhances compatibility with Interlisp and VMLISP.

Cost of converting existing code:

  None, it's upward compatible.

Aesthetics:

  The "insidious and disgusting aspect" doesn't get any worse.  Making
  primitive concepts explicitly available can only enhance aesthetics.

Discussion:

  Let's hear it!