doc/scheme/docume.89

.xgp
.vsp 11
.squish
.ltrspc 0
.c << text font >>
.font 0 25fr1
.c << SCHEME font >>
.font 1 22fg
.c << heading fonts >>
.font 2 30vrb
.font 3 66vr
.font 4 gls;foo1
.quote 
.dummy _
.twinch 6.25
.tlinch 9
.sidm 53
.c << want to flush losing multiple cr's >>
.crcomp
.c << want to make leading spaces on line small >>
.c << want to have at least 3 lines of a section on a page >>
.sblock 5
.spw 16
.adjust
.center
2MASSACHUSETTS INSTITUTE OF TECHNOLOGY
.CENTER
ARTIFICIAL INTELLIGENCE LABORATORY
.sp
.spread
/0AI Memo No. 452//January 1978
.sp
.center
2THE__REVISED__REPORT__ON
.sp 2
.center
3SCHEME
.sp
.center
2A__DIALECT__OF__LISP
.sp
.center
0by
.sp
.center
Guy Lewis Steele Jr.* and Gerald Jay Sussman
.sp 2
0Abstract:
.br
    SCHEME is a dialect of LISP.
It is an expression-oriented, applicative order,
interpreter-based language which allows one to
manipulate programs as data.
It differs from most current dialects of LISP
in that it closes all lambda-expressions
in the environment of their definition or declaration,
rather than in the execution environment.
This has the consequence that variables are normally lexically scoped,
as in ALGOL.  However, in contrast with ALGOL,
SCHEME treats procedures as a first-class data type.
They can be the values of variables, the returned values of
procedures, and components of data structures.
Another difference from LISP is that SCHEME is
implemented in such a way that tail-recursions execute
without net growth of the interpreter stack.
The effect of this is that a procedure call behaves like a GOTO,
and thus procedure calls can be used to implement iterations,
as in PLASMA.
    Here we give a complete "user manual" for the SCHEME
language.  Some features described here were not documented in the original
report on SCHEME (for instance particular macros).
Other features have been added, changed, or deleted
as our understanding of certain language issues evolved.
Annotations to the manual describe the motivations
for these changes.


.sp
.in 4
.un 4
Keywords:__LISP, SCHEME, LISP-like languages,
lambda-calculus, environments, lexical scoping, dynamic scoping,
fluid variables, control structures, macros, extensible syntax,
extensible languages
.in 0

.sp
This report describes research done at the Artificial Intelligence
Laboratory of the Massachusetts Institute of Technology.
Support for the laboratory's artificial intelligence research
is provided in part by the Advanced Research Projects Agency
of the Department of Defense under Office of Naval Research contract N00014-75-C-0643.
.sp
*__NSF Fellow

.page
.spage
.php1
.he1
1Steele and Sussman
.he2
1The Revised Report on SCHEME0

.section
A.__The Representation of SCHEME Procedures as S-expressions
.sp
	SCHEME programs are represented as LISP s-expressions.
The evaluator interprets these s-expressions in a specified way.
This specification constitutes the definition of the language.
	The definition of SCHEME is a little fuzzy around the edges.
This is because of the inherent extensibility of LISP-like languages
{Note LISP Is a Ball of Mud}.
We can define a few essential features
which constitute the "kernel" of the language,
and also enumerate several syntactic and semantic extensions
which are convenient and normally included in a given implementation.
The existence of a mechanism for such extensions
is a part of the kernel of SCHEME; however, any particular
such extension is not necessarily part of the kernel.
.sp
	For those who like this sort of thing,
