Proposed change to SPECIAL: proposed resolution

[David A. Moon <Moon%SCRC-TENEX@MIT-MC>]

Part 1:		(local vs. top-level declarations)

Okay, I am convinced that we need two magic words that introduce a declaration.
One is the one that is specially recognized at the start of certain special forms
and makes local declarations.  The other is a special form, intended to be used
at top level (or inside a PROGN at top level), that makes global declarations.
The first should be called DECLARE and the second PROCLAIM, unless anyone has
better names to propose.  Note that DECLARE is not a special form, but a magic
symbol specially checked for by the interpreter and the compiler.  In a correct
Common Lisp program, EVAL should never see a DECLARE form.  If it does, it will
signal an undefined-function error, unless a Maclisp-compatibility package has
defined a DECLARE special form for Maclisp compatibility (this should not be
included in standard Common Lisp).

There should probably also be an UNPROCLAIM special form, for undoing global
declarations that were "accidentally" made.  This would normally be typed in
by users, not included in files.  For example,
	(PROCLAIM (SPECIAL FLAG))
	(DEFUN FOO (FLAG LIST) (BAR LIST))
	(DEFUN BAR ...)
	(UNPROCLAIM (SPECIAL FLAG))
would behave differently in the interpreter than in the compiler, since
it would be unreasonable to require DEFUN to make a complete copy of the
current global declarations in the interpreter, yet this is effectively
what it does in the compiler.

Maybe PROCLAIM should be a function rather than a special form, even though
its arguments would always be quoted.  There are possible applications for
functions calling it to add global declarations to the world.  The compiler
would know in either case that this is one of the several functions/special
forms that get an automatic "eval-when compile" around them.
I have no opinion either way.

This should simplify and clarify the manual.  Let me restate the rules as I
understand them:

A local declaration of a variable is attached to a particular binding of that
variable, and affects all references captured by that particular binding.  It
does not affect lexically enclosed bindings of variables with the same name,
nor references captured by those inner bindings.

A local SPECIAL declaration not attached to a binding of the variable applies
to all references that would have been lexically captured by a binding of the
variable if there had been one, and makes those references use the dynamic
value.  This extends to a SPECIAL in a LOCALLY in the obvious fashion.

A local declaration of a non-variable type is "pervasive", applying to the
entire lexical body of the special form containing the declaration, including
any interior special forms and including any initialization forms for bound
variables.

To determine the effect of a variable-related local declaration on an
initialization form for a bound variable, you only need to know whether or not
the scope of the variable includes that form.

Global declarations (aka proclamations) of variables apply to the dynamic
value of the variable.

Note: the rules given above mean that LET cannot be written as a macro
expanding into a lambda-combination, a small price to pay for clarifying the
utterly confusing paragraph about this on page 102.  Note that the example
(using *princircle*) given there becomes incorrect, because special isn't
pervasive.  The example at the top of page 103 is incorrect also, because of
the simplification of the rules about bound-variable initialization forms;
the inline declaration will affect both calls to foo.

There are no locally pervasive declarations of variables.  Each variable
declaration applies to only a single binding.  Thus to determine whether a
variable binding is special, one need consider only declarations immediately
attached to that binding and proclamations, not declarations attached to
enclosing bindings.  No search of a declarations environment is required in
the interpreter.

There is no mechanism provided for global declarations whose scope is
limited to the file in which they appear.  Perhaps one will need to be
added later.  Perhaps not.


Part 2:		(efficiency of declarations in the interpreter)

I am very unenthusiastic about the idea of adding syntax to the language in order
to effect an improvement in the speed of the interpreter.  I think I can make some
plausible arguments that the speed improvement to be gained is very small (less
than 1%).

When the interpreter enters a lambda, or any variable-binding special form, it must
check for SPECIAL declarations before binding the variables.  If there are SPECIAL
declarations for variables not bound by the form, a "pseudo binding" entry in the
interpreter's environment structure must be made, so that variable lookup within
that scope will use the dynamic value.

This check consists of examining each element of the body until a non-DECLARE,
non-documentation-string is found.  Macro expansion is required in order to know
whether an element is a DECLARE.  When a DECLARE is found, each declaration
within it must be checked for SPECIAL.  The information from all the SPECIAL
declarations encountered must be used in making the bindings.

How much extra work is this?  The body is going to be looked at right after
binding the variables, in order to evaluate the body forms.  The interpreter
will cdr its handle on the body so that the DECLARE forms it found will not be
looked at again.  The first non-DECLARE form in the body will be macroexpanded
in order to determine that it is not a DECLARE; however it should be easy to
save the resulting expansion and use it as the first thing to be evaluated
once the bindings have been completed, so that the form need not be
macroexpanded again.  So there is no extra actual "interpretation":  the only
real extra work is whatever function-calling and decision-making overhead it
takes to do this, plus whatever overhead is required in deciding for each
variable to be bound whether or not it is in fact special; this probably
consists of mapping over the newly-constructed interpreter environment
structure each time a SPECIAL declaration is seen, looking up the entry for
the variable being declared, and bashing it so that the dynamic variable will
get bound.  My guess is that all of this is much less slow than implementing
&OPTIONAL, &REST, and &KEY in the interpreter.

Note that if the cost of looking for declarations, or of looking and
determining that there are no declarations present, is determined to be too
high in a particular implementation, this information is very easily memoized,
just as macro expansions are memoized.  This can be done by looking up the
lambda or form in a hash table, getting back either a possibly empty list of
variables declared special or "don't know".  Or it can be done by bashing
the form to contain at its front an internal parsed summary of the declarations,
just as macros can be displaced.  Code-understanding tools would need to
know to treat this as a comment.  I recommend that implementations with
limited virtual memory, or much smaller physical memory than virtual memory,
either use the displacing method or set a limit to the size of the hash table
and use a least-recently-used discipline to purge it when it reaches that size;
this applies to macro expansions as well as declarations.

I would not be strongly averse to changing documentation strings to be
	(DECLARE (DOCUMENTATION "foo"))
rather than raw strings if anyone feels that having to check for both strings
and declarations is a pain.  This is probably preferable to requiring that all
declarations precede the documentation string.  The only advantage to this is
that you don't have to special-case a string at the end of the body, which is
a constant value to be returned rather than a documentation string.  The
principal disadvantage, and it is not a trivial one, is that the string starts
very far to the right on the page, so that you don't have as much width in
which to write it, or else you have to grind it in a funny way.  Another possible
disadvantage is that documentation string declarations can be the result of
macro expansion, which therefore must be done (carefully!) by DEFUN in order
to record the documentation string.