A (new) (old) definition of "top-level"

[sandra%defun@cs.utah.edu (Sandra J Loosemore)]

I've spent the past few hours digging around through the literature to
try to get a historical perspective on the use of the term
"top-level".  Believe it or not, I've actually found a definition of
the term, from the 1st edition of Winston & Horn's LISP book:

  A function is said to be defined or used in the top-level environment
  if its definition or use is directly demanded by a user, rather
  than indirectly by way of the evaluation of one or more other functions.

Historically, it appears that the term "top-level" was first used in
the context of "top-level READ-EVAL-PRINT loop", a context which also
has an implication of direct evaluation.  For example, the manuals for
Stanford Lisp 1.6 (PDP-10) and UT Lisp (CDC-6000) talk about EVAL
being the default "top-level function", and use "top-level expression"
to mean an expression read in and evaluated by the top-level loop.
For example, here's what the UT Lisp manual has to say:

  A LISP program is usually composed of a simple sequence of LISP
  expressions, or forms, to be evaluated. [...]  Program execution is
  handled by the function EVAL, the usual "top-level function".  EVAL is
  called to evaluate successive input expressions in the order they
  appear.

Likewise, the Franz Lisp manual uses "top-level" as a noun to mean
"top-level loop".

So how does this notion of top-level-ness fit in to Common Lisp?  I
think we have to consider the traditional implementation of a Lisp
interpreter as a recursive procedure.  What the Winston & Horn
definition implies is that a top-level form is a form that is seen by
the outermost explicit call to EVAL, and that any recursive calls to
evaluate subforms are not top-level.

In Common Lisp, note that the EVAL function itself cannot be defined
recursively because it doesn't take an environment object.  (I hope
that's obvious without me needing to present a proof.)  Let's suppose
EVAL is implemented by calling a recursive internal function, passing
it the form and a null lexical environment object.  Then, any form
that EVAL itself receives as an argument is a top-level form, but any
subforms which are seen only by the internal function are not
top-level.

This definition doesn't have anything to do with what kinds of things
are in the lexical environment or whether or not they can be
determined in advance.  It does fit in with something we've discussed
before, namely that top-level-ness implies evaluation in a null
lexical environment.

Now to to extend this to file compilation.  LOADing a source file is
defined as reading and evaluating forms from the file.  Since there is
direct evaluation going on, each form that is read from the file is
top-level.  This notion applies just as well to COMPILE-FILE, which
must arrange for the loader to "evaluate" or "execute" each of the
top-level forms. 

Finally, we have implicitly accepted the idea that macroexpansion by
the compiler must preserve semantics.  That implies that
macroexpansion should not have any effect on top-level-ness.  Thinking
about our simple compiler model that doesn't do much besides walk the
code to expand all macros and print out the results, if it is allowed
to turn the bodies of COMPILER-LETs, MACROLETs, and SYMBOL-MACROLETs
into PROGNs, then that would be an argument for saying that those
three special forms should be treated the same as PROGN as far as
top-level-ness goes.  However, that rationale wouldn't cover
constructs like LOCALLY and LABELS (as Moon suggests) unless we modify
our compiler model. 

This way of thinking about top-level-ness makes sense to me.  How
about the rest of you?

-Sandra
-------