Date: 22 NOV 1982 1630-PST
From: JONL at PARC-MAXC
Subject: Re: Named lambdas
To:   MOON at MIT-MC, common-lisp at SU-AI
cc:   JONL

In response to the message sent  Monday, 22 November 1982  17:52-EST from MOON@SCRC-TENEX

I like this analysis in your reply -- it finally puts some
sense into what has been a confusing notion, namely "nameing"
of functions.

If I may paraphrase, "functions" in the computer sense, i.e.
compiled-code objects, lambda expressions, closures, etc, may
have a name which is independent of any symbol to which that
"function" has been assigned (by fdefinition).  The name is more
like commentary on the code body, and would be helpful in
debugging.  Thus we could have 500 functions with  the "name"
FOO, and have 500 symbols all with the "same function" as
their functional definition.

Assignment of functions to symbols, via fdefinition, is a tool
of programming syntax, and nameing of functions is a tool of
user commentary?


Date: Monday, 22 November 1982  17:52-EST
From: MOON at SCRC-TENEX
To:   common-lisp at SU-AI
Subject: Re: Named lambdas
In-reply-to: The message of 22-Nov-82 12:54:20 PST () from Masinter at PARC-MAXC

    Date: 22-Nov-82 12:54:20 PST (Monday)
    From: Masinter at PARC-MAXC

    If you 
    (defun a (x y) ..)
    and then
    (setf (fdefinition 'b) (fdefinition 'a))
    and then call b, should it say you are inside a?

I say yes, because I believe that functions are first-class objects and
have names.  Thus the defun creates a function named a and then fdefine's
the symbol a to it.  The setf picks up that function and puts in another
cell as well.  But it's the same function.


Date: Monday, 22 November 1982  17:52-EST
From: MOON at SCRC-TENEX
To:   common-lisp at SU-AI
Subject: Re: Named lambdas
In-reply-to: The message of 22-Nov-82 12:54:20 PST () from Masinter at PARC-MAXC

    Date: 22-Nov-82 12:54:20 PST (Monday)
    From: Masinter at PARC-MAXC

    If you 
    (defun a (x y) ..)
    and then
    (setf (fdefinition 'b) (fdefinition 'a))
    and then call b, should it say you are inside a?

I say yes, because I believe that functions are first-class objects and
have names.  Thus the defun creates a function named a and then fdefine's
the symbol a to it.  The setf picks up that function and puts in another
cell as well.  But it's the same function.


Date: Monday, 22 November 1982  17:52-EST
From: MOON at SCRC-TENEX
To:   common-lisp at SU-AI
Subject: Re: Named lambdas
In-reply-to: The message of 22-Nov-82 12:54:20 PST () from Masinter at PARC-MAXC

    Date: 22-Nov-82 12:54:20 PST (Monday)
    From: Masinter at PARC-MAXC

    If you 
    (defun a (x y) ..)
    and then
    (setf (fdefinition 'b) (fdefinition 'a))
    and then call b, should it say you are inside a?

I say yes, because I believe that functions are first-class objects and
have names.  Thus the defun creates a function named a and then fdefine's
the symbol a to it.  The setf picks up that function and puts in another
cell as well.  But it's the same function.


Date: 22-Nov-82 12:54:20 PST (Monday)
From: Masinter at PARC-MAXC
Subject: Re: Named lambdas
In-reply-to: dlw at SCRC-TENEX's message of Friday, 19 November 1982, 20:19-EST
To: common-lisp at SU-AI

If you 

(defun a (x y) ..)

and then

(setf (fdefinition 'b) (fdefinition 'a))

and then call b, should it say you are inside a?

In lieu of any primitives or functions which manipulate these "names", it may
be moot whether the name is associated with "original definition" (i.e., what
you called defun with) or "call location" (i.e., where the definition came
from this time).


Date: 22 November 1982 04:55-EST
From: Kent M. Pitman <KMP at MIT-MC>
Subject:  a LAMBDA special form
To: MOON at SCRC-TENEX
cc: common-lisp at SU-AI

    Date: Friday, 19 November 1982  22:36-EST
    From: MOON at SCRC-TENEX
    To:   common-lisp at SU-AI
    Re:   named lambdas

    ... One way to do this is to say that any list starting with LAMBDA is
    acceptable as a function, and will be translated into whatever the
    implementation wants...

ie, LAMBDA should be a special form which returns a "function" (I use quotes
since I don't mean here an datatype, but rather an intension on a [possibly
already existing] datatype.) A typical system-dependent implementation being
something like
 (defmacro lambda (bvl &body body) `#'(lambda ,@body)).
Similarly for named-lambda.

I think this is a good idea.


    ... Another way would be to add a new primitive MAKE-FUNCTION ...

I would say this should be not so much an addition as possible extension.
The LAMBDA special form would have the interesting advantage of not needing
a preceeding #' and would still be statically analyzable by the compiler,
which is a decided advantage. But LAMBDA would not be as general (without
asking the user to call something like EVAL, which is obviously wrong).
So both are really called for.


Date: Friday, 19 November 1982  22:36-EST
From: MOON at SCRC-TENEX
To:   common-lisp at SU-AI
Subject: named lambdas
In-reply-to: The message of 19 Nov 1982 21:54-EST from Glenn S. Burke <GSB at MIT-ML>

FDEFINITION on a symbol should be the same as FSYMEVAL.

What you get if you do (PRINT (FDEFINITION foo)) necessarily has to be
implementation-dependent, it appears.  So in that sense NAMED-LAMBDA should
not be in Common Lisp, nor should LAMBDA.  Two exceptions to this:

The user should be given certain portable operations on functions,
including extracting their name.  In the case of interpreted functions it
should also be possible to extract the argument list and the body.

The user should be able to construct functions using more primitive
mechanisms than DEFUN.  One way to do this is to say that any list starting
with LAMBDA is acceptable as a function, and will be translated into
whatever the implementation wants.  Storing this function with FDEFINE and
then retrieving it with FDEFINITION will not, in general, return the same
object.  One could accept NAMED-LAMBDA at this level, too, although I like
JonL's idea for flushing it.  Another way would be to add a new primitive
MAKE-FUNCTION.

To do this right requires a portable specification of the behavior of
the interpreter's representation of a lexical environment.


Date: 19 November 1982 21:54-EST
From: Glenn S. Burke <GSB at MIT-ML>
Subject: named lambdas
To: common-lisp at SU-AI

In NIL, a subr (compiled-code object) is the only thing which is allowed
to go into a function cell.  There is mediation performed by FSET to
handle this.  SUBRs for compiled functions have the function name in them.

Interpreted DEFUN does an FSET of the name to an interpreter-closure,
which also has the function name in it.  FSYMEVAL on the name returns
the closure (not the trampoline subr).  Although FLET doesn't happen
to do this because it is currently a macro which expands into a different
NIL binding construct, it could be written as a special form which
also stored the name in the closure.

So, does FDEFINITION want to return the lambda expression of a defun,
or the closure?  Is it different from FSYMEVAL on a symbol?  Looks
like the function cell of your typical interpreted function is going
to have to have an interpreted-lexical-closure in it, so it looks like
everything of interest is going to be encapsulated somehow by
something which would be a more appropriate place for the name.

I'm not really trying to argue against named-lambdas.  That would be
hypocritical since i recently put them into NIL, although they haven't
been exercised and i may have missed a couple places (especially in
the compiler, but that's going away anyway).  But it seems that the
problem they solve might not actually occur that much now.


Date: Friday, 19 November 1982, 20:19-EST
From: Daniel L. Weinreb <dlw at SCRC-TENEX at MIT-MC>
Subject: Named lambdas
To: Masinter at PARC-MAXC, common-lisp at SU-AI
In-reply-to: The message of 15 Nov 82 14:22-EST from Masinter at PARC-MAXC

    Date: 15-Nov-82 11:22:23 PST (Monday)
    From: Masinter at PARC-MAXC
    That the interpreter/compiled code forgets the name of the function you are
    executing in and/or the debugger has trouble finding it from looking at
    the stack seems more like a lack of functionality on the part of the debugger.
    Enough information is there to determine it 

Consider the following case:

(defun a (x y) ...)

(setq var (fdefinition 'a))

The value of var is now the definition of a, namely, the lambda expression
itself, or named-lambda expression on the Lisp Machine currently.

(funcall var 1 2)

At this point, suppose an error happens inside the body of a's
definition.  There is no way to tell that the function on the stack is
named "a" except because it says so inside it; currently, this is done
with named-lambda, although I agree that a stylized declaration could be
used instead.  But there's no way to get the name "a" from the surrounding
context.

I could come up with more involved cases, involving compiled functions
calling interpreted functions, but you get the idea.


Date: 18-Nov-82  8:47:44 PST (Thursday)
From: Masinter at PARC-MAXC
Subject: Re: Masinter's remarks on #,
In-reply-to: Guy.Steele's message of 16 November 1982 2129-EST (Tuesday)
To: Guy.Steele at CMU-CS-A
cc: common-lisp at SU-AI

While READ is many-to-one, most of the identifications are merely syntactic;
that is (x . (a b c)) and (x a b c) really are the same program fragment
as far as program semantics go, while #,X and 3  (when X=3) are semantically
different.

One test for the distinction between syntactic and semantic macro characters is
whether READ = READ-PRINT-(new environment)-READ. The difficult cases then
remain #+ #- #.  and #,. 

Larry


Date: 17 Nov 1982 2259-PST
From: Dave Dyer       <DDYER at USC-ISIB>
Subject: duplicate-p?
To: common-lisp at SU-AI


 I have been getting a LOT of duplicate messages from this mailing list,
most recently I got a gratuitous extra copy of Hedrick's "multiple value"
query of Nov 13.

 Is anyone else also receiving this garbage?  Whose mailer is stuttering?
-------


Date: 17 Nov 1982 2259-PST
From: Dave Dyer       <DDYER at USC-ISIB>
Subject: duplicate-p?
To: common-lisp at SU-AI


 I have been getting a LOT of duplicate messages from this mailing list,
most recently I got a gratuitous extra copy of Hedrick's "multiple value"
query of Nov 13.

 Is anyone else also receiving this garbage?  Whose mailer is stuttering?
-------


Date: 13 Nov 1982 2117-EST
From: HEDRICK at RUTGERS (Mgr DEC-20s/Dir LCSR Comp Facility)
Subject: implementing multiple values
To: common-lisp at SU-AI

We have gotten to the place where I have to actually implement multiple
values.  I find that I need to know a bit more about what the semantics
are, and what compromises are and are not acceptable.  What I would love
to hear is that I can use the Maclisp implementation.  It is certainly
the obvious approach for a conventional machine:  VALUES just saves away
its arguments in some global place (global variables - probably we would
use a separate stack - it doesn't much matter).  Then MULTIPLE-VALUE-xxx
simply retrieves them and makes them into a list, binds variables to
them, etc.  The problem turns out to be knowing when it is safe to use
those stored-away values. E.g. consider the following example from Maclisp:

(multiple-value-list (progn (values 'a 'b 'c) nil)) --> (nil b c)

It seems fairly clear that this should return either (nil) or (a b c).
This seems like a simple bug in the Maclisp implementation.  But it
does illustrate the kind of problems that are going to come up.
I do need to know exactly how long multiple values last.  Here are
the definitions I can see as being reasonable, with the ones I
prefer first (as you might guess, this is simply in order of how easy
they are to implement):

  - an m.v. receiver is only valid when the most recent value computed
	was computed by an m.v. producer.  Other cases are errors, and
	the results are undefined.
  - an m.v. receiver returns the most recent values produced by an
	m.v. producer.  Other non-multiple-values produced in the
	interim are ignored.
  - an m.v. receiver returns the most recent value computed, m.v. or
	otherwise.
  - like the last, except that some constructs "kill" multiple values
	and some do not.  If this definition is used, we need a list
	of the ones that do and don't.

Probably the last two definitions are going to require that every
value computation will interact with the m.v. mechanism, an overhead
I would like to avoid.  At least this is true if m.v.'s can be survive
function returns.  Consider the following example:

    (defun foo nil (bar) 'success)

Since (BAR) may return multiple values, even something as simple as
'SUCCESS is going to have to explicitly do something to make sure that
any multiple values returned by BAR are no longer active.  Either that
or

   (defun foo nil (bar))

is going to have to do something explicit to make sure that if (BAR)
happens to return multiple values, they get returned.

In any case, I need a precise definition.  Can somebody help? The
following cases are given just to spark your thoughts, not to relieve
Guy of the need to give a  precise specification. Please assume that
functions stay defined until they are explicitly redefined.

1.

(defun foo nil (values a b c))
(defun bar nil (foo))
(defun baz nil (multiple-value-list (bar]

2.

(defun baz nil (multiple-value-list
		 (cond ((moon-phase) (foo))
		       (t  (trunc 5 2]

3.

(defun bar nil (cond ((moon-phase) (foo))
		     (t (trunc 5 2]
(defun baz nil (multiple-value-list (bar]

4.

(defun baz nil (multiple-value-list (progn (foo]

5.

(defun baz nil (multiple-value-list (progn (foo) nil]



-------


Date: 17 NOV 1982 1357-PST
From: JONL at PARC-MAXC
Subject: What's wrong with '#,<frob> ?
To:   common-lisp at SU-AI

As GSB related, the Maclisp notion of #, centers around a hokey
notion of "reading for the purpose of compiling this function", as
opposed to reading for any other purpose.  The probelm as I see it
is that QUOTE is being squeezed a bit beyond its capabilities.

QUOTE should imply a constant which is constant over all incarnations
of Lisp, and throughout all time.  The #, indicates something
which varies on a per-loadup basis, but is constant after that.
Previous to "#,", users would just set aside a global variable 
which would be initialized a load up time.  But I much prefer
    (MUMBLE-UPON X '(SOME #,(machine-name) MESSAGES))
to the less apealing
    (MUMBLE-UPON X GLOBALVARIABLE.FOR.MSG.FUNCTION.A0025)

Suggestion:  a new special form, say CQUOTE, which is like QUOTE
    but actually processes over its form, looking for
    certain substitutions to make (such as evaluating some part).
    this is hardly a new idea, since Adolfo Guzeman had such a
    macro in his PhD Thesis program in 1967 (running on a PDP6
    at that -- R.I.P. PDP6!)  Thus the above example would become
        (MUMBLE-UPON X (CQUOTE (SOME (:, (machine-name)) MESSAGES))
    or, if you will permit me the a few # macrocharacter extensions,
        (MUMBLE-UPON X #!(SOME #,(machine-name) MESSAGES))

There are problems to be worked out about whether the processing is
to happen at read time, at compile time, at load time, or at first
reference (Masinter's msg noted severl Interlisp special forms to make
these distinctions).  But it does bring some of the burden for
identifying an "evaluation context" for data back to the original user.

I might add, in addendum to GSB's note, the Bob Kerns and I worked
a long time at trying to get the compiler/assembler to "percolate"
information about squids u p from the inner guts of quoted data
to some "higher" level so that FASLOAD wouldn't crap out because
the load-time evaluation wound up calling FASLOAD recursively.  [I dont
thnk we ever got it 100% right -- I believe I saw another Maclisp bug
report last summer which would have been explaind by this.  But
there is a point of diminishing returns of COMPLR development, and besides
the problem goes away if you cause the needed file to be loaded in
befor hand]

As ALAN mentioned, only the Maclisp version of backquote has the option
of guaranteeing to the user some interal structure of the output
of the backquote and comma macros -- and having some such guarantee
is crucial to having a "residential" system which doesn't keep the text
of all its sources internally.  So how about "conditionalquote", i.e.
CQUOTE, by analogy to the BQUOTE case?


Date: 17 NOV 1982 1357-PST
From: JONL at PARC-MAXC
Subject: What's wrong with '#,<frob> ?
To:   common-lisp at SU-AI

As GSB related, the Maclisp notion of #, centers around a hokey
notion of "reading for the purpose of compiling this function", as
opposed to reading for any other purpose.  The probelm as I see it
is that QUOTE is being squeezed a bit beyond its capabilities.

QUOTE should imply a constant which is constant over all incarnations
of Lisp, and throughout all time.  The #, indicates something
which varies on a per-loadup basis, but is constant after that.
Previous to "#,", users would just set aside a global variable 
which would be initialized a load up time.  But I much prefer
    (MUMBLE-UPON X '(SOME #,(machine-name) MESSAGES))
to the less apealing
    (MUMBLE-UPON X GLOBALVARIABLE.FOR.MSG.FUNCTION.A0025)

Suggestion:  a new special form, say CQUOTE, which is like QUOTE
    but actually processes over its form, looking for
    certain substitutions to make (such as evaluating some part).
    this is hardly a new idea, since Adolfo Guzeman had such a
    macro in his PhD Thesis program in 1967 (running on a PDP6
    at that -- R.I.P. PDP6!)  Thus the above example would become
        (MUMBLE-UPON X (CQUOTE (SOME (:, (machine-name)) MESSAGES))
    or, if you will permit me the a few # macrocharacter extensions,
        (MUMBLE-UPON X #!(SOME #,(machine-name) MESSAGES))

There are problems to be worked out about whether the processing is
to happen at read time, at compile time, at load time, or at first
reference (Masinter's msg noted severl Interlisp special forms to make
these distinctions).  But it does bring some of the burden for
identifying an "evaluation context" for data back to the original user.

I might add, in addendum to GSB's note, the Bob Kerns and I worked
a long time at trying to get the compiler/assembler to "percolate"
information about squids u p from the inner guts of quoted data
to some "higher" level so that FASLOAD wouldn't crap out because
the load-time evaluation wound up calling FASLOAD recursively.  [I dont
thnk we ever got it 100% right -- I believe I saw another Maclisp bug
report last summer which would have been explaind by this.  But
there is a point of diminishing returns of COMPLR development, and besides
the problem goes away if you cause the needed file to be loaded in
befor hand]

As ALAN mentioned, only the Maclisp version of backquote has the option
of guaranteeing to the user some interal structure of the output
of the backquote and comma macros -- and having some such guarantee
is crucial to having a "residential" system which doesn't keep the text
of all its sources internally.  So how about "conditionalquote", i.e.
CQUOTE, by analogy to the BQUOTE case?


Date: 17 NOV 1982 1322-PST
From: JONL at PARC-MAXC
Subject: Expansion of #, and the "residential" question.
To:   moon at MIT-AI, masinter, alan at MIT-MC
cc:   common-lisp at SU-AI

As one who has "crosssed the barrier" between the MacLisp/Interlisp
style of programming, let me proffer an opinion as to what the
"residential" style means.

"Residential" means that files, in the sense of structured
words/bytes on some disk volume, don't really exist!

At first I was taken aback when I found out that Interlisp's
FILEPKG only incidentally dealt with "files" in the above sense.
A "file" is primarily viewed as an agglomeration of functions,
variables with initial values, macros, typed-definitions and so on.
The problems observed to stem from the many-to-one mapping of
READ are irrelevant, and somewhat orthogonal to this issue; in fact,
Interlisp does have a #. feature in its reader -- control-Y -- and
although it doesn't have a general input-radix feature, you can
type numbers in octal or decimal and no attempt is made to remember
how it was read in.

Of course, real disks do exist, and the FILEPKG will incidentally 
"preserve" a "residential file" by prettyprinting a full snapshot of
it onto such a volume; and also the compiler will produce
a compiled disk file upon request.  One thinks of these as information
interchange media, rather than as the real source of the programs
contained therein.

The paramount issue, as raised by ALAN, is that in the MIT world,
one just never, but never, allows the machine-generated prettyprint
of his functions to be stored on disk file, or to be used for much
of anything other than casual inspection at the terminal.  Even
the style of editing isn't the critical factor (at lest for Interlisp-D
users -- tant pis for Interlisp-10), for there is a moderately good
E-style input buffer (E is the Standford editor which inspired EMACS)
called TTYIN.

In fact, I'd like to take this opportunity to praise the Display-based
structure editor of Interlisp-D, upon which I've become increasingly
dependent recently.  The combination of bitmap-display, multiple-fonts,
interface to old-style Interlisp structure editor, mouse-oriented
new-style operations, TTYIN keyboard interface, and so on, make this
the best editor by far, for LISP programs and data, of all those I've
ever seen.

Footnote:  there were a few comments about how semi-colon comments
    are "lost" by the READer; in Interlisp, the corresponding notion
    is asterisk comments, and the are not lost, but incorporated bodily
    intot he source code.  This has two implications: the reader's
    macrocharacter scheme is modified so taht 'FOO reads in as (QUOTE FOO)
    but Don't reads in as a 5-character symbol.  The second is that you
    can't bput comments just anywhere you please; e.g.
        (CONS X (* This is a comment about X.)
              Y)
    is wrong.  I've ocasionally resorted to kludges like
        (CONS (PROG1 X (* This is a comment about X.))
               Y)
    At least the prettyprinter moves comments over to a "comment
    column", just as the MacLisp GRINDEF would put semi-colon
    comments over in a comment column.
 


Date: 16 November 1982 21:45-EST
From: Alan Bawden <ALAN at MIT-MC>
Subject:  Defining the forms to which the # constructs expand
To: Masinter at PARC-MAXC
cc: Moon at SCRC-TENEX, common-lisp at SU-AI

    Date: 16-Nov-82 16:25:04 PST (Tuesday)
    From: Masinter at PARC-MAXC

    ..., but the most natural way to do this is to READ in the program,
    apply a transformation, and prettyprint it out again. It isn't
    acceptable if information like #. and #, get lost. It is preferable
    that the mechanism by which that information is preserved is visible,
    so that the code walkers can know about it.

    You may not think this is an important kind of thing to do, but it seems
    that defining COMMON-LISP in a way which precludes building such tools is
    unnecessary and a mistake.

Common Lisp is already chocked full of reader features that cannot be
preserved across an operation such as you discribe.  Things like the case
of symbols and the base of numbers are all lost in this procedure.  The ";"
comment character is pretty hard to deal with through reading and printing
(you can't just expand into a form), and no scheme I have yet seen will
properly preserve all cases of "`"'ed expressions (although the MacLisp
scheme for this is pretty close).

I would NEVER run any of my MacLisp or LispMachine code through READ and
then PRINT, it would render it totally unreadable.  If precluding such
tools is a mistake, then we have made that mistake long ago.



Date: 15-Nov-82 11:48:48 PST (Monday)
From: Masinter at PARC-MAXC
Subject: Re: #,
To: common-lisp at SU-AI

I would like to see most of the special forms currently in reader macros
merely be abbreviations for some form, since then it would not preclude
building a residential environment around common-lisp.

As for #,: Interlisp has three macros for constants:

(CONSTANT form). Returns the value of form available at compile time. 

(LOADTIMECONSTANT form). Returns the value of form as of load time.

(DEFERREDCONSTANT form). Returns the value of form as of first execution.

All of these merely return the value of "form" when interpreted. Some 
implementations of Interlisp don't support LOADTIMECONSTANT (the compiled-
code loader won't handle it) and those get turned into DEFERREDCONSTANT.

Larry


Date: 17 November 1982 00:12-EST
From: Glenn S. Burke <GSB at MIT-ML>
Subject: multiple values
To: common-lisp at SU-AI

NIL is not going to use the multiple-value scheme described by JonL,
but most likely something similar to what is in use on the "A"
lisp machine.  Function calls which pass back multiple-values
tail-recursively will be flagged;  extra information will be pushed
for call frames which expect to receive multiple values.  Returning
multiple values will involve tracing back call frames, and then if
it is found that multiple values are not expected, throwing them away,
otherwise interpreting what was pushed there in some fashion.

A declaration to the effect that a function returns exactly one value
always will be helpful.  My feeling is that this should not be used to
enforce the single-value return, except perhaps by having the
interpreter complain when the function returns multiple values.  (We
have some philosophy about declarations and program behaviour, don't
we?)  Actually stripping extra values can be done with (VALUES
<form>), which doesn't seem to me to be to be particularly unclear.


Date: Tuesday, 16 November 1982  23:02-EST
From: MOON at SCRC-TENEX
To:   Masinter at PARC-MAXC
Cc:   common-lisp at SU-AI
Subject: Re: Defining the forms to which the # constructs expand
In-reply-to: The message of 16-Nov-82 16:25:04 PST () from Masinter at PARC-MAXC

    Date: 16-Nov-82 16:25:04 PST (Tuesday)
    From: Masinter at PARC-MAXC

    You may not think this is an important kind of thing to do, but it seems that
    defining COMMON-LISP in a way which precludes building such tools is unnecessary
    and a mistake.

I could say exactly the same thing, word for word, about #,.  Of course the
presence of #, in the language hardly precludes building tools that can't work
with it, it only means that those tools cannot work with that construct, and a
user must choose one or the other.  This is not ideal, but I thought we went
through this discussion last year, and concluded that there was no way to
satisfy all requirements at the same time.  Of course, as Steele points out in
his message, you only have to crank up your cleverness a little and use a
smarter reader, and you can still write the same tools.


Date: 16 November 1982 2129-EST (Tuesday)
From: Guy.Steele at CMU-CS-A
To: common-lisp at SU-AI
Subject: Masinter's remarks on #,

I am very much in sympathy with the goal of writing program-writing programs
and program-transforming programs.  I don't think the existence or
non-existence of #, makes that job any harder or easier, however.
I think that any mechanism that can also preserve the distinction
between #o777 and 511, or for that matter between |(foo| and \(foo,
or even between (x . (a b c)) and (x a b c) [I sometimes write the former
in a constant a-list if necessary to preserve visual similarity of the
entries]---such a mechanism can also deal with #,.  The fact is that
vanilla READ is a many-to-one mapping; by the time you've got the
S-expression in memory you have already lost.  Preservation of the
information requires using a parser other than READ, which may imply
generation of internal structure different from what READ would
produce, that may be unsuitable for evaluation.  Alternatively, various
kinds of hashing could be used.  Nevertheless, in every LISP from
LISP 1.5 on, READ has been a many-to-one mapping.


Date: 16 November 1982 21:45-EST
From: Alan Bawden <ALAN at MIT-MC>
Subject:  Defining the forms to which the # constructs expand
To: Masinter at PARC-MAXC
cc: Moon at SCRC-TENEX, common-lisp at SU-AI

    Date: 16-Nov-82 16:25:04 PST (Tuesday)
    From: Masinter at PARC-MAXC

    ..., but the most natural way to do this is to READ in the program,
    apply a transformation, and prettyprint it out again. It isn't
    acceptable if information like #. and #, get lost. It is preferable
    that the mechanism by which that information is preserved is visible,
    so that the code walkers can know about it.

    You may not think this is an important kind of thing to do, but it seems
    that defining COMMON-LISP in a way which precludes building such tools is
    unnecessary and a mistake.

Common Lisp is already chocked full of reader features that cannot be
preserved across an operation such as you discribe.  Things like the case
of symbols and the base of numbers are all lost in this procedure.  The ";"
comment character is pretty hard to deal with through reading and printing
(you can't just expand into a form), and no scheme I have yet seen will
properly preserve all cases of "`"'ed expressions (although the MacLisp
scheme for this is pretty close).

I would NEVER run any of my MacLisp or LispMachine code through READ and
then PRINT, it would render it totally unreadable.  If precluding such
tools is a mistake, then we have made that mistake long ago.



Date: 16-Nov-82 16:25:04 PST (Tuesday)
From: Masinter at PARC-MAXC
Subject: Re: Defining the forms to which the # constructs expand
In-reply-to: MOON's message of Tuesday, 16 November 1982  15:22-EST
To: (MOON at SCRC-TENEX)
cc: common-lisp at SU-AI

Foo. By a residential system, I mean one in which you can write programs in Lisp to
write and modify programs (using the normal S-expression representation of the
program), and have the program-modified programs be first class.

I suppose since you haven't seen the point of this, I should give an example.
Let's suppose, for example, that I wanted to swap the order of arguments to a
function. I might write a program/edit command which would go through my code,
switching the  arguments, and wrapping the whole thing with a LET if necessary
to enforce argument evaluation. 

I could imagine writing TECO macros to do this, where you look at the text and
pretend that you were looking at the s-expression, but the most natural way to
do this is to READ in the program, apply a transformation, and prettyprint it
out again. It isn't acceptable if information like #. and #, get lost. It is
preferable that the mechanism by which that information is preserved is visible,
so that the code walkers can know about it.

You may not think this is an important kind of thing to do, but it seems that
defining COMMON-LISP in a way which precludes building such tools is unnecessary
and a mistake.


Date: 16 November 1982 19:24-EST
From: Glenn S. Burke <GSB at MIT-ML>
Subject: Re: #,
To: common-lisp at SU-AI

What can be done to allow load-time evaluation in a general fashion is
this.  (This has been implemented in Maclisp.  I won't say how because
it is a dirty kludge and was then specialized to a particular purpose.)

Provide the user with some means by which he can get load-time evaluation
performed to provide some object, no matter where it is in whatever
structure is being "dumped", by virtue of having some symbol (of HIS
choosing) as the car of a list.  (The CADR being the form which gets
evaluated at load time, for instance, although you might not want to
maintain that restriction.)

Then, the user is free to provide how to handle:
   (1)  What to do when the form is encountered by the compiler as a
form to be compiled, by defining some sort of compiler-macro or
optimizer or rewrite rule or whatever we have for that (which we
should also define).
   (2)  What to do when the form is encountered by the evaluator.
Since these forms are typically produced during compilation (by virtue
of the reading being done by the compiler, something which the user
should be able to determine [yet another thing to define]), this could
be considered an error, or the function could be a macro which quotes
itself, effectively causing the object to be self-evaluating.

So, for example, if this worked by virtue of the symbol having a
non-null :load-time-evaluation-form property, one might implement the
Maclisp SQUID form as follows:

;SQUID, "Self Quoting Internal Datum", has as its value a marker which
; you list around a form which should be evaluated at load time.  THe
; form is otherwise treated as being self-evaluating.
(defvar squid
  (copysymbol 'squid))

;Tell the compiler/assembler about the marker.
(putprop squid t :load-time-evaluation-form)

;Define how such a form compiles and evaluates:
(defun squid-quoter (form)
   (list 'quote form))

;I guess the following is probably wrong for common-lisp but anyway:
(fset squid '(macro . squid-quoter))

Then, the code for #, could simply do
	(if *reading-for-compilation*
	    (list squid (read))
	    (eval (read)))

"*reading-for-compilation*" should probably be
"*reading-for-external-compilation*" to distinguish it from the case
when the compiler is compiling directly to core.
----
Of course another way to do this is to have a flavor or
extend/message-passing system and simply define the right messages to
interface to the compiler and evaluator.
----
If you try to generalize this too much you run into problems
differentiating your runtime and compile-time environments;  for
example a macro which contains pointers to datastructure which should
be created with a special load-time-eval construct, but it can be used
both by the interpreter and the compiler.  Having the compiler not
bash the runtime environment with macro definitions it is compiling
(but save the definitions away and expand them otherwise) alleviates
this, but only for the single-file compilation.  There are potentially
other subtleties which make the read switch inadequate, such as having
a single textual definition which both needs to be compiled to a file
and stored in core (the traditional macro definition bashing the
runtime environment, for example, but this might arise in other ways).

Anyway, the reason i brought all this up is that we have played some
with writing, saving, and referring to nodes in semantic networks
here, and that is the sort of thing which "users" might try to do.
[JonL and/or Guy can testify to the Maclisp hacking in this regard
from variously the OWL, LMS, XLMS, and Brand-X systems, each of which
implemented yet another representation scheme and found the Lisp
primitives inadequate.]


Date: 16 Nov 1982 1650-MST
From: Eric Benson <BENSON at UTAH-20>
Subject: Re: (prog1 (trunc x y))
To: BROOKS at MIT-OZ at MIT-MC, common-lisp at SU-AI
In-Reply-To: Your message of 16-Nov-82 1324-MST

Indeed, this seems like a natural candidate for a declaration, being in the
category of "optional optimization." (DECLARE (SINGLE-VALUE TRUNC)) isn't
that ugly.
-------


Date: 16-Nov-82 16:25:04 PST (Tuesday)
From: Masinter at PARC-MAXC
Subject: Re: Defining the forms to which the # constructs expand
In-reply-to: MOON's message of Tuesday, 16 November 1982  15:22-EST
To: (MOON at SCRC-TENEX)
cc: common-lisp at SU-AI

Foo. By a residential system, I mean one in which you can write programs in Lisp to
write and modify programs (using the normal S-expression representation of the
program), and have the program-modified programs be first class.

I suppose since you haven't seen the point of this, I should give an example.
Let's suppose, for example, that I wanted to swap the order of arguments to a
function. I might write a program/edit command which would go through my code,
switching the  arguments, and wrapping the whole thing with a LET if necessary
to enforce argument evaluation. 

I could imagine writing TECO macros to do this, where you look at the text and
pretend that you were looking at the s-expression, but the most natural way to
do this is to READ in the program, apply a transformation, and prettyprint it
out again. It isn't acceptable if information like #. and #, get lost. It is
preferable that the mechanism by which that information is preserved is visible,
so that the code walkers can know about it.

You may not think this is an important kind of thing to do, but it seems that
defining COMMON-LISP in a way which precludes building such tools is unnecessary
and a mistake.


Date: 16 November 1982 19:24-EST
From: Glenn S. Burke <GSB at MIT-ML>
Subject: Re: #,
To: common-lisp at SU-AI

What can be done to allow load-time evaluation in a general fashion is
this.  (This has been implemented in Maclisp.  I won't say how because
it is a dirty kludge and was then specialized to a particular purpose.)

Provide the user with some means by which he can get load-time evaluation
performed to provide some object, no matter where it is in whatever
structure is being "dumped", by virtue of having some symbol (of HIS
choosing) as the car of a list.  (The CADR being the form which gets
evaluated at load time, for instance, although you might not want to
maintain that restriction.)

Then, the user is free to provide how to handle:
   (1)  What to do when the form is encountered by the compiler as a
form to be compiled, by defining some sort of compiler-macro or
optimizer or rewrite rule or whatever we have for that (which we
should also define).
   (2)  What to do when the form is encountered by the evaluator.
Since these forms are typically produced during compilation (by virtue
of the reading being done by the compiler, something which the user
should be able to determine [yet another thing to define]), this could
be considered an error, or the function could be a macro which quotes
itself, effectively causing the object to be self-evaluating.

So, for example, if this worked by virtue of the symbol having a
non-null :load-time-evaluation-form property, one might implement the
Maclisp SQUID form as follows:

;SQUID, "Self Quoting Internal Datum", has as its value a marker which
; you list around a form which should be evaluated at load time.  THe
; form is otherwise treated as being self-evaluating.
(defvar squid
  (copysymbol 'squid))

;Tell the compiler/assembler about the marker.
(putprop squid t :load-time-evaluation-form)

;Define how such a form compiles and evaluates:
(defun squid-quoter (form)
   (list 'quote form))

;I guess the following is probably wrong for common-lisp but anyway:
(fset squid '(macro . squid-quoter))

Then, the code for #, could simply do
	(if *reading-for-compilation*
	    (list squid (read))
	    (eval (read)))

"*reading-for-compilation*" should probably be
"*reading-for-external-compilation*" to distinguish it from the case
when the compiler is compiling directly to core.
----
Of course another way to do this is to have a flavor or
extend/message-passing system and simply define the right messages to
interface to the compiler and evaluator.
----
If you try to generalize this too much you run into problems
differentiating your runtime and compile-time environments;  for
example a macro which contains pointers to datastructure which should
be created with a special load-time-eval construct, but it can be used
both by the interpreter and the compiler.  Having the compiler not
bash the runtime environment with macro definitions it is compiling
(but save the definitions away and expand them otherwise) alleviates
this, but only for the single-file compilation.  There are potentially
other subtleties which make the read switch inadequate, such as having
a single textual definition which both needs to be compiled to a file
and stored in core (the traditional macro definition bashing the
runtime environment, for example, but this might arise in other ways).

Anyway, the reason i brought all this up is that we have played some
with writing, saving, and referring to nodes in semantic networks
here, and that is the sort of thing which "users" might try to do.
[JonL and/or Guy can testify to the Maclisp hacking in this regard
from variously the OWL, LMS, XLMS, and Brand-X systems, each of which
implemented yet another representation scheme and found the Lisp
primitives inadequate.]


Date: 16 Nov 1982 1650-MST
From: Eric Benson <BENSON at UTAH-20>
Subject: Re: (prog1 (trunc x y))
To: BROOKS at MIT-OZ at MIT-MC, common-lisp at SU-AI
In-Reply-To: Your message of 16-Nov-82 1324-MST

Indeed, this seems like a natural candidate for a declaration, being in the
category of "optional optimization." (DECLARE (SINGLE-VALUE TRUNC)) isn't
that ugly.
-------


Date: 16 November 1982 15:45-EST
From: Alan Bawden <ALAN at MIT-MC>
Subject:  (prog1 (trunc x y))
To: common-lisp at SU-AI

I believe the LispMachine uses (VALUES (TRUNC X Y)) to force the return of
a single value.  What could be clearer?


Date: 16 November 1982 1538-EST (Tuesday)
From: Guy.Steele at CMU-CS-A
To: common-lisp at SU-AI
Subject: Forcing one value from a function

I have been given to believe that in Lisp Machine LISP
the approved convention is
	(VALUES (FLOOR x y))
to get back exactly one value.  I suppose this might be
somewhat misleading to the novice.
--Guy


Date: 16 November 1982 1538-EST (Tuesday)
From: Guy.Steele at CMU-CS-A
To: common-lisp at SU-AI
Subject: Forcing one value from a function

I have been given to believe that in Lisp Machine LISP
the approved convention is
	(VALUES (FLOOR x y))
to get back exactly one value.  I suppose this might be
somewhat misleading to the novice.
--Guy


Date: 16 Nov 1982 1648-EST
From: Ron <FISCHER at RUTGERS>
Subject: Re: Obliquity of the vernacular...
To: BROOKS at MIT-OZ at MIT-MC, common-lisp at SU-AI
In-Reply-To: Your message of 16-Nov-82 1524-EST

I agree with BROOKS.  Where is all the perspicuity to which the manual
constantly refers?  How could something as obscure as (prog1 (trunc x
y)) be suggested in this light?  Give the poor thing a name if it will
be used.

(ron fischer)
-------


Date: 16 Nov 1982 1648-EST
From: Ron <FISCHER at RUTGERS>
Subject: Re: Obliquity of the vernacular...
To: BROOKS at MIT-OZ at MIT-MC, common-lisp at SU-AI
In-Reply-To: Your message of 16-Nov-82 1524-EST

I agree with BROOKS.  Where is all the perspicuity to which the manual
constantly refers?  How could something as obscure as (prog1 (trunc x
y)) be suggested in this light?  Give the poor thing a name if it will
be used.

(ron fischer)
-------


Date: 16 Nov 1982 1524-EST
From: BROOKS at MIT-OZ at MIT-MC
Subject: (prog1 (trunc x y))
To: common-lisp at SU-AI

(return (prog1 (trunc x y))) looks like awful black magic, and
the intent is not very clear. How about
  (or (trunc x y) ())
since in that position multiple values are defined not to work
so the compiler can figure it out there too. I'd prefer to
see a clear mechanism provided rather than (by default) encouraging
users to come up with obscure gobble-de-gook to make use of
essentially side effects of the semantics of special forms.
-------


Date: 16 November 1982 15:45-EST
From: Alan Bawden <ALAN at MIT-MC>
Subject:  (prog1 (trunc x y))
To: common-lisp at SU-AI

I believe the LispMachine uses (VALUES (TRUNC X Y)) to force the return of
a single value.  What could be clearer?


Date: 16 Nov 1982 1524-EST
From: BROOKS at MIT-OZ at MIT-MC
Subject: (prog1 (trunc x y))
To: common-lisp at SU-AI

(return (prog1 (trunc x y))) looks like awful black magic, and
the intent is not very clear. How about
  (or (trunc x y) ())
since in that position multiple values are defined not to work
so the compiler can figure it out there too. I'd prefer to
see a clear mechanism provided rather than (by default) encouraging
users to come up with obscure gobble-de-gook to make use of
essentially side effects of the semantics of special forms.
-------


Date: Tuesday, 16 November 1982  15:22-EST
From: MOON at SCRC-TENEX
To:   HEDRICK at RUTGERS, Masinter at PARC-MAXC
Cc:   common-lisp at SU-AI
Subject: Defining the forms to which the # constructs expand

I agree with you, since I think that primitives should always be available
to the user.

Note, however, that you both missed a vital point.  Neither #. nor #,
expands into a form!  Both of these can be used inside of an expression
which is data, as well as inside an expression which is a program.  When
reading into the environment (as opposed to reading into the compiler),
the #. and #, constructs must produce precisely the result of evaluating
their argument.  They cannot produce any sort of "wrapper" around it.

The only hidden primitive involved in #. and #, is the "magic wrapper"
that #, uses when reading into the compiler.

The inability to deal with things like #. is the inherent bankruptcy of
residential systems, if by that you mean an editor which regenerates your
source text from the actual contents of memory, rather than keeping a
separate copy of it.  On the other hand, if by residential system you mean
merely the ability to switch rapidly between typing at the Lisp evaluator
and typing at the editor, and the ability to edit single functions and get
them into memory without the overhead of reading or compiling whole files,
this is what we have in the Lisp machine, while still using text-based
editing, and Boy!  Is it ever an improvement over the old file-based ways
of doing things!


Date: 16 November 1982 1315-EST (Tuesday)
From: Guy.Steele at CMU-CS-A
To: common-lisp at SU-AI
Subject: 1000th message

Since I started collecting COMMON-LISP messages into a
separtate file on 27 October 1981, this is the one-thousandth
message.


Date: Tuesday, 16 November 1982  13:52-EST
From: Scott E. Fahlman <Fahlman at Cmu-20c>
To:   BROOKS at MIT-OZ at MIT-MC
Cc:   common-lisp at SU-AI
Subject: DLW's message and Fateman's FLOOR.


I don't think we need a new declaration.  If you want to suppress the
return of multiple values for some form in tail-recursive position, you
can easily do that with, for example,

... (return (prog1 (trunc x y))) ...

Static analysis at compile time will now show that only one value is
coming back.  As Rod Brooks points out, one would seldom bother with
this: it is useful only in a call to a multiple-value producer in
tail-recursive position in a place where the speed matters.  The use of
TRUNC and friends in a context where the consumer of the value is
lexically apparent can be optimized at compile-time.

-- Scott


Date: 16 Nov 1982 1355-EST
From: HEDRICK at RUTGERS
To: Masinter at PARC-MAXC, common-lisp at SU-AI
Subject: Re: #,
Message-ID: <"MS10(2117)+GLXLIB1(1135)" 11872446256.46.19.20844 at RUTGERS>
Regarding: Message from Masinter at PARC-MAXC of 15-Nov-82 1148-EST

I strongly concur with Masinter's request to define the forms to which
the # constructs expand.  It should be possible to represent anything
that can be in a Lisp file using S-expressions, for fairly obvious
reasons.  Although I regard existing "residential system" as
relatively unattractive (in particular I think most of our users
prefer an LEDIT interface to EMACS to the Interlisp structure editor),
we have some very attractive proposals for systems that mix features
of in-core function editors and systems such as LEDIT.  Certainly this
kind of system will only work if we can write back out what we read
in.  This includes both # constructs and comments.  We will surely
define these things locally if we have to, but it seems like a good
idea for everybody to agree on them.
   --------


Date: Tuesday, 16 November 1982  13:52-EST
From: Scott E. Fahlman <Fahlman at Cmu-20c>
To:   BROOKS at MIT-OZ at MIT-MC
Cc:   common-lisp at SU-AI
Subject: DLW's message and Fateman's FLOOR.


I don't think we need a new declaration.  If you want to suppress the
return of multiple values for some form in tail-recursive position, you
can easily do that with, for example,

... (return (prog1 (trunc x y))) ...

Static analysis at compile time will now show that only one value is
coming back.  As Rod Brooks points out, one would seldom bother with
this: it is useful only in a call to a multiple-value producer in
tail-recursive position in a place where the speed matters.  The use of
TRUNC and friends in a context where the consumer of the value is
lexically apparent can be optimized at compile-time.

-- Scott


Date: 16 Nov 1982 1316-EST
From: BROOKS at MIT-OZ at MIT-MC
Subject: Re: DLW's message and Fateman's FLOOR.
To: common-lisp at SU-AI

Right.

Most of the time the complaint about FLOOR being expensive
doesn't apply, as it will get compiled down to one result.
But what about when it is a tail recursive call. The compiler
can't know whether both values are needed. How about having
some way of declaring that a function will only return one
value: e.g.

(DEFUN USER-MOD3 (X)
  (DECLARE (SINGLE-VALUE USER-MOD3))
  (MOD X 3))

where we probably want something less ugly.

I suspect (as long as we don't arbitrarily start loading up all
sorts of random functions with multiple values) that this would
only be needed very infrequently.
-------


Date: Monday, 15 November 1982  19:34-EST
Sender: DLW at MIT-OZ
From: DLW at MIT-MC
To:   Kim.fateman at Berkeley
Cc:   common-lisp at su-ai
Subject:  multiple-value return
In-reply-to: The message of 14-Nov-82 09:42:03-PST (Sun) from Kim.fateman@Berkeley

If you spent more time thinking about how to produce a low-cost
implementation and less time trying to convince us to remove multiple
values from the language, I bet you could come up with
a cheap implementation.  It's largely a matter of how
you choose to expend your efforts.  I'm glad there are
some people on this mailing list who are spending their
time trying to solve problems and figure out good ways
to implement Common Lisp.

Indeed, a very tricky and crafty scheme might be needed
to implement multiple values efficiently.  That's fine.
As long as the user doesn't see it, it's worth it.  I
consider this analogous to the "fast number" scheme in
PDP-10 Maclisp.  Our goal should be to eliminate the
"Lisp is inherently inefficient and can't ever be competitive
with other languages" mentality.

It's also a good thing that Common Lisp is not being designed
purely by a group of language implementors, who have lots
of motivation to eliminate features to keep their own job
easy.  Common Lisp's design has been heavily influenced
by the experience of real users of Maclisp and the Lisp Machine,
who are interested in getting work done and writing code that
can be both efficient and elegant, and who are not interested
especially in keeping things easy for the implementors.  Let
us continue to develop Common Lisp with the needs of the user
foremost in our minds.


Date: Monday, 15 November 1982  19:34-EST
Sender: DLW at MIT-OZ
From: DLW at MIT-MC
To:   Kim.fateman at Berkeley
Cc:   common-lisp at su-ai
Subject:  multiple-value return
In-reply-to: The message of 14-Nov-82 09:42:03-PST (Sun) from Kim.fateman@Berkeley

If you spent more time thinking about how to produce a low-cost
implementation and less time trying to convince us to remove multiple
values from the language, I bet you could come up with
a cheap implementation.  It's largely a matter of how
you choose to expend your efforts.  I'm glad there are
some people on this mailing list who are spending their
time trying to solve problems and figure out good ways
to implement Common Lisp.

Indeed, a very tricky and crafty scheme might be needed
to implement multiple values efficiently.  That's fine.
As long as the user doesn't see it, it's worth it.  I
consider this analogous to the "fast number" scheme in
PDP-10 Maclisp.  Our goal should be to eliminate the
"Lisp is inherently inefficient and can't ever be competitive
with other languages" mentality.

It's also a good thing that Common Lisp is not being designed
purely by a group of language implementors, who have lots
of motivation to eliminate features to keep their own job
easy.  Common Lisp's design has been heavily influenced
by the experience of real users of Maclisp and the Lisp Machine,
who are interested in getting work done and writing code that
can be both efficient and elegant, and who are not interested
especially in keeping things easy for the implementors.  Let
us continue to develop Common Lisp with the needs of the user
foremost in our minds.


Date: 15 NOV 1982 1421-PST
From: JONL at PARC-MAXC
Subject: Multiple-Value implementations
To:   hedrick at RUTGERS
cc:   common-lisp at SU-AI, jonl

Apologies for not being able to reply as fast and prolifically
as others on this issue (still "snowed under" from house buying etc),
but I think the VAX/NIL method of handling multiple values should
be considered.  It has the virtue of being incredibly more
siimple than the summary you suggested, and the minor disadvantage
that MVPROG1 is slightly more expensive than it would be in a stack-
oriented implementation.

One machine register is dedicated to communicating back the number
of values returned by any function.  This is the only failing of the
MacLisp "add-on" macro scheme -- it was judged to be too expensive  to
the non MV user to have every function, including built-in system
functions, take the time (adn space!) to do this; besides, all compiled
code would be invalidated should such a demand be enforced.  

But back to the to the topic: on the VAX, the function-exit sequence includes
a two-byte instruction to set the number of values being returned.  Thus
(COND ((FOO) 'A) (T (VALUES 'B 'A)))  would have two slightly different exit
sequences (if this form were the return-value of a function).  All values
are returned in a "value-return" vector; and as Moon rightly pointed out,
having the first location of this conceptual vector be the register where
single-value function results would *normally* be found means that non-users
of the MV stuff pay only the two-byte penalty (this is truly zilch on the VAX,
considering its funciton call overhead, and it ought to be so on the PDP10).
Since this is not a stack protocol, then a tail-recursive instance of MVPROG1 must
be compiled in such a way as to save-and-restore the active value-return vector;
the cost of this may not be zilch (that is, it may actually be measurable), but
then how often and how important is this case?

The compiler need not be more clever than to "fold-out" lexical instances of
apparent mv usage.  Callers who want exactly one value from a function call need
not be perturbed at all (unless  you want to provide run-time checking for the
case of zero arguments returned).  Sume support might be given to the interpreter so 
that it not actually cons-up-into-a-list the multiple values returned -- such
as using resource-allocated scratch vectors or whatnot; perhaps some syntax is
needed whereby a "scratch list" can be given to MULTIPLE-VALUE-LIST.  [Unfortunately,
not all of these ideas got integrated into VAX/NIL before the mail development
group dissolved -- it was just using the MacLisp-like macros last time I checked --
but most of them had been coded and tested out.  It  may still be at what
you called "stage 1".]

I prefer the notion of disconnecting any rigid link between caller and callee
on this mater -- there is no m ore reason why returning multiple-values when not
explicitly "called for" is bad than there is reason to proscribe value-returning
functions from being called "for effects".  Like Moon pointed out in reply to
Fateman's concern: it's better to produce the multiple valuues even when not
wanted than it would be to produce some gross structure that had to be "torn apart"
at run time to get at the one value wanted.


Date: 15-Nov-82 11:48:48 PST (Monday)
From: Masinter at PARC-MAXC
Subject: Re: #,
To: common-lisp at SU-AI

I would like to see most of the special forms currently in reader macros
merely be abbreviations for some form, since then it would not preclude
building a residential environment around common-lisp.

As for #,: Interlisp has three macros for constants:

(CONSTANT form). Returns the value of form available at compile time. 

(LOADTIMECONSTANT form). Returns the value of form as of load time.

(DEFERREDCONSTANT form). Returns the value of form as of first execution.

All of these merely return the value of "form" when interpreted. Some 
implementations of Interlisp don't support LOADTIMECONSTANT (the compiled-
code loader won't handle it) and those get turned into DEFERREDCONSTANT.

Larry


Date: 15-Nov-82 11:22:23 PST (Monday)
From: Masinter at PARC-MAXC
Subject: Named lambdas
To: common-lisp at SU-AI

That the interpreter/compiled code forgets the name of the function you are executing in and/or the debugger has trouble finding it from looking at
the stack seems more like a lack of functionality on the part of the debugger.
Enough information is there to determine it (e.g., looking at the instruction 
preceding the return PC to see what function was called) that a kludge like
NAMED-LAMBDA doesn't seem at all a reasonable part of the white pages.

I had imagined, incorrectly, that NAMED-LAMBDA actually had some semantics
associated with it, e.g. it was similar to the Interlisp notion of creating
a frame with a name which was visible to STKPOS, RETFROM, and other stack
primitives. The current common-lisp spec seems to have a big hole in the area
of primitives which would allow one to write an implementation-independent 
debugger.


Date: 15-Nov-82 08:53:20-PST (Mon)
From: Kim.fateman@Berkeley
Subject: multiple thanks
Message-Id: <8210151653.22738@UCBVAX.BERKELEY.ARPA>
Received: by UCBVAX.BERKELEY.ARPA (3.227 [10/22/82])
	id A22720; 15-Nov-82 08:53:18-PST (Mon)
To: hedrick@rutgers
Cc: common-lisp@su-ai

Thanks for presenting a proposed mechanism for multiple values which seems
to penalize the producers of multiple values (and the implementors of 
lisp systems).  Yet,now there is this hidden cost in
using some m-v producers: should one use them, since in some
circumstances they have to do a fair amount of stack-grovelling?
(e.g. one might think that "floor" would always be fairly cheap to use).


Date: 15 November 1982 06:34-EST
From: Kent M. Pitman <KMP at MIT-MC>
Subject:  Multiple Value Return and Continuation Passing Style
To: common-lisp at SU-AI

I guess it's worth noting just for completeness that there is an alternative
to the multiple-value-return idea which is suggested by continuation-passing
style a la Sussman/Steele papers... I take no stand on whether this would be
the right thing for Common-Lisp, but I point it out for completeness since
it involves no pervasive effect upon the whole interpreter to implement things
in this style. Here's an example from the preliminary T manual (May '82):

    (DIV2 n1 n2 proc)

     Division yielding quotient and remainder. Not yet implemented. The
     PROC should be a procedure of two arguments; it will be invoked on
     the quotient and remainder. For example:

      (DIV2 11 4 LIST)  => (2 3)
      (DIV2 11 4 PROJ0) => 2

Where PROJ0 is like the subr version of BLOCK0 (which is T's name for PROG1).

This is upward compatible with the LispM in that although it doesn't use 
multiple values at all, it can be implemented by taking advantage of 
functions that return them. eg, a sample LispM implementation would be:

 (DEFUN DIV2 (X Y FN)
   (MULTIPLE-VALUE-BIND (QUO REM)
       (QUOTIENT X Y)
     (FN QUO REM)))

Also, remember that constructs like:

 (MULTIPLE-VALUE-LIST (PROG1 (G) (H) (I)))

where (G) might return multiple values can always be re-written if G can
be made to accept a continuation arg as something like:

 (G #'(LAMBDA (&REST ARGS) (H) (I) ARGS))

The intent here is not to say this is what we should do, but just to make
sure we're not overly restricting our mode of thinking in this issue...
-kmp


Date: 15-Nov-82 11:22:23 PST (Monday)
From: Masinter at PARC-MAXC
Subject: Named lambdas
To: common-lisp at SU-AI

That the interpreter/compiled code forgets the name of the function you are executing in and/or the debugger has trouble finding it from looking at
the stack seems more like a lack of functionality on the part of the debugger.
Enough information is there to determine it (e.g., looking at the instruction 
preceding the return PC to see what function was called) that a kludge like
NAMED-LAMBDA doesn't seem at all a reasonable part of the white pages.

I had imagined, incorrectly, that NAMED-LAMBDA actually had some semantics
associated with it, e.g. it was similar to the Interlisp notion of creating
a frame with a name which was visible to STKPOS, RETFROM, and other stack
primitives. The current common-lisp spec seems to have a big hole in the area
of primitives which would allow one to write an implementation-independent 
debugger.


Date: 15-Nov-82 11:48:48 PST (Monday)
From: Masinter at PARC-MAXC
Subject: Re: #,
To: common-lisp at SU-AI

I would like to see most of the special forms currently in reader macros
merely be abbreviations for some form, since then it would not preclude
building a residential environment around common-lisp.

As for #,: Interlisp has three macros for constants:

(CONSTANT form). Returns the value of form available at compile time. 

(LOADTIMECONSTANT form). Returns the value of form as of load time.

(DEFERREDCONSTANT form). Returns the value of form as of first execution.

All of these merely return the value of "form" when interpreted. Some 
implementations of Interlisp don't support LOADTIMECONSTANT (the compiled-
code loader won't handle it) and those get turned into DEFERREDCONSTANT.

Larry


Date: 15-Nov-82 08:53:20-PST (Mon)
From: Kim.fateman@Berkeley
Subject: multiple thanks
Message-Id: <8210151653.22738@UCBVAX.BERKELEY.ARPA>
Received: by UCBVAX.BERKELEY.ARPA (3.227 [10/22/82])
	id A22720; 15-Nov-82 08:53:18-PST (Mon)
To: hedrick@rutgers
Cc: common-lisp@su-ai

Thanks for presenting a proposed mechanism for multiple values which seems
to penalize the producers of multiple values (and the implementors of 
lisp systems).  Yet,now there is this hidden cost in
using some m-v producers: should one use them, since in some
circumstances they have to do a fair amount of stack-grovelling?
(e.g. one might think that "floor" would always be fairly cheap to use).


Date: 14 Nov 1982 1827-EST
From: HEDRICK at RUTGERS
To: common-lisp at SU-AI
Subject: results of analyzing answers to my question about m.v.'s
Message-ID: <"MS10(2117)+GLXLIB1(1135)" 11871971621.32.19.89560 at RUTGERS>

Having started this discussion on multiple values, I feel some
responsibility to prevent it from going off into unnecessary directions.
What I was trying to do was to determine what was needed to implement
m.v.'s.  Moon's response, as well as a private interchange with Steele,
gave the information I needed.  Since other people seem to share my
original concerns, it seems worthwhile telling everybody the design I
have arrived at from this information. To be honest, I would prefer to
see a definition wherein an m.v. producer is an error unless there was
some m.v. receiver there to receive it. That is easy to implement.  But
I am now convinced that there are designs for implementing the existing
C.L. semantics without incurring unreasonable overheads on conventional
machines.

Let me approach this by successive approximation.

Stage I.  M.v. producer is called only when there is an m.v. receiver
to receive the value.

The Maclisp implementation will work here.  (VALUES A B C) simply saves
away the values of A, B, and C in some global places.  MV-LIST (or
anything else) just takes values from that global places and returns
them.  In most cases this mechanism would suffice taken alone. However
there are a couple of cases (MVPROG1 and MVCALL) where  multiple values
have to be saved while an arbitrary computation is done.  Thus it is
probably best for the values to be stored on a stack.  This will allow
for the possibility that m.v.'s can be done recursively.  The simplest
implementation is to push the number of m.v.'s on the top of the stack.
As long as every m.v. producer has an m.v. consumer, this implementation
should be sound.

Stage II.  The real case.

The problem is that the receiver may not call the producer directly.
Furthermore, we have no way of getting rid of m.v.'s if they are
produced erroneously, e.g.
   (multiple-value-list (values a b c) nil)
Thus I propose the following:

  - VALUES and VALUES-LIST will produce multiple values only if they
	know they are going to be used
  - we establish a protocol that allows us to follow the stack to
	see whether they are going to be used

The trickiest part is the second.  This is going to require some care
in the translator, but I claim that it is not that complex.  We have
three categories of calls:

  - calls where multiple values are required.  These are calls
	made by MV-LIST, MV-BIND, etc. (the m.v. consumers).  If the
	thing called would not normally produce m.v.'s, we need to
	convert the single normal value to a single m.v.
  - calls where multiple values are not allowed.  There are calls
	such as all but the last in a PROGN, where any m.v.'s are
	discarded.
  - calls where m.v.'s are returned if available, but are not required.
	I have it on good authority that the only case where this applies
	is terminal calls, i.e. the last call in a function (last being
	judged in execution, not lexically.  e.g. in
		(defun foo nil (cond (x (bar)) (t (baz]
	(bar) is a terminal call.

Let's ignore the third case for the moment.  All we need is some way to
mark calls so VALUES can tell whether m.v.'s are really going to be
used.  Clearly we want to mark the calls where m.v.'s are going to be
used, as opposed to those where m.v.'s are not going to be used, since
we want the overhead to be confined to users of m.v.'s. On the PDP-10
the obvious way to do this is to put a special instruction after the
call.  One way to do this is to put a particular no-op after each such
call. (Since the PDP-10 has several million kinds of no-ops, we can
afford to use one as a flag.)  Then VALUES would simply look up the
stack and see if its return address points to such a no-op.  As it
happens, we will probably do something a bit trickier.  We will probably
use a call to a routine MAKE-MV.  Thus a call done inside MV-LIST would
look like
  (MULTIPLE-VALUE-LIST (FOO) (BAR))
	CALL FOO	;m.v.'s not needed - nothing special
	CALL BAR	;m.v.'s needed - flag it with CALL MAKE-MV
	CALL MAKE-MV
	CALL MULTIPLE-VALUE-LIST ;do the actual return of the m.v.'s

The idea is that when we return from BAR, we will do a skip return if
we are actually returning multiple values (I will show how that happens
in a minute).  In that case the m.v.'s are left as is.  If we are not
returning m.v's, we do the normal return, and fall into the call to
MAKE-MV.  MAKE-MV is the routine that takes the conventional single
value and stores it away as a single multiple value.  Clearly this is
going to have to be done anyway when m.v.'s are needed, so we might as
well use CALL MAKE-MV as the flag that m.v.'s are required.

Now, we have two ways of implementing this, either of which is fairly
easy:

1) make sure that all terminal calls are compiled as jumps.  This is
a fairly standard optimization.  If done reliably, it guarantees that
the third case I ignored above will never occur.  VALUES will simply
be able to look at the place where it called directly, with no fancy
stack chasing.  If the return address points to CALL MAKE-MV,
VALUES puts the m.v.'s onto the mv stack, and takes the skip return.
Otherwise it returns the first of the m.v.'s, ignores the rest, and
does a conventional return.  If you choose this implementation, then
you will have to look at forms such as MVPROG1, which explicitly pass on
m.v.'s in contexts other than terminal calls.  They will have to
do calls that require m.v.'s, save those m.v.'s, and then themselves
return as VALUES (or any other m.v. producer) would do (i.e. looking
at their return address and throwing away the m.v.'s if they are not
required).

2. Have VALUES detect terminal calls, and simply follow the stack up
until something is found which is not a terminal call.  Otherwise
do things as in 1.  (That is, once you find something other than a
terminal call, look to see whether the return address there points to
MAKE-MV...)  If you choose this implementation there is a simple
modification for handling MVPROG1 and similar forms.  Add yet another
special mark (i.e. a no-op used only for this), call it MVFLAG.

   (mvprog1 (foo) (bar))
	call foo
	mvflag
	push returned value
	call bar
	pop returned value
	return

If somewhere inside FOO there is a call to VALUES, the stack search
will detect MVFLAG as the next instruction after the return address.
MVFLAG will be treated like a terminal call, i.e. the stack search
will continue to see whether the caller of the MVPROG1 really needed
the m.v.'s or not.  If so, they will be put on the m.v. stack, and
then the caller will retrieve them.  (The call to BAR will not be
pass on m.v.'s because of the POP after it.  This POP prevents the
next thing from being a RETURN, and thus prevents it from looking
like a terminal call.)

This mechanism has the advantage that if my informants are wrong, and
there is some context other than terminal calls that preserves m.v.'s,
we can handle it by putting MVFLAG there.

Both of the mechanisms suggested have only slight overhead, and that
overhead exists only if m.v.'s are used.  The extra no-op's are used
only in code compiled for m.v. receivers (or constructions such as
MVPROG1 that explicitly protect m.v.'s).  The m.v. producers need
only look up the stack to see what to do.  m.v.'s are never produced
if they are going to be thrown away.  I think that these mechanisms,
or something closely related, should work on machines other than the 
PDP-10.

I am not pleased with this sort of hackery, but it is no worse than
that needed to implement default arguments, &REST, and funarg's.
I would rather see Lisp free from this sort of thing, but I think I
have shown that it is possible to do with acceptable overhead and
no increased complexity in the compiler (except that you must be
able to detect terminal calls, something that all compilers known to
me do anyway).


None the less, I do not accept the argument that it is too late to
eliminate M.V.'s from Common Lisp, should people decide to do so.
Clearly the time to eliminate things is now.  We will be able to add
things later, but not to remove them.  But you should realize that
I am really a reactionary.  If it came to a vote, I would vote against
default arguments, &REST, and multiple values.
   --------


Date: Sunday, 14 November 1982  16:48-EST
From: Scott E. Fahlman <Fahlman at Cmu-20c>
To:   common-lisp at SU-AI
Subject: Multiple Values


All of these arguments about multiple values are interesting, possibly
valid, and should be kept in mind the next time we design a new Lisp
system.  It is too late for us to seriously consider any changes in the
fundamental function-calling mechanisms of Common Lisp unless it is
shown that the current mechanisms are fatally flawed -- not just
inelegant or slightly inefficient on some architectures.

-- Scott


Date: 14-Nov-82 11:54:06-PST (Sun)
From: UCBERNIE.jkf@Berkeley (John Foderaro)
Subject: m-v on conventional machines
Message-Id: <8210141954.22028@UCBERNIE.BERKELEY.ARPA>
Received: by UCBERNIE.BERKELEY.ARPA (3.227 [10/22/82])
	id A22021; 14-Nov-82 11:54:14-PST (Sun)
Received: from UCBERNIE.BERKELEY.ARPA by UCBVAX.BERKELEY.ARPA (3.227 [10/22/82])
	id A00135; 14-Nov-82 12:55:05-PST (Sun)
To: common-lisp@su-ai

  I too must disagree with Moon's statement that m-v's are free on
conventional machines if the user doesn't use them:

1) You must put a special mark on the stack for every tail recursive
   call, whether you plan to use m-v's or not.  This is not free on
   conventional machines, and tail recursive calls happen often.

2) Lisps on conventional machines often have a mode which permits rapid
   execution at the price of losing the ability to interpret the stack's
   contents.  Since a m-v return requires being able to go back on the
   stack to find a possible m-v-b, such rapid execution modes would
   have to be forbidden, causing grief to those users who don't care
   about m-v's.   The difficulty of interpreting the stack's contents
   on conventional machines is compounded by the fact that the operating
   system often dumps data on the stack (during interrupts for example) and
   your lisp system will have to make sure that it ignores those stack
   frames.  Also, if you run multiple languages inside your lisp, then
   you will have stack frames whose form you have no way of predicting in
   advance.


As an exercise in futility, I will express my feelings on what m-v's should
do:
  m-v's should be a protocol for passing multiple values from callee to
caller.   If the caller does a m-v call and the last thing executed before
returning to the caller does a values, then the values will be transfered
back.  All other cases are undefined!!!!!   Like everything else in lisp, if
the user does something illegal it is his own fault and the system may or
may not catch it (depending on how expensive the checks are on a given
machine).  In a lisp on a conventional machine, the best place to check for
things like this

(multiple-value-list (progn (values 'a 'b 'c) nil)) --> (nil b c)

is not at runtime, but at compile time (or by using a special program which
does extensive type analysis of the source code).  Thus, since the above
example is illegal, its result is undefined, and so (nil b c) is as good a
value as any to return.




Date: 14-Nov-82 11:54:06-PST (Sun)
From: UCBERNIE.jkf@Berkeley (John Foderaro)
Subject: m-v on conventional machines
Message-Id: <8210141954.22028@UCBERNIE.BERKELEY.ARPA>
Received: by UCBERNIE.BERKELEY.ARPA (3.227 [10/22/82])
	id A22021; 14-Nov-82 11:54:14-PST (Sun)
Received: from UCBERNIE.BERKELEY.ARPA by UCBVAX.BERKELEY.ARPA (3.227 [10/22/82])
	id A00135; 14-Nov-82 12:55:05-PST (Sun)
To: common-lisp@su-ai

  I too must disagree with Moon's statement that m-v's are free on
conventional machines if the user doesn't use them:

1) You must put a special mark on the stack for every tail recursive
   call, whether you plan to use m-v's or not.  This is not free on
   conventional machines, and tail recursive calls happen often.

2) Lisps on conventional machines often have a mode which permits rapid
   execution at the price of losing the ability to interpret the stack's
   contents.  Since a m-v return requires being able to go back on the
   stack to find a possible m-v-b, such rapid execution modes would
   have to be forbidden, causing grief to those users who don't care
   about m-v's.   The difficulty of interpreting the stack's contents
   on conventional machines is compounded by the fact that the operating
   system often dumps data on the stack (during interrupts for example) and
   your lisp system will have to make sure that it ignores those stack
   frames.  Also, if you run multiple languages inside your lisp, then
   you will have stack frames whose form you have no way of predicting in
   advance.


As an exercise in futility, I will express my feelings on what m-v's should
do:
  m-v's should be a protocol for passing multiple values from callee to
caller.   If the caller does a m-v call and the last thing executed before
returning to the caller does a values, then the values will be transfered
back.  All other cases are undefined!!!!!   Like everything else in lisp, if
the user does something illegal it is his own fault and the system may or
may not catch it (depending on how expensive the checks are on a given
machine).  In a lisp on a conventional machine, the best place to check for
things like this

(multiple-value-list (progn (values 'a 'b 'c) nil)) --> (nil b c)

is not at runtime, but at compile time (or by using a special program which
does extensive type analysis of the source code).  Thus, since the above
example is illegal, its result is undefined, and so (nil b c) is as good a
value as any to return.




Date: 14-Nov-82 09:42:03-PST (Sun)
From: Kim.fateman@Berkeley
Subject: Re:  multiple-value return
Message-Id: <8210141741.18720@UCBVAX.BERKELEY.ARPA>
Received: by UCBVAX.BERKELEY.ARPA (3.227 [10/22/82])
	id A18697; 14-Nov-82 09:41:16-PST (Sun)
To: Moon@SCRC-TENEX@MIT-MC
Cc: common-lisp@su-ai

	
	The constant overhead is zero in any reasonable implementation of multiple
	values.
We seem to have different ground rules here.

Unless you remove all m-v stuff at compile time, I do not see how you can
write a Lisp that has m-v, which is as fast as a good one without m-v.
Since one can demonstrate the impossibility of total run-time removal,
Lisps with m-v will be slower.  And I believe this is whether or not
m-v are used.

If you are arguing that CL, or any "reasonable implementation" of lisp
already pays the run-time cost, that is a different argument.
(E.g. it has been argued that spaghetti stacks are free in interlisp
  because the cost has already been paid when implementing other features;
  yet overall, interlisp speed suffers somewhat for this generality.)

In summary:

In Franz and probably other VAX Lisps,
compiled access to a value on a stack is implemented
as an addressing mode: PART of a SINGLE INSTRUCTION!  If you can show how
to check for multiple-valued-ness without the execution of a single
instruction or the use of any data space, in a language not otherwise
encumbered, I will believe it is free.  If it is not free, I suggest
alternatives and justification be considered.

Note, I am not arguing against conceptual simplicity; in fact I
brought up the divide function to make that point.  If it is decided
that conceptual simplicity is worth doubling the time to access
values some percent of the time, fine.


Date: 14 Nov 1982 1025-MST
From: Martin.Griss <Griss at UTAH-20>
Subject: Re: multiple-value return
To: Kim.fateman at UCB-C70
cc: Griss at UTAH-20, common-lisp at SU-AI
In-Reply-To: Your message of 13-Nov-82 2233-MST

I agree totally with Fateman; it seems these features are always added to support
some <1% code (if at all), that result in  alot of compiler hair just to
make the cost tolerable
-------


Date: Sunday, 14 November 1982, 02:52-EST
From: David A. Moon <Moon at SCRC-TENEX at MIT-MC>
Subject: multiple-value return
To: Kim.fateman at UCB-C70
Cc: common-lisp at su-ai
In-reply-to: <8210140532.2906@UCBVAX.BERKELEY.ARPA>

    Date: 13-Nov-82 21:33:35-PST (Sat)
    From: Kim.fateman@Berkeley

    It seems to me that the costs associated with doing this right can be
    absorbed as Moon suggests, in microcode, but I am not convinced that the
    costs can be easily borne in conventional machines.  Ordinarily a receiver
    of a value will not know whether it must extract the first item in a multiple
    value, or just use the non-multiple-value as given, unless some check
    is performed.

Too bad you didn't read my message, which said not that costs can be absorbed
in microcode, but that there is absolutely nothing about the Lisp machine
implementation of multiple values that is dependent on having microcode
(unlike other Lisp machine features, invisible pointers for instance).

    I believe that if conses/gc were really cheap,
    there would be much less benefit to m-v-r.
    e.g. divide could just return (quotient . remainder), other objects could
    be cons'd up  (or put in vectors ...)

You certainly provided a fine argument for having multiple values here.  Compare
the last sentence in your first paragraph.  If divide returns two values, and you
only want one, you don't have to extract the first item in a multiple value, you
simply accept the first value and ignore the rest.  But if divide returns a cons
of the quotient and the remainder, and you only want the quotient you do have to
pay the overhead of extracting the quotient from that cons.  Not only is there
run-time overhead, there is conceptual overhead since now the packaging of the
multiple values is visible to the user.

Of course divide isn't a good example, because it surely open-codes and hence
generates different code depending on the number of values you ask for.

    The constant overhead looking
    for m-v-r in, for example, macsyma, which does not, at the moment, 
    use m-v-r even once, would be distasteful. 

The constant overhead is zero in any reasonable implementation of multiple
values.


Date: 13-Nov-82 21:33:35-PST (Sat)
From: Kim.fateman@Berkeley
Subject: multiple-value return
Message-Id: <8210140532.2906@UCBVAX.BERKELEY.ARPA>
Received: by UCBVAX.BERKELEY.ARPA (3.227 [10/22/82])
	id A02900; 13-Nov-82 21:32:36-PST (Sat)
To: common-lisp@su-ai

It seems to me that the costs associated with doing this right can be
absorbed as Moon suggests, in microcode, but I am not convinced that the
costs can be easily borne in conventional machines.  Ordinarily a receiver
of a value will not know whether it must extract the first item in a multiple
value, or just use the non-multiple-value as given, unless some check
is performed.

What is the point of all this?  I see two points:  one: a minor convenience
for functions like divide (returning quotient and remainder), and its ilk
[its ilk growing extremely rapidly when hackers realize they can do this
free]; two: an important feature of a lisp where conses must be avoided.
Lisp Machines, esp. without garbage collectors, presumably benefit from the
avoidance of conses.  Lisps which must serve as system programming
languages (instead of using, say, C, which deals with call-by-reference
by the obvious kind of mechanism), is another possibility.

Let us turn the table a bit.  I believe that if conses/gc were really cheap,
there would be much less benefit to m-v-r.
e.g. divide could just return (quotient . remainder), other objects could
be cons'd up  (or put in vectors ...).  Now on conventional computers,
conses and gcs may not actually be so cheap, but if m-v-r is expensive,
perhaps conses WOULD be more acceptable? 

The constant overhead looking
for m-v-r in, for example, macsyma, which does not, at the moment, 
use m-v-r even once, would be distasteful. 

If m-v-r is free, of course, I suppose that's fine.  If it is not free,
perhaps it should be flushed from Common Lisp.


Date: 13-Nov-82 21:33:35-PST (Sat)
From: Kim.fateman@Berkeley
Subject: multiple-value return
Message-Id: <8210140532.2906@UCBVAX.BERKELEY.ARPA>
Received: by UCBVAX.BERKELEY.ARPA (3.227 [10/22/82])
	id A02900; 13-Nov-82 21:32:36-PST (Sat)
To: common-lisp@su-ai

It seems to me that the costs associated with doing this right can be
absorbed as Moon suggests, in microcode, but I am not convinced that the
costs can be easily borne in conventional machines.  Ordinarily a receiver
of a value will not know whether it must extract the first item in a multiple
value, or just use the non-multiple-value as given, unless some check
is performed.

What is the point of all this?  I see two points:  one: a minor convenience
for functions like divide (returning quotient and remainder), and its ilk
[its ilk growing extremely rapidly when hackers realize they can do this
free]; two: an important feature of a lisp where conses must be avoided.
Lisp Machines, esp. without garbage collectors, presumably benefit from the
avoidance of conses.  Lisps which must serve as system programming
languages (instead of using, say, C, which deals with call-by-reference
by the obvious kind of mechanism), is another possibility.

Let us turn the table a bit.  I believe that if conses/gc were really cheap,
there would be much less benefit to m-v-r.
e.g. divide could just return (quotient . remainder), other objects could
be cons'd up  (or put in vectors ...).  Now on conventional computers,
conses and gcs may not actually be so cheap, but if m-v-r is expensive,
perhaps conses WOULD be more acceptable? 

The constant overhead looking
for m-v-r in, for example, macsyma, which does not, at the moment, 
use m-v-r even once, would be distasteful. 

If m-v-r is free, of course, I suppose that's fine.  If it is not free,
perhaps it should be flushed from Common Lisp.


Date: Saturday, 13 November 1982, 22:42-EST
From: David A. Moon <Moon at SCRC-TENEX at MIT-MC>
Subject: implementing multiple values
To: Mgr DEC-20s/Dir LCSR Comp Facility <HEDRICK at RUTGERS>
Cc: common-lisp at SU-AI
In-reply-to: The message of 13 Nov 82 21:17-EST from Mgr DEC-20s/Dir LCSR Comp Facility <HEDRICK at RUTGERS>

    Date: 13 Nov 1982 2117-EST
    From: HEDRICK at RUTGERS (Mgr DEC-20s/Dir LCSR Comp Facility)

    E.g. consider the following example from Maclisp:
    (multiple-value-list (progn (values 'a 'b 'c) nil)) --> (nil b c)

Certainly the only sane and rational definition is that returning one
value by traditional Lisp and returning one value by using VALUES with
one argument must do the same thing.  The Maclisp implementation of
multiple values is broken; this is because it was kludged into an existing
implementation as a set of macros.

    It seems fairly clear that this should return either (nil) or (a b c).

The former.

    Probably the last two definitions are going to require that every
    value computation will interact with the m.v. mechanism, an overhead
    I would like to avoid.

Certainly.  But there is no run-time overhead, there is only the overhead of
making the interpreter and the compiler understand multiple values, rather
than kludging them in on top.

    (defun foo nil (values a b c))
    (defun bar nil (foo))
    (defun baz nil (multiple-value-list (bar]

(foo) and (bar) return the same 3 values, (baz) returns a list of them.

    (defun baz nil (multiple-value-list
		     (cond ((moon-phase) (foo))
			   (t  (trunc 5 2]

(baz) returns a different number of values depending on the predicate.

    (defun bar nil (cond ((moon-phase) (foo))
			 (t (trunc 5 2]
    (defun baz nil (multiple-value-list (bar]

This is the same as the previous example.

    (defun baz nil (multiple-value-list (progn (foo]

progn makes no difference.

    (defun baz nil (multiple-value-list (progn (foo) nil]

This returns a list of one element, NIL, of course.

You left out the only case that isn't obvious, namely

    (prog1 (foo) (bleagh))

I believe the current c.l. definition is that this returns one value, a,
and multiple-value-prog1 also exists and returns three values.


Maybe it would be instructive to look at how the Lisp machines (both of
them) implement multiple values.  Although these are machines specially
microcoded for Lisp, there is nothing microcode-dependent about this.
There is no extra overhead when multiple values are not being used.

When a function is called by a multiple value receiving form, a bit is
set somewhere in the stack frame.  This bit is in a place that gets
cleared for free when a function is called expecting only one value.
When a function is called tail-recursively, another bit is set.  When a
single value is returned from a function, these bits can be ignored.
When multiple values are returned, the microcode for that (and it could
just as well be a run-time support routine) follows back through
tail-recursive calls until it reaches the guy who is going to receive
the values, then checks his bit to see whether he wants multiple values.
If so, all the values are returned; if not, only the first value is
returned.

In practice there are some complexities about just where the values sit
while the stack is being unwound.  But these don't affect the semantics,
depend on implementation details, and in fact differ between the "A" and
"L" varieties of Lisp machines.  On a machine with enough general registers,
such as the pdp-10 or the VAX, you would probably put the values there.

Function-calling takes care of all cases of multiple values.  In the
interpreter, the function is always EVAL.  In compiled code, if the <form>
argument to MULTIPLE-VALUE or MULTIPLE-VALUE-BIND does not compile into
a function call, the compiler expands out the multiple value passing.
Thus (MULTIPLE-VALUE-BIND (A B C) (VALUES D E F) body) is just LET.


Date: Saturday, 13 November 1982, 22:42-EST
From: David A. Moon <Moon at SCRC-TENEX at MIT-MC>
Subject: implementing multiple values
To: Mgr DEC-20s/Dir LCSR Comp Facility <HEDRICK at RUTGERS>
Cc: common-lisp at SU-AI
In-reply-to: The message of 13 Nov 82 21:17-EST from Mgr DEC-20s/Dir LCSR Comp Facility <HEDRICK at RUTGERS>

    Date: 13 Nov 1982 2117-EST
    From: HEDRICK at RUTGERS (Mgr DEC-20s/Dir LCSR Comp Facility)

    E.g. consider the following example from Maclisp:
    (multiple-value-list (progn (values 'a 'b 'c) nil)) --> (nil b c)

Certainly the only sane and rational definition is that returning one
value by traditional Lisp and returning one value by using VALUES with
one argument must do the same thing.  The Maclisp implementation of
multiple values is broken; this is because it was kludged into an existing
implementation as a set of macros.

    It seems fairly clear that this should return either (nil) or (a b c).

The former.

    Probably the last two definitions are going to require that every
    value computation will interact with the m.v. mechanism, an overhead
    I would like to avoid.

Certainly.  But there is no run-time overhead, there is only the overhead of
making the interpreter and the compiler understand multiple values, rather
than kludging them in on top.

    (defun foo nil (values a b c))
    (defun bar nil (foo))
    (defun baz nil (multiple-value-list (bar]

(foo) and (bar) return the same 3 values, (baz) returns a list of them.

    (defun baz nil (multiple-value-list
		     (cond ((moon-phase) (foo))
			   (t  (trunc 5 2]

(baz) returns a different number of values depending on the predicate.

    (defun bar nil (cond ((moon-phase) (foo))
			 (t (trunc 5 2]
    (defun baz nil (multiple-value-list (bar]

This is the same as the previous example.

    (defun baz nil (multiple-value-list (progn (foo]

progn makes no difference.

    (defun baz nil (multiple-value-list (progn (foo) nil]

This returns a list of one element, NIL, of course.

You left out the only case that isn't obvious, namely

    (prog1 (foo) (bleagh))

I believe the current c.l. definition is that this returns one value, a,
and multiple-value-prog1 also exists and returns three values.


Maybe it would be instructive to look at how the Lisp machines (both of
them) implement multiple values.  Although these are machines specially
microcoded for Lisp, there is nothing microcode-dependent about this.
There is no extra overhead when multiple values are not being used.

When a function is called by a multiple value receiving form, a bit is
set somewhere in the stack frame.  This bit is in a place that gets
cleared for free when a function is called expecting only one value.
When a function is called tail-recursively, another bit is set.  When a
single value is returned from a function, these bits can be ignored.
When multiple values are returned, the microcode for that (and it could
just as well be a run-time support routine) follows back through
tail-recursive calls until it reaches the guy who is going to receive
the values, then checks his bit to see whether he wants multiple values.
If so, all the values are returned; if not, only the first value is
returned.

In practice there are some complexities about just where the values sit
while the stack is being unwound.  But these don't affect the semantics,
depend on implementation details, and in fact differ between the "A" and
"L" varieties of Lisp machines.  On a machine with enough general registers,
such as the pdp-10 or the VAX, you would probably put the values there.

Function-calling takes care of all cases of multiple values.  In the
interpreter, the function is always EVAL.  In compiled code, if the <form>
argument to MULTIPLE-VALUE or MULTIPLE-VALUE-BIND does not compile into
a function call, the compiler expands out the multiple value passing.
Thus (MULTIPLE-VALUE-BIND (A B C) (VALUES D E F) body) is just LET.


Date: 13 Nov 1982 2117-EST
From: HEDRICK at RUTGERS (Mgr DEC-20s/Dir LCSR Comp Facility)
Subject: implementing multiple values
To: common-lisp at SU-AI

We have gotten to the place where I have to actually implement multiple
values.  I find that I need to know a bit more about what the semantics
are, and what compromises are and are not acceptable.  What I would love
to hear is that I can use the Maclisp implementation.  It is certainly
the obvious approach for a conventional machine:  VALUES just saves away
its arguments in some global place (global variables - probably we would
use a separate stack - it doesn't much matter).  Then MULTIPLE-VALUE-xxx
simply retrieves them and makes them into a list, binds variables to
them, etc.  The problem turns out to be knowing when it is safe to use
those stored-away values. E.g. consider the following example from Maclisp:

(multiple-value-list (progn (values 'a 'b 'c) nil)) --> (nil b c)

It seems fairly clear that this should return either (nil) or (a b c).
This seems like a simple bug in the Maclisp implementation.  But it
does illustrate the kind of problems that are going to come up.
I do need to know exactly how long multiple values last.  Here are
the definitions I can see as being reasonable, with the ones I
prefer first (as you might guess, this is simply in order of how easy
they are to implement):

  - an m.v. receiver is only valid when the most recent value computed
	was computed by an m.v. producer.  Other cases are errors, and
	the results are undefined.
  - an m.v. receiver returns the most recent values produced by an
	m.v. producer.  Other non-multiple-values produced in the
	interim are ignored.
  - an m.v. receiver returns the most recent value computed, m.v. or
	otherwise.
  - like the last, except that some constructs "kill" multiple values
	and some do not.  If this definition is used, we need a list
	of the ones that do and don't.

Probably the last two definitions are going to require that every
value computation will interact with the m.v. mechanism, an overhead
I would like to avoid.  At least this is true if m.v.'s can be survive
function returns.  Consider the following example:

    (defun foo nil (bar) 'success)

Since (BAR) may return multiple values, even something as simple as
'SUCCESS is going to have to explicitly do something to make sure that
any multiple values returned by BAR are no longer active.  Either that
or

   (defun foo nil (bar))

is going to have to do something explicit to make sure that if (BAR)
happens to return multiple values, they get returned.

In any case, I need a precise definition.  Can somebody help? The
following cases are given just to spark your thoughts, not to relieve
Guy of the need to give a  precise specification. Please assume that
functions stay defined until they are explicitly redefined.

1.

(defun foo nil (values a b c))
(defun bar nil (foo))
(defun baz nil (multiple-value-list (bar]

2.

(defun baz nil (multiple-value-list
		 (cond ((moon-phase) (foo))
		       (t  (trunc 5 2]

3.

(defun bar nil (cond ((moon-phase) (foo))
		     (t (trunc 5 2]
(defun baz nil (multiple-value-list (bar]

4.

(defun baz nil (multiple-value-list (progn (foo]

5.

(defun baz nil (multiple-value-list (progn (foo) nil]



-------


Date: 13 Nov 1982 2117-EST
From: HEDRICK at RUTGERS (Mgr DEC-20s/Dir LCSR Comp Facility)
Subject: implementing multiple values
To: common-lisp at SU-AI

We have gotten to the place where I have to actually implement multiple
values.  I find that I need to know a bit more about what the semantics
are, and what compromises are and are not acceptable.  What I would love
to hear is that I can use the Maclisp implementation.  It is certainly
the obvious approach for a conventional machine:  VALUES just saves away
its arguments in some global place (global variables - probably we would
use a separate stack - it doesn't much matter).  Then MULTIPLE-VALUE-xxx
simply retrieves them and makes them into a list, binds variables to
them, etc.  The problem turns out to be knowing when it is safe to use
those stored-away values. E.g. consider the following example from Maclisp:

(multiple-value-list (progn (values 'a 'b 'c) nil)) --> (nil b c)

It seems fairly clear that this should return either (nil) or (a b c).
This seems like a simple bug in the Maclisp implementation.  But it
does illustrate the kind of problems that are going to come up.
I do need to know exactly how long multiple values last.  Here are
the definitions I can see as being reasonable, with the ones I
prefer first (as you might guess, this is simply in order of how easy
they are to implement):

  - an m.v. receiver is only valid when the most recent value computed
	was computed by an m.v. producer.  Other cases are errors, and
	the results are undefined.
  - an m.v. receiver returns the most recent values produced by an
	m.v. producer.  Other non-multiple-values produced in the
	interim are ignored.
  - an m.v. receiver returns the most recent value computed, m.v. or
	otherwise.
  - like the last, except that some constructs "kill" multiple values
	and some do not.  If this definition is used, we need a list
	of the ones that do and don't.

Probably the last two definitions are going to require that every
value computation will interact with the m.v. mechanism, an overhead
I would like to avoid.  At least this is true if m.v.'s can be survive
function returns.  Consider the following example:

    (defun foo nil (bar) 'success)

Since (BAR) may return multiple values, even something as simple as
'SUCCESS is going to have to explicitly do something to make sure that
any multiple values returned by BAR are no longer active.  Either that
or

   (defun foo nil (bar))

is going to have to do something explicit to make sure that if (BAR)
happens to return multiple values, they get returned.

In any case, I need a precise definition.  Can somebody help? The
following cases are given just to spark your thoughts, not to relieve
Guy of the need to give a  precise specification. Please assume that
functions stay defined until they are explicitly redefined.

1.

(defun foo nil (values a b c))
(defun bar nil (foo))
(defun baz nil (multiple-value-list (bar]

2.

(defun baz nil (multiple-value-list
		 (cond ((moon-phase) (foo))
		       (t  (trunc 5 2]

3.

(defun bar nil (cond ((moon-phase) (foo))
		     (t (trunc 5 2]
(defun baz nil (multiple-value-list (bar]

4.

(defun baz nil (multiple-value-list (progn (foo]

5.

(defun baz nil (multiple-value-list (progn (foo) nil]



-------


Date: Saturday, 13 November 1982, 18:11-EST
From: David A. Moon <Moon at SCRC-TENEX at MIT-MC>
Subject: Re: Named lambdas
To: Common-Lisp at SU-AI
In-reply-to: The message of 13 Nov 82 13:40-EST from JONL at PARC-MAXC

    Date: 13 NOV 1982 1040-PST
    From: JONL at PARC-MAXC

    Why not eliminate another proliferation of mindless
    primitives, NAMED-LAMBDA, and just have DEFUN etc insert
    a "commentary" in a local declaration.

This is a good idea, provided that there is a primitive defined to
extract the name buried in the declaration buried in the lambda.  It's
called SYS:FUNCTION-NAME in the Lisp machine; no really strong reason
why it isn't global.

If the Lisp machine LOCAL-DECLARATIONS mechanism were adopted, this would
also answer the other request for a way for macros to find out what function
they were inside, since they would do (CADR (ASSQ 'NAME LOCAL-DECLARATIONS)),
mutatis mutandis.


Date: 13 NOV 1982 1148-PST
From: JONL at PARC-MAXC
Subject: Re: Named lambdas
To:   Fahlman at CMU-20C
cc:   common-lisp at SU-AI, JONL

In response to your message sent  Saturday, 13 November 1982  14:27-EST

Sorry for not making it more clear -- SI:DEFEXPR was just a
meta-name intended to imply it's action.


Date: Saturday, 13 November 1982  14:27-EST
From: Scott E. Fahlman <Fahlman at Cmu-20c>
To:   JONL at PARC-MAXC
Cc:   common-lisp at SU-AI
Subject: Named lambdas
In-reply-to: The message of 13 Nov 1982  13:40-EST from JONL at PARC-MAXC


The SI:DEFEXPR business confused me for awhile, but your basic
suggestion of hiding the name of the function in a declaration looks
good.  This would eliminate any need for NAMED-LAMBDA.  It might be
worthwhile to create a standard declaration form ("NAME" or
"FUNCTION-NAME" looks OK to me) to hold this sort of thing and explain
what it's for.  We already have the machinery to ignore declarations, so
this should add minimal new hair to any implementation.

-- Scott


Date: 13 NOV 1982 1040-PST
From: JONL at PARC-MAXC
Subject: Re: Named lambdas
To:   Fahlman at CMU-20C, Masinter
cc:   common-lisp at SU-AI, JONL

In response to the message sent  Thursday, 11 November 1982  11:54-EST from Fahlman@Cmu-20c

I thought so.  Why not eliminate another proliferation of mindless
primitives, NAMED-LAMBDA, and just have DEFUN etc insert
a "commentary" in a local declaration.  For example,
    (DEFUN FOO (X) (LIST X))
becomes something like
    (SI:DEFEXPR 'FOO '(LAMBDA (X) (DECLARE (NAME FOO)) (LIST X)))

This "DECLARE" syntax is Interlisp's and MacLisp's, but no
objection to this way of nameing should be entertained on
the basis of local declaration syntax.


Date: 13 November 1982 05:32-EST
From: Kent M. Pitman <KMP at MIT-MC>
Subject:  #,
To: Killian at MIT-MULTICS
cc: common-lisp at SU-AI



Date: Saturday, 13 November 1982, 04:16-EST
From: David A. Moon <Moon at SCRC-TENEX at MIT-MC>
Subject: #,
To: Earl A. Killian <Killian at MIT-MULTICS>
Cc: common-lisp at SU-AI
In-reply-to: The message of 12 Nov 82 13:21-EST from Earl A. Killian <Killian at MIT-MULTICS>

    Date:     12 November 1982 1021-pst
    From:     Earl A. Killian            <Killian at MIT-MULTICS>

    Shouldn't #, be a reader abbreviations for some form just like ' is?
    Otherwise, how do you have a macro that uses the load-time-eval facility
    for constructed code?

We use (CONS COMPILER:EVAL-AT-LOAD-TIME-MARKER form) for this.  There is
absolutely nothing special or good about the name (other than that it is
better than calling it SQUID).  Speaking of primitives, Common Lisp also
prevents the user from writing the #, macro himself by not providing a way
to tell whether you are reading normally, or reading forms to be compiled
into a file that will later be loaded into another environment.


Date: 13 Nov 1982 0054-EST
From: STEELE at CMU-20C
Subject: Revised evaluators
To: common-lisp at SU-AI

The enclosed two revised evaluators include changes for the following
bugs noted by Bawden:
(1) EVALHOOK was incorrectly hooking on the given form; it should only
hook on subforms.  To this end %EVAL was split into two parts %EVAL
and %EVAL1.
(2) Two ocurrences of LEXP in%LAMBDA-APPLY-1 should have been NEWFN.
(3) The PROG macro was failing to call MACROEXPAND when looking for
declarations.

Also, %VARBIND and %LAMBDA-APPLY-1 were changed, and a new function
%ADD-SPECIALS introduced, to fix a bug in the handling of SPECIAL
declarations.  One wants
	(DEFUN BLAG (X)
	  (DECLARE (SPECIAL *BARF*))
	  ...)
to cause *BARF* to be special in the body of BLAG even though BLAG does
not bind *BARF*.  The new evaluators should fix this problem.
--Guy
-------------------------------------------------------------
;;; This evaluator splits the lexical environment into four
;;; logically distinct entities:
;;;	VENV = lexical variable environment
;;;	FENV = lexical function and macro environment
;;;	BENV = block name environment
;;;	GENV = go tag environment
;;; Each environment is an a-list.  It is never the case that
;;; one can grow and another shrink simultaneously; the four
;;; parts could be united into a single a-list.  The four-part
;;; division saves consing and search time.
;;;
;;; Each entry in VENV has one of two forms: (VAR VALUE) or (VAR).
;;; The first indicates a lexical binding of VAR to VALUE, and the
;;; second indicates a special binding of VAR (implying that the
;;; special value should be used).
;;;
;;; Each entry in FENV looks like (NAME TYPE . FN), where NAME is the
;;; functional name, TYPE is either FUNCTION or MACRO, and FN is the
;;; function or macro-expansion function, respectively.  Entries of
;;; type FUNCTION are made by FLET and LABELS; those of type MACRO
;;; are made by MACROLET.
;;;
;;; Each entry in BENV looks like (NAME), where NAME is the name
;;; of the block.  The cons cell that is the entry is used as a
;;; catch tag for implementing RETURN-FROM.  If the entry has been
;;; clobbered to look like (NAME . INVALID), then the block has
;;; been exited, and a return to that block is an error.
;;;
;;; Each entry in GENV looks like (TAG MARKER . BODY), where TAG is
;;; a go tag, MARKER is a unique cons used as a catch tag, and BODY
;;; is the statement sequence that follows the go tag.  If the car of
;;; MARKER, normally NIL, has been clobbered to be INVALID, then
;;; the tag body has been exited, and a GO to that tag is an error.

;;; An interpreted-lexical-closure contains a function (normally a
;;; lambda-expression) and the lexical environment.

(defstruct interpreted-lexical-closure function venv fenv benv genv)


;;; The EVALHOOK feature allows a user-supplied function to be called
;;; whenever a form is to be evaluated.  The presence of the lexical
;;; environment requires an extension of the feature as it is defined
;;; in MacLISP.  Here, the user hook function must accept not only
;;; the form to be evaluated, but also the components of the lexical
;;; environment; these must then be passed verbatim to EVALHOOK or
;;; *EVAL in order to perform the evaluation of the form correctly.
;;; The precise number of components should perhaps be allowed to be
;;; implementation-dependent, so it is probably best to require the
;;; user hook function to accept arguments as (FORM &REST ENV) and
;;; then to perform evaluation by (APPLY #'EVALHOOK FORM HOOKFN ENV),
;;; for example.

(defvar *evalhook* nil)

(defun evalhook (exp hookfn venv fenv benv genv)
  (let ((*evalhook* hookfn)) (%eval1 exp venv fenv benv genv)))

(defun eval (exp)
  (*eval exp nil nil nil nil))

;;; *EVAL looks useless here, but does more complex things
;;; in alternative implementations of this evaluator.

(defun *eval (exp venv fenv benv genv)
  (%eval exp venv fenv benv genv))
!
;;; Function names beginning with "%" are intended to be internal
;;; and not defined in the Common LISP white pages.

;;; %EVAL is the main evaluation function.  It is split into two
;;; parts, with the main part called %EVAL1, for the benefit of EVALHOOK.

(defun %eval (exp venv fenv benv genv)
  (if *evalhook*
      (let ((hookfn *evalhook*) (*evalhook* nil))
	(funcall hookfn exp venv fenv benv genv))
      (t (%eval1 exp venv fenv benv genv))))

(defun %eval1 (exp venv fenv benv genv)
  (typecase exp
    ;; A symbol is first looked up in the lexical variable environment.
    (symbol (let ((slot (assq exp venv)))
	      (cond ((and slot (not (null (cdr slot))))
		     (cadr slot))
		    ((boundp exp) (symbol-value exp))
		    (t (cerror :unbound-variable
			       "The symbol ~S has no value"
			       exp)))))
    ;; Numbers, strings, bit-vectors, and characters self-evaluate.
    ((or number string bit-vector character) exp)
    ;; Conses require elaborate treatment based on the car.
    (cons (typecase (car exp)
	    ;; A symbol is first looked up in the lexical function environment.
	    ;; This lookup is cheap if the environment is empty, a common case.
	    (symbol
	     (let ((fn (car exp)))
	       (loop (let ((slot (assq fn fenv)))
		       (unless (null slot)
			 (return (case (cadr slot)
				   (macro (%eval (%macroexpand
						  (cddr slot)
						  (if (eq fn (car exp))
						      exp
						      (cons fn (cdr exp))))))
				   (function (%apply (cddr slot)
						     (%evlis (cdr exp) venv fenv benv genv)
						     venv fenv benv genv))
				   (t <implementation-error>)))))
		     ;; If not in lexical function environment,
		     ;;  try the definition cell of the symbol.
		     (when (fboundp fn)
		       (return (cond ((special-form-p fn)
				      (%invoke-special-form
				       fn (cdr exp) venv fenv benv genv))
				     ((macro-p fn)
				      (%eval (%macroexpand
					      (get-macro-function (symbol-function fn))
					      (if (eq fn (car exp))
						  exp
						  (cons fn (cdr exp))))
					     venv fenv benv genv))
				     (t (%apply (symbol-function fn)
						(%evlis (cdr exp) venv fenv benv genv)
						venv fenv benv genv)))))
		     (setq fn
			   (cerror :undefined-function
				   "The symbol ~S has no function definition"
				   fn))
		     (unless (symbolp fn)
		       (return (%apply fn
				       (%evlis (cdr exp) venv fenv benv genv)
				       venv fenv benv genv))))))
	    ;; A cons in function position must be a lambda-expression.
	    ;; Note that the construction of a lexical closure is avoided here.
	    (cons (%apply (car exp)
			  (%evlis (cdr exp) venv fenv benv genv)
			  venv fenv benv genv))
	    (t (%eval (cerror :invalid-form
			      "Cannot evaluate the form ~S: function position has invalid type ~S"
			      exp (type-of (car exp)))
		      venv fenv benv genv))))
    (t (%eval (cerror :invalid-form
		      "Cannot evaluate the form ~S: invalid type ~S"
		      exp (type-of exp))
	      venv fenv benv genv))))
!
;;; Given a list of forms, evaluate each and return a list of results.

(defun %evlis (forms venv fenv benv genv)
  (mapcar #'(lambda (form) (%eval form venv fenv benv genv)) forms))

;;; Given a list of forms, evaluate each, discarding the results of
;;; all but the last, and returning all results from the last.

(defun %evprogn (body venv fenv benv genv)
  (if (endp body) nil
      (do ((b body (cdr b)))
	  ((endp (cdr b))
	   (%eval (car b) venv fenv benv genv))
	(%eval (car b) venv fenv benv genv))))

;;; APPLY takes a function, a number of single arguments, and finally
;;; a list of all remaining arguments.  The following song and dance
;;; attempts to construct efficiently a list of all the arguments.

(defun apply (fn firstarg &rest args*)
  (%apply fn
	  (cond ((null args*) firstarg)
		((null (cdr args*)) (cons firstarg (car args*)))
		(t (do ((x args* (cdr x))
			(z (cddr args*) (cdr z)))
		       ((null z)
			(rplacd x (cadr x))
			(cons firstarg (car args*))))))
	  nil nil nil nil))
!
;;; %APPLY does the real work of applying a function to a list of arguments.
;;; The environment is passed in because it leads to more natural error
;;; recovery.

(defun %apply (fn args venv fenv benv genv)
  (typecase fn
    ;; For a compiled function, an implementation-dependent "spread"
    ;;  operation and invocation is required.
    (compiled-function (%invoke-compiled-function fn args))
    ;; The same goes for a compiled closure over lexical variables.
    (compiled-lexical-closure (%invoke-compiled-lexical-closure fn args))
    ;; The treatment of interpreted lexical closures is elucidated fully here.
    (interpreted-lexical-closure
     (%lambda-apply (interpreted-lexical-closure-function fn)
		    args
		    (interpreted-lexical-closure-venv fn)
		    (interpreted-lexical-closure-fenv fn)
		    (interpreted-lexical-closure-benv fn)
		    (interpreted-lexical-closure-genv fn)))
    ;; For a symbol, the function definition is used, if it is a function.
    (symbol (%apply (cond ((not (fboundp fn))
			   (cerror :undefined-function
				   "The symbol ~S has no function definition"
				   fn))
			  ((special-form-p fn)
			   (cerror :invalid-function
				   "The symbol ~S cannot be applied: it names a special form"
				   fn))
			  ((macro-p fn)
			   (cerror :invalid-function
				   "The symbol ~S cannot be applied: it names a macro"
				   fn))
			  (t (symbol-function fn)))
		    args venv fenv benv genv))
    (cons (if (eq (car fn) 'lambda)
	      (%lambda-apply fn args venv fenv benv genv)
	      (%apply (cerror :invalid-function
			      "~S is not a valid function"
			      fn)
		      args venv fenv benv genv)))
    (t (%apply (cerror :invalid function
		       "~S has an invalid type ~S for a function"
		       fn (type-of fn))
	       args venv fenv benv genv))))
!
;;; %LAMBDA-APPLY is the hairy part, that takes care of applying
;;; a lambda-expression in a given lexical environment to given
;;; arguments.  The complexity arises primarily from the processing
;;; of the parameter list.
;;;
;;; If at any point the lambda-expression is found to be malformed
;;; (typically because of an invalid parameter list), or if the list
;;; of arguments is not suitable for the lambda-expression, a correctable
;;; error is signalled; correction causes a throw to be performed to
;;; the tag %LAMBDA-APPLY-RETRY, passing back a (possibly new)
;;; lambda-expression and a (possibly new) list of arguments.
;;; The application is then retried.  If the new lambda-expression
;;; is not really a lambda-expression, then %APPLY is used instead of
;;; %LAMBDA-APPLY.
;;;
;;; In this evaluator, PROGV is used to instantiate variable bindings
;;; (though its use is embedded with a macro called %varbind).
;;; The throw that precedes a retry will cause special bindings to
;;; be popped before the retry.

(defun %lambda-apply (lexp args venv fenv benv genv)
  (multiple-value-bind (newfn newargs)
		       (catch '%lambda-apply-retry
			 (return-from %lambda-apply
			   (%lambda-apply-1 lexp args venv fenv benv genv)))
    (if (and (consp newfn) (eq (car newfn) 'lambda))
	(%lambda-apply newfn newargs venv fenv benv genv)
	(%apply newfn newargs venv fenv benv genv))))

;;; Calling this function will unwind all special variables
;;; and cause FN to be applied to ARGS in the original lexical
;;; and dynamic environment in force when %LAMBDA-APPLY was called.

(defun %lambda-apply-retry (fn args)
  (throw '%lambda-apply-retry (values fn args)))

;;; This function is convenient when the lambda expression is found
;;; to be malformed.  REASON should be a string explaining the problem.

(defun %bad-lambda-exp (lexp oldargs reason)
  (%lambda-apply-retry
   (cerror :invalid-function
	   "Improperly formed lambda-expression ~S: ~A"
	   lexp reason)
   oldargs))

;;; (%varbind VAR VALUE . BODY) evaluates VAR to produce a symbol name
;;; and VALUE to produce a value.  If VAR is determined to have been
;;; declared special (as indicated by the current binding of the variable
;;; SPECIALS, which should be a list of symbols, or by a SPECIAL property),
;;; then a special binding is established using PROGV.  Otherwise an
;;; entry is pushed onto the a-list presumed to be in the variable VENV.

;;; The CONSTANTP test ideally is true for any constant symbol;
;;; it should at least check for T, NIL, and keywords.

(defmacro %varbind (var value &body body)
  (let ((xvar (gensym)) (xvalue (gensym)))
    `(let ((,xvar ,var) (,xvalue ,value))
       (loop (when (not (constantp ,xvar)) (return))
	     (setq ,xvar (cerror :invalid-variable
				 "~S is a constant and may not be bound"
				 ,xvar)))
       (let ((specp (or (memq ,xvar specials) (get ,xvar 'special))))
	 (progv (and specp (list ,xvar)) (and specp (list ,xvalue))
		(unless specp (push (list ,xvar ,xvalue) venv))
		,@body)))))

;;; %LAMBDA-KEYWORD-P is true iff X (which must be a symbol)
;;; has a name beginning with an ampersand.

(defun %lambda-keyword-p (x)
  (char= #\& (char 0 (symbol-pname x))))
!
;;; %LAMBDA-APPLY-1 is responsible for verifying that LEXP is
;;; a lambda-expression, for extracting a list of all variables
;;; declared SPECIAL in DECLARE forms, and for finding the
;;; body that follows any DECLARE forms.

(defun %lambda-apply-1 (lexp args venv fenv benv genv)
  (cond ((or (not (consp lexp))
	     (not (eq (car lexp) 'lambda))
	     (atom (cdr lexp))
	     (not (listp (cadr lexp))))
	 (%bad-lambda-exp lexp args "improper lambda-expression"))
	(t (do ((body (cddr lexp) (cdr body))
		(specials '()))
	       ((or (endp body) (not (consp (car body))))
		(%bind-required lexp args (cadr lexp)
				(%add-specials venv specials)
				fenv benv genv args specials nil body))
	     (let ((form (macroexpand (car body))))
	       (cond ((or (not (consp form))
			  (not (eq (car form) 'declare)))
		      (return (%bind-required lexp args (cadr lexp)
					      (%add-specials venv specials)
					      fenv benv genv args specials form body)))
		     (t (dolist (decl (cdar form))
			  (when (eq (car decl) 'special)
			    (setq specials
				  (if (null specials)	;Avoid consing
				      (cdar decl)
				      (append (cdar decl) specials))))))))))))

;;; %ADD-SPECIALS adds entries to VENV to account for SPECIAL declarations.

(defun %add-specials (venv specials)
  (do ((s specials (cdr s))
       (v venv (cons (list (car s)) v)))
      ((endp s) v)))

;;; %BIND-REQUIRED handles the pairing of arguments to required parameters.
;;; Error checking is performed for too few or too many arguments.
;;; If a lambda-list keyword is found, %TRY-OPTIONAL is called.
;;; Here, as elsewhere, if the binding process terminates satisfactorily
;;; then the body is evaluated using %EVPROGN in the newly constructed
;;; dynamic and lexical environment.

(defun %bind-required (lexp oldargs varlist venv fenv benv genv args specials form body)
  (cond ((endp varlist)
	 (if (null args)
	     (%lambda-evprogn form body venv fenv benv genv)
	     (%lambda-apply-retry lexp
				  (cerror :too-many-arguments
					  "Too many arguments for function ~S: ~S"
					  lexp oldargs))))
	((not (symbolp (car varlist)))
	 (%bad-lambda-exp lexp oldargs "required parameter name not a symbol"))
	((%lambda-keyword-p (car varlist))
	 (%try-optional lexp oldargs varlist venv fenv benv genv args specials form body))
	((null args)
	 (%lambda-apply-retry lexp 
			      (cerror :too-few-arguments
				      "Too few arguments for function ~S: ~S"
				      lexp oldargs)))
	(t (%varbind (car varlist) (car args)
		      (%bind-required lexp oldargs (cdr varlist) venv fenv benv genv (cdr args) specials form body)))))
!
;;; %TRY-OPTIONAL determines whether the lambda-list keyword &OPTIONAL
;;; has been found.  If so, optional parameters are processed; if not,
;;; the buck is passed to %TRY-REST.

(defun %try-optional (lexp oldargs varlist venv fenv benv genv args specials form body)
  (cond ((eq (car varlist) '&optional)
	 (%bind-optional lexp oldargs (cdr varlist) venv fenv benv genv args specials form body))
	(t (%try-rest lexp oldargs varlist venv fenv benv genv args specials form body))))

;;; %BIND-OPTIONAL determines whether the parameter list is exhausted.
;;; If not, it parses the next specifier.

(defun %bind-optional (lexp oldargs varlist venv fenv benv genv args specials form body)
  (cond ((endp varlist)
	 (if (null args)
	     (%lambda-evprogn form body venv fenv benv genv)
	     (%lambda-apply-retry lexp
				  (cerror :too-many-arguments
					  "Too many arguments for function ~S: ~S"
					  lexp oldargs))))
	(t (let ((varspec (car varlist)))
	     (cond ((symbolp varspec)
		    (if (%lambda-keyword-p varspec)
			(%try-rest lexp oldargs varlist venv fenv benv genv args specials form body)
			(%process-optional lexp oldargs varlist venv fenv benv
					   genv args specials form body varspec nil nil)))
		   ((and (consp varspec)
			 (symbolp (car varspec))
			 (listp (cdr varspec))
			 (or (endp (cddr varspec))
			     (and (symbolp (caddr varspec))
				  (not (endp (caddr varspec)))
				  (endp (cdddr varspec)))))
		    (%process-optional lexp oldargs varlist venv fenv benv
				       genv args specials form body
				       (car varspec)
				       (cadr varspec)
				       (caddr varspec)))
		   (t (%bad-lambda-exp lexp oldargs "malformed optional parameter specifier")))))))

;;; %PROCESS-OPTIONAL takes care of binding the parameter,
;;; and also the supplied-p variable, if any.

(defun %process-optional (lexp oldargs varlist venv fenv benv genv args specials form body var init varp)
  (let ((value (if (null args) (%eval init venv fenv benv genv) (car args))))
    (%varbind var value
      (if varp
	  (%varbind varp (not (null args))
	    (%bind-optional lexp oldargs (cdr varlist) venv fenv benv genv (cdr args) specials form body))
	  (%bind-optional lexp oldargs (cdr varlist) venv fenv benv genv (cdr args) specials form body)))))
!
;;; %TRY-REST determines whether the lambda-list keyword &REST
;;; has been found.  If so, the rest parameter is processed;
;;; if not, the buck is passed to %TRY-KEY, after a check for
;;; too many arguments.

(defun %try-rest (lexp oldargs varlist venv fenv benv genv args specials form body)
  (cond ((eq (car varlist) '&rest)
	 (%bind-rest lexp oldargs (cdr varlist) venv fenv benv genv args specials form body))
	((and (not (eq (car varlist) '&key))
	      (not (null args)))
	 (%lambda-apply-retry lexp
			      (cerror :too-many-arguments
				      "Too many arguments for function ~S: ~S"
				      lexp oldargs)))
	(t (%try-key lexp oldargs varlist venv fenv benv genv args specials form body))))

;;; %BIND-REST ensures that there is a parameter specifier for
;;; the &REST parameter, binds it, and then evaluates the body or
;;; calls %TRY-KEY.

(defun %bind-rest (lexp oldargs varlist venv fenv benv genv args specials form body)
  (cond ((or (endp varlist)
	     (not (symbolp (car varlist))))
	 (%bad-lambda-exp lexp oldargs "missing rest parameter specifier"))
	(t (%varbind (car varlist) args
	     (cond ((endp (cdr varlist))
		    (%lambda-evprogn form body venv fenv benv genv))
		   ((and (symbolp (cadr varlist))
			 (%lambda-keyword-p (cadr varlist)))
		    (%try-key lexp oldargs (cdr varlist) venv fenv benv genv args specials form body))
		   (t (%bad-lambda-exp lexp oldargs "malformed after rest parameter specifier")))))))
!
;;; %TRY-KEY determines whether the lambda-list keyword &KEY
;;; has been found.  If so, keyword parameters are processed;
;;; if not, the buck is passed to %TRY-AUX.

(defun %try-key (lexp oldargs varlist venv fenv benv genv args specials form body)
  (cond ((eq (car varlist) '&key)
	 (%bind-key lexp oldargs (cdr varlist) venv fenv benv genv args specials form body nil))
	(t (%try-aux lexp oldargs varlist venv fenv benv genv specials form body))))

;;; %BIND-KEY determines whether the parameter list is exhausted.
;;; If not, it parses the next specifier.

(defun %bind-key (lexp oldargs varlist venv fenv benv genv args specials form body keys)
  (cond ((endp varlist)
	 (%check-for-bad-keywords lexp args keys)
	 (%lambda-evprogn form body venv fenv benv genv))
	(t (let ((varspec (car varlist)))
	     (cond ((symbolp varspec)
		    (if (%lambda-keyword-p varspec)
			(cond ((not (eq varspec '&allow-other-keywords))
			       (%check-for-bad-keywords lexp args keys)
			       (%try-aux lexp oldargs varlist venv fenv benv genv specials form body))
			      ((endp (cdr varlist))
			       (%lambda-evprogn form body venv fenv benv genv))
			      ((%lambda-keyword-p (cadr varlist))
			       (%try-aux lexp oldargs (cdr varlist) venv fenv benv genv specials form body))
			      (t (%bad-lambda-exp lexp oldargs "invalid after &ALLOW-OTHER-KEYWORDS")))
			(%process-key lexp oldargs varlist venv fenv benv
				      genv args specials form body keys
				      (intern (symbol-print-name varspec) keyword-package)
				      varspec nil nil)))
		   ((and (consp varspec)
			 (or (symbolp (car varspec))
			     (and (consp (car varspec))
				  (consp (cdar varspec))
				  (symbolp (cadar varspec))
				  (endp (cddar varspec))))
			 (listp (cdr varspec))
			 (or (endp (cddr varspec))
			     (and (symbolp (caddr varspec))
				  (not (endp (caddr varspec)))
				  (endp (cdddr varspec)))))
		    (%process-key lexp oldargs varlist venv fenv benv
				  genv args specials form body keys
				  (if (consp (car varspec))
				      (caar varspec)
				      (intern (symbol-print-name (car varspec)) keyword-package))
				  (if (consp (car varspec))
				      (cadar varspec)
				      (car varspec))
				  (cadr varspec)
				  (caddr varspec)))
		   (t (%bad-lambda-exp lexp oldargs "malformed keyword parameter specifier")))))))

;;; Optional error check for bad keyword arguments.

(defun %check-for-bad-keywords (lexp args keys)
  (do ((a args (cddr a)))
      ((endp args))
    (unless (memq (car a) keys)
      (cerror :unexpected-keyword
	      "Keyword not expected by function ~S: ~S"
	      lexp (car a)))))

;;; %PROCESS-KEY takes care of binding the parameter,
;;; and also the supplied-p variable, if any.

(defun %process-key (lexp oldargs varlist venv fenv benv genv args specials form body keys kwd var init varp)
  (do ((a args (cddr a)))
      ((endp a)
       (%process-key-1 lexp oldargs varlist venv fenv benv genv args specials
		       form body keys kwd var init varp
		       (%eval init venv fenv benv genv) nil))
    (when (eq (car a) kwd)
      (return (%process-key-1 lexp oldargs varlist venv fenv benv genv args specials
			      form body keys kwd var init varp
			      (cadr a) t)))))

(defun %process-key-1 (lexp oldargs varlist venv fenv benv genv args specials form body keys kwd var init varp value suppliedp)
  (%varbind var value
    (if varp
	(%varbind varp suppliedp
	  (%bind-key lexp oldargs varlist venv fenv benv genv args specials form body (cons kwd keys)))
	(%bind-key lexp oldargs varlist venv fenv benv genv args specials form body (cons kwd keys)))))
!
;;; %TRY-AUX determines whether the keyword &AUX
;;; has been found.  If so, auxiliary variables are processed;
;;; if not, an error is signalled.

(defun %try-aux (lexp oldargs varlist venv fenv benv genv specials form body)
  (cond ((eq (car varlist) '&aux)
	 (%bind-aux lexp oldargs (cdr varlist) venv fenv benv genv specials form body))
	(t (%bad-lambda-exp lexp oldargs "unknown or misplaced lambda-list keyword"))))

;;; %BIND-AUX determines whether the parameter list is exhausted.
;;; If not, it parses the next specifier.

(defun %bind-aux (lexp oldargs varlist venv fenv benv genv specials form body)
  (cond ((endp varlist)
	 (%lambda-evprogn form body venv fenv benv genv))
	(t (let ((varspec (car varlist)))
	     (cond ((symbolp varspec)
		    (if (%lambda-keyword-p varspec)
			(%bad-lambda-exp lexp oldargs "unknown or misplaced lambda-list keyword")
			(%process-aux lexp oldargs varlist venv fenv benv
				      genv specials form body varspec nil)))
		   ((and (consp varspec)
			 (symbolp (car varspec))
			 (listp (cdr varspec))
			 (endp (cddr varspec)))
		    (%process-aux lexp oldargs varlist venv fenv benv
				       genv specials form body
				       (car varspec)
				       (cadr varspec)))
		   (t (%bad-lambda-exp lexp oldargs "malformed aux variable specifier")))))))

;;; %PROCESS-AUX takes care of binding the auxiliary variable.

(defun %process-aux (lexp oldargs varlist venv fenv benv genv specials form body var init)
  (%varbind var (and init (%eval init venv fenv benv genv))
    (%bind-aux lexp oldargs varlist venv fenv benv genv specials form body)))

(defun %lambda-evprogn (form body venv fenv benv genv)
  (unless (null form) (%eval form venv fenv benv genv))
  (%evprogn body venv fenv benv genv))
!
;;; Definitions for various special forms and macros.

(defspec quote (obj) (venv fenv benv genv) obj)

(defspec function (fn) (venv fenv benv genv)
  (loop (cond ((consp fn)
	       (cond ((eq (car fn) 'lambda)
		      (return (make-interpreted-closure :function fn
							:venv venv
							:fenv fenv
							:benv benv
							:genv genv)))
		     (t (setq fn (cerror :invalid-function
					 "~S is not a valid argument for FUNCTION"
					 fn)))))
	      ((symbolp fn)
	       (let ((slot (assq fn fenv)))
		 (cond (slot
			(case (cadr slot)
			  (macro (setq fn (cerror :invalid-function
						  "The name ~S is invalid for FUNCTION: it names a macro"
						  fn)))
			  (function (return (cddr slot)))
			  (t <implementation-error>)))
		       ((fboundp fn)
			(cond ((special-form-p fn)
			       (setq fn (cerror :invalid-function
						"The symbol ~S is invalid for FUNCTION: it names a special form"
						fn)))
			      ((macro-p fn)
			       (setq fn (cerror :invalid-function
						"The symbol ~S is invalid for FUNCTION: it names a macro"
						fn)))
			      (t (setq fn (symbol-function fn)))))
		       (t (setq fn (cerror :invalid-function
					   "The symbol ~S has no function definition"
					   fn))))))
	      (t (setq fn (cerror :invalid-function
				  "~S is not a valid argument for FUNCTION"
				  fn))))))

(defspec if (pred con &optional alt) (venv fenv benv genv)
  (if (%eval pred venv fenv benv genv)
      (%eval con venv fenv benv genv)
      (%eval alt venv fenv benv genv)))

;;; The BLOCK construct provides a PROGN with a named contour around it.
;;; It is interpreted by first putting an entry onto BENV, consisting
;;; of a 1-list of the name.  This list cell serves as a catch tag.
;;; Then the body is executed.
;;; If a RETURN-FROM is interpreted, a throw occurs.  If the BLOCK
;;; construct is exited for any reason (including falling off the end, which
;;; returns the results of evaluating the last form in the body), the cdr of
;;; the entry is clobbered to be INVALID, to indicate that that particular
;;; entry is no longer valid for RETURN-FROM.

(defspec block (name &body body) (venv fenv benv genv)
  (let ((slot (list name)))
    (unwind-protect (catch slot
		      (%evprogn body venv fenv (cons slot benv) genv))
		    (rplacd slot 'invalid))))

(defspec return (form) (venv fenv benv genv)
  (let ((slot (assq nil benv)))
    (cond ((null slot) (ferror ???<unseen-block-name>))
	  ((eq (cdr slot) 'invalid) (ferror ???<block-name-no-longer-valid>))
	  (t (throw slot (%eval form venv fenv benv genv))))))

(defspec return-from (name form) (venv fenv benv genv)
  (let ((slot (assq name benv)))
    (cond ((null slot) (ferror ???<unseen-block-name>))
	  ((eq (cdr slot) 'invalid) (ferror ???<block-name-no-longer-valid>))
	  (t (throw slot (%eval form venv fenv benv genv))))))
!
(defmacro prog (vars &rest body)
  (do ((b body (cdr b))
       (decls '() (cons (car b) decls)))
      ((or (endp b)
	   (atom (car b))
	   (let ((x (macroexpand (car b))))
	     (or (atom x) (not (eq (car x) 'declare)))))
       `(let ,vars ,@(nreverse decls) (block nil (tagbody ,@b))))))

;;; The TAGBODY construct provides a body with GO tags in it.
;;; It is interpreted by first putting one entry onto GENV for
;;; every tag in the body; doing this ahead of time saves searching
;;; at GO time.  A unique cons whose car is NIL is constructed for
;;; use as a unique catch tag.  Then the body is executed.
;;; If a GO is interpreted, a throw occurs, sending as the thrown
;;; value the point in the body after the relevant tag.
;;; If the TAGBODY construct is exited for any reason (including
;;; falling off the end, which produces the value NIL), the car of
;;; the unique marker is clobbered to be INVALID, to indicate that
;;; tags associated with that marker are no longer valid.

(defspec tagbody (&rest body) (venv fenv benv genv)
  (do ((b body (cdr b))
       (marker (list nil)))
      ((endp p)
       (block exit
	 (unwind-protect
	  (loop (setq body
		      (catch marker
			(do ((b body (cdr b)))
			    ((endp b) (return-from exit nil))
			  (unless (atom (car b))
			    (%eval (car b) venv fenv benv genv))))))
	  (rplaca marker 'invalid))))
    (when (atom (car b))
      (push (list* (car b) marker (cdr b)) genv))))

(defspec go (tag) (venv fenv benv genv)
  (let ((slot (assq tag genv)))
    (cond ((null slot) (ferror ???<unseen-go-tag>))
	  ((eq (caadr slot) 'invalid) (ferror ???<go-tag-no-longer-valid>))
	  (t (throw (cadr slot) (cddr slot))))))
-------------------------------------------------------------
;;; This version uses some special variables to avoid passing stuff around.

;;; This evaluator splits the lexical environment into four
;;; logically distinct entities:
;;;	VENV = lexical variable environment
;;;	FENV = lexical function and macro environment
;;;	BENV = block name environment
;;;	GENV = go tag environment
;;; Each environment is an a-list.  It is never the case that
;;; one can grow and another shrink simultaneously; the four
;;; parts could be united into a single a-list.  The four-part
;;; division saves consing and search time.
;;;
;;; In this implementation, the four environment parts are normally
;;; kept in four special variables %VENV%, %FENV%, %BENV%, and %GENV%.
;;; (These are internal to the implementation, and are not meant to
;;; be user-accessible.)

(defvar %venv% nil)
(defvar %fenv% nil)
(defvar %benv% nil)
(defvar %genv% nil)

;;; Each entry in VENV has one of two forms: (VAR VALUE) or (VAR).
;;; The first indicates a lexical binding of VAR to VALUE, and the
;;; second indicates a special binding of VAR (implying that the
;;; special value should be used).
;;;
;;; Each entry in FENV looks like (NAME TYPE . FN), where NAME is the
;;; functional name, TYPE is either FUNCTION or MACRO, and FN is the
;;; function or macro-expansion function, respectively.  Entries of
;;; type FUNCTION are made by FLET and LABELS; those of type MACRO
;;; are made by MACROLET.
;;;
;;; Each entry in BENV looks like (NAME), where NAME is the name
;;; of the block.  The cons cell that is the entry is used as a
;;; catch tag for implementing RETURN-FROM.  If the entry has been
;;; clobbered to look like (NAME . INVALID), then the block has
;;; been exited, and a return to that block is an error.
;;;
;;; Each entry in GENV looks like (TAG MARKER . BODY), where TAG is
;;; a go tag, MARKER is a unique cons used as a catch tag, and BODY
;;; is the statement sequence that follows the go tag.  If the car of
;;; MARKER, normally NIL, has been clobbered to be INVALID, then
;;; the tag body has been exited, and a go to that tag is an error.

;;; An interpreted-lexical-closure contains a function (normally a
;;; lambda-expression) and the lexical environment.

(defstruct interpreted-lexical-closure function venv fenv benv genv)


;;; The EVALHOOK feature allows a user-supplied function to be called
;;; whenever a form is to be evaluated.  The presence of the lexical
;;; environment requires an extension of the feature as it is defined
;;; in MacLISP.  Here, the user hook function must accept not only
;;; the form to be evaluated, but also the components of the lexical
;;; environment; these must then be passed verbatim to EVALHOOK or
;;; *EVAL in order to perform the evaluation of the form correctly.
;;; The precise number of components should perhaps be allowed to be
;;; implementation-dependent, so it is probably best to require the
;;; user hook function to accept arguments as (FORM &REST ENV) and
;;; then to perform evaluation by (APPLY #'EVALHOOK FORM HOOKFN ENV),
;;; for example.

(defvar *evalhook* nil)

(defun evalhook (exp hookfn %venv% %fenv% %benv% %genv%)
  (let ((*evalhook* hookfn))
	(%eval1 exp)))

(defun eval (exp)
  (*eval exp nil nil nil nil))

(defun *eval (exp %venv% %fenv% %benv% %genv%)
  (%eval exp))
!
;;; Function names beginning with "%" are intended to be internal
;;; and not defined in the Common LISP white pages.

;;; %EVAL is the main evaluation function.  It is split into two
;;; parts, with the main part called %EVAL1, for the benefit of EVALHOOK.
;;; It evaluates EXP in the current lexical environment, assumed to be
;;; in %VENV%, %FENV%, %BENV%, and %GENV%.

(defun %eval (exp)
  (if *evalhook*
      (let ((hookfn *evalhook*) (*evalhook* nil))
	(funcall hookfn exp %venv% %fenv% %benv% %genv%))
      (t (%eval1 exp))))

(defun %eval1 (exp)
  (typecase exp
    ;; A symbol is first looked up in the lexical variable environment.
    (symbol (let ((slot (assq exp %venv%)))
	      (cond ((and slot (not (null (cdr slot))))
		     (cadr slot))
		    ((boundp exp) (symbol-value exp))
		    (t (cerror :unbound-variable
			       "The symbol ~S has no value"
			       exp)))))
    ;; Numbers, strings, bit-vectors, and characters self-evaluate.
    ((or number string bit-vector character) exp)
    ;; Conses require elaborate treatment based on the car.
    (cons (typecase (car exp)
	    ;; A symbol is first looked up in the lexical function environment.
	    ;; This lookup is cheap if the environment is empty, a common case.
	    (symbol
	     (let ((fn (car exp)))
	       (loop (let ((slot (assq fn %fenv%)))
		       (unless (null slot)
			 (return (case (cadr slot)
				   (macro (%eval (%macroexpand
						  (cddr slot)
						  (if (eq fn (car exp))
						      exp
						      (cons fn (cdr exp))))))
				   (function (%apply (cddr slot)
						     (%evlis (cdr exp))))
				   (t <implementation-error>)))))
		     ;; If not in lexical function environment,
		     ;;  try the definition cell of the symbol.
		     (when (fboundp fn)
		       (return (cond ((special-form-p fn)
				      (%invoke-special-form fn (cdr exp)))
				     ((macro-p fn)
				      (%eval (%macroexpand
					      (get-macro-function (symbol-function fn))
					      (if (eq fn (car exp))
						  exp
						  (cons fn (cdr exp))))))
				     (t (%apply (symbol-function fn)
						(%evlis (cdr exp)))))))
		     (setq fn
			   (cerror :undefined-function
				   "The symbol ~S has no function definition"
				   fn))
		     (unless (symbolp fn)
		       (return (%apply fn (%evlis (cdr exp))))))))
	    ;; A cons in function position must be a lambda-expression.
	    ;; Note that the construction of a lexical closure is avoided here.
	    (cons (apply (car exp) (%evlis (cdr exp))))
	    (t (%eval (cerror :invalid-form
			      "Cannot evaluate the form ~S: function position has invalid type ~S"
			      exp (type-of (car exp)))))))
    (t (%eval (cerror :invalid-form
		      "Cannot evaluate the form ~S: invalid type ~S"
		      exp (type-of exp))))))
!
;;; Given a list of forms, evaluate each and return a list of results.

(defun %evlis (forms)
  (mapcar #'(lambda (form) (%eval form)) forms))

;;; Given a list of forms, evaluate each, discarding the results of
;;; all but the last, and returning all results from the last.

(defun %evprogn (body)
  (if (endp body) nil
      (do ((b body (cdr b)))
	  ((endp (cdr b))
	   (%eval (car b)))
	(%eval (car b)))))

;;; APPLY takes a function, a number of single arguments, and finally
;;; a list of all remaining arguments.  The following song and dance
;;; attempts to construct efficiently a list of all the arguments.

(defun apply (fn firstarg &rest args*)
  (let ((%venv% nil) (%fenv% nil) (%benv% nil) (%genv% nil))
    (%apply fn
	    (cond ((null args*) firstarg)
		  ((null (cdr args*)) (cons firstarg (car args*)))
		  (t (do ((x args* (cdr x))
			  (z (cddr args*) (cdr z)))
			 ((null z)
			  (rplacd x (cadr x))
			  (cons firstarg (car args*)))))))))
!
;;; %APPLY does the real work of applying a function to a list of arguments.

(defun %apply (fn args)
  (typecase fn
    ;; For a compiled function, an implementation-dependent "spread"
    ;;  operation and invocation is required.
    (compiled-function (%invoke-compiled-function fn args))
    ;; The same goes for a compiled closure over lexical variables.
    (compiled-lexical-closure (%invoke-compiled-lexical-closure fn args))
    ;; The treatment of interpreted lexical closures is elucidated fully here.
    (interpreted-lexical-closure
     (let ((%venv% (interpreted-lexical-closure-venv fn))
	   (%fenv% (interpreted-lexical-closure-fenv fn))
	   (%benv% (interpreted-lexical-closure-benv fn))
	   (%genv% (interpreted-lexical-closure-genv fn)))
       (%lambda-apply (interpreted-lexical-closure-function fn) args)))
    ;; For a symbol, the function definition is used, if it is a function.
    (symbol (%apply (cond ((not (fboundp fn))
			   (cerror :undefined-function
				   "The symbol ~S has no function definition"
				   fn))
			  ((special-form-p fn)
			   (cerror :invalid-function
				   "The symbol ~S cannot be applied: it names a special form"
				   fn))
			  ((macro-p fn)
			   (cerror :invalid-function
				   "The symbol ~S cannot be applied: it names a macro"
				   fn))
			  (t (symbol-function fn)))
		    args))
    (cons (if (eq (car fn) 'lambda)
	      (%lambda-apply fn args)
	      (%apply (cerror :invalid-function
			      "~S is not a valid function"
			      fn)
		      args)))
    (t (%apply (cerror :invalid function
		       "~S has an invalid type ~S for a function"
		       fn (type-of fn))
	       args))))
!
;;; %LAMBDA-APPLY is the hairy part, that takes care of applying
;;; a lambda-expression in a given lexical environment to given
;;; arguments.  The complexity arises primarily from the processing
;;; of the parameter list.
;;;
;;; If at any point the lambda-expression is found to be malformed
;;; (typically because of an invalid parameter list), or if the list
;;; of arguments is not suitable for the lambda-expression, a correctable
;;; error is signalled; correction causes a throw to be performed to
;;; the tag %LAMBDA-APPLY-RETRY, passing back a (possibly new)
;;; lambda-expression and a (possibly new) list of arguments.
;;; The application is then retried.  If the new lambda-expression
;;; is not really a lambda-expression, then %APPLY is used instead of
;;; %LAMBDA-APPLY.
;;;
;;; In this evaluator, PROGV is used to instantiate variable bindings
;;; (though its use is embedded with a macro called %varbind).
;;; The throw that precedes a retry will cause special bindings to
;;; be popped before the retry.

(defun %lambda-apply (lexp args)
  (multiple-value-bind (newfn newargs)
		       (catch '%lambda-apply-retry
			 (return-from %lambda-apply
			   (let ((%venv% %venv%))
			     (%lambda-apply-1 lexp args))))
    (if (and (consp newfn) (eq (car newfn) 'lambda))
	(%lambda-apply newfn newargs)
	(%apply newfn newargs))))

;;; Calling this function will unwind all special variables
;;; and cause FN to be applied to ARGS in the original lexical
;;; and dynamic environment in force when %LAMBDA-APPLY was called.

(defun %lambda-apply-retry (fn args)
  (throw '%lambda-apply-retry (values fn args)))

(defvar %lexp%)
(defvar %oldargs%)

;;; This function is convenient when the lambda expression is found
;;; to be malformed.  REASON should be a string explaining the problem.

(defun %bad-lambda-exp (reason)
  (%lambda-apply-retry
   (cerror :invalid-function
	   "Improperly formed lambda-expression ~S: ~A"
	   %lexp% reason)
   %oldargs%))

;;; (%varbind VAR VALUE . BODY) evaluates VAR to produce a symbol name
;;; and VALUE to produce a value.  If VAR is determined to have been
;;; declared special (as indicated by the current binding of the variable
;;; SPECIALS, which should be a list of symbols, or by a SPECIAL property),
;;; then a special binding is established using PROGV.  Otherwise an
;;; entry is pushed onto the a-list presumed to be in the variable VENV.

;;; The CONSTANTP test ideally is true for any constant symbol;
;;; it should at least check for T, NIL, and keywords.

(defmacro %varbind (var value &body body)
  (let ((xvar (gensym)) (xvalue (gensym)))
    `(let ((,xvar ,var) (,xvalue ,value))
       (loop (when (not (constantp ,xvar)) (return))
	     (setq ,xvar (cerror :invalid-variable
				 "~S is a constant and may not be bound"
				 ,xvar)))
       (let ((specp (or (memq ,xvar %specials%) (get ,xvar 'special))))
	 (progv (and specp (list ,xvar)) (and specp (list ,xvalue))
		(unless specp (push (list ,xvar ,xvalue) venv))
		,@body)))))

;;; %LAMBDA-KEYWORD-P is true iff X (which must be a symbol)
;;; has a name beginning with an ampersand.

(defun %lambda-keyword-p (x)
  (char= #\& (char 0 (symbol-pname x))))
!
;;; %LAMBDA-APPLY-1 is responsible for verifying that LEXP is
;;; a lambda-expression, for extracting a list of all variables
;;; declared SPECIAL in DECLARE forms, and for finding the
;;; body that follows any DECLARE forms.

(defvar %specials%)
(defvar %form%)
(defvar %body%)

(defun %lambda-apply-1 (%lexp% %oldargs%)
  (cond ((or (not (consp %lexp%))
	     (not (eq (car %lexp%) 'lambda))
	     (atom (cdr %lexp%))
	     (not (listp (cadr %lexp%))))
	 (%bad-lambda-exp "improper lambda-expression"))
	(t (do ((%body% (cddr %lexp%) (cdr %body%))
		(%specials% '()))
	       ((or (endp %body%)
		    (not (listp (car %body%))))
		(let ((%form% nil))
		  (%add-specials)
		  (%bind-required (cadr %lexp%) %oldargs%)))
	     (let ((%form% (macroexpand (car %body%))))
	       (cond ((or (not (consp %form%))
			  (not (eq (car %form%) 'declare)))
		      (%add-specials)
		      (return (%bind-required (cadr %lexp%) %oldargs%)))
		     (t (dolist (decl (cdr %form%))
			  (when (eq (car decl) 'special)
			    (setq %specials%
				  (if (null %specials%)	;Avoid consing
				      (cdar decl)
				      (append (cdar decl) %specials%))))))))))))

;;; %ADD-SPECIALS adds entries to VENV to account for SPECIAL declarations.

(defun %add-specials ()
  (dolist (s %specials%)
    (push (list s) %venv%)))

;;; %BIND-REQUIRED handles the pairing of arguments to required parameters.
;;; Error checking is performed for too few or too many arguments.
;;; If a lambda-list keyword is found, %TRY-OPTIONAL is called.
;;; Here, as elsewhere, if the binding process terminates satisfactorily
;;; then the body is evaluated using %EVPROGN in the newly constructed
;;; dynamic and lexical environment.

(defun %bind-required (varlist args)
  (cond ((endp varlist)
	 (if (null args)
	     (%lambda-evprogn%)
	     (%lambda-apply-retry lexp
				  (cerror :too-many-arguments
					  "Too many arguments for function ~S: ~S"
					  %lexp% %oldargs%))))
	((not (symbolp (car varlist)))
	 (%bad-lambda-exp "required parameter name not a symbol"))
	((%lambda-keyword-p (car varlist))
	 (%try-optional varlist args))
	((null args)
	 (%lambda-apply-retry lexp 
			      (cerror :too-few-arguments
				      "Too few arguments for function ~S: ~S"
				      %lexp% %oldargs%)))
	  (t (%varbind (car varlist) (car args)
			(%bind-required (cdr varlist) (cdr args))))))
!
;;; %TRY-OPTIONAL determines whether the lambda-list keyword &OPTIONAL
;;; has been found.  If so, optional parameters are processed; if not,
;;; the buck is passed to %TRY-REST.

(defun %try-optional (varlist args)
  (cond ((eq (car varlist) '&optional)
	 (%bind-optional (cdr varlist) args))
	(t (%try-rest varlist args))))

;;; %BIND-OPTIONAL determines whether the parameter list is exhausted.
;;; If not, it parses the next specifier.

(defun %bind-optional (varlist args)
  (cond ((endp varlist)
	 (if (null args)
	     (%lambda-evprogn%)
	     (%lambda-apply-retry lexp
				  (cerror :too-many-arguments
					  "Too many arguments for function ~S: ~S"
					  %lexp% %oldargs%))))
	(t (let ((varspec (car varlist)))
	     (cond ((symbolp varspec)
		    (if (%lambda-keyword-p varspec)
			(%try-rest varlist args)
			(%process-optional varlist args varspec nil nil)))
		   ((and (consp varspec)
			 (symbolp (car varspec))
			 (listp (cdr varspec))
			 (or (endp (cddr varspec))
			     (and (symbolp (caddr varspec))
				  (not (endp (caddr varspec)))
				  (endp (cdddr varspec)))))
		    (%process-optional varlist args
				       (car varspec)
				       (cadr varspec)
				       (caddr varspec)))
		   (t (%bad-lambda-exp "malformed optional parameter specifier")))))))

;;; %PROCESS-OPTIONAL takes care of binding the parameter,
;;; and also the supplied-p variable, if any.

(defun %process-optional (varlist args var init varp)
  (let ((value (if (null args) (%eval init) (car args))))
    (%varbind var value
      (if varp
	  (%varbind varp (not (null args))
	    (%bind-optional (cdr varlist) (cdr args)))
	  (%bind-optional (cdr varlist) (cdr args))))))
!
;;; %TRY-REST determines whether the lambda-list keyword &REST
;;; has been found.  If so, the rest parameter is processed;
;;; if not, the buck is passed to %TRY-KEY, after a check for
;;; too many arguments.

(defun %try-rest (varlist args)
  (cond ((eq (car varlist) '&rest)
	 (%bind-rest (cdr varlist) args))
	((and (not (eq (car varlist) '&key))
	      (not (null args)))
	 (%lambda-apply-retry lexp
			      (cerror :too-many-arguments
				      "Too many arguments for function ~S: ~S"
				      %lexp% %oldargs%)))
	(t (%try-key varlist args))))

;;; %BIND-REST ensures that there is a parameter specifier for
;;; the &REST parameter, binds it, and then evaluates the body or
;;; calls %TRY-KEY.

(defun %bind-rest (varlist args)
  (cond ((or (endp varlist)
	     (not (symbolp (car varlist))))
	 (%bad-lambda-exp "missing rest parameter specifier"))
	(t (%varbind (car varlist) args
	     (cond ((endp (cdr varlist))
		    (%lambda-evprogn%))
		   ((and (symbolp (cadr varlist))
			 (%lambda-keyword-p (cadr varlist)))
		    (%try-key (cdr varlist) args))
		   (t (%bad-lambda-exp "malformed after rest parameter specifier")))))))
!
;;; %TRY-KEY determines whether the lambda-list keyword &KEY
;;; has been found.  If so, keyword parameters are processed;
;;; if not, the buck is passed to %TRY-AUX.

(defun %try-key (varlist args)
  (cond ((eq (car varlist) '&key)
	 (%bind-key (cdr varlist) args nil))
	(t (%try-aux varlist))))

;;; %BIND-KEY determines whether the parameter list is exhausted.
;;; If not, it parses the next specifier.

(defun %bind-key (varlist args keys)
  (cond ((endp varlist)
	 (%check-for-bad-keywords args keys)
	 (%lambda-evprogn%))
	(t (let ((varspec (car varlist)))
	     (cond ((symbolp varspec)
		    (if (%lambda-keyword-p varspec)
			(cond ((not (eq varspec '&allow-other-keywords))
			       (%check-for-bad-keywords args keys)
			       (%try-aux varlist))
			      ((endp (cdr varlist))
			       (%lambda-evprogn%))
			      ((%lambda-keyword-p (cadr varlist))
			       (%try-aux (cdr varlist)))
			      (t (%bad-lambda-exp "invalid after &ALLOW-OTHER-KEYWORDS")))
			(%process-key varlist args keys
				      (intern (symbol-print-name varspec) keyword-package)
				      varspec nil nil)))
		   ((and (consp varspec)
			 (or (symbolp (car varspec))
			     (and (consp (car varspec))
				  (consp (cdar varspec))
				  (symbolp (cadar varspec))
				  (endp (cddar varspec))))
			 (listp (cdr varspec))
			 (or (endp (cddr varspec))
			     (and (symbolp (caddr varspec))
				  (not (endp (caddr varspec)))
				  (endp (cdddr varspec)))))
		    (%process-key varlist args keys
				  (if (consp (car varspec))
				      (caar varspec)
				      (intern (symbol-print-name (car varspec)) keyword-package))
				  (if (consp (car varspec))
				      (cadar varspec)
				      (car varspec))
				  (cadr varspec)
				  (caddr varspec)))
		   (t (%bad-lambda-exp "malformed keyword parameter specifier")))))))

;;; Optional error check for bad keywords.

(defun %check-for-bad-keywords (args keys)
  (do ((a args (cddr a)))
      ((endp args))
    (unless (memq (car a) keys)
      (cerror :unexpected-keyword
	      "Keyword not expected by function ~S: ~S"
	      %lexp% (car a)))))

;;; %PROCESS-KEY takes care of binding the parameter,
;;; and also the supplied-p variable, if any.

(defun %process-key (varlist args keys kwd var init varp)
  (do ((a args (cddr a)))
      ((endp a)
       (%process-key-1 varlist args keys kwd var init varp (%eval init) nil))
    (when (eq (car a) kwd)
      (return (%process-key-1 varlist args keys kwd var init varp (cadr a) t)))))

(defun %process-key-1 (varlist args keys kwd var init varp value suppliedp)
  (%varbind var value
    (if varp
	(%varbind varp suppliedp
	  (%bind-key varlist args (cons kwd keys)))
	(%bind-key varlist args (cons kwd keys)))))
!
;;; %TRY-AUX determines whether the keyword &AUX
;;; has been found.  If so, auxiliary variables are processed;
;;; if not, an error is signalled.

(defun %try-aux (varlist)
  (cond ((eq (car varlist) '&aux)
	 (%bind-aux (cdr varlist)))
	(t (%bad-lambda-exp "unknown or misplaced lambda-list keyword"))))

;;; %BIND-AUX determines whether the parameter list is exhausted.
;;; If not, it parses the next specifier.

(defun %bind-aux (varlist)
  (cond ((endp varlist)
	 (%lambda-evprogn%))
	(t (let ((varspec (car varlist)))
	     (cond ((symbolp varspec)
		    (if (%lambda-keyword-p varspec)
			(%bad-lambda-exp "unknown or misplaced lambda-list keyword")
			(%process-aux varlist varspec nil)))
		   ((and (consp varspec)
			 (symbolp (car varspec))
			 (listp (cdr varspec))
			 (endp (cddr varspec)))
		    (%process-aux varlist (car varspec) (cadr varspec)))
		   (t (%bad-lambda-exp "malformed aux variable specifier")))))))

;;; %PROCESS-AUX takes care of binding the auxiliary variable.

(defun %process-aux (varlist var init)
    (%varbind var (and init (%eval init))
       (%bind-aux varlist)))

(defun %lambda-evprogn ()
  (unless (null %form%) (%eval %form%))
  (%evprogn %body%))
!
;;; Definitions for various special forms and macros.

(defspec quote (obj) obj)

(defspec function (fn)
  (loop (cond ((consp fn)
	       (cond ((eq (car fn) 'lambda)
		      (return (make-interpreted-closure :function fn
							:venv %venv%
							:fenv %fenv%
							:benv %benv%
							:genv %genv%)))
		     (t (setq fn (cerror :invalid-function
					 "~S is not a valid argument for FUNCTION"
					 fn)))))
	      ((symbolp fn)
	       (let ((slot (assq fn fenv)))
		 (cond (slot
			(case (cadr slot)
			  (macro (setq fn (cerror :invalid-function
						  "The name ~S is invalid for FUNCTION: it names a macro"
						  fn)))
			  (function (return (cddr slot)))
			  (t <implementation-error>)))
		       ((fboundp fn)
			(cond ((special-form-p fn)
			       (setq fn (cerror :invalid-function
						"The symbol ~S is invalid for FUNCTION: it names a special form"
						fn)))
			      ((macro-p fn)
			       (setq fn (cerror :invalid-function
						"The symbol ~S is invalid for FUNCTION: it names a macro"
						fn)))
			      (t (setq fn (symbol-function fn)))))
		       (t (setq fn (cerror :invalid-function
					   "The symbol ~S has no function definition"
					   fn))))))
	      (t (setq fn (cerror :invalid-function
				  "~S is not a valid argument for FUNCTION"
				  fn))))))

(defspec if (pred con &optional alt)
  (if (%eval pred) (%eval con) (%eval alt)))

;;; The BLOCK construct provides a PROGN with a named contour around it.
;;; It is interpreted by first putting an entry onto BENV, consisting
;;; of a 1-list of the name.  This list cell serves as a catch tag.
;;; Then the body is executed.
;;; If a RETURN-FROM is interpreted, a throw occurs.  If the BLOCK
;;; construct is exited for any reason (including falling off the end, which
;;; returns the results of evaluating the last form in the body), the cdr of
;;; the entry is clobbered to be INVALID, to indicate that that particular
;;; entry is no longer valid for RETURN-FROM.

(defspec block (name &body body)
  (let ((slot (list name)))
    (unwind-protect (catch slot
		      (let ((%benv% (cons slot %benv%)))
			(%evprogn body)))
		    (rplaca (cdr slot) 'invalid))))

(defspec return (form)
  (let ((slot (assq nil %benv%)))
    (cond ((null slot) (ferror ???<unseen-block-name>))
	  ((eq (cdr slot) 'invalid) (ferror ???<block-name-no-longer-valid>))
	  (t (throw slot (%eval form))))))

(defspec return-from (name form)
  (let ((slot (assq name %benv%)))
    (cond ((null slot) (ferror ???<unseen-block-name>))
	  ((eq (cdr slot) 'invalid) (ferror ???<block-name-no-longer-valid>))
	  (t (throw slot (%eval form))))))
!
(defmacro prog (vars &rest body)
  (do ((b body (cdr b))
       (decls '() (cons (car b) decls)))
      ((or (endp b)
	   (atom (car b))
	   (let ((x (macroexpand (car b))))
	     (or (atom x) (not (eq (car x) 'declare)))))
       `(let ,vars ,@(nreverse decls) (block nil (tagbody ,@b))))))

;;; The TAGBODY construct provides a body with GO tags in it.
;;; It is interpreted by first putting one entry onto GENV for
;;; every tag in the body; doing this ahead of time saves searching
;;; at GO time.  A unique cons whose car is NIL is constructed for
;;; use as a unique catch tag.  Then the body is executed.
;;; If a GO is interpreted, a throw occurs, sending as the thrown
;;; value the point in the body after the relevant tag.
;;; If the TAGBODY construct is exited for any reason (including
;;; falling off the end, which produces the value NIL), the car of
;;; the unique marker is clobbered to be INVALID, to indicate that
;;; tags associated with that marker are no longer valid.

(defspec tagbody (&rest body)
  (let ((%genv% %genv%))
    (do ((b body (cdr b))
	 (marker (list nil)))
	((endp p)
	 (block exit
	   (unwind-protect
	    (loop (setq body
			(catch marker
			  (do ((b body (cdr b)))
			      ((endp b) (return-from exit nil))
			    (unless (atom (car b))
			      (%eval (car b)))))))
	    (rplaca marker 'invalid))))
      (when (atom (car b))
	(push (list* (car b) marker (cdr b)) %genv%)))))

(defspec go (tag)
  (let ((slot (assq tag %genv%)))
    (cond ((null slot) (ferror ???<unseen-go-tag>))
	  ((eq (caadr slot) 'invalid) (ferror ???<go-tag-no-longer-valid>))
	  (t (throw (cadr slot) (cddr slot))))))
-------


Date: 12 Nov 1982 1426-MST
From: Eric Benson <BENSON at UTAH-20>
Subject: Re: NAMED-LAMBDA and function cells
To: MOON at SCRC-TENEX at MIT-MC, Killian at MIT-MULTICS
cc: common-lisp at SU-AI
In-Reply-To: Your message of 12-Nov-82 1341-MST

If you like, this is another wart which has been retained in Common Lisp,
like (SYMBOLP ()).  I think most of us would agree that the Scheme
approach is much more sensible, since it eliminates the "name vs. use"
problem, as in (:PROPERTY FOO BAR), etc.  Like the () vs. NIL, this has
2 effects: confusing semantics and difficulty or inefficiency of
implementation.  Too bad, but that's the price of compatibility with the
past.

P.S. Brian Smith's thesis should be required reading (at least browsing)
for all of us.  I know we can't change Lisp too radically, but we should
be conscious of the kludges we are perpetuating.
-------


Date: Friday, 12 November 1982  15:23-EST
From: MOON at SCRC-TENEX
To:   Earl A. Killian <Killian at MIT-MULTICS>
Cc:   common-lisp at SU-AI
Subject: NAMED-LAMBDA and function cells
In-reply-to: The message of 12 Nov 1982 0931-pst from Earl A. Killian            <Killian at MIT-MULTICS>

    Date:     12 November 1982 0931-pst
    From:     Earl A. Killian            <Killian at MIT-MULTICS>

    This is actually a good argument against allowing
    (APPLY '(LAMBDA ...) ...)

Now there's a significant break with the past!

The rest of your message is a result of confusing two different meanings for
the term "function cell."  One is an internal object of the implementation,
the part of a symbol through which calls to a function named by that symbol
indirect.  The other is that conceptual piece of storage manipulated by the
FDEFINE and FDEFINITION primitives, or (at a lower level) SYMBOL-FUNCTION-VALUE
and its SETF.  These happen to be the same in the Lisp machine, and I guess
in the PERQ, but there is no reason for them to be the same.  The former is
implementation-dependent and its goal is to make function calling efficient.
The latter is Common-Lisp-defined and its goal is to allow portable programs
to manipulate function definitions.  What the machine sees must be efficient;
what the user sees must be portable.  (Read "ought" for "must" if you like).


Date:     12 November 1982 1021-pst
From:     Earl A. Killian            <Killian at MIT-MULTICS>
Subject:  #,
To:       common-lisp at SU-AI

Shouldn't #, be a reader abbreviations for some form just like ' is?
Otherwise, how do you have a macro that uses the load-time-eval facility
for constructed code?


Date:     12 November 1982 0931-pst
From:     Earl A. Killian            <Killian at MIT-MULTICS>
Subject:  NAMED-LAMBDA
To:       common-lisp at SU-AI

This is ok with me, but I would like to clarify some things about it.

Fahlman has said twice that you put (NAMED-LAMBDA name args . body) in
the function cell of symbols.  That may be true on the LispM or PERQ,
but on a conventional architecture I'd never put anything but a compiled
function pointer in the function cell in order to keep function calling
fast. Instead, I'd have interpreted DEFUN create a tiny compiled transfer
function to an EVAL entrypoint with the lambda expression as an
argument.  And actually it wouldn't be DEFUN that did this: the compiled
transfer function would be the result of evaluating a LAMBDA or
NAMED-LAMBDA.  This is actually a good argument against allowing
(APPLY '(LAMBDA ...) ...) since that implies that
(SETF (SYMBOL-FUNCTION-VALUE 'F) '(LAMBDA ...)) will work.  I'd be very
upset if Common-Lisp tried to force that on an implementation.  For
efficiency on a conventional architecure, I'd also make all functions be
closures, i.e. have a lexical environment, even if it is ().  That's
another reason not to put lambda forms into function cells.

Thus, on conventional machines, users would almost never see
NAMED-LAMBDAs.  The name for debugging would be presumably be retreived
from this compiled transfer function.  The only use of NAMED-LAMBDA is
as a way for DEFUN to communicate the name to whatever creates the
transfer code.


Date: 12 Nov 1982 1030-MST
From: Eric Benson <BENSON at UTAH-20>
Subject: Re: primitives
To: Killian at MIT-MULTICS, Common-Lisp at SU-AI
In-Reply-To: Your message of 11-Nov-82 1402-MST

Amen.  That's what I was getting at in my last message.  The number of
primitives that can't be written in the language itself can and should
be very small.  Now that controversies over user-level features seem
to be dying down, let's fill in the gaps.
-------


Date: 12 November 1982 09:08-EST
From: Kent M. Pitman <KMP at MIT-MC>
Subject:  primitives
To: Moon at SCRC-TENEX
cc: Common-Lisp at SU-AI

    Date: Friday, 12 November 1982  02:31-EST
    From: MOON at SCRC-TENEX

    ... there is going to be a fairly large update in 6 months to a year.  It
    might be easier to put in the missing primitives then.  Of course the
    danger of this is that each implementation will have its own slightly
    incompatible primitives already by then...

Agreed. But users take what comes if they rely on such things as are not
in the language spec even if they are in an implementation. I think we 
should certainly be willing to discuss proposals for standardizing on
primitives, but there is no reason we have to rush to any decisions. We 
should keep in mind that it's always easier to add new primitives than to
remove ones we decide should never have been... 


Date: Friday, 12 November 1982  02:31-EST
From: MOON at SCRC-TENEX
To:   Earl A. Killian <Killian at MIT-MULTICS>
Cc:   Common-Lisp at SU-AI
Subject: primitives, and dynamic binding
In-reply-to: The message of 11 Nov 1982 1302-pst from Earl A. Killian            <Killian at MIT-MULTICS>

    Date:     11 November 1982 1302-pst
    From:     Earl A. Killian            <Killian at MIT-MULTICS>

    I am somewhat concerned about the lack of primitives in Common-Lisp.

I agree with you.  There is a problem, though, which is that if you specify
too many primitives you put a lot of constraints on the implementation.  This
doesn't apply to all of the specific points you brought up in your message,
though.

I think at this point the best thing would be to recognize that we are
specifying the first version of Common Lisp, and contrary to what it says
about stability in the front of the manual, there is going to be a fairly
large update in 6 months to a year.  It might be easier to put in the missing
primitives then.  Of course the danger of this is that each implementation
will have its own slightly incompatible primitives already by then.  But this
isn't really different from the situation we started with, with multiple
incompatible dialects.  If people are willing to be flexible we can adjust
our primitives to meet a common standard, or argue when techniques used in
a particular implementation rule out adherence to the proposed standard.

I do think it is important for the long-term success of the language that
as few of the underlying primitives as possible be concealed from the user.

    - Dynamic binding.  PROGV comes close to being a primitive, but is
      cumbersome and only works for the value cell of symbols.

This is a good case in point.  I would agree with you that there should be a
true binding primitive (although note that it would require adding locatives
to the language), however this would put fairly strong restrictions on
possible implementation techniques.  In fact the Common Lisp implementation
proposed for -your very own- machine can -only- bind the value cells of
symbols, because it uses deep binding, because it is a multi-processor with
a von Neumann memory.


Date: Friday, 12 November 1982  02:31-EST
From: MOON at SCRC-TENEX
To:   Earl A. Killian <Killian at MIT-MULTICS>
Cc:   Common-Lisp at SU-AI
Subject: primitives, and dynamic binding
In-reply-to: The message of 11 Nov 1982 1302-pst from Earl A. Killian            <Killian at MIT-MULTICS>

    Date:     11 November 1982 1302-pst
    From:     Earl A. Killian            <Killian at MIT-MULTICS>

    I am somewhat concerned about the lack of primitives in Common-Lisp.

I agree with you.  There is a problem, though, which is that if you specify
too many primitives you put a lot of constraints on the implementation.  This
doesn't apply to all of the specific points you brought up in your message,
though.

I think at this point the best thing would be to recognize that we are
specifying the first version of Common Lisp, and contrary to what it says
about stability in the front of the manual, there is going to be a fairly
large update in 6 months to a year.  It might be easier to put in the missing
primitives then.  Of course the danger of this is that each implementation
will have its own slightly incompatible primitives already by then.  But this
isn't really different from the situation we started with, with multiple
incompatible dialects.  If people are willing to be flexible we can adjust
our primitives to meet a common standard, or argue when techniques used in
a particular implementation rule out adherence to the proposed standard.

I do think it is important for the long-term success of the language that
as few of the underlying primitives as possible be concealed from the user.

    - Dynamic binding.  PROGV comes close to being a primitive, but is
      cumbersome and only works for the value cell of symbols.

This is a good case in point.  I would agree with you that there should be a
true binding primitive (although note that it would require adding locatives
to the language), however this would put fairly strong restrictions on
possible implementation techniques.  In fact the Common Lisp implementation
proposed for -your very own- machine can -only- bind the value cells of
symbols, because it uses deep binding, because it is a multi-processor with
a von Neumann memory.


Date: Friday, 12 November 1982  01:47-EST
From: MOON at SCRC-TENEX
To:   Scott E. Fahlman <Fahlman at Cmu-20c>
Cc:   common-lisp at SU-AI, Masinter at PARC-MAXC
Subject: Named lambdas
In-reply-to: The message of 11 Nov 1982  10:47-EST from Scott E. Fahlman <Fahlman at Cmu-20c>

Lambdas created by a LABELS would be named, with :INTERNAL function-specs.

Also note that in the Lisp machine the format got expanded to
(NAMED-LAMBDA (name . other-data) (args...) body...).  If Common Lisp
standardizes on NAMED-LAMBDA it should perhaps only have this format.
Other-data is used for dozens of things.


Date:     11 November 1982 1302-pst
From:     Earl A. Killian            <Killian at MIT-MULTICS>
Subject:  primitives
To:       Common-Lisp at SU-AI

I am somewhat concerned about the lack of primitives in Common-Lisp.
Usually the Common Lisp language design has been oriented toward
high-level features.  This is good, but it is not sufficient.  For
example, DEFCONSTANT was defined at a high-level; people thought about
what they wanted to write in their source programs and specified that as
the behavoir of DEFCONSTANT.  What bothers me is that no facilities were
provided so that the user could write DEFCONSTANT (or more likely, a
variant thereof) himself.  In this example, there is no function that
examines or sets a symbols constantness.  A recent proposal has asked
for CONSTANTP; if (SETF (CONSTANTP 'X) ...) also works, then I would be
satisfied in this case.

I think that are a number of other cases like this one.  We should take
a close look at the next language manual sent to us and try to identify
those high-level parts of the language that should be suplemented by
low-level primitives.  A good way to locate these is to look for
facilities that work only for unevaluated arguments (such as
DEFCONSTANT) or exist at only one of several levels of abstraction (such
as the compiler).

Some more examples:

- A lower-level interface to the compiler should exist.  How about
  something that takes a lambda expression and some other things (e.g. a
  name for debugging) and returns a compiled code object.

- I think DEFUN/DEFMACRO/DEFTYPE should be definable by the user in
  terms of functions with evaluated arguments.  They should be part of a
  Common Lisp library, and not implementation dependent.
  The recent suggestion to expand
  (DEFUN F ARGS BODY)
  into
  (SETF (SYMBOL-FUNCTION-VALUE 'F) #'(LAMBDA ARGS BODY))
  is simplistic, but this is not a fatal flaw.  There should be a
  function (ie. something that evaluates its arguments) like the LISPM's
  FDEFINE or FSET-CAREFULLY or whatever that sets a function cell with
  all the hair of remembering source files and giving warnings and
  whatever other objections were given against the simple SETF.

- Dynamic binding.  PROGV comes close to being a primitive, but is
  cumbersome and only works for the value cell of symbols.


Date:     11 November 1982 1302-pst
From:     Earl A. Killian            <Killian at MIT-MULTICS>
Subject:  primitives
To:       Common-Lisp at SU-AI

I am somewhat concerned about the lack of primitives in Common-Lisp.
Usually the Common Lisp language design has been oriented toward
high-level features.  This is good, but it is not sufficient.  For
example, DEFCONSTANT was defined at a high-level; people thought about
what they wanted to write in their source programs and specified that as
the behavoir of DEFCONSTANT.  What bothers me is that no facilities were
provided so that the user could write DEFCONSTANT (or more likely, a
variant thereof) himself.  In this example, there is no function that
examines or sets a symbols constantness.  A recent proposal has asked
for CONSTANTP; if (SETF (CONSTANTP 'X) ...) also works, then I would be
satisfied in this case.

I think that are a number of other cases like this one.  We should take
a close look at the next language manual sent to us and try to identify
those high-level parts of the language that should be suplemented by
low-level primitives.  A good way to locate these is to look for
facilities that work only for unevaluated arguments (such as
DEFCONSTANT) or exist at only one of several levels of abstraction (such
as the compiler).

Some more examples:

- A lower-level interface to the compiler should exist.  How about
  something that takes a lambda expression and some other things (e.g. a
  name for debugging) and returns a compiled code object.

- I think DEFUN/DEFMACRO/DEFTYPE should be definable by the user in
  terms of functions with evaluated arguments.  They should be part of a
  Common Lisp library, and not implementation dependent.
  The recent suggestion to expand
  (DEFUN F ARGS BODY)
  into
  (SETF (SYMBOL-FUNCTION-VALUE 'F) #'(LAMBDA ARGS BODY))
  is simplistic, but this is not a fatal flaw.  There should be a
  function (ie. something that evaluates its arguments) like the LISPM's
  FDEFINE or FSET-CAREFULLY or whatever that sets a function cell with
  all the hair of remembering source files and giving warnings and
  whatever other objections were given against the simple SETF.

- Dynamic binding.  PROGV comes close to being a primitive, but is
  cumbersome and only works for the value cell of symbols.


Date: 11 November 1982 1549-EST (Thursday)
From: Guy.Steele at CMU-CS-A
To: common-lisp at SU-AI
Subject: Benson's remarks on CONSTANTP
In-Reply-To: Eric Benson's message of 11 Nov 82 12:42-EST

I must say that when I hear the functio name CONSTANTP my first
thought is "Oh, that tells you whether or not something self-evaluates";
clearly Standard LISP has given that name its natural definition.
What I have proposes is probably better called CONSTANT-SYMBOL-P.
--Guy


Date: 11 Nov 1982 1042-MST
From: Eric Benson <BENSON at UTAH-20>
Subject: Re: Quick query about CONSTANTP
To: Guy.Steele at CMU-10A, common-lisp at SU-AI
In-Reply-To: Your message of 9-Nov-82 2206-MST

Uh-oh, CONSTANTP is defined in Standard Lisp already and means
(AND (NOT (CONSP X)) (NOT (SYMBOLP X))).  If you put this in, please
call it something (slightly) different, e.g. CONSTANT-P.  By the way,
I do think this is a useful idea.  I think it's important not to leave
too much undefined in the standard.  For example, it would be very nice
if a function (not special form) were defined for defining macros, and
there should be some way to find out how many multiple values are
returned by a function without having to make a list of them.
-------


Date: Thursday, 11 November 1982  11:54-EST
From: Scott E. Fahlman <Fahlman at Cmu-20c>
To:   Masinter at PARC-MAXC
Cc:   common-lisp at SU-AI
Subject: Named lambdas


Yes, the name in named-lambda is just machine-readable commentary -- the
evaluator just ignores it.

(defun foo (a b c) ...)

puts

(NAMED-LAMBDA FOO (A B C) ...)

into the symbol-function slot of the symbol FOO, instead of the more
traditional

(LAMBDA (A B C) ...)

When the DEFUN gets compiled, the name is hidden in the compiled
function object, so similar debugging information is available.  In the
Spice Lisp implementation, at least, the LAMBDA form is on the stack,
but not the calling form, so it would be awkward (not impossible) to
recover the function name for debugging; the NAMED-LAMBDA hack solves
the problem.  This is something of a kludge, and I have no strong
opinion about whether it should be in the white pages or whether we
should just quietly do our dirty hacking behind the scenes.  The only
problem is that users might see named-lambdas on the stack and wonder
what is up, so they at least have to be documented in the red pages of
implementations that use this trick.

-- Scott


Date: 11-Nov-82  8:21:52 PST (Thursday)
From: Masinter at PARC-MAXC
Subject: Re: Named lambdas
In-reply-to: Fahlman's message of Thursday, 11 November 1982  10:47-EST
To: Scott E. Fahlman <Fahlman at Cmu-20c>
cc: Masinter, common-lisp at SU-AI

My reading of what you say is that, as far as the semantics of what is
accessible from common-lisp functions, the name in NAMED-LAMBDA is just 
commentary? You say how NAMED-LAMBDA is used, but not what it means.

I don't quite understand about interpreted DEFUNs. Do you mean

(DEFUN FOO (NAMED-LAMBDA FUM (A B C) --))

that the debugger will show FUM on the stack? There's nothing so far in common
lisp which had led me to believe that if you said

(DEFUN FOO (A B C) --) 

that the debugger COULDN'T tell that you were inside FOO; I don't believe
such enforced brain-damage should be in the spec for Common-Lisp.

Also: does NAMED-LAMBDA have a different meaning for compiled & interpreted code?
I.e., they get thrown away when you interpret?




Date: Thursday, 11 November 1982  10:47-EST
From: Scott E. Fahlman <Fahlman at Cmu-20c>
To:   Masinter at PARC-MAXC
Cc:   common-lisp at SU-AI
Subject: Named lambdas


Named-Lambda was invented by the Lisp Machine folk (I think).  The
syntax is

(NAMED-LAMBDA name arglist . body)

This works in all respects like a lambda, with the name being ignored.
The name is there solely for debugging.  The reason this exists is that
interpreted DEFUN can now put the named-lambda form in the function slot
of a symbol, with the name indicating the name of the function as seen
by DEFUN.  (I guess now this is a function-spec.)  No attempt is made to
keep this up to date if the form is passed around to other places.  At
various times in the interpreter, only the lambda or named-lambda form
is on the stack, and if it is a named-lambda, the debugger can say
something intelligent about what the function is.  In some
implementations, at least, it is very hard to recover the name of the
function in any other way -- it does not appear on the stack in any
meaningful form.  Assorted other code-browsing functions may also find
the name useful.

Since the name is just commentary, and doesn't really do anything, I
don't think that the scoping issues apply.  I'm not really sure whether
lambdas created inside a LABELS or some such would be named -- this
would be used so rarely that I don't really care.  The point is to do
something useful for the normal case of a DEFUN.

-- Scott


Date: 11-Nov-82  7:26:02 PST (Thursday)
From: Masinter at PARC-MAXC
Subject: Named lambdas
To: common-lisp at SU-AI

I can nowhere find a description of NAMED-LAMBDA and its semantics.
I've made a guess, but it doesn't map very well into extant common-lisp
structures; e.g., who can see the name? I assume from the discussion
about debuggers that the name is dynamic in scope rather than lexical.


Date: Wednesday, 10 November 1982, 10:44-EST
From: Daniel L. Weinreb <dlw at SCRC-TENEX at MIT-MC>
Subject: Re: Mini-ballot
To: common-lisp at SU-AI
In-reply-to: The message of 8 Nov 82 19:58-EST from Mgr DEC-20s/Dir LCSR Comp Facility <HEDRICK at RUTGERS>,
             The message of 8 Nov 82 20:10-EST from Eric Benson <BENSON at UTAH-20>,
             The message of 9 Nov 82 01:52-EST from Mgr DEC-20s/Dir LCSR Comp Facility <HEDRICK at RUTGERS>,
             The message of 9 Nov 82 04:33-EST from Guy.Steele at CMU-10A,
             The message of 9 Nov 82 07:44-EST from Scott E. Fahlman <Fahlman at Cmu-20c>

    Date:  8 Nov 1982 1810-MST
    From: Eric Benson <BENSON at UTAH-20>
    (1) It should not be necessary to extend DEFUN in this manner.
    (SETF (GET 'FOO 'BAR) #'(LAMBDA ...))
    should do exactly what you want.  Is there a problem with this?
Several.  Among others, a "definition" special form is parsable; on the Lispm
it records the source file name and checks for invalid redefinitions, etc.
I won't bother to go one since this seems to have been decided in the
right direction.

    Date:  8 Nov 1982 1958-EST
    From: HEDRICK at RUTGERS (Mgr DEC-20s/Dir LCSR Comp Facility)
							 Do you gurantee
    that we can always do (APPLY (GET 'FOO 'BAR) args)?
We do guarantee that if you get a function object by calling the appropriate
function (the Lispm calls it FDEFINITION) on the function spec, then you
can apply what you got, but that doesn't mean we have to make any statements
about what you got.

    Date:  9 Nov 1982 0152-EST
    From: HEDRICK at RUTGERS (Mgr DEC-20s/Dir LCSR Comp Facility)
				  However I would like to have someone define
    what the construct for MACRO's, FEXPR's (if Common Lisp has such
    things), and any other odd things that DEFUN can generate.  If it is not
    possible to do that, then I think we would be better off using (PUTPROP
    'FOO 'BAR '#(LAMBDA ...  
Pardon me, but this doesn't make any sense.  The function spec FOO refers
to the function "cell" of FOO, whether it holds a macro or a function or
whatever.  (defmacro (:property foo bar) xxx) would mean to put onto
foo's bar property the same object that (defmacro baz xxx) would have put
into foo's function "cell".  There aren't any alternative constructs for
macros.

			     Furthermore, I would like to request that the
    this definition include a specification of the actual data structure to
    be used for interpreted functions.  
Gee, I thought that defining the format of functions was exactly what you
didn't want to do.  However, FDEFINITION of a defined function-spec is
guaranteed to return a function, suitable for APPLY and FUNCALL; it
is NOT allowed to return (expr lambda ...) or anything like that.
So I think function specs are actually the way to solve the problems that
you are bringing up.

    Date:  9 November 1982 0433-EST (Tuesday)
    From: Guy.Steele at CMU-10A

    I might believe that (APPLY '(:PROPERTY FOO BAR) args) shouldn't work,

In the Lisp Machine, symbols are a special case:  it is defined that all
symbols are functions, and when applied, they apply their definition.
However, it is not defined that all function specs in general are
functions and do the analogous thing just the way symbols do.  Actually,
we could make this change if we wanted, simply by saying that it's
illegal to have a function spec that looks like (LAMBDA ...).  I'm not
convinced that this would be a good idea, though.

    However, if you believe in the thing-name distinction, then it is
    even more important that ((:PROPERTY FOO BAR) 3 5 :START 7) work
This is exactly what I argued, about a year or two ago.  It's the general
"normal evaluation"/"functional evaluation" distinction.  If #'(:property a b)
works then, by analogy, ((:property a b) ...) ought to work.  However:

    Date: Tuesday, 9 November 1982  07:44-EST
    From: Scott E. Fahlman <Fahlman at Cmu-20c>

    I am really getting scared.  Allowing ((:property foo bar) ...) seems to
    me to open up all sorts of evil and hairy possibilities.
This is what everybody else told me, including Moon.  My feeling on the
matter is that we did, frankly, leave a semantic asymmetry in the by
leaving it in its current state.  Zvona's argument that the users expect
((:property a b) ...) to work is an important one: this is an instance
of a fundamental principle of user-interface, which makes sense applied
to language design too.  I still feel that ((:property a b) ...) really
ought to work, but I have already accepted Fahlman's argument and am
slightly scared myself.  Note that I don't know what Moon thinks about
this; I haven't discused it with him in some time.

As for the asterisks issue, I abstain (I don't think I have anything
useful to contribute and you guys seem to have the issue under control).


Date: Wednesday, 10 November 1982, 10:46-EST
From: Daniel L. Weinreb <dlw at SCRC-TENEX at MIT-MC>
Subject: Named lambdas
To: Guy.Steele at CMU-10A, common-lisp at SU-AI
In-reply-to: The message of 9 Nov 82 22:33-EST from Guy.Steele at CMU-10A

Yes, we should have NAMED-LAMBDA.  It is invaluable for debugging if you
ever use interpreted code.

CONSTANTP is OK with me; I have no strong feelings about it.


Date: Wednesday, 10 November 1982  08:30-EST
From: Scott E. Fahlman <Fahlman at Cmu-20c>
To:   Guy.Steele at CMU-10A
Cc:   common-lisp at SU-AI
Subject: Named lambdas


NAMED-LAMBDA looks like a total crock to me, but we use it anyway.  It
is by far the simplest way for us to keep around the name (or I guess
the function spec) of a lambda for use by the debugger.  I guess this
could be done with a hash-table or something, but that is gruesome.
Our plan was to just use this internally in evaluated DEFUN, but maybe
it would be better to inform the users of this.

-- Scott


Date: Wednesday, 10 November 1982  08:27-EST
From: Scott E. Fahlman <Fahlman at Cmu-20c>
To:   Guy.Steele at CMU-10A
Cc:   common-lisp at SU-AI
Subject: Quick query about CONSTANTP


I've got no problem with Constantp, or even with a requirement that
resetting a constant in the evaluator signals a correctable error.  I
don't want to do this check in compiled code right now.

-- Scott


Date: 10 NOV 1982 0037-PST
From: JONL at PARC-MAXC
Subject: Re: Quick query about CONSTANTP
To:   Guy.Steele at CMU-10A, common-lisp at SU-AI
cc:   JONL

In response to the message sent  10 November 1982 0006-EST (Wednesday) from Guy.Steele@CMU-10A

Interlisp-D has the (currently undocumented, but "upcoming")
function CONSTANTEXPRESSIONP; it works not only for symbols,
but for other forms such as (QUOTE FOO) and (CONSTANT (LIST 1 2))
-- the latter being somewhat like '#.(LIST 1 2) except that the
evaluation is performed at eval/compile time rather than readtime.
Ultimately CONSTANTEXPRESSIONP should even work of forms like
(COND ((EQ PI PI) 3) (T 4)), but its current status is more limited.

Just exactly how CONSTANTP, or CONSTANTEXPRESSIONP if you care to
follow the Interlisp pattern, is implemented for symbols is
probably not all that important.  But your suggestion of a bit
in the symbol header brings back memories of LISP1.5 which
had certain property names treated specially by the equivalent
of PUTPROP -- namely a word of bits that could be turned on
or off.  If efficiency is important in matters like these
(i.e., system properties whose values are always true or false),
them maybe it's not such a bad idea to have these  property
bits again.  But that's *if* ...


Date: 10 Nov 1982 0133-EST
From: STEELE at CMU-20C
Subject: New proposed evaluators
To: common-lisp at SU-AI

There follow improved and corrected versions of the proposed model
evaluators for Common LISP.  Improvements include renaming of
the variable EVALHOOK to *EVALHOOK*, allowing macro calls to
expand into declarations, improved interaction of error handling
and lexical environments (many thanks to KMP), increased use of
speial variables in the second version, and many bug fixes.
---------------------------------------------------------------
;;; This evaluator splits the lexical environment into four
;;; logically distinct entities:
;;;	VENV = lexical variable environment
;;;	FENV = lexical function and macro environment
;;;	BENV = block name environment
;;;	GENV = go tag environment
;;; Each environment is an a-list.  It is never the case that
;;; one can grow and another shrink simultaneously; the four
;;; parts could be united into a single a-list.  The four-part
;;; division saves consing and search time.
;;;
;;; Each entry in VENV has one of two forms: (VAR VALUE) or (VAR).
;;; The first indicates a lexical binding of VAR to VALUE, and the
;;; second indicates a special binding of VAR (implying that the
;;; special value should be used).
;;;
;;; Each entry in FENV looks like (NAME TYPE . FN), where NAME is the
;;; functional name, TYPE is either FUNCTION or MACRO, and FN is the
;;; function or macro-expansion function, respectively.  Entries of
;;; type FUNCTION are made by FLET and LABELS; those of type MACRO
;;; are made by MACROLET.
;;;
;;; Each entry in BENV looks like (NAME), where NAME is the name
;;; of the block.  The cons cell that is the entry is used as a
;;; catch tag for implementing RETURN-FROM.  If the entry has been
;;; clobbered to look like (NAME . INVALID), then the block has
;;; been exited, and a return to that block is an error.
;;;
;;; Each entry in GENV looks like (TAG MARKER . BODY), where TAG is
;;; a go tag, MARKER is a unique cons used as a catch tag, and BODY
;;; is the statement sequence that follows the go tag.  If the car of
;;; MARKER, normally NIL, has been clobbered to be INVALID, then
;;; the tag body has been exited, and a GO to that tag is an error.

;;; An interpreted-lexical-closure contains a function (normally a
;;; lambda-expression) and the lexical environment.

(defstruct interpreted-lexical-closure function venv fenv benv genv)


;;; The EVALHOOK feature allows a user-supplied function to be called
;;; whenever a form is to be evaluated.  The presence of the lexical
;;; environment requires an extension of the feature as it is defined
;;; in MacLISP.  Here, the user hook function must accept not only
;;; the form to be evaluated, but also the components of the lexical
;;; environment; these must then be passed verbatim to EVALHOOK or
;;; *EVAL in order to perform the evaluation of the form correctly.
;;; The precise number of components should perhaps be allowed to be
;;; implementation-dependent, so it is probably best to require the
;;; user hook function to accept arguments as (FORM &REST ENV) and
;;; then to perform evaluation by (APPLY #'EVALHOOK FORM HOOKFN ENV),
;;; for example.

(defvar *evalhook* nil)

(defun evalhook (exp hookfn venv fenv benv genv)
  (let ((*evalhook* hookfn)) (%eval exp venv fenv benv genv)))

(defun eval (exp)
  (*eval exp nil nil nil nil))

;;; *EVAL looks useless here, but does more complex things
;;; in alternative implementations of this evaluator.

(defun *eval (exp venv fenv benv genv)
  (%eval exp venv fenv benv genv))
!
;;; Function names beginning with "%" are intended to be internal
;;; and not defined in the Common LISP white pages.

;;; %EVAL is the main evaluation function.

(defun %eval (exp venv fenv benv genv)
  (if *evalhook*
      (let ((hookfn *evalhook*) (*evalhook* nil))
	(funcall hookfn exp venv fenv benv genv))
      (typecase exp
	;; A symbol is first looked up in the lexical variable environment.
	(symbol (let ((slot (assq exp venv)))
		  (cond ((and slot (not (null (cdr slot))))
			 (cadr slot))
			((boundp exp) (symbol-value exp))
			(t (cerror :unbound-variable
				   "The symbol ~S has no value"
				   exp)))))
	;; Numbers, strings, bit-vectors, and characters self-evaluate.
	((or number string bit-vector character) exp)
	;; Conses require elaborate treatment based on the car.
	(cons (typecase (car exp)
		;; A symbol is first looked up in the lexical function environment.
		;; This lookup is cheap if the environment is empty, a common case.
		(symbol
		 (let ((fn (car exp)))
		   (loop (let ((slot (assq fn fenv)))
			   (unless (null slot)
			     (return (case (cadr slot)
				       (macro (%eval (%macroexpand
						      (cddr slot)
						      (if (eq fn (car exp))
							  exp
							  (cons fn (cdr exp))))))
				       (function (%apply (cddr slot)
							 (%evlis (cdr exp) venv fenv benv genv)
							 venv fenv benv genv))
				       (t <implementation-error>)))))
			 ;; If not in lexical function environment,
			 ;;  try the definition cell of the symbol.
			 (when (fboundp fn)
			   (return (cond ((special-form-p fn)
					  (%invoke-special-form
					   fn (cdr exp) venv fenv benv genv))
					 ((macro-p fn)
					  (%eval (%macroexpand
						  (get-macro-function (symbol-function fn))
						  (if (eq fn (car exp))
						      exp
						      (cons fn (cdr exp))))
						 venv fenv benv genv))
					 (t (%apply (symbol-function fn)
						    (%evlis (cdr exp) venv fenv benv genv)
						    venv fenv benv genv)))))
			 (setq fn
			       (cerror :undefined-function
				       "The symbol ~S has no function definition"
				       fn))
			 (unless (symbolp fn)
			   (return (%apply fn
					   (%evlis (cdr exp) venv fenv benv genv)
					   venv fenv benv genv))))))
		;; A cons in function position must be a lambda-expression.
		;; Note that the construction of a lexical closure is avoided here.
		(cons (%apply (car exp)
			      (%evlis (cdr exp) venv fenv benv genv)
			      venv fenv benv genv))
		(t (%eval (cerror :invalid-form
				  "Cannot evaluate the form ~S: function position has invalid type ~S"
				  exp (type-of (car exp)))
			  venv fenv benv genv))))
	(t (%eval (cerror :invalid-form
			  "Cannot evaluate the form ~S: invalid type ~S"
			  exp (type-of exp))
		  venv fenv benv genv)))))
!
;;; Given a list of forms, evaluate each and return a list of results.

(defun %evlis (forms venv fenv benv genv)
  (mapcar #'(lambda (form) (%eval form venv fenv benv genv)) forms))

;;; Given a list of forms, evaluate each, discarding the results of
;;; all but the last, and returning all results from the last.

(defun %evprogn (body venv fenv benv genv)
  (if (endp body) nil
      (do ((b body (cdr b)))
	  ((endp (cdr b))
	   (%eval (car b) venv fenv benv genv))
	(%eval (car b) venv fenv benv genv))))

;;; APPLY takes a function, a number of single arguments, and finally
;;; a list of all remaining arguments.  The following song and dance
;;; attempts to construct efficiently a list of all the arguments.

(defun apply (fn firstarg &rest args*)
  (%apply fn
	  (cond ((null args*) firstarg)
		((null (cdr args*)) (cons firstarg (car args*)))
		(t (do ((x args* (cdr x))
			(z (cddr args*) (cdr z)))
		       ((null z)
			(rplacd x (cadr x))
			(cons firstarg (car args*))))))
	  nil nil nil nil))
!
;;; %APPLY does the real work of applying a function to a list of arguments.
;;; The environment is passed in because it leads to more natural error
;;; recovery.

(defun %apply (fn args venv fenv benv genv)
  (typecase fn
    ;; For a compiled function, an implementation-dependent "spread"
    ;;  operation and invocation is required.
    (compiled-function (%invoke-compiled-function fn args))
    ;; The same goes for a compiled closure over lexical variables.
    (compiled-lexical-closure (%invoke-compiled-lexical-closure fn args))
    ;; The treatment of interpreted lexical closures is elucidated fully here.
    (interpreted-lexical-closure
     (%lambda-apply (interpreted-lexical-closure-function fn)
		    args
		    (interpreted-lexical-closure-venv fn)
		    (interpreted-lexical-closure-fenv fn)
		    (interpreted-lexical-closure-benv fn)
		    (interpreted-lexical-closure-genv fn)))
    ;; For a symbol, the function definition is used, if it is a function.
    (symbol (%apply (cond ((not (fboundp fn))
			   (cerror :undefined-function
				   "The symbol ~S has no function definition"
				   fn))
			  ((special-form-p fn)
			   (cerror :invalid-function
				   "The symbol ~S cannot be applied: it names a special form"
				   fn))
			  ((macro-p fn)
			   (cerror :invalid-function
				   "The symbol ~S cannot be applied: it names a macro"
				   fn))
			  (t (symbol-function fn)))
		    args venv fenv benv genv))
    (cons (if (eq (car fn) 'lambda)
	      (%lambda-apply fn args venv fenv benv genv)
	      (%apply (cerror :invalid-function
			      "~S is not a valid function"
			      fn)
		      args venv fenv benv genv)))
    (t (%apply (cerror :invalid function
		       "~S has an invalid type ~S for a function"
		       fn (type-of fn))
	       args venv fenv benv genv))))
!
;;; %LAMBDA-APPLY is the hairy part, that takes care of applying
;;; a lambda-expression in a given lexical environment to given
;;; arguments.  The complexity arises primarily from the processing
;;; of the parameter list.
;;;
;;; If at any point the lambda-expression is found to be malformed
;;; (typically because of an invalid parameter list), or if the list
;;; of arguments is not suitable for the lambda-expression, a correctable
;;; error is signalled; correction causes a throw to be performed to
;;; the tag %LAMBDA-APPLY-RETRY, passing back a (possibly new)
;;; lambda-expression and a (possibly new) list of arguments.
;;; The application is then retried.  If the new lambda-expression
;;; is not really a lambda-expression, then %APPLY is used instead of
;;; %LAMBDA-APPLY.
;;;
;;; In this evaluator, PROGV is used to instantiate variable bindings
;;; (though its use is embedded with a macro called %BIND-VAR).
;;; The throw that precedes a retry will cause special bindings to
;;; be popped before the retry.

(defun %lambda-apply (lexp args venv fenv benv genv)
  (multiple-value-bind (newfn newargs)
		       (catch '%lambda-apply-retry
			 (return-from %lambda-apply
			   (%lambda-apply-1 lexp args venv fenv benv genv)))
    (if (and (consp lexp) (eq (car lexp) 'lambda))
	(%lambda-apply newfn newargs venv fenv benv genv)
	(%apply newfn newargs venv fenv benv genv))))

;;; Calling this function will unwind all special variables
;;; and cause FN to be applied to ARGS in the original lexical
;;; and dynamic environment in force when %LAMBDA-APPLY was called.

(defun %lambda-apply-retry (fn args)
  (throw '%lambda-apply-retry (values fn args)))

;;; This function is convenient when the lambda expression is found
;;; to be malformed.  REASON should be a string explaining the problem.

(defun %bad-lambda-exp (lexp oldargs reason)
  (%lambda-apply-retry
   (cerror :invalid-function
	   "Improperly formed lambda-expression ~S: ~A"
	   lexp reason)
   oldargs))

;;; (%BIND-VAR VAR VALUE . BODY) evaluates VAR to produce a symbol name
;;; and VALUE to produce a value.  If VAR is determined to have been
;;; declared special (as indicated by the current binding of the variable
;;; SPECIALS, which should be a list of symbols, or by a SPECIAL property),
;;; then a special binding is established using PROGV.  Otherwise an
;;; entry is pushed onto the a-list presumed to be in the variable VENV.

;;; The CONSTANTP test ideally is true for any constant symbol;
;;; it should at least check for T, NIL, and keywords.

(defmacro %bind-var (var value &body body)
  (let ((xvar (gensym)) (xvalue (gensym)))
    `(let ((,xvar ,var) (,xvalue ,value))
       (loop (when (not (constantp ,xvar)) (return))
	     (setq ,xvar (cerror :invalid-variable
				 "~S is a constant and may not be bound"
				 ,xvar)))
       (let ((specp (or (memq ,xvar specials) (get ,xvar 'special))))
	 (progv (and specp (list ,xvar)) (and specp (list ,xvalue))
		(push (if specp (list ,xvar) (list ,xvar ,xvalue)) venv)
		,@body)))))

;;; %LAMBDA-KEYWORD-P is true iff X (which must be a symbol)
;;; has a name beginning with an ampersand.

(defun %lambda-keyword-p (x)
  (char= #\& (char 0 (symbol-pname x))))
!
;;; %LAMBDA-APPLY-1 is responsible for verifying that LEXP is
;;; a lambda-expression, for extracting a list of all variables
;;; declared SPECIAL in DECLARE forms, and for finding the
;;; body that follows any DECLARE forms.

(defun %lambda-apply-1 (lexp args venv fenv benv genv)
  (cond ((or (not (consp lexp))
	     (not (eq (car lexp) 'lambda))
	     (atom (cdr lexp))
	     (not (listp (cadr lexp))))
	 (%bad-lambda-exp lexp args "improper lambda-expression"))
	(t (do ((body (cddr lexp) (cdr body))
		(specials '()))
	       ((or (endp body) (not (consp (car body))))
		(%bind-required lexp args (cadr lexp) fenv benv genv venv args specials nil body))
	     (let ((form (macroexpand (car body))))
	       (cond ((or (not (consp form))
			  (not (eq (car form) 'declare)))
		      (return (%bind-required lexp args (cadr lexp) fenv benv genv venv args specials form body)))
		     (t (dolist (decl (cdar form))
			  (when (eq (car decl) 'special)
			    (setq specials
				  (if (null specials)	;Avoid consing
				      (cdar decl)
				      (append (cdar decl) specials))))))))))))

;;; %BIND-REQUIRED handles the pairing of arguments to required parameters.
;;; Error checking is performed for too few or too many arguments.
;;; If a lambda-list keyword is found, %TRY-OPTIONAL is called.
;;; Here, as elsewhere, if the binding process terminates satisfactorily
;;; then the body is evaluated using %EVPROGN in the newly constructed
;;; dynamic and lexical environment.

(defun %bind-required (lexp oldargs varlist venv fenv benv genv args specials form body)
  (cond ((endp varlist)
	 (if (null args)
	     (%lambda-evprogn form body venv fenv benv genv)
	     (%lambda-apply-retry lexp
				  (cerror :too-many-arguments
					  "Too many arguments for function ~S: ~S"
					  lexp oldargs))))
	((not (symbolp (car varlist)))
	 (%bad-lambda-exp lexp oldargs "required parameter name not a symbol"))
	((%lambda-keyword-p (car varlist))
	 (%try-optional lexp oldargs varlist venv fenv benv genv args specials form body))
	((null args)
	 (%lambda-apply-retry lexp 
			      (cerror :too-few-arguments
				      "Too few arguments for function ~S: ~S"
				      lexp oldargs)))
	(t (%varbind (car varlist) (car args)
		      (%bind-required lexp oldargs (cdr varlist) venv fenv benv genv (cdr args) specials form body)))))
!
;;; %TRY-OPTIONAL determines whether the lambda-list keyword &OPTIONAL
;;; has been found.  If so, optional parameters are processed; if not,
;;; the buck is passed to %TRY-REST.

(defun %try-optional (lexp oldargs varlist venv fenv benv genv args specials form body)
  (cond ((eq (car varlist) '&optional)
	 (%bind-optional lexp oldargs (cdr varlist) venv fenv benv genv args specials form body))
	(t (%try-rest lexp oldargs varlist venv fenv benv genv args specials form body))))

;;; %BIND-OPTIONAL determines whether the parameter list is exhausted.
;;; If not, it parses the next specifier.

(defun %bind-optional (lexp oldargs varlist venv fenv benv genv args specials form body)
  (cond ((endp varlist)
	 (if (null args)
	     (%lambda-evprogn form body venv fenv benv genv)
	     (%lambda-apply-retry lexp
				  (cerror :too-many-arguments
					  "Too many arguments for function ~S: ~S"
					  lexp oldargs))))
	(t (let ((varspec (car varlist)))
	     (cond ((symbolp varspec)
		    (if (%lambda-keyword-p varspec)
			(%try-rest lexp oldargs varlist venv fenv benv genv args specials form body)
			(%process-optional lexp oldargs varlist venv fenv benv
					   genv args specials form body varspec nil nil)))
		   ((and (consp varspec)
			 (symbolp (car varspec))
			 (listp (cdr varspec))
			 (or (endp (cddr varspec))
			     (and (symbolp (caddr varspec))
				  (not (endp (caddr varspec)))
				  (endp (cdddr varspec)))))
		    (%process-optional lexp oldargs varlist venv fenv benv
				       genv args specials form body
				       (car varspec)
				       (cadr varspec)
				       (caddr varspec)))
		   (t (%bad-lambda-exp lexp oldargs "malformed optional parameter specifier")))))))

;;; %PROCESS-OPTIONAL takes care of binding the parameter,
;;; and also the supplied-p variable, if any.

(defun %process-optional (lexp oldargs varlist venv fenv benv genv args specials form body var init varp)
  (let ((value (if (null args) (%eval init venv fenv benv genv) (car args))))
    (%varbind var value
      (if varp
	  (%varbind varp (not (null args))
	    (%bind-optional lexp oldargs (cdr varlist) venv fenv benv genv (cdr args) specials form body))
	  (%bind-optional lexp oldargs (cdr varlist) venv fenv benv genv (cdr args) specials form body)))))
!
;;; %TRY-REST determines whether the lambda-list keyword &REST
;;; has been found.  If so, the rest parameter is processed;
;;; if not, the buck is passed to %TRY-KEY, after a check for
;;; too many arguments.

(defun %try-rest (lexp oldargs varlist venv fenv benv genv args specials form body)
  (cond ((eq (car varlist) '&rest)
	 (%bind-rest lexp oldargs (cdr varlist) venv fenv benv genv args specials form body))
	((and (not (eq (car varlist) '&key))
	      (not (null args)))
	 (%lambda-apply-retry lexp
			      (cerror :too-many-arguments
				      "Too many arguments for function ~S: ~S"
				      lexp oldargs)))
	(t (%try-key lexp oldargs varlist venv fenv benv genv args specials form body))))

;;; %BIND-REST ensures that there is a parameter specifier for
;;; the &REST parameter, binds it, and then evaluates the body or
;;; calls %TRY-KEY.

(defun %bind-rest (lexp oldargs varlist venv fenv benv genv args specials form body)
  (cond ((or (endp varlist)
	     (not (symbolp (car varlist))))
	 (%bad-lambda-exp lexp oldargs "missing rest parameter specifier"))
	(t (%varbind (car varlist) args
	     (cond ((endp (cdr varlist))
		    (%lambda-evprogn form body venv fenv benv genv))
		   ((and (symbolp (cadr varlist))
			 (%lambda-keyword-p (cadr varlist)))
		    (%try-key lexp oldargs (cdr varlist) venv fenv benv genv args specials form body))
		   (t (%bad-lambda-exp lexp oldargs "malformed after rest parameter specifier")))))))
!
;;; %TRY-KEY determines whether the lambda-list keyword &KEY
;;; has been found.  If so, keyword parameters are processed;
;;; if not, the buck is passed to %TRY-AUX.

(defun %try-key (lexp oldargs varlist venv fenv benv genv args specials form body)
  (cond ((eq (car varlist) '&key)
	 (%bind-key lexp oldargs (cdr varlist) venv fenv benv genv args specials form body nil))
	(t (%try-aux lexp oldargs varlist venv fenv benv genv specials form body))))

;;; %BIND-KEY determines whether the parameter list is exhausted.
;;; If not, it parses the next specifier.

(defun %bind-key (lexp oldargs varlist venv fenv benv genv args specials form body keys)
  (cond ((endp varlist)
	 (%check-for-bad-keywords lexp args keys)
	 (%lambda-evprogn form body venv fenv benv genv))
	(t (let ((varspec (car varlist)))
	     (cond ((symbolp varspec)
		    (if (%lambda-keyword-p varspec)
			(cond ((not (eq varspec '&allow-other-keywords))
			       (%check-for-bad-keywords lexp args keys)
			       (%try-aux lexp oldargs varlist venv fenv benv genv specials form body))
			      ((endp (cdr varlist))
			       (%lambda-evprogn form body venv fenv benv genv))
			      ((%lambda-keyword-p (cadr varlist))
			       (%try-aux lexp oldargs (cdr varlist) venv fenv benv genv specials form body))
			      (t (%bad-lambda-exp lexp oldargs "invalid after &ALLOW-OTHER-KEYWORDS")))
			(%process-key lexp oldargs varlist venv fenv benv
				      genv args specials form body keys
				      (intern (symbol-print-name varspec) keyword-package)
				      varspec nil nil)))
		   ((and (consp varspec)
			 (or (symbolp (car varspec))
			     (and (consp (car varspec))
				  (consp (cdar varspec))
				  (symbolp (cadar varspec))
				  (endp (cddar varspec))))
			 (listp (cdr varspec))
			 (or (endp (cddr varspec))
			     (and (symbolp (caddr varspec))
				  (not (endp (caddr varspec)))
				  (endp (cdddr varspec)))))
		    (%process-key lexp oldargs varlist venv fenv benv
				  genv args specials form body keys
				  (if (consp (car varspec))
				      (caar varspec)
				      (intern (symbol-print-name (car varspec)) keyword-package))
				  (if (consp (car varspec))
				      (cadar varspec)
				      (car varspec))
				  (cadr varspec)
				  (caddr varspec)))
		   (t (%bad-lambda-exp lexp oldargs "malformed keyword parameter specifier")))))))

;;; Optional error check for bad keyword arguments.

(defun %check-for-bad-keywords (lexp args keys)
  (do ((a args (cddr a)))
      ((endp args))
    (unless (memq (car a) keys)
      (cerror :unexpected-keyword
	      "Keyword not expected by function ~S: ~S"
	      lexp (car a)))))

;;; %PROCESS-KEY takes care of binding the parameter,
;;; and also the supplied-p variable, if any.

(defun %process-key (lexp oldargs varlist venv fenv benv genv args specials form body keys kwd var init varp)
  (do ((a args (cddr a)))
      ((endp a)
       (%process-key-1 lexp oldargs varlist venv fenv benv genv args specials
		       form body keys kwd var init varp
		       (%eval init venv fenv benv genv) nil))
    (when (eq (car a) kwd)
      (return (%process-key-1 lexp oldargs varlist venv fenv benv genv args specials
			      form body keys kwd var init varp
			      (cadr a) t)))))

(defun %process-key-1 (lexp oldargs varlist venv fenv benv genv args specials form body keys kwd var init varp value suppliedp)
  (%varbind var value
    (if varp
	(%varbind varp suppliedp
	  (%bind-key lexp oldargs varlist venv fenv benv genv args specials form body (cons kwd keys)))
	(%bind-key lexp oldargs varlist venv fenv benv genv args specials form body (cons kwd keys)))))
!
;;; %TRY-AUX determines whether the keyword &AUX
;;; has been found.  If so, auxiliary variables are processed;
;;; if not, an error is signalled.

(defun %try-aux (lexp oldargs varlist venv fenv benv genv specials form body)
  (cond ((eq (car varlist) '&aux)
	 (%bind-aux lexp oldargs (cdr varlist) venv fenv benv genv specials form body))
	(t (%bad-lambda-exp lexp oldargs "unknown or misplaced lambda-list keyword"))))

;;; %BIND-AUX determines whether the parameter list is exhausted.
;;; If not, it parses the next specifier.

(defun %bind-aux (lexp oldargs varlist venv fenv benv genv specials form body)
  (cond ((endp varlist)
	 (%lambda-evprogn form body venv fenv benv genv))
	(t (let ((varspec (car varlist)))
	     (cond ((symbolp varspec)
		    (if (%lambda-keyword-p varspec)
			(%bad-lambda-exp lexp oldargs "unknown or misplaced lambda-list keyword")
			(%process-aux lexp oldargs varlist venv fenv benv
				      genv specials form body varspec nil)))
		   ((and (consp varspec)
			 (symbolp (car varspec))
			 (listp (cdr varspec))
			 (endp (cddr varspec)))
		    (%process-aux lexp oldargs varlist venv fenv benv
				       genv specials form body
				       (car varspec)
				       (cadr varspec)))
		   (t (%bad-lambda-exp lexp oldargs "malformed aux variable specifier")))))))

;;; %PROCESS-AUX takes care of binding the auxiliary variable.

(defun %process-aux (lexp oldargs varlist venv fenv benv genv specials form body var init)
  (%varbind var (and init (%eval init venv fenv benv genv))
    (%bind-aux lexp oldargs varlist venv fenv benv genv specials form body)))

(defun %lambda-evprogn (form body venv fenv benv genv)
  (unless (null form) (%eval form venv fenv benv genv))
  (%evprogn body venv fenv benv genv))
!
;;; Definitions for various special forms and macros.

(defspec quote (obj) (venv fenv benv genv) obj)

(defspec function (fn) (venv fenv benv genv)
  (loop (cond ((consp fn)
	       (cond ((eq (car fn) 'lambda)
		      (return (make-interpreted-closure :function fn
							:venv venv
							:fenv fenv
							:benv benv
							:genv genv)))
		     (t (setq fn (cerror :invalid-function
					 "~S is not a valid argument for FUNCTION"
					 fn)))))
	      ((symbolp fn)
	       (let ((slot (assq fn fenv)))
		 (cond (slot
			(case (cadr slot)
			  (macro (setq fn (cerror :invalid-function
						  "The name ~S is invalid for FUNCTION: it names a macro"
						  fn)))
			  (function (return (cddr slot)))
			  (t <implementation-error>)))
		       ((fboundp fn)
			(cond ((special-form-p fn)
			       (setq fn (cerror :invalid-function
						"The symbol ~S is invalid for FUNCTION: it names a special form"
						fn)))
			      ((macro-p fn)
			       (setq fn (cerror :invalid-function
						"The symbol ~S is invalid for FUNCTION: it names a macro"
						fn)))
			      (t (setq fn (symbol-function fn)))))
		       (t (setq fn (cerror :invalid-function
					   "The symbol ~S has no function definition"
					   fn))))))
	      (t (setq fn (cerror :invalid-function
				  "~S is not a valid argument for FUNCTION"
				  fn))))))

(defspec if (pred con &optional alt) (venv fenv benv genv)
  (if (%eval pred venv fenv benv genv)
      (%eval con venv fenv benv genv)
      (%eval alt venv fenv benv genv)))

;;; The BLOCK construct provides a PROGN with a named contour around it.
;;; It is interpreted by first putting an entry onto BENV, consisting
;;; of a 1-list of the name.  This list cell serves as a catch tag.
;;; Then the body is executed.
;;; If a RETURN-FROM is interpreted, a throw occurs.  If the BLOCK
;;; construct is exited for any reason (including falling off the end, which
;;; returns the results of evaluating the last form in the body), the cdr of
;;; the entry is clobbered to be INVALID, to indicate that that particular
;;; entry is no longer valid for RETURN-FROM.

(defspec block (name &body body) (venv fenv benv genv)
  (let ((slot (list name)))
    (unwind-protect (catch slot
		      (%evprogn body venv fenv (cons slot benv) genv))
		    (rplacd slot 'invalid))))

(defspec return (form) (venv fenv benv genv)
  (let ((slot (assq nil benv)))
    (cond ((null slot) (ferror ???<unseen-block-name>))
	  ((eq (cdr slot) 'invalid) (ferror ???<block-name-no-longer-valid>))
	  (t (throw slot (%eval form venv fenv benv genv))))))

(defspec return-from (name form) (venv fenv benv genv)
  (let ((slot (assq name benv)))
    (cond ((null slot) (ferror ???<unseen-block-name>))
	  ((eq (cdr slot) 'invalid) (ferror ???<block-name-no-longer-valid>))
	  (t (throw slot (%eval form venv fenv benv genv))))))
!
(defmacro prog (vars &rest body)
  (do ((b body (cdr b))
       (decls '() (cons (car b) decls)))
      ((or (endp b)
	   (atom (car b))
	   (not (eq (caar b) 'declare)))
       `(let ,vars ,@(nreverse decls) (block nil (tagbody ,@b))))))

;;; The TAGBODY construct provides a body with GO tags in it.
;;; It is interpreted by first putting one entry onto GENV for
;;; every tag in the body; doing this ahead of time saves searching
;;; at GO time.  A unique cons whose car is NIL is constructed for
;;; use as a unique catch tag.  Then the body is executed.
;;; If a GO is interpreted, a throw occurs, sending as the thrown
;;; value the point in the body after the relevant tag.
;;; If the TAGBODY construct is exited for any reason (including
;;; falling off the end, which produces the value NIL), the car of
;;; the unique marker is clobbered to be INVALID, to indicate that
;;; tags associated with that marker are no longer valid.

(defspec tagbody (&rest body) (venv fenv benv genv)
  (do ((b body (cdr b))
       (marker (list nil)))
      ((endp p)
       (block exit
	 (unwind-protect
	  (loop (setq body
		      (catch marker
			(do ((b body (cdr b)))
			    ((endp b) (return-from exit nil))
			  (unless (atom (car b))
			    (%eval (car b) venv fenv benv genv))))))
	  (rplaca marker 'invalid))))
    (when (atom (car b))
      (push (list* (car b) marker (cdr b)) genv))))

(defspec go (tag) (venv fenv benv genv)
  (let ((slot (assq tag genv)))
    (cond ((null slot) (ferror ???<unseen-go-tag>))
	  ((eq (caadr slot) 'invalid) (ferror ???<go-tag-no-longer-valid>))
	  (t (throw (cadr slot) (cddr slot))))))
---------------------------------------------------------------
;;; This version uses some special variables to avoid passing stuff around.

;;; This evaluator splits the lexical environment into four
;;; logically distinct entities:
;;;	VENV = lexical variable environment
;;;	FENV = lexical function and macro environment
;;;	BENV = block name environment
;;;	GENV = go tag environment
;;; Each environment is an a-list.  It is never the case that
;;; one can grow and another shrink simultaneously; the four
;;; parts could be united into a single a-list.  The four-part
;;; division saves consing and search time.
;;;
;;; In this implementation, the four environment parts are normally
;;; kept in four special variables %VENV%, %FENV%, %BENV%, and %GENV%.
;;; (These are internal to the implementation, and are not meant to
;;; be user-accessible.)

(defvar %venv% nil)
(defvar %fenv% nil)
(defvar %benv% nil)
(defvar %genv% nil)

;;; Each entry in VENV has one of two forms: (VAR VALUE) or (VAR).
;;; The first indicates a lexical binding of VAR to VALUE, and the
;;; second indicates a special binding of VAR (implying that the
;;; special value should be used).
;;;
;;; Each entry in FENV looks like (NAME TYPE . FN), where NAME is the
;;; functional name, TYPE is either FUNCTION or MACRO, and FN is the
;;; function or macro-expansion function, respectively.  Entries of
;;; type FUNCTION are made by FLET and LABELS; those of type MACRO
;;; are made by MACROLET.
;;;
;;; Each entry in BENV looks like (NAME), where NAME is the name
;;; of the block.  The cons cell that is the entry is used as a
;;; catch tag for implementing RETURN-FROM.  If the entry has been
;;; clobbered to look like (NAME . INVALID), then the block has
;;; been exited, and a return to that block is an error.
;;;
;;; Each entry in GENV looks like (TAG MARKER . BODY), where TAG is
;;; a go tag, MARKER is a unique cons used as a catch tag, and BODY
;;; is the statement sequence that follows the go tag.  If the car of
;;; MARKER, normally NIL, has been clobbered to be INVALID, then
;;; the tag body has been exited, and a go to that tag is an error.

;;; An interpreted-lexical-closure contains a function (normally a
;;; lambda-expression) and the lexical environment.

(defstruct interpreted-lexical-closure function venv fenv benv genv)


;;; The EVALHOOK feature allows a user-supplied function to be called
;;; whenever a form is to be evaluated.  The presence of the lexical
;;; environment requires an extension of the feature as it is defined
;;; in MacLISP.  Here, the user hook function must accept not only
;;; the form to be evaluated, but also the components of the lexical
;;; environment; these must then be passed verbatim to EVALHOOK or
;;; *EVAL in order to perform the evaluation of the form correctly.
;;; The precise number of components should perhaps be allowed to be
;;; implementation-dependent, so it is probably best to require the
;;; user hook function to accept arguments as (FORM &REST ENV) and
;;; then to perform evaluation by (APPLY #'EVALHOOK FORM HOOKFN ENV),
;;; for example.

(defvar *evalhook* nil)

(defun evalhook (exp hookfn %venv% %fenv% %benv% %genv%)
  (let ((*evalhook* hookfn))
	(%eval exp)))

(defun eval (exp)
  (*eval exp nil nil nil nil))

(defun *eval (exp %venv% %fenv% %benv% %genv%)
  (%eval exp))
!
;;; Function names beginning with "%" are intended to be internal
;;; and not defined in the Common LISP white pages.

;;; %EVAL is the main evaluation function.  It evaluates EXP in
;;; the current lexical environment, assumed to be in %VENV%, etc.

(defun %eval (exp)
  (if *evalhook*
      (let ((hookfn *evalhook*) (*evalhook* nil))
	(funcall hookfn exp %venv% %fenv% %benv% %genv%))
      (typecase exp
	;; A symbol is first looked up in the lexical variable environment.
	(symbol (let ((slot (assq exp %venv%)))
		  (cond ((and slot (not (null (cdr slot))))
			 (cadr slot))
			((boundp exp) (symbol-value exp))
			(t (cerror :unbound-variable
				   "The symbol ~S has no value"
				   exp)))))
	;; Numbers, strings, bit-vectors, and characters self-evaluate.
	((or number string bit-vector character) exp)
	;; Conses require elaborate treatment based on the car.
	(cons (typecase (car exp)
		;; A symbol is first looked up in the lexical function environment.
		;; This lookup is cheap if the environment is empty, a common case.
		(symbol
		 (let ((fn (car exp)))
		   (loop (let ((slot (assq fn %fenv%)))
			   (unless (null slot)
			     (return (case (cadr slot)
				       (macro (%eval (%macroexpand
						      (cddr slot)
						      (if (eq fn (car exp))
							  exp
							  (cons fn (cdr exp))))))
				       (function (%apply (cddr slot)
							 (%evlis (cdr exp))))
				       (t <implementation-error>)))))
			 ;; If not in lexical function environment,
			 ;;  try the definition cell of the symbol.
			 (when (fboundp fn)
			   (return (cond ((special-form-p fn)
					  (%invoke-special-form fn (cdr exp)))
					 ((macro-p fn)
					  (%eval (%macroexpand
						  (get-macro-function (symbol-function fn))
						  (if (eq fn (car exp))
						      exp
						      (cons fn (cdr exp))))))
					 (t (%apply (symbol-function fn)
						    (%evlis (cdr exp)))))))
			 (setq fn
			       (cerror :undefined-function
				       "The symbol ~S has no function definition"
				       fn))
			 (unless (symbolp fn)
			   (return (%apply fn (%evlis (cdr exp))))))))
		;; A cons in function position must be a lambda-expression.
		;; Note that the construction of a lexical closure is avoided here.
		(cons (apply (car exp) (%evlis (cdr exp))))
		(t (%eval (cerror :invalid-form
				  "Cannot evaluate the form ~S: function position has invalid type ~S"
				  exp (type-of (car exp)))))))
	(t (%eval (cerror :invalid-form
			  "Cannot evaluate the form ~S: invalid type ~S"
			  exp (type-of exp)))))))
!
;;; Given a list of forms, evaluate each and return a list of results.

(defun %evlis (forms)
  (mapcar #'(lambda (form) (%eval form)) forms))

;;; Given a list of forms, evaluate each, discarding the results of
;;; all but the last, and returning all results from the last.

(defun %evprogn (body)
  (if (endp body) nil
      (do ((b body (cdr b)))
	  ((endp (cdr b))
	   (%eval (car b)))
	(%eval (car b)))))

;;; APPLY takes a function, a number of single arguments, and finally
;;; a list of all remaining arguments.  The following song and dance
;;; attempts to construct efficiently a list of all the arguments.

(defun apply (fn firstarg &rest args*)
  (let ((%venv% nil) (%fenv% nil) (%benv% nil) (%genv% nil))
    (%apply fn
	    (cond ((null args*) firstarg)
		  ((null (cdr args*)) (cons firstarg (car args*)))
		  (t (do ((x args* (cdr x))
			  (z (cddr args*) (cdr z)))
			 ((null z)
			  (rplacd x (cadr x))
			  (cons firstarg (car args*)))))))))
!
;;; %APPLY does the real work of applying a function to a list of arguments.

(defun %apply (fn args)
  (typecase fn
    ;; For a compiled function, an implementation-dependent "spread"
    ;;  operation and invocation is required.
    (compiled-function (%invoke-compiled-function fn args))
    ;; The same goes for a compiled closure over lexical variables.
    (compiled-lexical-closure (%invoke-compiled-lexical-closure fn args))
    ;; The treatment of interpreted lexical closures is elucidated fully here.
    (interpreted-lexical-closure
     (let ((%venv% (interpreted-lexical-closure-venv fn))
	   (%fenv% (interpreted-lexical-closure-fenv fn))
	   (%benv% (interpreted-lexical-closure-benv fn))
	   (%genv% (interpreted-lexical-closure-genv fn)))
       (%lambda-apply (interpreted-lexical-closure-function fn) args)))
    ;; For a symbol, the function definition is used, if it is a function.
    (symbol (%apply (cond ((not (fboundp fn))
			   (cerror :undefined-function
				   "The symbol ~S has no function definition"
				   fn))
			  ((special-form-p fn)
			   (cerror :invalid-function
				   "The symbol ~S cannot be applied: it names a special form"
				   fn))
			  ((macro-p fn)
			   (cerror :invalid-function
				   "The symbol ~S cannot be applied: it names a macro"
				   fn))
			  (t (symbol-function fn)))
		    args))
    (cons (if (eq (car fn) 'lambda)
	      (%lambda-apply fn args)
	      (%apply (cerror :invalid-function
			      "~S is not a valid function"
			      fn)
		      args)))
    (t (%apply (cerror :invalid function
		       "~S has an invalid type ~S for a function"
		       fn (type-of fn))
	       args))))
!
;;; %LAMBDA-APPLY is the hairy part, that takes care of applying
;;; a lambda-expression in a given lexical environment to given
;;; arguments.  The complexity arises primarily from the processing
;;; of the parameter list.
;;;
;;; If at any point the lambda-expression is found to be malformed
;;; (typically because of an invalid parameter list), or if the list
;;; of arguments is not suitable for the lambda-expression, a correctable
;;; error is signalled; correction causes a throw to be performed to
;;; the tag %LAMBDA-APPLY-RETRY, passing back a (possibly new)
;;; lambda-expression and a (possibly new) list of arguments.
;;; The application is then retried.  If the new lambda-expression
;;; is not really a lambda-expression, then %APPLY is used instead of
;;; %LAMBDA-APPLY.
;;;
;;; In this evaluator, PROGV is used to instantiate variable bindings
;;; (though its use is embedded with a macro called %varbind).
;;; The throw that precedes a retry will cause special bindings to
;;; be popped before the retry.

(defun %lambda-apply (lexp args)
  (multiple-value-bind (newfn newargs)
		       (catch '%lambda-apply-retry
			 (return-from %lambda-apply
			   (let ((%venv% %venv%))
			     (%lambda-apply-1 lexp args))))
    (if (and (consp lexp) (eq (car lexp) 'lambda))
	(%lambda-apply newfn newargs)
	(%apply newfn newargs))))

;;; Calling this function will unwind all special variables
;;; and cause FN to be applied to ARGS in the original lexical
;;; and dynamic environment in force when %LAMBDA-APPLY was called.

(defun %lambda-apply-retry (fn args)
  (throw '%lambda-apply-retry (values fn args)))

(defvar %lexp%)
(defvar %oldargs%)

;;; This function is convenient when the lambda expression is found
;;; to be malformed.  REASON should be a string explaining the problem.

(defun %bad-lambda-exp (reason)
  (%lambda-apply-retry
   (cerror :invalid-function
	   "Improperly formed lambda-expression ~S: ~A"
	   %lexp% reason)
   %oldargs%))

;;; (%varbind VAR VALUE . BODY) evaluates VAR to produce a symbol name
;;; and VALUE to produce a value.  If VAR is determined to have been
;;; declared special (as indicated by the current binding of the variable
;;; SPECIALS, which should be a list of symbols, or by a SPECIAL property),
;;; then a special binding is established using PROGV.  Otherwise an
;;; entry is pushed onto the a-list presumed to be in the variable VENV.

;;; The CONSTANTP test ideally is true for any constant symbol;
;;; it should at least check for T, NIL, and keywords.

(defmacro %varbind (var value &body body)
  (let ((xvar (gensym)) (xvalue (gensym)))
    `(let ((,xvar ,var) (,xvalue ,value))
       (loop (when (not (constantp ,xvar)) (return))
	     (setq ,xvar (cerror :invalid-variable
				 "~S is a constant and may not be bound"
				 ,xvar)))
       (let ((specp (or (memq ,xvar %specials%) (get ,xvar 'special))))
	 (progv (and specp (list ,xvar)) (and specp (list ,xvalue))
		(push (if specp (list ,xvar) (list ,xvar ,xvalue)) venv)
		,@body)))))

;;; %LAMBDA-KEYWORD-P is true iff X (which must be a symbol)
;;; has a name beginning with an ampersand.

(defun %lambda-keyword-p (x)
  (char= #\& (char 0 (symbol-pname x))))
!
;;; %LAMBDA-APPLY-1 is responsible for verifying that LEXP is
;;; a lambda-expression, for extracting a list of all variables
;;; declared SPECIAL in DECLARE forms, and for finding the
;;; body that follows any DECLARE forms.

(defvar %specials%)
(defvar %form%)
(defvar %body%)

(defun %lambda-apply-1 (%lexp% %oldargs%)
  (cond ((or (not (consp %lexp%))
	     (not (eq (car %lexp%) 'lambda))
	     (atom (cdr %lexp%))
	     (not (listp (cadr %lexp%))))
	 (%bad-lambda-exp "improper lambda-expression"))
	(t (do ((%body% (cddr %lexp%) (cdr %body%))
		(%specials% '()))
	       ((or (endp %body%)
		    (not (listp (car %body%))))
		(let ((%form% nil))
		  (%bind-required (cadr %lexp%) %oldargs%)))
	     (let ((%form% (macroexpand (car %body%))))
	       (cond ((or (not (consp %form%))
			  (not (eq (car %form%) 'declare)))
		      (return (%bind-required (cadr %lexp%) %oldargs%)))
		     (t (dolist (decl (cdr %form%))
			  (when (eq (car decl) 'special)
			    (setq %specials%
				  (if (null %specials%)	;Avoid consing
				      (cdar decl)
				      (append (cdar decl) %specials%))))))))))))

;;; %BIND-REQUIRED handles the pairing of arguments to required parameters.
;;; Error checking is performed for too few or too many arguments.
;;; If a lambda-list keyword is found, %TRY-OPTIONAL is called.
;;; Here, as elsewhere, if the binding process terminates satisfactorily
;;; then the body is evaluated using %EVPROGN in the newly constructed
;;; dynamic and lexical environment.

(defun %bind-required (varlist args)
  (cond ((endp varlist)
	 (if (null args)
	     (%lambda-evprogn%)
	     (%lambda-apply-retry lexp
				  (cerror :too-many-arguments
					  "Too many arguments for function ~S: ~S"
					  %lexp% %oldargs%))))
	((not (symbolp (car varlist)))
	 (%bad-lambda-exp "required parameter name not a symbol"))
	((%lambda-keyword-p (car varlist))
	 (%try-optional varlist args))
	((null args)
	 (%lambda-apply-retry lexp 
			      (cerror :too-few-arguments
				      "Too few arguments for function ~S: ~S"
				      %lexp% %oldargs%)))
	  (t (%varbind (car varlist) (car args)
			(%bind-required (cdr varlist) (cdr args))))))
!
;;; %TRY-OPTIONAL determines whether the lambda-list keyword &OPTIONAL
;;; has been found.  If so, optional parameters are processed; if not,
;;; the buck is passed to %TRY-REST.

(defun %try-optional (varlist args)
  (cond ((eq (car varlist) '&optional)
	 (%bind-optional (cdr varlist) args))
	(t (%try-rest varlist args))))

;;; %BIND-OPTIONAL determines whether the parameter list is exhausted.
;;; If not, it parses the next specifier.

(defun %bind-optional (varlist args)
  (cond ((endp varlist)
	 (if (null args)
	     (%lambda-evprogn%)
	     (%lambda-apply-retry lexp
				  (cerror :too-many-arguments
					  "Too many arguments for function ~S: ~S"
					  %lexp% %oldargs%))))
	(t (let ((varspec (car varlist)))
	     (cond ((symbolp varspec)
		    (if (%lambda-keyword-p varspec)
			(%try-rest varlist args)
			(%process-optional varlist args varspec nil nil)))
		   ((and (consp varspec)
			 (symbolp (car varspec))
			 (listp (cdr varspec))
			 (or (endp (cddr varspec))
			     (and (symbolp (caddr varspec))
				  (not (endp (caddr varspec)))
				  (endp (cdddr varspec)))))
		    (%process-optional varlist args
				       (car varspec)
				       (cadr varspec)
				       (caddr varspec)))
		   (t (%bad-lambda-exp "malformed optional parameter specifier")))))))

;;; %PROCESS-OPTIONAL takes care of binding the parameter,
;;; and also the supplied-p variable, if any.

(defun %process-optional (varlist args var init varp)
  (let ((value (if (null args) (%eval init) (car args))))
    (%varbind var value
      (if varp
	  (%varbind varp (not (null args))
	    (%bind-optional (cdr varlist) (cdr args)))
	  (%bind-optional (cdr varlist) (cdr args))))))
!
;;; %TRY-REST determines whether the lambda-list keyword &REST
;;; has been found.  If so, the rest parameter is processed;
;;; if not, the buck is passed to %TRY-KEY, after a check for
;;; too many arguments.

(defun %try-rest (varlist args)
  (cond ((eq (car varlist) '&rest)
	 (%bind-rest (cdr varlist) args))
	((and (not (eq (car varlist) '&key))
	      (not (null args)))
	 (%lambda-apply-retry lexp
			      (cerror :too-many-arguments
				      "Too many arguments for function ~S: ~S"
				      %lexp% %oldargs%)))
	(t (%try-key varlist args))))

;;; %BIND-REST ensures that there is a parameter specifier for
;;; the &REST parameter, binds it, and then evaluates the body or
;;; calls %TRY-KEY.

(defun %bind-rest (varlist args)
  (cond ((or (endp varlist)
	     (not (symbolp (car varlist))))
	 (%bad-lambda-exp "missing rest parameter specifier"))
	(t (%varbind (car varlist) args
	     (cond ((endp (cdr varlist))
		    (%lambda-evprogn%))
		   ((and (symbolp (cadr varlist))
			 (%lambda-keyword-p (cadr varlist)))
		    (%try-key (cdr varlist) args))
		   (t (%bad-lambda-exp "malformed after rest parameter specifier")))))))
!
;;; %TRY-KEY determines whether the lambda-list keyword &KEY
;;; has been found.  If so, keyword parameters are processed;
;;; if not, the buck is passed to %TRY-AUX.

(defun %try-key (varlist args)
  (cond ((eq (car varlist) '&key)
	 (%bind-key (cdr varlist) args nil))
	(t (%try-aux varlist))))

;;; %BIND-KEY determines whether the parameter list is exhausted.
;;; If not, it parses the next specifier.

(defun %bind-key (varlist args keys)
  (cond ((endp varlist)
	 (%check-for-bad-keywords args keys)
	 (%lambda-evprogn%))
	(t (let ((varspec (car varlist)))
	     (cond ((symbolp varspec)
		    (if (%lambda-keyword-p varspec)
			(cond ((not (eq varspec '&allow-other-keywords))
			       (%check-for-bad-keywords args keys)
			       (%try-aux varlist))
			      ((endp (cdr varlist))
			       (%lambda-evprogn%))
			      ((%lambda-keyword-p (cadr varlist))
			       (%try-aux (cdr varlist)))
			      (t (%bad-lambda-exp "invalid after &ALLOW-OTHER-KEYWORDS")))
			(%process-key varlist args keys
				      (intern (symbol-print-name varspec) keyword-package)
				      varspec nil nil)))
		   ((and (consp varspec)
			 (or (symbolp (car varspec))
			     (and (consp (car varspec))
				  (consp (cdar varspec))
				  (symbolp (cadar varspec))
				  (endp (cddar varspec))))
			 (listp (cdr varspec))
			 (or (endp (cddr varspec))
			     (and (symbolp (caddr varspec))
				  (not (endp (caddr varspec)))
				  (endp (cdddr varspec)))))
		    (%process-key varlist args keys
				  (if (consp (car varspec))
				      (caar varspec)
				      (intern (symbol-print-name (car varspec)) keyword-package))
				  (if (consp (car varspec))
				      (cadar varspec)
				      (car varspec))
				  (cadr varspec)
				  (caddr varspec)))
		   (t (%bad-lambda-exp "malformed keyword parameter specifier")))))))

;;; Optional error check for bad keywords.

(defun %check-for-bad-keywords (args keys)
  (do ((a args (cddr a)))
      ((endp args))
    (unless (memq (car a) keys)
      (cerror :unexpected-keyword
	      "Keyword not expected by function ~S: ~S"
	      %lexp% (car a)))))

;;; %PROCESS-KEY takes care of binding the parameter,
;;; and also the supplied-p variable, if any.

(defun %process-key (varlist args keys kwd var init varp)
  (do ((a args (cddr a)))
      ((endp a)
       (%process-key-1 varlist args keys kwd var init varp (%eval init) nil))
    (when (eq (car a) kwd)
      (return (%process-key-1 varlist args keys kwd var init varp (cadr a) t)))))

(defun %process-key-1 (varlist args keys kwd var init varp value suppliedp)
  (%varbind var value
    (if varp
	(%varbind varp suppliedp
	  (%bind-key varlist args (cons kwd keys)))
	(%bind-key varlist args (cons kwd keys)))))
!
;;; %TRY-AUX determines whether the keyword &AUX
;;; has been found.  If so, auxiliary variables are processed;
;;; if not, an error is signalled.

(defun %try-aux (varlist)
  (cond ((eq (car varlist) '&aux)
	 (%bind-aux (cdr varlist)))
	(t (%bad-lambda-exp "unknown or misplaced lambda-list keyword"))))

;;; %BIND-AUX determines whether the parameter list is exhausted.
;;; If not, it parses the next specifier.

(defun %bind-aux (varlist)
  (cond ((endp varlist)
	 (%lambda-evprogn%))
	(t (let ((varspec (car varlist)))
	     (cond ((symbolp varspec)
		    (if (%lambda-keyword-p varspec)
			(%bad-lambda-exp "unknown or misplaced lambda-list keyword")
			(%process-aux varlist varspec nil)))
		   ((and (consp varspec)
			 (symbolp (car varspec))
			 (listp (cdr varspec))
			 (endp (cddr varspec)))
		    (%process-aux varlist (car varspec) (cadr varspec)))
		   (t (%bad-lambda-exp "malformed aux variable specifier")))))))

;;; %PROCESS-AUX takes care of binding the auxiliary variable.

(defun %process-aux (varlist var init)
    (%varbind var (and init (%eval init))
       (%bind-aux varlist)))

(defun %lambda-evprogn ()
  (unless (null %form%) (%eval %form%))
  (%evprogn %body%))
!
;;; Definitions for various special forms and macros.

(defspec quote (obj) obj)

(defspec function (fn)
  (loop (cond ((consp fn)
	       (cond ((eq (car fn) 'lambda)
		      (return (make-interpreted-closure :function fn
							:venv %venv%
							:fenv %fenv%
							:benv %benv%
							:genv %genv%)))
		     (t (setq fn (cerror :invalid-function
					 "~S is not a valid argument for FUNCTION"
					 fn)))))
	      ((symbolp fn)
	       (let ((slot (assq fn fenv)))
		 (cond (slot
			(case (cadr slot)
			  (macro (setq fn (cerror :invalid-function
						  "The name ~S is invalid for FUNCTION: it names a macro"
						  fn)))
			  (function (return (cddr slot)))
			  (t <implementation-error>)))
		       ((fboundp fn)
			(cond ((special-form-p fn)
			       (setq fn (cerror :invalid-function
						"The symbol ~S is invalid for FUNCTION: it names a special form"
						fn)))
			      ((macro-p fn)
			       (setq fn (cerror :invalid-function
						"The symbol ~S is invalid for FUNCTION: it names a macro"
						fn)))
			      (t (setq fn (symbol-function fn)))))
		       (t (setq fn (cerror :invalid-function
					   "The symbol ~S has no function definition"
					   fn))))))
	      (t (setq fn (cerror :invalid-function
				  "~S is not a valid argument for FUNCTION"
				  fn))))))

(defspec if (pred con &optional alt)
  (if (%eval pred) (%eval con) (%eval alt)))

;;; The BLOCK construct provides a PROGN with a named contour around it.
;;; It is interpreted by first putting an entry onto BENV, consisting
;;; of a 1-list of the name.  This list cell serves as a catch tag.
;;; Then the body is executed.
;;; If a RETURN-FROM is interpreted, a throw occurs.  If the BLOCK
;;; construct is exited for any reason (including falling off the end, which
;;; returns the results of evaluating the last form in the body), the cdr of
;;; the entry is clobbered to be INVALID, to indicate that that particular
;;; entry is no longer valid for RETURN-FROM.

(defspec block (name &body body)
  (let ((slot (list name)))
    (unwind-protect (catch slot
		      (let ((%benv% (cons slot %benv%)))
			(%evprogn body)))
		    (rplaca (cdr slot) 'invalid))))

(defspec return (form)
  (let ((slot (assq nil %benv%)))
    (cond ((null slot) (ferror ???<unseen-block-name>))
	  ((eq (cdr slot) 'invalid) (ferror ???<block-name-no-longer-valid>))
	  (t (throw slot (%eval form))))))

(defspec return-from (name form)
  (let ((slot (assq name %benv%)))
    (cond ((null slot) (ferror ???<unseen-block-name>))
	  ((eq (cdr slot) 'invalid) (ferror ???<block-name-no-longer-valid>))
	  (t (throw slot (%eval form))))))
!
(defmacro prog (vars &rest body)
  (do ((b body (cdr b))
       (decls '() (cons (car b) decls)))
      ((or (endp b)
	   (atom (car b))
	   (not (eq (caar b) 'declare)))
       `(let ,vars ,@(nreverse decls) (block nil (tagbody ,@b))))))

;;; The TAGBODY construct provides a body with GO tags in it.
;;; It is interpreted by first putting one entry onto GENV for
;;; every tag in the body; doing this ahead of time saves searching
;;; at GO time.  A unique cons whose car is NIL is constructed for
;;; use as a unique catch tag.  Then the body is executed.
;;; If a GO is interpreted, a throw occurs, sending as the thrown
;;; value the point in the body after the relevant tag.
;;; If the TAGBODY construct is exited for any reason (including
;;; falling off the end, which produces the value NIL), the car of
;;; the unique marker is clobbered to be INVALID, to indicate that
;;; tags associated with that marker are no longer valid.

(defspec tagbody (&rest body)
  (let ((%genv% %genv%))
    (do ((b body (cdr b))
	 (marker (list nil)))
	((endp p)
	 (block exit
	   (unwind-protect
	    (loop (setq body
			(catch marker
			  (do ((b body (cdr b)))
			      ((endp b) (return-from exit nil))
			    (unless (atom (car b))
			      (%eval (car b)))))))
	    (rplaca marker 'invalid))))
      (when (atom (car b))
	(push (list* (car b) marker (cdr b)) %genv%)))))

(defspec go (tag)
  (let ((slot (assq tag %genv%)))
    (cond ((null slot) (ferror ???<unseen-go-tag>))
	  ((eq (caadr slot) 'invalid) (ferror ???<go-tag-no-longer-valid>))
	  (t (throw (cadr slot) (cddr slot))))))
-------


Date: 10 November 1982 0006-EST (Wednesday)
From: Guy.Steele at CMU-10A
To: common-lisp at SU-AI
Subject: Quick query about CONSTANTP

Sometimes it is useful to know whether a symbol is a constant
(for example, T, NIL, PI, MOST-POSITIVE-FIXNUM, :DIRECTORY, and so on).
How about a function CONSTANTP for this purpose?  (In particular,
the evaluator needs it for error-checking.)  It could be implemented
as a property-list chek, though for speed it would be nice if an
implementation could dig up a bit in the symbol itself.  This bit
would be set by DEFCONSTANT and when interning in the keyword package.
--Guy


Date: 10 November 1982 0006-EST (Wednesday)
From: Guy.Steele at CMU-10A
To: common-lisp at SU-AI
Subject: Quick query about CONSTANTP

Sometimes it is useful to know whether a symbol is a constant
(for example, T, NIL, PI, MOST-POSITIVE-FIXNUM, :DIRECTORY, and so on).
How about a function CONSTANTP for this purpose?  (In particular,
the evaluator needs it for error-checking.)  It could be implemented
as a property-list chek, though for speed it would be nice if an
implementation could dig up a bit in the symbol itself.  This bit
would be set by DEFCONSTANT and when interning in the keyword package.
--Guy


Date:  9 November 1982 2233-EST (Tuesday)
From: Guy.Steele at CMU-10A
To: common-lisp at SU-AI
Subject: Named lambdas

In response to DILL's message: actually, NAMED-LAMBDA is not
presently in Common LISP, though Spice LISP does support it.
Should NAMED-LAMBDA be in Common LISP?
--Guy


Date:  9 November 1982 2055-EST (Tuesday)
From: David.Dill at CMU-10A (L170DD60)
To: common-lisp at su-ai
Subject: mini-ballot
Message-Id: <09Nov82 205523 DD60@CMU-10A>

1. I am not convinced that the usefulness of SETF-like defun syntax
for putting the things where you want them, or for debugging, justifies
the extra hair and ugliness.  A case could be made that it's sociable
to name your functions if you want it to be easy to debug code that calls
them.  In common lisp, you can even have named lambda expressions
without doing a DEFUN.

2. Since the special declarations generated by DEFVAR are pervasive, it
is relatively easy to bind a special accidentally, thinking that it's a
local variable.  The best solution to this sort of problem, and a lot
of others, would be to distinguish syntactically special bindings and
references from lexical ones.  Otherwise, a special/lexical naming
convention seems like the best thing (e.g. if the variable starts with
an "S", it's special).




Date:  9 Nov 1982 1700-MST
From: Eric Benson <BENSON at UTAH-20>
Subject: #'(LAMBDA ...) ==> CODE
To: KMP at MIT-MC
cc: Common-Lisp at SU-AI
In-Reply-To: Your message of 8-Nov-82 1853-MST

I believe any occurence of (FUNCTION (LAMBDA ...)) in a file at the top
level should be compiled when the file is compiled.  In fact any
occurences which are created by macroexpansion at the top level should
be compiled as well.  Are these to be called "subrs" or "code objects"
or what?
-------


Date: 8 November 1982 20:54-EST
From: Kent M. Pitman <KMP at MIT-MC>
Subject:  Mini-ballot
To: Guy.Steele at CMU-10A
cc: common-lisp at SU-AI

(1) My experience with LispM function specs leads me to believe that 
    something along these lines is worthwhile. I waver between saying "yes"
    to (c) because I am not firm on the details and it might be better to
    wait and (a) because I know it's a valuable tool and I've seen what 
    happens when you don't have it. With regard to (b), I object rather 
    strongly on the following counts:

     * I would prefer that they be statically analyzable. I can figure out
       at code analysis time (eg, compile time or at the time I'm reading 
       someone else's code) what (DEFUN (GET 'FOO 'BAR) ...) means. And have
       a pretty good idea of what the code is trying to say. But if the
       person does (DEFUN (GET FOO BAR) ...), I can analyze this code only
       formally and have no good feeling for what it's going to do. 
       I think definitional forms should try to stay simple and the programmer
       should write (SETF (GET FOO BAR) #'(LAMBDA ...)) in the few cases 
       where he needs it.

       I would be uncomfortable with special-casing (ie, requiring) QUOTE
       in this kind of form, so restricting things to the (GET 'FOO 'BAR)
       case will not make me feel better.

     * If (DEFUN (GET 'FOO 'BAR) (X) X) means (SETF (GET 'FOO 'BAR)
						    #'(LAMBDA (X) X))
       then (DEFUN F (X) X) should mean (SETF F #'(LAMBDA (X) X)) and
       not (SETF #'F #'(LAMBDA (X) ...)). This incompatibility bothers me.

    I'd like to see a concrete proposal for exactly what LispM style stuff
    we'd put in before I vote for (a) over (c), however.

    A more conservative alternative is to go the Maclisp route and say that
    the useful case of DEFUN'ing properties can be done by
	(DEFUN (sym prop) bvl . body)
    and not go for either the function spec or the SETF approach for now
    until more thinking has been done. This syntax would be fairly easily
    upgraded later if people were encouraged to never use a sym which was
    on the keyword package in such a DEFUN so that later upgrading if desired
    could be done in an upward compatible fashion.
    This is preferable in my mind to HEDRICK's (DEFUN-PROP ...) proposal 
    because it is not as verbose and it is upward compatible in a way that
    doesn't introduce arbitrarily many new operators.

(2) I guess I buy the argument that constants oughtn't have *'s around them.
    Knowing by looking at a thing whether it's intended to be bound is 
    certainly a useful property.


Date: 8 November 1982 20:53-EST
From: Kent M. Pitman <KMP at MIT-MC>
To: Benson at UTAH-20
cc: Common-Lisp at SU-AI

In most current Lisp implementations, one cannot write
 (SETF (GET 'FOO 'BAR) #'(LAMBDA ...))
unless he doesn't mind #'(LAMBDA ...) not being compiled. Toplevel
non-definitional forms are not compiled in Maclisp or LispM, for example.
Hence, without the existence of (DEFUN (:PROPERTY FOO BAR) ...), one
would have to write
   (DEFUN something ...)
   (SETF (GET 'FOO 'BAR) #'something)
which is a bit tedious.

I don't know if Common-Lisp has taken a stand on whether toplevel LAMBDAs
like this one get compiled. Discussion came up about it before. It's related
to the (PROGN 'COMPILE ...) issue and should probably be defined. I'm 
personally in favor of avoiding a (PROGN 'COMPILE ...) primitive
and compiling all toplevel forms. In such case, the SETF you show would be
technically correct, but it lacks the declarative appeal of being integrated
into a DEFUN.

The question, I guess, comes down to whether you think of what you're
doing as defining a function with a complex name or creating an
anonymous function and putting it in a complex place. I think there is
need for both and the two issues should be kept separate.


Date: Tuesday, 9 November 1982  10:49-EST
Sender: ZVONA at MIT-OZ
From: ZVONA at MIT-MC
To:   Guy.Steele at CMU-10A
Cc:   common-lisp at SU-AI
Subject: function specs
In-reply-to: The message of 9 Nov 1982 0245-EST () from Guy.Steele at CMU-10A

    However, the analogy above also indicates to me that function specs
    like (:PROPERTY FOO BAR) really are a kind of generalized name for
    a function.  If so, orthogonality demands that they be permissible
    in a lot of places where currently I believe they are not in Lisp Machine
    LISP:
    (a) In FUNCTION:  #'(:PROPERTY FOO BAR) ought to be legal.
    (b) As an argument to APPLY:  (APPLY '(:PROPERTY FOO BAR) args)
    (c) In ordinary function calls!  ((:PROPERTY FOO BAR) 5 7 :START 3 :END 5)

Empirical evidence:

I've seen naive users trying to put function specs in places like these,
and losing, and wondering what they did wrong.


Date: Tuesday, 9 November 1982  10:49-EST
Sender: ZVONA at MIT-OZ
From: ZVONA at MIT-MC
To:   Guy.Steele at CMU-10A
Cc:   common-lisp at SU-AI
Subject: function specs
In-reply-to: The message of 9 Nov 1982 0245-EST () from Guy.Steele at CMU-10A

    However, the analogy above also indicates to me that function specs
    like (:PROPERTY FOO BAR) really are a kind of generalized name for
    a function.  If so, orthogonality demands that they be permissible
    in a lot of places where currently I believe they are not in Lisp Machine
    LISP:
    (a) In FUNCTION:  #'(:PROPERTY FOO BAR) ought to be legal.
    (b) As an argument to APPLY:  (APPLY '(:PROPERTY FOO BAR) args)
    (c) In ordinary function calls!  ((:PROPERTY FOO BAR) 5 7 :START 3 :END 5)

Empirical evidence:

I've seen naive users trying to put function specs in places like these,
and losing, and wondering what they did wrong.


Date: Tuesday, 9 November 1982  07:44-EST
From: Scott E. Fahlman <Fahlman at Cmu-20c>
To:   Guy.Steele at CMU-10A
Cc:   common-lisp at SU-AI, David A. Moon <Moon at SCRC-POINTER at MIT-MC>
Subject: Remarks on mini-ballot


I am really getting scared.  Allowing ((:property foo bar) ...) seems to
me to open up all sorts of evil and hairy possibilities.  I can't name
them right now, but I think they're out there and we should all think
hard before swallowing this.  If this turns out to be an error, it may
be too late to correct it by the time we realize the problem, since
we're going to press fairly soon.  Consistency is OK in its place, but
we shouldn't let it push us around.

-- Scott


Date:  9 November 1982 0433-EST (Tuesday)
From: Guy.Steele at CMU-10A
To: David A. Moon <Moon@SCRC-POINTER at MIT-MC>
Subject: Re: Remarks on mini-ballot
CC: common-lisp at SU-AI
In-Reply-To: David A. Moon's message of 9 Nov 82 03:51-EST

I might believe that (APPLY '(:PROPERTY FOO BAR) args) shouldn't work,
on the basis of your argument that the name of the thing is not the same
as the thing (true enough), except that in LMLISP and in Common LISP
APPLY is willing to accept the name of the thing in lieu of the thing
(for example, (APPLY 'FOO args) instead of (APPLY #'FOO args)).
However, if you believe in the thing-name distinction, then it is
even more important that ((:PROPERTY FOO BAR) 3 5 :START 7) work
as a function call!  It has the name of the function first, and then
the argument forms.  It is entirely analogous to (FOO 3 5 :START 7).


Date: Tuesday, 9 November 1982, 03:51-EST
From: David A. Moon <Moon at SCRC-POINTER at MIT-MC>
Subject: Remarks on mini-ballot
To: Guy.Steele at CMU-10A
Cc: common-lisp at SU-AI
In-reply-to: The message of 9 Nov 82 02:45-EST from Guy.Steele at CMU-10A

    Date:  9 November 1982 0245-EST (Tuesday)
    From: Guy.Steele at CMU-10A

    However, the analogy above also indicates to me that function specs
    like (:PROPERTY FOO BAR) really are a kind of generalized name for
    a function.  If so, orthogonality demands that they be permissible
    in a lot of places where currently I believe they are not in Lisp Machine
    LISP:
    (a) In FUNCTION:  #'(:PROPERTY FOO BAR) ought to be legal.
It is.  I don't remember there ever being a time when it wasn't, although
I might be forgetting.
    (b) As an argument to APPLY:  (APPLY '(:PROPERTY FOO BAR) args).
    (c) In ordinary function calls!  ((:PROPERTY FOO BAR) 5 7 :START 3 :END 5)
These two aren't, on the theory that the name for a thing is not the thing.
I won't try to argue that this theory is right, but that's the way it is
right at the moment.  The lack of (c) actually required introducing a new
special form, MACROCALL, which is kind of like FUNCALL except that it works
for macros.  Of course if you think about it more precisely, and with proper
understanding of Lisp semantics, this means that MACROCALL is nothing whatever
like FUNCALL!  It's a macro that gets the macro definition of its first subform
and uses it to macro-expand the form.