here is the BNF for SCHEME programs {Note LISP BNF}:
.sp
.nofill
.spw 13
.in 4
1<form> ::= <non-symbol atom> | <identifier> | <magic> | <combination>
<identifier> ::= <atomic symbol>
<magic> ::= <lambda-expression>
	  | (QUOTE <s-expression> )
	  | (IF <form> <form> <form> )
	  | (IF <form> <form> )
	  | (LABELS ( <labels list> ) <body> )
	  | (DEFINE <identifier> <lambda-expression> )
	  | (DEFINE <identifier> ( <identifier list> ) <form> )
	  | (DEFINE ( <identifier> <identifier list> ) <form> )
	  | (ASET' <identifier> <form> )
	  | (FLUIDBIND ( <fluidbind list> ) <form> )
	  | (FLUID <identifier> )
	  | (FLUIDSET' <identifier> <form> )
	  | (CATCH <identifier> <form> )
	  | <syntactic extension>
<lambda-expression> ::= (LAMBDA ( <identifier list> ) <body>)
<identifier list> ::= <empty> | <identifier> <identifier list>
<body> ::= <form>
<labels list> ::= <empty>
	  | ( <identifier> <lambda-expression> ) <labels list>
<fluidbind list> ::= <empty> | ( <identifier> <form> ) <fluidbind list>
<combination> ::= ( <form list> )
<form list> ::= <form> | <form> <form list>
<syntactic extension> ::= ( <magic word> . <s-expression> )
<magic word> ::= <atomic symbol>
<non-symbol atom> ::= <number> | <array> | <string> | ...0
.in 0
.spw 16
.adjust
.sp
	Atoms which are not atomic symbols (identifiers) evaluate to themselves.
Typical examples of such atoms are numbers, arrays, and strings (character arrays).
Symbols are treated as identifiers or variables.
They may be lexically bound by lambda-expressions.
There is a global environment containing values for (some) free variables.
Many of the variables in this global environment initially
have as their values primitive operations such as, for example,
1CAR0, 1CONS0, and 1PLUS0.
SCHEME differs from most LISP systems in that the atom 1CAR0
is not itself an operation (in the sense of being an invocable object,
e.g. a valid first argument to 1APPLY*),
but only has one as a value when considered as an identifier.
	Non-atomic forms are divided by the evaluator into two classes:
combinations and "magic (special) forms".
The BNF given above is ambiguous; any magic form can also be parsed
as a combination.  The evaluator always treats an ambiguous case as
a magic form.  Magic forms are recognized by the presence of a
"magic (reserved) word" in the car position of the form.
All non-atomic forms which are not magic forms
are considered to be combinations.
The system has a small initial set of magic words;
there is also a mechanism for creating new ones
{Note FUNCALL is a Pain}.
	A combination is considered to be a list
of subforms.  These subforms are all evaluated.
The first value must be a procedure; it is applied
to the other values to get the value of the combination.
There are four important points here:
.sp
.in 3
(1)__The procedure position is always evaluated
just like any other position.  (This is why the primitive
operators are the values of global identifiers.)
.sp
(2)__The procedure is never "re-evaluated"; if the first subform fails to
evaluate to an applicable procedure, it is an error.
Thus, unlike most LISP systems, SCHEME always evaluates the
first subform of a combination exactly once.
.sp
(3)__The arguments are all completely evaluated
before the procedure is applied; that is, SCHEME,
like most LISP systems, is an applicative-order language.
Many SCHEME programs exploit this fact.
.sp
(4)__The argument forms (and procedure form) may in principle
be evaluated in any order.  This is unlike the usual LISP left-to-right order.
(All SCHEME interpreters implemented so far have in fact
performed left-to-right evaluation, but we do not wish programs
to depend on this fact.  Indeed, there are some reasons why
a clever interpreter might want to evaluate them right-to-left,
e.g. to get things on a stack in the correct order.)
.in 0

.page

.section
B.__Catalogue of Magic Forms
.sp
.section
B.1.__Kernel Magic Forms
.sp
	The magic forms in this section are all part of the kernel of SCHEME,
and so must exist in any SCHEME implementation.

.in 3

.sp 2
.block 4
.un 3
1(LAMBDA ( <identifier list> ) <body> )0
.sp
	Lambda-expressions evaluate to procedures.
Unlike most LISP systems, SCHEME does not consider a lambda-expression
(an s-expression whose car is the atom 1LAMBDA0)
to be a procedure.  A lambda-expression only evaluates to a procedure.
A lambda-expression should be thought of as a partial
description of a procedure; a procedure and a description
of it are conceptually distinct objects.
A lambda-expression must be "closed" (associated with an
environment) to produce a procedure object.
Evaluation of a lambda-expression performs such a closure operation.
	The resulting procedure takes as many arguments as there are
identifiers in the identifier list of the lambda-expression.
When the procedure is eventually invoked,
the intuitive effect is that the evaluation of the procedure call is
equivalent to the evaluation
of the 1<body>0 in an environment consisting of
(a)_the environment in which the lambda-expression had been evaluated to
produce the procedure, plus (b)_the pairing of the
identifiers of the 1<identifier list>0 with the arguments supplied
to the procedure.  The pairings (b) take precedence over the environment (a),
and to prevent confusion no identifier may appear twice
in the 1<identifier list>*.
The net effect is to implement ALGOL-style lexical
scoping [Naur], and to "solve the funarg problem" [Moses].

.sp 2
.block 4
.un 3
1(IF <predicate> <consequent> <alternative>)0
.sp
	This is a primitive conditional operator.
The predicate form is evaluated.  If the result
is non-1NIL0 {Note 1IF* Is Data-Dependent},
then the consequent is evaluated, and otherwise the alternative is evaluated.
The resulting value (if there is one) is the value of the 1IF0 form.

.sp 2
.block 4
.un 3
1(IF <predicate> <consequent>)0
.sp
	As above, but if the predicate evaluates to 1NIL0,
then 1NIL0 is the value of the 1IF0 form.  (As a matter of style,
this is usually used
only when the value of the 1IF0 form doesn't matter,
for example, when the consequent is intended to cause a side effect.)


.sp 2
.block 4
.un 3
1(QUOTE <s-expression>)0
.sp
	As in LISP, this quotes the argument form so
that it will be passed verbatim as data; the value of
this form is 1<s-expression>0.
If a SCHEME implementation has the MacLISP read-macro-character feature, then
the abbreviation 1'FOO0 may be used instead of 1(QUOTE FOO)0.

.sp 2
.block 4
.un 3
1(LABELS ( <labels list> ) <body> )0
    where 1<labels list> ::=0
1		<empty> | ( <identifier> <lambda-expression> ) <labels list>0
.sp
	This has the effect of evaluating the 1<body>0 in an environment
where all the identifiers (which, as for 1LAMBDA*, must all be distinct)
in the labels list evaluate to
the values of the respective lambda-expressions.
Furthermore, the procedures which are the values of
the lambda-expressions are themselves closed in that environment,
and not in the outer environment; this allows the procedures to call
themselves and each other recursively.
For example, consider a procedure which counts all the atoms in a list
structure recursively to all levels, but which doesn't count the 1NIL0s
which terminate lists (but 1NIL0s in the car of a list count).
In order to perform this we define two mutually recursive procedures,
one to count the car and one to count the cdr, as follows:
.sp
.block 14
.nofill
.spw 13
	1(DEFINE COUNT
		(LAMBDA (L)
			(LABELS ((COUNTCAR
				  (LAMBDA (L)
					  (IF (ATOM L) 1
					      (+ (COUNTCAR (CAR L))
						 (COUNTCDR (CDR L))))))
				 (COUNTCDR
				  (LAMBDA (L)
					  (IF (ATOM L)
					      (IF (NULL L) 0 1)
					      (+ (COUNTCAR (CAR L))
						 (COUNTCDR (CDR L)))))))
				(COUNTCDR L))))0
.spw 16
.adjust
.sp
	(We have decided not to use the traditional LISP
1LABEL0 primitive in SCHEME because it is difficult to define several mutually
recursive procedures using only 1LABEL0.
Although 1LABELS* is a little more complicated than 1LABEL*,
it is considerably more convenient.
Contrast this design decision with the choice of
1IF* over the more traditional 1COND*, where the definitional
simplicity of 1IF* outweighed the somewhat greater convenience of 1COND*.)


.in 0

.sp 2
.section
B.2.__Side Effects
.sp
	These magic forms produce side effects in the environment.

.in 3

.sp 2
.block 4
.un 3
1(DEFINE <identifier> <lambda-expression> )0
.sp
	This is used for defining a procedure in the "global environment" permanently,
as opposed to 1LABELS0, which is used for temporary procedure definitions
in a local environment.  1DEFINE0 takes a name and a lambda-expression;
it evaluates the lambda-expression in the global environment and
causes the result to be the global value of the identifier.
(1DEFINE0 may perform other implementation-dependent operations as well,
such as keeping track of defined procedures for an editor.
For this reason it is the preferred way to define a globally
available procedure.)

.sp 2
.block 4
.un 3
1(DEFINE <identifier> ( <identifier list> ) <form list> )0
.br
.un 3
1(DEFINE ( <identifier> <identifier list> ) <form list> )0
.sp
These alternative syntaxes permitted by 1DEFINE0
are equivalent to:
.sp
.block 3
.nofill
.spw 13
	1(DEFINE <identifier>
		(LAMBDA ( <identifier list> )
			(BLOCK <form list> )))0
.spw 16
.adjust
.sp
where 1BLOCK* is a syntactic extension defined below.
For example, these three definitions are equivalent:
.sp
.nofill
.spw 13
.block 3
	1(DEFINE CIRCULATE (LAMBDA (X) (RPLACD X X)))
	(DEFINE CIRCULATE (X) (RPLACD X X))
	(DEFINE (CIRCULATE X) (RPLACD X X))0
.spw 16
.adjust
.sp
These forms are provided to support stylistic diversity.


.sp 2
.block 4
.un 3
1(ASET' <identifier> <form>)0
.sp
	This is analogous to the LISP primitive 1SETQ0.
For example, to define a cell [Smith and Hewitt],
we may use 1ASET'0 as follows:
.sp
.block 12
.nofill
.spw 13
	1(DEFINE CONS-CELL
	    (LAMBDA (CONTENTS)
		(LABELS ((THE-CELL
			  (LAMBDA (MSG)
			      (IF (EQ MSG 'CONTENTS?) CONTENTS
				  (IF (EQ MSG 'CELL?) 'YES
				      (IF (EQ (CAR MSG) '<-)
					  (BLOCK (ASET' CONTENTS (CADR MSG))
						 THE-CELL)
					  (ERROR '|UNRECOGNIZED MESSAGE - CELL|
						  MSG
						  'WRNG-TYPE-ARG)))))))
			THE-CELL)))0
.spw 16
.adjust
.sp
Note that 1ASET'0 may be used on global identifiers as well as locally bound identifiers
{Note 1ASET0 Has Disappeared}.

.in 0

.sp 2
.section
B.3.__Dynamic Magic
.sp
	These magic forms implement escape objects and fluid (dynamic)
variables.  They are not a part of the essential kernel.
For a further explication of their semantics in terms of kernel primitives,
see [Imperative].

.in 3

.sp 2
.block 4
.un 3
1(FLUIDBIND ( <fluidbind list> ) <form> )0
    where 1<fluidbind list> ::=0
1		<empty> | ( <identifier> <form> ) <fluidbind list>0
.sp
	This evaluates the 1<form>0 in the environment of the
1FLUIDBIND0 form, with a dynamic environment to which
dynamic bindings of the identifiers in the 1<fluidbind list>0
have been added.  Any procedure dynamically called by
the form, even if not lexically apparent to the 1FLUIDBIND0 form,
will see this dynamic environment (unless modified by further
1FLUIDBIND0s, of course).  The dynamic environment is restored
on return from the form.
	Most LISP systems use a dynamic environment for
all variables.  A SCHEME which implements 1FLUIDBIND0 provides two
distinct environments.  The fluid variable named 1FOO0 is completely
unrelated to a normal lexical variable named 1FOO0
{Note Global Fluid Environment},
and the access mechanisms for the two are distinct.

.sp 2
.block 4
.un 3
1(FLUID <identifier> )0
.sp
	The value of this form is the value of the 1<identifier>* in
the current dynamic environment.  In SCHEME implementations
which have the MacLISP read-macro-character feature,
1(FLUID FOO)0 may be abbreviated to 1FOO0.

.sp 2
.block 4
.un 3
1(FLUIDSET' <identifier> <form> )0
.sp
	The value of the 1<form>0 is assigned to the 1<identifier>0 in the
current dynamic environment.

.sp 2
.block 4
.un 3
1(STATIC <identifier>)0
.sp
	The value of this is the value of the lexical identifier;
writing this is the same as writing just 1<identifier>0
{Note What Good Is It?}.

.sp 2
.block 4
.un 3
1(CATCH <identifier> <form> )0
.sp
	This evaluates the form in an environment where the identifier is bound to
an "escape object" [Landin] [Reynolds].
This is a strange object which can be invoked as if
it were a procedure of one argument.  When the escape object is so invoked,
then control proceeds as if the 1CATCH0 expression had returned with the
supplied argument as its value
{Note Multiple Throw}.
	If both 1CATCH0 and 1FLUIDBIND0 are implemented, then their
semantics are intertwined.  When the escape object is called,
then the dynamic environment is restored to
the one which was current at the time the 1CATCH0 form was evaluated
{Note Environment Symmetry}.
	For a contorted example,
consider the following obscure definition of 1SQRT0
(Sussman's least favorite style/Steele's favorite; but see [SCHEME]):
.sp
.block 13
.nofill
.spw 13
	1(DEFINE SQRT
	    (LAMBDA (X EPSILON)
		((LAMBDA (ANS TAG GO)
		     (CATCH RETURN
			    (BLOCK
			     (CATCH M (ASET' TAG M))			;CREATE PROG TAG
			     (IF (< (ABS (-$ (*$ ANS ANS) X)) EPSILON)	;CAMGE
				 (RETURN ANS))				;POPJ
			     (ASET' ANS (//$ (+$ (//$ X ANS) ANS) 2.0))	;MOVEM
			     (GO TAG))))				;JRST
		 1.0
		 NIL
		 (LAMBDA (F) (F NIL)))))0
.spw 16
.adjust
.sp
This example differs slightly from the version given in [SCHEME];
notice the forms 1(RETURN ANS)0 and 1(GO TAG)0.
	As another example, we can define a 1THROW0 function,
which may then be used with 1CATCH0 much as it is in MacLISP [Moon]
(except that in MacLISP the tag is written after the body of the 1CATCH0,
not before):
.sp
.nofill
.spw 13
	1(DEFINE THROW (LAMBDA (TAG RESULT) (TAG RESULT)))*
.spw 16
.adjust
.sp
An example of its use:
.sp
.nofill
.spw 13
.block 3
	1(CATCH LOSE
	       (MAPCAR (LAMBDA (X) (IF (MINUSP X) (THROW LOSE NIL) (SQRT X)))
		       NUMLIST))0
.spw 16
.adjust
.sp
Indeed, note the similarity between 1THROW0 and the definition of
1GO0 in the first example.

.in 0

.page

.section
C.__Syntactic Extensions
.sp
	SCHEME has a syntactic extension mechanism which provides
a way to define an identifier to be a magic word,
and to associate a function with that word.
The function accepts the magic form as an argument,
and produces a new form; this new form is then evaluated
in place of the original (magic) form.
This is precisely the same as the MacLISP macro facility.

.sp 2
.section
C.1.__System-Provided Extensions
.sp
	Some standard syntactic extensions are provided by the system
for convenience in ordinary programming.  They are distinguished
from other magic words in that they are semantically defined in terms of others
rather than being primitive {Note FEXPRs Are Okay by Us}.
For expository purposes they are described here in a
pattern-matching/production-rule kind of language.
The matching is on s-expression structure, not on character string syntax,
and takes advantage of the definition of list notation:
1(A_B_C) = (A_._(B_._(C_._NIL)))0.
Thus the pattern 1(x_._r)0 matches 1(A_B_C)0, with 1x_=_A0
and 1r_=_(B C)0.
The ordering of the "productions" is significant;
the first one which matches is to be used.


.in 3

.sp 2
.block 4
.nofill
.spw 13
.un 3
1(BLOCK x1 x2 ... xn)0
.sp
1	(BLOCK x) 41 x0
1	(BLOCK x . r) 41 ((LAMBDA (A B) (B)) x (LAMBDA () (BLOCK . r)))0
.spw 16
.adjust
.sp
1BLOCK0 sequentially evaluates the subforms 1xi0 from left to right.
For example:
.sp
.nofill
.spw 13
1	(BLOCK (ASET' X 43) (PRINT X) (+ X 1))0
.spw 16
.adjust
.sp
returns 1440 after setting 1X0 to 143* and then printing it
{Note 1BLOCK0 Exploits Applicative Order}.

.sp 2
.block 4
.nofill
.spw 13
.un 3
1(LET ((v1 x1) (v2 x2) ... (vn xn)) . body)0
.sp
	41 ((LAMBDA (v1 v2 ... vn) (BLOCK . body)) x1 x2 ... xn)0
.spw 16
.adjust
.sp
1LET0 provides a convenient syntax for binding several
variables to corresponding quantities.  It allows the
forms for the quantities to appear textually adjacent
to their corresponding variables.  Notice that the
variables are all bound simultaneously, not sequentially,
and that the initialization forms 1xi* may be evaluated
in any order.
For convenience, 1LET0 also supplies a 1BLOCK0 around the forms constituting its body.


.sp 2
.nofill
.spw 13
.block 10
.un 3
1(DO ((v1 x1 s1) ... (vn xn sn)) (test . done) . body)0
.sp
.block 8
.nofill
.spw 13
	41 (LET ((A1 (LAMBDA () x1))
		 (B1 (LAMBDA (v1 ... vn) s1))
		 ...
		 (An (LAMBDA () xn))
		 (Bn (LAMBDA (v1 ... vn) sn))
		 (TS (LAMBDA (v1 ... vn) test))
		 (DN (LAMBDA (v1 ... vn) (BLOCK . done)))
		 (BD (LAMBDA (v1 ... vn) (BLOCK . body))))
.block 9
		(LABELS ((LOOP
			  (LAMBDA (Z1 ... Zn)
				  (IF (TS Z1 ... Zn)
				      (DN Z1 ... Zn)
				      (BLOCK (BD Z1 ... Zn)
					     (LOOP (B1 Z1 ... Zn)
						   ...
						   (Bn Z1 ... Zn)))))))
			(LOOP (A1) ... (An))))0
.spw 16
.adjust
.sp
This is essentially the MacLISP "new-style" 1DO0 loop [Moon].
The variables 1vi0 are bound to the values of the corresponding 1xi0,
and stepped in parallel after every execution of the body by the 1si0
(by "step" we mean "set to the value of", not "increment by").
If an 1si0 is omitted, 1vi0 is assumed; this results in the variable
not being stepped.  If in addition 1xi0 is omitted, 1NIL0 is assumed.
The loop terminates when the test evaluates non-1NIL0; it is
evaluated before each execution of the body.  When this occurs,
the 1done0 part is evaluated as a 1BLOCK0.
	The complexity of the definition shown is due to an effort to
avoid conflict of variable names, as for 1BLOCK0.
The auxiliary variables 1Ai0, 1Bi0, and 1Zi0 must be generated
to produce as many as are needed, but they need not be chosen
different from all variables appearing in 1xi0, 1si0, 1body0, etc.
	The iteration is effected entirely by procedure calls.
In this manner the definition of 1DO* exploits the tail-recursive
properties of SCHEME [SCHEME] [Imperative].
	As an example, here is a definition of a function
to find the length of a list:
.sp
.nofill
.spw 13
	1(DEFINE (LENGTH X)
		(DO ((Z X (CDR Z))
		     (N 0 (+ N 1)))
		    ((NULL Z) N)))0
.spw 16
.adjust
.sp
	The initializations forms 1xi* may be evaluated in any order,
and on each iteration the stepping form 1si* may be evaluated in any order.
This differs from the MacLISP definition of 1DO*.
For example, this definition of 1NREVERSE* (destructively reverse a list)
would work in MacLISP but not necessarily in SCHEME:
.sp
.nofill
.spw 13
.block 4
1	(DEFINE NREVERSE (X)
		(DO ((A X (CDR A))
		     (B NIL (RPLACD A B)))
		    ((NULL A) B)))0
.spw 16
.adjust
.sp
This definition depends on the 1CDR* occurring before the 1RPLACD*.
In SCHEME we must instead write:
.sp
.nofill
.spw 13
.block 4
	1(DEFINE NREVERSE (X)
		(DO ((A X (PROG1 (CDR A) (RPLACD A B)))
		     (B NIL A))
		    ((NULL A) B)))*
.spw 16
.adjust
.sp
where by 1(PROG1 x y)* we mean 1((LAMBDA (P_Q) (BLOCK_(Q)_P)) x_(LAMBDA_()_y))*
(but 1PROG1* is not really a defined SCHEME primitive).
	Note also that the effect of an 1ASET'0 on a 1DO0 variable does not
survive to the next iteration; this differs from using 1SETQ0
on a 1DO0 variable in MacLISP.


.sp 2
.block 6
.un 3
1(ITERATE name ((v1 e1) ... (vn en)) . body)0
.sp
.nofill
.spw 13
	41 (LABELS ((name (LAMBDA (v1 ... vn) (BLOCK . body))))
		   (name e1 ... en))0
.spw 16
.adjust
.sp
	This defines a looping construct more general than 1DO0.
For example, consider a function to sort out a list of
s-expressions into atoms and lists:
.sp
.nofill
.spw 13
.block 9
	1(DEFINE COLLATE
		(LAMBDA (X)
			(ITERATE COL
				 ((Z X) (ATOMS NIL) (LISTS NIL))
				 (IF (NULL Z)
				     (LIST ATOMS LISTS)
				     (IF (ATOM (CAR Z))
					 (COL (CDR Z) (CONS (CAR Z) ATOMS) LISTS)
					 (COL (CDR Z) ATOMS (CONS (CAR Z) LISTS)))))))0
.spw 16
.adjust
.sp
We have found many situations involving loops where there may be more
than one condition on which to exit and/or more than one condition
to iterate, where 1DO0 is too restrictive but 1ITERATE0 suffices.
Notice that because each loop has a name, one can
specify from an inner loop that the next iteration of any outer
loop is to occur.  Here is a function very similar to the one used
in one SCHEME implementation for variable lookup:
there are two lists of lists, one containing names and the other values.
.sp
.nofill
.spw 13
.block 4
	1(DEFINE (LOOKUP NAME VARS VALUES)
		(ITERATE MAJOR-LOOP
			 ((VARS-BACKBONE VARS)
			  (VALUES-BACKBONE VALUES))
.block 5
			 (IF (NULL VARS-BACKBONE)
			     NIL
			     (ITERATE MINOR-LOOP
				      ((VARS-RIB (CAR VARS-BACKBONE))
				       (VALUES-RIB (CAR VALUES-BACKBONE)))
.block 3
				      (IF (NULL VARS-RIB)
					  (MAJOR-LOOP (CDR VARS-BACKBONE)
						      (CDR VALUES-BACKBONE))
.block 4
					  (IF (EQ (CAR VARS-RIB) NAME)
					      VALUES-RIB
					      (MINOR-LOOP (CDR VARS-RIB)
							  (CDR VALUES-RIB))))))))0
.spw 16
.adjust
.sp
	(We had originally wanted to call this construct 1LOOP0,
but see {Note 1FUNCALL0 is a Pain}.  Compare this with looping constructs
appearing in [Hewitt].)
	It happens that 1ITERATE* is a misleading name; the construct can actually
be used for recursion ("true" recursion, as opposed to tail-recursion) as well.
If the 1name* is invoked from a non-tail-recursive situation,
the argument evaluation in which the call is embedded is not
aborted.  It just so happens that we have found 1ITERATE0 useful
primarily to implement complicated iterations.
One can draw the rough analogy 1ITERATE* : 1LABELS* ::
1LET* : 1LAMBDA*.


.sp 2
.block 6
.un 3
1(TEST pred fn alt)0
.sp
.nofill
.spw 13
	41 ((LAMBDA (P F A) (IF P ((F) P) (A)))
	    pred
	    (LAMBDA () fn)
	    (LAMBDA () alt))0
.spw 16
.adjust
.sp
The predicate is evaluated; if its value is non-1NIL0
then the form 1fn0 should evaluate to a procedure of one argument,
which is then invoked on the value of the predicate.  Otherwise
the alternative 1alt0 is evaluated.
	This construct is of occasional use with LISP "predicates" which
return a "useful" non-1NIL0 value.  For the consequent of an 1IF0
to get at the non-1NIL0 value of the predicate, one might first
bind a variable to the value of the predicate, and this variable
would then be visible to the alternative as well.  With 1TEST0, the use
of the variable is restricted to the consequent.
	An example:
.sp
.nofill
.spw 13
	1(TEST (ASSQ VARIABLE ENVIRONMENT)
	      CDR
	      (GLOBALVALUE VARIABLE))0
.spw 16
.adjust
.sp
Using an a-list to represent an environment, one wants
to use the cdr of the result of 1ASSQ0 if it is non-1NIL0;
but if it is 1NIL0, then the variable was not in the environment,
and one must look elsewhere.

.sp 2
.block 8
.nofill
.spw 13
.un 3
1(COND (p1 . e1) ... (pn . en))0
.sp
.nofill
.spw 13
.block 6
	1(COND)  41  'NIL
	(COND (p) . r)  41  ((LAMBDA (V R) (IF V V (R)))
			     p
			     (LAMBDA () (COND . r)))
	(COND (p => f) . r)  41  (TEST p f (COND . r))
	(COND (p . e) . r)  41  (IF p (BLOCK . e) (COND . r))0
.spw 16
.adjust
.sp
This 1COND0 is a superset of the MacLISP 1COND0.
As in MacLISP, singleton clauses return the value of the predicate if it is non-1NIL0, and
clauses with two or more forms treat the first as the predicate
and the rest as constituents of a 1BLOCK0, thus evaluating them
in order.
	The extension to the MacLISP 1COND0 made in SCHEME is flagged
by the atom 1=>0.
(It cannot be confused with the more general case of two 1BLOCK0
constituents because having the atom 1=>0 as the first element of a 1BLOCK0
is not useful.)  In this situation the form 1f0 following the 1=>0
should have as its value a function of one argument;
if the predicate 1p0 is non-1NIL0, this function is determined
and invoked on the value returned by the predicate.
This is useful for the common situation encountered in LISP:
.sp
.nofill
.spw 13
.block 2
	1(COND ((SETQ IT (GET X 'PROPERTY)) (HACK IT))
	      ...)0
.spw 16
.adjust
.sp
which in SCHEME can be rendered without using a variable global to the 1COND0:
.sp
.nofill
.spw 13
.block 3
	1(COND ((GET X 'PROPERTY)
	       => (LAMBDA (IT) (HACK IT)))
	      ...)0
.spw 16
.adjust
.sp
or, in this specific instance, simply as:
.sp
.nofill
.spw 13
.block 2
	1(COND ((GET X 'PROPERTY) => HACK)
	      ...)0
.spw 16
.adjust
.sp


.sp 2
.block 5
.un 3
1(OR x1 x2 ... xn)0
.sp
.nofill
.spw 13
1	(OR)  41  'NIL
	(OR x)  41  x
	(OR x . r)  41  (COND (x) (T (OR . r)))0
.spw 16
.adjust
.sp
This standard LISP primitive evaluates the forms 1xi0 in order,
returning the first non-1NIL0 value (and ignoring all following forms).
If all forms produce 1NIL0, then 1NIL0 is returned
{Note Tail-Recursive 1OR0}.

.sp 2
.block 5
.un 3
1(AND x1 x2 ... xn)0
.sp
.nofill
.spw 13
1	(AND)  41  'T
	(AND x)  41  x
	(AND x . r)  41  (COND (x (AND . r)))0
.spw 16
.adjust
.sp
This standard LISP primitive evaluates the forms 1xi0 in order.
If any form produces 1NIL0, then 1NIL0 is returned, and succeeding forms 1xi0
are ignored.  If all forms produce non-1NIL0 values, the value of the
last is returned
{Note Tail-Recursive 1AND0}.

.sp 2
.block 10
.un 3
1(AMAPCAR f x1 x2 ... xn)0
.sp
.nofill
.spw 13
.block 8
	41 (DO ((FN f)
		 (V1 x1 (CDR V1))
		 (V2 x2 (CDR V2))
		 ...
		 (Vn xn (CDR Vn))
		 (Q 'NIL (CONS (FN (CAR V1) (CAR V2) ... (CAR Vn)) Q)))
		((OR (NULL V1) (NULL V2) ... (NULL Vn))
		 (NREVERSE Q)))0
.spw 16
.adjust
.sp
1AMAPCAR0 is analogous to the MacLISP 1MAPCAR0 function.  The function 1f0,
a function of 1n0 arguments,
is mapped simultaneously down the lists 1x10, 1x20, ..., 1xn0;
that is, 1f0 is applied to tuples of successive elements of the lists.
The values returned by 1f0 are collected and returned as a list.
Note that 1AMAPCAR0 of a fixed number of arguments could easily
be written as a function in SCHEME.  It is a syntactic extension
only so that it may accommodate any number of arguments,
which saves the trouble of defining an entire set of primitive
functions 1AMAPCAR10, 1AMAPCAR20, ... where 1AMAPCARn0 takes 1n+10 arguments.

.sp 2
.block 10
.un 3
1(AMAPLIST f x1 x2 ... xn)0
.sp
.nofill
.spw 13
.block 8
	41 (DO ((FN f)
		(V1 x1 (CDR V1))
		(V2 x2 (CDR V2))
		...
		(Vn xn (CDR Vn))
	        (Q 'NIL (CONS (FN V1 V2 ... Vn) Q)))
	       ((OR (NULL V1) (NULL V2) ... (NULL Vn))
		(NREVERSE Q)))0
.spw 16
.adjust
.sp
1AMAPLIST0 is analogous to the MacLISP 1MAPLIST0 function.  The function 1f0,
a function of 1n0 arguments,
is applied to tuples of successive tails of the lists.
The values returned by 1f0 are collected and returned as a list.


.sp 2
.block 10
.un 3
1(AMAPC f x1 x2 ... xn)0
.sp
.nofill
.spw 13
.block 8
	41 (DO ((FN f)
		(X1 x1 (CDR X1))
		(X2 x2 (CDR X2))
		...
		(Xn xn (CDR Xn)))
	       ((OR (NULL X1) (NULL X2) ... (NULL Xn))
		'NIL)
	       (FN (CAR X1) (CAR X2) ... (CAR Xn)))0
.spw 16
.adjust
.sp
1AMAPC0 is analogous to the MacLISP 1MAPC0 function.  The procedure 1f0,
a procedure taking 1n0 arguments,
is mapped simultaneously down the lists 1x10, 1x20, ..., 1xn0;
that is, 1f0 is applied to tuples of successive elements of the lists.
Thus 1AMAPC0 is similar to 1AMAPCAR0, except that no values are expected
from 1f0; therefore 1f0 need not be a function, but may be any procedure.

.sp 2
.block 4
.un 3
1(PROG varlist s1 s2 ... sn)0
.sp
	The SCHEME 1PROG0 is like the ordinary LISP 1PROG0.
There is no simple way to describe the transformation
of 1PROG0 syntax into SCHEME primitives.
The basic idea is that a large 1LABELS0 statement is created,
with a labelled procedure (of zero arguments) for each 1PROG0 statement.
Each statement is transformed in such a way that each one that
"drops through" is made to call the labelled procedure for the succeeding
statement; each appearance of 1(GO tag)0 is converted to a call
on the labelled procedure for the statement following the tag;
and each appearance of 1(RETURN value)0 is replaced by 1value0.
	Practical experience with SCHEME has shown that 1PROG0
is almost never used.  It is usually more convenient just
to write the corresponding 1LABELS0 directly.  This allows one to
write 1LABELS0 procedures which take arguments, which tends to
clarify the flow of data [Imperative].

.in 0

.sp 2
	The rest of this section (FSUBRs) applies only to the PDP-10 MacLISP
implementation of SCHEME.

.in 3

.sp 2
.block 2
.un 3
FSUBRs
.sp
	As a user convenience, the PDP-10 MacLISP implementation
of SCHEME treats FSUBRs specially; any FSUBR provided by the MacLISP
system is automatically a SCHEME primitive (but user FSUBRs are not).
Of course, if the FSUBR tries to evaluate some form obtained from its
argument, the variable references will not refer to SCHEME variables.
As a special case, the SCHEME syntactic extension
1AARRAYCALL0 is provided to get the
effect of the MacLISP FSUBR 1ARRAYCALL0.

.in 0

.sp 2
.section
C.2.__User-Provided Extensions
.sp

	A SCHEME implementation should have one or more ways for the user to extend
the inventory of magic words.  The methods provided will vary
from implementation to implementation.  The following primitive
(1SCHMAC0) is provided in the PDP-10 MacLISP implementation of SCHEME.

.in 3

.sp 2
.block 2
.un 3
1(SCHMAC name pattern body)0
.sp
	After execution of this form, a syntactic extension keyed on the
atom 1name0 is defined.  When a form 1(name_._rest)0 is to be evaluated,
1rest0 is matched against the pattern, which is a (possibly "dotted")
list of variables.  The 1body0 is then evaluated in an environment
where the variables in the pattern have as values the corresponding parts
of rest.  This should result in a form to be evaluated in place of the
form 1(name_._rest)0.
	The body is not necessarily SCHEME code, but rather code
in the same meta-language used to write the evaluator.
In the PDP-10 MacLISP SCHEME implementation, the body is MacLISP code.
	As an example, here is a definition of 1TEST0:
.sp
.nofill
.spw 13
.block 5
	1(SCHMAC TEST (PRED FN ALT)
		(LIST '(LAMBDA (P F A) (IF P ((F) P) (A)))
		      PRED
		      (LIST 'LAMBDA '() FN)
		      (LIST 'LAMBDA '() ALT)))0
.spw 16
.adjust
.sp
	The body of a SCHMAC almost always performs a complicated consing-up
of a program structure.  Often one needs to make a copy of a
standard structure, with a few values filled in.
To make this easier, SCHEME provides an "unquoting quote" feature.
An expression of the form 1"<s-expression>0 is just like 1'<s-expression>0,
except that sub-expressions preceded by "1,0" or "1@0" represent
expressions whose values are to be made part of (a copy of)
the s-expression at that point.  A "1,0" denotes simple inclusion,
while "1@0" denotes "splicing" or "segment" inclusion.
(Compare this with the treatment of lists with embedded forms
in MUDDLE [Galley and Pfister], which in turn inspired the 1!"0 syntax of CONNIVER [McDermott and Sussman],
from which SCHEME's 1"0 syntax is derived.)
Using this, one can define 1TEST0 as follows:
.sp
.nofill
.spw 13
.block 5
1	(SCHMAC TEST (PRED FN ALT)
		"((LAMBDA (P F A) (IF P ((F) P) (A)))
		  ,PRED
		  (LAMBDA () ,FN)
		  (LAMBDA () ,ALT)))0
.spw 16
.adjust
.sp
Similarly, 1LET0 can be defined as:
.sp
.nofill
.spw 13
.block 4
	1(SCHMAC LET (DEFNS . BODY)
		"((LAMBDA ,(MAPCAR 'CAR DEFNS)
			  (BLOCK . ,BODY))
		  @(MAPCAR 'CADR DEFNS)))0
.spw 16
.adjust
.sp
One could also write 1(BLOCK_@BODY)0 instead of 1(BLOCK_._,BODY)0.
	Notice the use of 1(MAPCAR 'CAR DEFNS)0 rather than
1(AMAPCAR CAR DEFNS)0, and recall that, as stated above,
the body of a 1SCHMAC0 is MacLISP code, not SCHEME code.
Consider too this definition of 1COND0:
.sp
.nofill
.spw 13
.block 11
	1(SCHMAC COND CLAUSES
		(COND ((NULL CLAUSES) ''NIL)
		      ((NULL (CDAR CLAUSES))
		       "((LAMBDA (V R) (IF V V R))
			 ,(CAAR CLAUSES)
			 (LAMBDA () (COND . ,(CDR CLAUSES)))))
		      ((EQ (CADAR CLAUSES) '=>)
		       "(TEST ,(CAAR CLAUSES) ,(CADDAR CLAUSES) (COND . ,(CDR CLAUSES))))
		      (T "(IF ,(CAAR CLAUSES)
			      (BLOCK . ,(CDAR CLAUSES))
			      (COND . ,(CDR CLAUSES))))))0
.spw 16
.adjust
.sp
We have used 1COND0 to define 1COND0!  The definition is not circular, however;
the MacLISP 1COND0 is being used to define the SCHEME 1COND0,
and indeed the two have slightly different semantics.
The definition would have been circular had we written
1(COND (V) (R))0 instead of 1(IF V V R)0, for the latter is part
of the generated SCHEME code.


.sp 2
.block 2
.un 3
1(MACRO name pattern body)0
.sp
	This is just like 1SCHMAC*, except that 1body* is SCHEME
code rather than MacLISP code.  While macros defined with 1SCHMAC*
run only in a MacLISP implementation of SCHEME, those defined
with 1MACRO* should be completely transportable.
(We described 1SCHMAC* first to emphasize the fact that macros
are conceptually part of the interpreter, and so conceptually
written in the meta-language.  It so happens, however, that
SCHEME is a good meta-language for SCHEME, and so introducing
this meta-circularity provides no serious problems.
Contrast this with writing PL/I macros in PL/I!)
	The example of defining 1COND* using 1SCHMAC* above
would be circular if we changed the word 1SCHMAC* to 1MACRO*.
However, we can avoid this by avoiding the use of 1COND*
in the definition:
.sp
.nofill
.spw 13
.block 11
	1(MACRO COND CLAUSES
		 (IF (NULL CLAUSES) ''NIL
		     (IF (NULL (CDAR CLAUSES))
			 "((LAMBDA (V R) (IF V V R))
			   ,(CAAR CLAUSES)
			   (LAMBDA () (COND . ,(CDR CLAUSES))))
			 (IF (EQ (CADAR CLAUSES) '=>)
			     "(TEST ,(CAAR CLAUSES)
				    ,(CADDAR CLAUSES)
				    (COND . ,(CDR CLAUSES)))
			     "(IF ,(CAAR CLAUSES)
				   (BLOCK . ,(CDAR CLAUSES))
				   (COND . ,(CDR CLAUSES)))))))0
.spw 16
.adjust
.sp
	We strongly encourage the use of 1MACRO* instead of 1SCHMAC*
in practice so that macro definitions will not be dependent on
the properties of a specific implementation.

.in 0

.page

.section
D.__Primitive SCHEME Functions
.sp
	All the usual MacLISP SUBRs are available in SCHEME
as procedures which are the values of global variables.
The particular primitives 1CONS0, 1CAR0, 1CDR0, 1ATOM0, and 1EQ0
are part of the kernel of SCHEME!  Others, such as 1+0, 1-0, 1*0, 1//0, 1=0,
1EQUAL0, 1RPLACA0, 1RPLACD0, etc. are quite convenient to have.
	Although there is no way in SCHEME to write a LEXPR
(a function of a variable number of arguments),
MacLISP LSUBRs are also available to the SCHEME user.
One may wish to regard these as syntactic extensions
in much the same way 1AMAPCAR0 is; for example, 1LIST0 may be thought of
as a syntactic extension such that:
.sp
.block 2
.nofill
.spw 13
1	(LIST) 41 'NIL
	(LIST x . r) 41 (CONS x (LIST . r))0
.spw 16
.adjust
.sp
	Below we also describe some additional primitive functions
provided with SCHEME.  Their names do not have any special syntactic
properties in the way that the magic words for syntactic extensions described
in the previous section do.  However, they do deal with
the underlying implementation, and so could not be programmed
directly by the user were they not provided as primitives.

.sp 2
	The following primitive functions (1PROCP0 and
1ENCLOSE0) are part of the kernel of SCHEME.

.in 3

.sp 2
.block 4
.un 3
1(PROCP thing)0
.sp
	This is a predicate which is true of procedures, and not of
anything else.  Thus if 1(PROCP X)0 is true, then it is safe
to invoke the value of 1X0.
	More precisely, if 1PROCP0 returns a non-1NIL0 value, then
the value describes the number of arguments accepted by the procedure.
For SCHEME procedures this will be an integer, the number of arguments.
For primitive functions, this may be implementation-dependent;
in the PDP-10 MacLISP implementation of SCHEME, 1PROCP0 of an LSUBR
returns the MacLISP 1ARGS0 property for that LSUBR.
If an object given to 1PROCP0 is a procedure but
the number of arguments it requires cannot be determined for some reason,
then 1PROCP0 returns 1T0.

.sp 2
.block 4
.un 3
1(ENCLOSE fnrep envrep)0
.sp
	1ENCLOSE0 takes two s-expressions, one representing the code
for a procedure, and the other representing the (lexical) environment
in which the procedure is to run.  1ENCLOSE0 returns a (closed) procedure
which can be invoked.
	The representation of the code is the standard
s-expression description (a lambda-expression).
The representation of the environment is an association list (a-list)
of the traditional kind:
.sp
.nofill
.spw 13
1	((var1 . value1) (var2 . value2) ...)0
.spw 16
.adjust
.sp
1NIL0 represents the global lexical environment.
	This description of 1ENCLOSE0 should not be construed as describing how the
implementation of SCHEME represents either environment or code
internally.  Indeed, 1ENCLOSE0 could be as simple as 1CONS0, or as complicated
as a compiler.  All that 1ENCLOSE0 guarantees to do is to
compute a procedure object given a description of its desired behavior.
The description must be in the prescribed form; but the result may be in any form
convenient to the implementation, as long as it satisfies the predicate 1PROCP0
{Note 1EVALUATE0 Has Disappeared}
{Note S-expressions Are Not Functions}.
	As an example, we can write 1APPLY0 using 1ENCLOSE0.
One way is to generate a lot of names for the arguments involved:
.sp
.nofill
.spw 13
.block 7
1	(DEFINE APPLY
		(LAMBDA (FN ARGS)
			(LET ((VARS (AMAPCAR (LAMBDA (X) (GENSYM)) ARGS))
			      (FNVAR (GENSYM)))
			     ((ENCLOSE "(LAMBDA () (,FNVAR @VARS))
				       (CONS (CONS FNVAR FN)
					     (AMAPCAR CONS VARS ARGS)))))))0
.spw 16
.adjust
.sp
Here a procedure which will call the procedure 1FN0 on the required
number of arguments is enclosed in an environment with all
the variables bound to the appropriate values.  For those
who don't like 1GENSYM0, here is another way to do it: 
.sp
.nofill
.spw 13
.block 7
1	(DEFINE APPLY
		(LAMBDA (FN ARGS)
			(DO ((TAIL 'A "(CDR ,TAIL))
			     (REFS NIL (CONS "(CAR ,TAIL) REFS))
			     (COUNT ARGS (CDR COUNT)))
			    ((NULL COUNT)
			     ((ENCLOSE "(LAMBDA (F A) (F @(REVERSE REFS))) NIL)
			      FN ARGS)))))0
.spw 16
.adjust
.sp
In this version we create a series of forms 1(CAR_A)0, 1(CAR_(CDR_A))0,
1(CAR_(CDR (CDR_A)))0, ...
to be used to access the arguments.  (In a way, these are distinct names
for the arguments in the same way that the gensyms were for the first version.)
The values 1FN0 and 1ARGS0 are passed in as arguments to the enclosed
procedure, rather than giving a non-1NIL0 environment representation to 1ENCLOSE0.
	As another example, we define a function called 1*LAMBDA*:
.sp
.nofill
.spw 13
.block 2
	1(DEFINE (*LAMBDA VARS BODY)
		(ENCLOSE "(LAMBDA ,VARS ,BODY) NIL))*
.spw 16
.adjust
.sp
Writing 1(*LAMBDA '(X Y) '(FOO Y X))* is just like writing
1(LAMBDA (X Y) (FOO Y X))*.  However, if there are any free variables
in the supplied body, then 1*LAMBDA* will cause them to refer to the
global environment, not the current one.
We cannot in general simulate 1LAMBDA* by using 1*LAMBDA*,
because SCHEME (purposefully) does not provide a general way to get a representation
of the current environment.
We could, of course, require the user to give 1*LAMBDA*
a representation of the current environment, but this hardly
seems worthwhile.


.in 0

.sp 3
	The following primitive functions allow for multiprocessing.
We do not pretend that they are "right" in any sense, and are not
particularly attached to these specific definitions.
They are not part of the kernel of SCHEME.
(Their primary use in practice is for bootstrapping SCHEME by creating
an initial process for the top-level user interface loop.)
	There are no primitives for process synchronization,
as we have no good theory of how best to do this.
However, in the PDP-10 MacLISP implementation of SCHEME
we guarantee that SUBRs and LSUBRs execute in an uninterruptible
fashion; that is, such functions can be considered "atomic"
for synchronization purposes.  The user is invited to exploit this
fact to invent his own synchronization primitives
{Note 1EVALUATE!UNINTERRUPTIBLY0 Has Disappeared}.

.in 3

.sp 2
.block 4
.un 3
1(CREATE!PROCESS proc)0
.sp
	This is the process generator for multiprocessing.
It takes one argument, a procedure of no arguments.
If the procedure ever terminates, the entire process
automatically terminates.  The value of 1CREATE!PROCESS0
is a process ID for the newly generated process.
Note that the newly created process will not actually
run until it is explicitly started.  When started,
the procedure will be invoked (with no arguments), and the process will run
"in parallel" with all other active processes.

.sp 2
.block 4
.un 3
1(START!PROCESS procid)0
.sp
	This takes one argument, a process id, and
starts up or resumes that process, which then runs.

.sp 2
.block 4
.un 3
1(STOP!PROCESS procid)0
.sp
	This also takes a process id, but stops the
process.  The stopped process may be continued from
where it was stopped by using 1START!PROCESS0
again on it.  The global variable 1**PROCESS**0
always contains the process id of the currently running
process; thus a process can stop itself by doing
1(STOP!PROCESS **PROCESS**)0.


.sp 2
.block 4
.un 3
1(TERMINATE)0
.sp
	This primitive stops and kills the process which invokes it.
The process may not be resumed by 1START!PROCESS0.
Some other process is selected to run.  If the last process is
terminated, SCHEME automatically
prints a warning message, and then creates a new process
running the standard SCHEME "read-eval-print"
(actually "read4-0stick_1(LAMBDA_()_.)0_around4-0enclose_in_top-level_environment4-0invoke4-0print")
loop.
	An example of the use of 1TERMINATE*:
.sp
.nofill
.spw 13
1	(TERMINATE)*
.spw 16
.adjust
.sp

.in 0

.page

.section
Notes
.sp

.in 3
{Note Notes Are in Alphabetical Order}


.sp 3
.block 5
.un 3
{1ASET0 Has Disappeared}
.sp
	The more general primitive 1ASET0 described in [SCHEME]
has been removed from the SCHEME language.
Although the case of a general evaluated expression
for the variable name causes no real semantic difficulty
(it can be viewed as a syntactic extension representing
a large 1CASE0 statement, as pointed out in [Declarative]),
it can be confusing to the reader.  Moreover, in two
years we have not found a use for it.  Therefore
we have replaced 1ASET0 with 1ASET'0, which requires the name of
the variable to be modified to appear manifestly.
	We confess to being "cute" when we say that the name
of the primitive is 1ASET'0.  We have not changed the implementation at all,
but merely require that the first argument be quoted.
The form 1(ASET' FOO BAR)0 is parsed by the MacLISP reader
as 1(ASET (QUOTE FOO) BAR)0.  Of course, a different implementation of SCHEME
might actually take 1ASET'0 as a single name.
We apologize for this nonsense.

.sp 3
.block 5
.un 3
{1BLOCK0 Exploits Applicative Order}
.sp
	The definition shown for 1BLOCK0 exploits the applicative order
of evaluation of SCHEME to perform this
{Note Normal Order Loses}.
It does not depend on left-to-right evaluation of arguments to functions!
Notice also that in
.sp
.nofill
.spw 13
1	(BLOCK x . r) 41 ((LAMBDA (A B) (B)) x (LAMBDA () (BLOCK . r)))0
.spw 16
.adjust
.sp
there can be no conflict between the auxiliary
variables 1A0 and 1B0 and any variables occurring in 1x0 and 1r.0
It is thus unnecessary to choose variables different from
any others appearing in the code.  In this respect this definition
is an improvement over the one given in [Imperative].
This trick (which is actually a deep property of the lexical
scoping rules) is used in a general way in most of the definitions
of syntactic extensions: one wraps all the "user code"
in lambda-expressions in the outer environment,
passes them in bound to internal names, and
then invokes them as necessary
within the internal code for the definition.


.sp 3
.block 5
.un 3
{Environment Symmetry}
.sp
	One may think of an escape object as being "closed"
with respect to a dynamic environment (and here we mean not only fluid
variables but the chain of pending procedure calls)
in much the same way that an ordinary procedure is closed
with respect to a lexical environment.  Just as a procedure
cannot execute properly except in conjunction with a static environment
of the appropriate form, so an escape object cannot properly
resume control except in a dynamic environment of the appropriate form.

.sp 3
.block 5
.un 3
{1EVALUATE0 Has Disappeared}
.sp
	The 1EVALUATE0 primitive described in [SCHEME] has
been removed from the language.  We discovered (the hard way)
that the straightforward implementation of 1EVALUATE0
(evaluate the given expression in the current environment)
destroys referential transparency.
We then altered it to evaluate the expression in the top-level
environment, but were still disturbed by the extent to
which one is tied to a particular representation of a
procedure to be executed.
	We eventually invented an 1ENCLOSE0
of one argument (a lambda-expression), which enclosed
the procedure in the top-level environment.
This allowed one to remove the dependence on representation
by making a procedure, and then to pass the procedure around
for a while before invoking it.
We had no provision for closing in an arbitrary environment,
because we did not want to provide the user with direct
access to environments as data objects.
The excellent idea of allowing 1ENCLOSE0 to accept a
representation of an environment was suggested to us
by R. M. Fano.

.sp 3
.block 5
.un 3
{1EVALUATE!UNINTERRUPTIBLY0 Has Disappeared}
.sp
	The 1EVALUATE!UNINTERRUPTIBLY0 primitive described in [SCHEME]
has been removed from the language.  This primitive was
half a joke, and we have since discovered that it had a serious
flaw in its definition, namely that the scope of the uninterruptibility
is lexical.  This worked in our limited examples only by virtue of the
fact that SUBRs were atomic operations.  In general,
this primitive is worse than useless for synchronization purposes.
Synchronization is clearly a dynamic and not a static phenomenon.
We have no good theory of synchronization (primitives for this
were included in [SCHEME] primarily to show that it could be done,
however kludgily), and so have defined no replacement for
1EVALUATE!UNINTERRUPTIBLY0.
We apologize for any confusion this mistake may have caused.

.sp 3
.block 5
.un 3
{FEXPRs Are Okay by Us}
.sp
	While the syntactic extensions are defined in terms of other
constructs, they need not be implemented in terms of them.
For example, in the current PDP-10 MacLISP implementation of SCHEME,
1BLOCK0 is actually implemented in the same way 1IF0 and 1QUOTE0
are, rather than as a macro in terms of 1LAMBDA0.
This was done purely to speed up the interpreter.
The compiler still uses the macro definition (though we could change that too
if warranted).  The point is that the user doesn't have to know about all this.
	It is somewhat an accident that magic forms look like procedure calls
(see also {Note 1FUNCALL0 is a Pain}): a name appearing in the car of a list
may represent either a procedure or a magic word, but not both.
(We could, for example, say that magic forms are distinguished
by a magic word in the cadr of a list, thus allowing forms
such as 1(FOO := (+ FOO 1))0, where 1:=0 is a magic word for assignment.
PLASMA [Smith and Hewitt]
allowed just this ability with its "italics" or "reserved word" feature.)
Thanks to this accident many LISP interpreters store the magic function definition
in the place where an ordinary procedure definition is stored.
A special marker (traditionally EXPR/SUBR or FEXPR/FSUBR) distinguishes
ordinary functions from magic ones.
This allows the lookup for a magic word definition and an ordinary value
to be simultaneous, thus speeding up the implementation; it is purely
an engineering trick and not a semantic essence.
However, this trick has led to a generalization wherein 1QUOTE* and 1COND* are regarded as
functions on an equal basis with 1CAR* and 1CONS*; to be sure, they take their arguments
in a funny way 4-0 unevaluated 4-0 but they are still regarded as functions.
This leads to all manner of confusion, which has its roots in
a confusion between a procedure and its representation.
	It is helpful to consider a simple thought experiment.
Let us postulate a toy language called "Number-LISP".
Programs in this language are written as s-expressions, as usual;
the kernel primitives 1LAMBDA0, 1IF0, 1LABELS0, etc. are all present.
However, the primitive functions 1CONS0, 1CAR0, and 1CDR0 are absent;
one has only 1+0, 1-0, 1*0, 1//0, and 1=0.
1QUOTE0 is not available; the only constants one can write are numbers.
	Now Number-LISP can be used to perform all kinds of
arithmetic, but it is clearly a poor language in which to write
a LISP interpreter.  Now consider the magic form processors
and syntactic extension
functions for Number-LISP.  They are procedures on s-expressions
or functions from s-expressions
to s-expressions which transform one form into another.
Whatever processes 1IF0 or 1LABELS0 or 1BLOCK* is clearly not a Number-LISP
procedure, because it must deal with the text
of a Number-LISP procedure, not just the data to be operated on by that procedure.
The 1IF0-processor (a "FEXPR") for Number-LISP must be coded in the meta-language
for Number-LISP, whatever that may be.
	Now it is one of the great features of ordinary LISP
that it can serve as its own meta-language.  This provides great power,
but also permits great confusion.  If the implementation allows
mixing of levels of definition, we must keep them separate in our minds.
For this reason we don't mind using the "FEXPR hack" to
implement syntactic forms, but we do mind thinking of them
as functions just like EXPRs.


.sp 3
.block 5
.un 3
{1FUNCALL0 is a Pain}
.sp
	The ambiguity between magic forms and combinations
could be eliminated by reserving a special subclass
of lists to represent combinations, and allowing all others
to represent magic forms.  For example, we might say that
all lists beginning with the atom 1CALL0 are combinations.
Then we would write 1(CALL CONS A B)0 rather than 1(CONS A B)0.
One could then have a procedure named 1LAMBDA0, for example;
there could be no confusion between 1(LAMBDA (A) (B A))0
and 1(CALL LAMBDA (CALL A) (CALL B A))0, as there would be
between 1(LAMBDA (A) (B A))0 as a combination and as a magic form
denoting a procedure.
Notice that 1CALL0 is intended to be
merely a syntactic marker, like 1LAMBDA0 or 1IF0,
and not a function as 1FUNCALL0 is in MacLISP [Moon].
	If this 1CALL0 convention were adopted, there could be no
confusion between combinations and other kinds of forms.
Not all expressions would have meaningful interpretations;
for example 1(FOO A B)0 would not mean anything (certainly
not a call to the function 1FOO0, which would be written
as 1(CALL FOO A B)0).  The space of meaningful s-expressions
would be a very sparse subset of all s-expressions,
rather than a dense one.
It would also make writing SCHEME code very clumsy.
(These two facts are of course correlated.)
Combinations occur about as often as all other non-atomic forms put together;
we would like to write as little as possible to denote a call.
As in traditional LISP, we agree to tolerate the ambiguity
in SCHEME as the price of notational convenience.
Indeed, this ambiguity is sometimes exploited; it is convenient
not to have to know whether 1AMAPCAR0 is a function or a magic word.
	This compromise does lead to difficulties, however.
For example, we had wanted to define an iteration feature:
.sp
.nofill
.spw 13
1	(LOOP name varspecs body)0
.spw 16
.adjust
.sp
Unfortunately, there is a great deal of existing code written in
SCHEME of the form:
.sp
.nofill
.spw 13
.block 2
	1(LABELS ((LOOP (LAMBDA ... (LOOP ...) ...)))
		(LOOP ...))0
.spw 16
.adjust
.sp
because 1LOOP0 has become a standard name for use in a 1LABELS0
procedure which implements an iteration (see, for example,
our definition of 1DO0!).  If 1LOOP0
were to become a new magic word, then all this existing code
would no longer work.  We were therefore forced to name it 1ITERATE* instead
(after verifying that no existing code used the name 1ITERATE* for another purpose!).
There would have been no problem if
all this code had been written as:
.sp
.nofill
.spw 13
.block 2
	1(LABELS ((LOOP (LAMBDA ... (CALL LOOP ...) ...)))
		(CALL LOOP ...))0
.spw 16
.adjust
.sp
To this extent SCHEME has unfortunately, despite our best intentions,
inherited a certain amount of referential opacity.

.sp 3
.block 5
.un 3
{Global Fluid Environment}
.sp
	There is a question as to the meaning of the global fluid environment.
In the PDP-10 MacLISP implementation of SCHEME, the global lexical
and fluid environments coincide, but this was an arbitrary choice of
convenience influenced by the structure of MacLISP.
We recommend that the two global environments be kept distinct.

.sp 3
.block 5
.un 3
{1IF* Is Data-Dependent}
.sp
	We should note that the usefulness of the definition of 1IF*
explicitly depends on the particular kinds of data types and the
particular primitive functions available; we expect to use 1IF*
with primitive predicates such as 1ATOM0 and 1EQ0.
This is in contrast to other kernel forms such as 1LAMBDA* and 1LABELS0
expressions, whose semantics are independent of the data.
	We erred in [SCHEME] when we stated that a practical
interpreter must have a little of each of call-by-value and call-by-name
in it.  The argument was roughly that a call-by-name interpreter
must become call-by-value when a primitive operator is to be
applied, and a call-by-value interpreter must have some
primitive conditional such as 1IF*.
We did mention the trick of eliminating 1IF* in a call-by-name interpreter
by defining predicates to return 1(LAMBDA_(X_Y)_X)* for TRUE
and 1(LAMBDA_(X_Y)_Y)* for FALSE, whereupon
one typically writes:
.sp
.nofill
.spw 13
	1((= A B) <do this if TRUE> <do this if FALSE>)*
.spw 16
.adjust
.sp
but noted that it depends
critically on the use of normal order evaluation.
	What we had not fully understood at that point was the trick of
simulating call-by-name in terms of call-by-value
by using lambda-expressions
(our use of it in the TRY!TWO!THINGS!IN!PARALLEL example notwithstanding!);
this trick was described generally in [Imperative].  A special case of this trick
is to define the primitive predicates in a call-by-value interpreter
to return 1(LAMBDA_(X_Y)_(X))* for TRUE and 1(LAMBDA_(X_Y)_(Y))*
for FALSE.
Then one can write things like:
.sp
.nofill
.spw 13
.block 3
	1((= A B)
	 (LAMBDA () <do this if TRUE>)
	 (LAMBDA () <do this if FALSE>))*
.spw 16
.adjust
.sp
and so eliminate a call-by-name-like magic form such as 1IF*.
One can make the dependence of the conditional
on the primitive data operations even more explicit by defining predicates
not to return any particular value, but to require two "continuations"
as arguments, of which it will invoke one:
.sp
.nofill
.spw 13
.block 3
	1(= A B
	   (LAMBDA () <do this if TRUE>)
	   (LAMBDA () <do this if FALSE>))*
.spw 16
.adjust
.sp
We were correct when we said that a practical interpreter must have call-by-name
to some extent in that there must be some way to designate
two pieces of as yet uninterpreted program text of which
only one is to be evaluated.  We simply did not notice
that 1LAMBDA* provides this ability, and so a separate
primitive such as 1IF0 is not necessary.
We have chosen to retain 1IF0 in the language because
it is traditional, because its implementation is easy to
understand, and because it allows us to take advantage of
many existing predicates in the host language in the PDP-10 MacLISP
implementation.

.sp 3
.block 6
.un 3
{LISP BNF}
.sp
	These rules refer to the following rules for LISP s-expressions:
.sp
.nofill
.spw 13
1	<atomic symbol> ::= <alphanumeric string> <letter> <alphanumeric string>
.block 2
	<alphanumeric string> ::= <empty> | <alphanumeric character> <alphanumeric string>
	<alphanumeric character> ::= <letter> | <digit> | / <character>
	<letter> ::= A | B | ... | Y | Z | * | $ | % | ...
	<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
	<number> ::= <VERY implementation dependent>
.block 3
	<string> ::= " <character string> "
	<character string> ::= <empty> | <literal character> <character string>
	<literal character> ::= <any character except " or /> | / <character>0
.spw 16
.adjust
.sp
(In the PDP-10 MacLISP implementation of SCHEME, we use the " character
for another purpose because PDP-10 MacLISP does not have a string data type.
We mention strings only as a familiar example other than numbers
of an atomic data type other than identifiers.)
	In addition, we assume the usual interchangeability of list notation and
dot notation for s-expressions: 1(A_B_C) = (A_._(B_._(C_._NIL)))0.
Thus the pattern 1(_<magic_word> . <s-expression>_)0 may match
the list 1(COND (A_B) (T_C))0.  It is the s-expression representation
we care about, not particular character strings.


.sp 3
.block 5
.un 3
{LISP Is a Ball of Mud}
.sp
	LISP is extensible in two ways.  First, there is the simple
ability to define new functions; these are used in a way that is
both syntactically and semantically identical to built-in primitive functions
like 1CAR0.  This is in contrast to "algebraic" programming languages,
which either make an arbitrary syntactic distinction between addition, say,
and a user function, or wander into the quagmire of extensible parsers.
Second, there is a uniform macro facility for transforming one syntactic form
into another; this facility is based on internal data structures rather than
external character-string syntax.
	Joel Moses (private communication) once made some remarks on the difference
between LISP and APL, which we paraphrase here:
"APL is like a diamond.  It has a beautiful crystal structure; all of its parts
are related in a uniform and elegant way.  But if you try to extend this structure
in any way 4-0 even by adding another diamond 4-0 you get an ugly kludge.
LISP, on the other hand, is like a ball of mud.  You can add any amount of
mud to it (e.g. MICRO-PLANNER or CONNIVER) and it still looks like a ball of mud!"


.sp 3
.block 5
.un 3
{Multiple Throw}
.sp
	A full implementation of SCHEME allows this to work even if
the CATCH has already been "returned from";  that is, the escape object can be used
to "return from the catch" several times.  However, we allow the possibility
that an implementation may allow
the escape object to be invoked only from within the execution of the form
inside the catch.  (This is essentially the restriction that MacLISP
makes on its 1CATCH0 construct [Moon].)
This restriction permits a stack discipline for the allocation
of continuations, and also greatly simplifies the flow analysis
problem for a compiler [RABBIT].

.sp 3
.block 5
.un 3
{Normal Order Loses}
.sp
	Our definition of 1BLOCK0 exploits the fact that SCHEME
is an applicative-order (call-by-value) language in order to enforce
sequencing.  Sussman has proved that one cannot do a similar thing
in a normal-order (call-by-name) language:
.sp
.block 4
.in 11
.un 4
Theorem:  Normal order, as such, is incapable of
enforcing sequencing (whereas applicative order is)
in the form of the 1BLOCK0 construct.
.un 4
(Informal) proof:  The essence of 1(BLOCK_a_b)0 is that 1a0 is evaluated before
1b0, and that the value of 1b0 is the value of the 1BLOCK0 (or, more
correctly, the value or meaning of the 1BLOCK0 is independent of 1a0;
1a0 is executed only for its side effects).
Now we know that if 1(BLOCK_a_b)0 has any value at all,
it can be found by using normal order (normal order terminates
if any order does).  Now suppose that the computation of 1a0
does not terminate, but the computation of 1b0 does.
Then 1(BLOCK_a_b)0 must terminate under normal order,
because the value of the block is the value of 1b0;
but this contradicts the requirement that 1a0 finish before
1b0 is calculated.  QED
.sp
.in 3
This is an informal indication that normal order is less useful
(or at least less powerful)
in a programming language than applicative order.
We also noted in [SCHEME] that normal order iterations
tend to consume more space that applicative order iterations,
because of the buildup of thunk structure.
Given that one can simulate normal order in applicative order by
explicitly creating closures [Imperative], there seems to be little
to recommend normal order over applicative order in a practical
programming language.

.sp 3
.block 5
.un 3
{Notes Are in Alphabetical Order}
.sp
	The notes are ordered alphabetically by name, not in order of reference
within the text.

.sp 3
.block 5
.un 3
{S-expressions Are Not Functions}
.sp
	Recall that a lambda-expression (i.e. an s-expression
whose car is the atomic symbol 1LAMBDA0) is not itself a valid
procedure.  It is necessary to 1ENCLOSE0 it in order to invoke it.
	Moreover, the particular representations we have chosen
for procedures and environments are arbitrary.
In principle, one could have several kinds of ENCLOSE, each
transforming instances of a particular representation into procedures.
For example, someone might actually want to implement
a primitive 1ALGOL-ENCLOSE0, taking a string and a 2-by-N array
representing code and environment for an ALGOL procedure:
.sp
.nofill
.spw 13
.block 4
	1(ALGOL-ENCLOSE "integer procedure fact(n); value n; integer n;
			   fact := if n=0 then 1 else n*fact(n-1)"
		       NULL-ARRAY)0
.spw 16
.adjust
.sp
This could return a factorial function completely acceptable to SCHEME.
Of course, the implementation of the primitive 1ALGOL-ENCLOSE0
would have to know about the internal representations of procedures
used by the implementation of SCHEME; but this is hidden from the user.
	Similarly, one could have 1APL-ENCLOSE0, 1BASIC-ENCLOSE0,
1COBOL-ENCLOSE0, 1FORTRAN-ENCLOSE0, 1RPG-ENCLOSE0 ...

.sp 3
.block 5
.un 3
{Tail-Recursive 1AND0}
.sp
	The definition of 1AND0 has three rules,
not only for the same reasons 1OR0 does, but because
1AND0 is not a precise dual to 1OR0.  1OR0, on failure,
returns 1NIL0, but 1AND0 does not just return non-1NIL0
on success.  It must return the non-1NIL0 thing
returned by its last form.


.sp 3
.block 5
.un 3
{Tail-Recursive 1OR0}
.sp
	We might have defined 1OR0 with only two rules:
.sp
.nofill
.spw 13
1	(OR)  41  'NIL
	(OR x . r)  41  (COND (x) (T (OR . r)))0
.spw 16
.adjust
.sp
However, because of the way 1OR0 is sometimes used,
it is a technical convenience to be able
to guarantee to the user that the last form
in an 1OR0 is evaluated without an extra "stack frame";
that is, a function called as the last form in an
1OR0 will be invoked tail-recursively.
For example:
.sp
.nofill
.spw 13
1	(DEFINE NOT-ALL-NIL-P
		(LAMBDA (X)
			(LABELS ((LOOP
				  (LAMBDA (Z)
					  (OR (CAR Z) (LOOP (CDR Z))))))
				(LOOP X))))0
.spw 16
.adjust
.sp
executes iteratively in SCHEME, but would not execute
iteratively if the two-rule definition of 1OR0 were used.

.sp 3
.block 5
.un 3
{What Use Is It?}
.sp
	We should perhaps say instead that 1<identifier>0 is treated the same
as 1(STATIC <identifier>)0.  The 1STATIC0 construction is included in SCHEME
primarily for pedagogical purposes, to provide symmetry to 1(FLUID <identifier>)0.
The fact that lone atomic symbols are interpreted as lexical variables
rather than dynamic ones is in some sense arbitrary.
Some critics of SCHEME [personal communications] have expressed a certain horror that
there are two kinds of variables, perhaps imagining some confusion in
the interpretation of simple identifiers.
We can have as many kinds of variables as we like (though we have so
far discovered only two kinds of any great use), as long as we
can distinguish them.  In SCHEME we distinguish them with
a special marker, such as 1STATIC0 or 1FLUID0; then, as a convenience,
we prescribe that simple atomic symbols, not marked by such a keyword,
shall also be interpreted as lexical variables, because that is the kind
we use most often in SCHEME.  We could as easily have defined simple
symbols to be interpreted as fluid variables, or for that matter
as constants (as numbers and strings are).  We could also have prescribed
a different method of distinguishing types, e.g. "all variables
beginning with I, J, K, L, M, or N shall be fluid".
(This is not as silly as it sounds.  A fairly wide-spread LISP convention
is to spell global variables with leading and trailing 1**,
as in 1*FOO**, and some programmers have wished that the compiler
would automatically treat variables so spelled as SPECIAL.)
Indeed, given the read-macro-character facility, we effectively have
the syntactic rule "all variables beginning with 10 shall be fluid".
We have settled on the current definition of SCHEME as being the
most convenient both to implement and to use.
	Compare the use of syntactic markers and read-macro-characters
to the constructions 1<GVAL X>0 = 1,X =0 "global value of 1X0"
and 1<LVAL X>0 = 1.X =0 "local value of 1X0"
in MUDDLE [Galley and Pfister].  Indeed, in MUDDLE
a simple atomic symbol is regarded as a constant, not as an identifier.
	All this suggests another solution to the problem
posed in {Note 1FUNCALL0 is a Pain} (the confusion of magic forms
with combinations).  The real problem is distinguishing a magic word
from a variable.  Let us abbreviate 1(STATIC_FOO)0 to 1FOO0,
just as 1(FLUID_FOO)0 can be abbreviated as 1FOO0.
Then 1(LOOP_A_B)0 would have to be a call on the function 1LOOP0,
and not a magic form.  Similarly, we could write 1(MAGICWORD COND)0
instead of 1COND0, and invent an abbreviation for that too.
This all raises as many problems as it solves by becoming too clumsy;
but then again, maybe it isn't asking too much to require the user to write
all magic words in boldface (as in the ALGOL reference language) or in italics
(as in an early version of PLASMA [Smith and Hewitt])...

.in 0


.sp 4
.block 6
.section
Acknowledgements
.sp
	Comments by Carl Hewitt and Berthold Horn were of considerable value
in preparing this paper.  Ed Barton (who is also helping to maintain the
PDP-10 MacLISP SCHEME implementation) made important contributions
to the revisions of the language definition.


.page

.section
References
.sp 2
.in 8

.block 4
.un 8
[Declarative]
.br
Steele, Guy Lewis Jr.
LAMBDA: The Ultimate Declarative.
AI Memo 379.  MIT AI Lab (Cambridge, November 1976).
.sp
.block 4
.un 8
[Galley and Pfister]
.br
Galley, S.W. and Pfister, Greg.
The MDL Language.
Programming Technology Division Document SYS.11.01.
Project MAC, MIT (Cambridge, November 1975).
.sp
.block 4
.un 8
[Hewitt]
.br
Hewitt, Carl.
"Viewing Control Structures as Patterns of Passing Messages."
AI Journal 8, 3 (June 1977), 323-364.
.sp
.block 4
.un 8
[Imperative]
.br
Steele, Guy Lewis Jr., and Sussman, Gerald Jay.
LAMBDA: The Ultimate Imperative.
AI Memo 353.  MIT AI Lab (Cambridge, March 1976).
.sp
.block 4
.un 8
[Landin]
.br
Landin, Peter J.
"A Correspondence between ALGOL 60 and Church's Lambda-Notation."
Comm. ACM 8, 2-3 (February and March 1965).
.sp
.block 4
.un 8
[McDermott and Sussman]
.br
McDermott, Drew V. and Sussman, Gerald Jay.
The CONNIVER Reference Manual.
AI Memo 295a.  MIT AI Lab (Cambridge, January 1974).
.sp
.block 4
.un 8
[Moon]
.br
Moon, David A.
MacLISP Reference Manual, Revision 0.
Project MAC, MIT (Cambridge, April 1974).
.sp
.block 4
.un 8
[Moses]
.br
Moses, Joel.
The Function of FUNCTION in LISP.
AI Memo 199, MIT AI Lab (Cambridge, June 1970).
.sp
.block 4
.un 8
[Naur]
.br
Naur, Peter (ed.), et al.
"Revised Report on the Algorithmic Language ALGOL 60."
Comm. ACM 6, 1 (January 1963), 1-20.
.sp
.block 4
.un 8
[RABBIT]
.br
Steele, Guy Lewis Jr.
Compiler Optimization Based on Viewing LAMBDA as Rename plus Goto.
S.M. thesis.  MIT (Cambridge, May 1977).
.sp
.block 4
.un 8
[Reynolds]
.br
Reynolds, John C.
"Definitional Interpreters for Higher Order Programming Languages."
ACM Conference Proceedings 1972.
.sp
.block 4
.un 8
[SCHEME]
.br
Sussman, Gerald Jay, and Steele, Guy Lewis Jr.
SCHEME: An Interpreter for Extended Lambda Calculus.
AI Memo 349.  MIT AI Lab (Cambridge, December 1975).
.sp
.block 4
.un 8
[Smith and Hewitt]
.br
Smith, Brian C. and Hewitt, Carl.
A PLASMA Primer (draft).
MIT AI Lab (Cambridge, October 1975).
.in 0