.c	Friday  March 25,1983  21:59  FQ+4D.16H.20M.55S.  -*- Bolio -*-
.headings off
.c These little horseshow frobs are until Moon fixes .space to work at
.c the top of a page ***
 
.space 8
.center 9Introduction to NIL*
.space 11
.center March 1983
.space 3
.center 5Glenn Burke*
.space 10
.nopara
This report describes research done at the Laboratory for Computer
Science of the Massachusetts Institute of Technology.  Support for
this research was provided in part by the National Institutes of
Health grant no. 1 P01 LM 03374-04 from the National Library of
Medicine, the U. S. Air Force under grant F49620-79-C-020, the
National Aeronautics and Space Administration under grant NSG 1323,
the U. S. Department of Energy under grant ET-78-C-02-4687, and
the Digital Equipment Corporation of Maynard, Massachusetts, with
grants of equipment.
.space 3
.center "MASSACHUSETTS INSTITUTE OF TECHNOLOGY"
.center "LABORATORY FOR COMPUTER SCIENCE"
.space 1
.spread /CAMBRIDGE//MASSACHUSETTS 02139/
.page
.c These little horseshow frobs are until Moon fixes .space to work at the top of a page ***
 
.page
.headings on


.chapter "Introduction"

lan{Nil} is a dialect of lan{lisp} which runs on DEC VAXes under
the VMS operating system.  It is destined to be compatible with
lan{common lisp}.  lan{common lisp} is a sufficiently complete
specification of Lisp that many programs should be able to be written
conforming to that standard, and thus be able to be transported to
other lan{common lisp} implementations.  At this time, the "final
draft" of the lan{common lisp} manual has not been published, and
also certain fine points are not finalized.  lan{nil}, although not
nearly complete, conforms closely to most of the existing and known
lan{common lisp} functionality;  it may be the only currently
distributed lan{lisp} dialect which does so.

The lan{nil} system provides a lexical interpreter complete with
closures, a compiler, a primitive interactive debugger, and (under
development now) an editor (written in lan{nil}).  lan{nil} is
compatible with lan{maclisp} to whatever extent is possible, given
that the interpreter uses lexical scoping rules, and certain fine
incompatibility points between lan{common lisp} and lan{maclisp}.
Certain of these will be described later.

.chapter "Style, Conventions, Etc."

.section "Major Implementation Points"

lan{Nil}, like lan{zetalisp}, utilizes a function cell in which
to define functions and macros.  It does not use the property list the
way lan{maclisp} does.  Interpretation of whether a name is a
function or a variable is done purely syntactically;  in, for example,
.lisp
(fact number)
.end_lisp
3fact* is interpreted as a function, and 3number* as a
variable.  Doing a 3setq* of 3fact* will not affect this
interpretation, and neither will doing a 3defun* of 3number*.

lan{nil} is one of the few "production" Lisps around now which
utilize lexical scoping rules in the interpreter, as opposed to that
only being the default interpretation when the code is compiled (as is
the case in lan{maclisp} and lan{zetalisp}).  The lan{nil}
interpreter thus behaves somewhat like the compiler, and heeds
variable declarations.  This also has an impact on the efficiency of
interpreted code, but no comparisons of its speed have been made
with any comparable Lisp implementations.  One of the major impacts of
lexical scoping within the interpreter is on debugging interpreted
code, outside of a function, variable values may no longer be
lexically apparent.  The debugger ((debug-fun)) and exhibitor
((exhibit-fun)) are capable of compensating for this somewhat.

.section "NIL and T"

In lan{nil}, the canonical objects for representing boolean true and
false are atomic symbols, just as they are in lan{maclisp},
lan{zetalisp}, and as specified by lan{common lisp}.  (This
differs from earlier implementations of lan{nil} including the one,
made in December 1982, which is being distributed as Release 0.)  One
may not bind or setq these symbols.  They do, however, have values and
potentially functions associated with them, just as all other symbols
do.  The mechanism by which they have values which are not allowed to
be modified is available to the user by use of the 3defconstant*
form ((defconstant-fun)).

.section "Syntax and Symbols"

lan{nil} by default "comes up" using the reader syntax specified by
lan{common lisp}.  The primary difference of note involves the
3/* and 3\* characters:  the "quoting" or "slashification"
character in lan{common lisp} is backslash (3\*), rather than
slash (3/*) as it is in lan{maclisp} and lan{zetalisp}.
Thus, the division function whose print name consists of the single
character 3/* may be typed in as just that single character,
unlike (for instance) lan{maclisp} where the slashes needed to be
doubled;  conversely, the function in lan{nil} which performs the
3gcd* operation on fixnums only (for lan{maclisp}
compatibility), and which has a print name consisting of two
backslashes (3\\*), must be typed in as 3\\\\*.
In documentation, symbols are displayed without the (back)slashes
which may be necessary for them to be typed in.  Within lisp examples,
lisp expressions are displayed with the necessary slashification,
utilizing lan{common lisp} syntax.

One other syntax difference is that lan{nil} has a special data type
to represent term_i{characters}.  Those who use the sharpsign
(3#*) reader macro should note that in lan{common lisp}
syntax, there is no 3#/* syntax, only 3#\* which can
accept both character names and single characters, and that the object
represented is a 3character*, not the fixnum representation of the
character.

.chapter "Interpretation"

.section "Binding and Scoping"

The lan{nil} interpreter uses lexical scoping.  What this means,
simply, is that variable references which are "textually within" the
code which binds them, are valid.  Those references which are not
"textually within" the binding form are not, and will (typically)
cause unbound-variable errors.  Consider the definition
.lisp
(defun make-associations (keys single-value)
   (mapcar #'(lambda (key) (cons key single-value)) keys))
.end_lisp
which takes a list of keys (perhaps for use by 3assoc*), and
returns an association list associating all of those keys with the
same single value.  The first argument to 3mapcar*, the lambda
expression, is technically a function.  (The 3#'* construct is
explained below.)  It is, however, textually
within the binding of the argument 3single-value*, so that
variable reference is lexical, and that function works in lan{nil}
as desired.  Consider the alternative form
.lisp
(defun make-associations (keys single-value)
   (mapcar #'make-one-association keys))
(defun make-one-association (key)
   (cons key single-value))
.end_lisp
which might appear to be equivalent.  The reference to
3single-value* in the definition of 3make-one-association* is
2not* textually within the binding of that variable, hence appears
"free".  Although this function (in the absence of extra declarations,
as described below) would function "properly" in the lan{maclisp} or
lan{zetalisp} interpreters, it will not in lan{nil}.  It is
interesting to note that  (again without special declarative
information) both the lan{maclisp} and lan{zetalisp} compilers
will treat the second example as an error (or at least produce
incorrect code), because although the interpreters do not enforce
lexical scoping rules, code is compiled that way.

A short note may be in order on the 3#'* construct which
appeared above.  3#'* is an abbreviation for 3(function
...)*, just as 3'* is an abbreviation for 3quote*.  In
lan{maclisp}, the two are equivalent.  However, in lan{nil} (and
in lan{zetalisp} too), use of this special form is
necessary to cause the proper (functional) interpretation of the form
being evaluated.  In fact, in the 3make-associations* example, it
is that special interpretation which makes the lexical reference to
3single-value* "work".  If 3quote* was used instead of
3function*, the example would not work as desired.  3function*
(or 3#'*) need not just be used around lambda expressions.  It may
also be used around function names (as in the second
3make-associations* example).  The effect of evaluating
3(function 2name*)* is equivalent to what the interpreter does
when it "evaluates" 2name* in the function position of a list
being evaluated.

lan{nil} does not restrict one to using only lexical scoping rules.
It is possible to declare to lan{nil} that a variable is
term_i{special}, and should be able to be referenced by code
2not* textually within the binding construct.  Or, perhaps a
variable should have a global toplevel value and not be bound
anywhere, or maybe even have a toplevel value, and be bound in some
places.  This is the purpose of the 3special* declaration, which
lan{nil} implements compatibly with lan{common lisp}, and which is
about the same as it is in lan{zetalisp} and lan{maclisp}.

Most of the time, term_i{special variables} are declared to be
special globally.  This means that the lan{nil} interpreter (and
compiler) will always treat the variable as being special, even if
there is no declaration for it at the place it is bound.  As a matter
of style, variables declared 3special* are usually given names
which begin and end with the character 3** so that they can be
visually distinguished from more "ordinary" lexically scoped
variables.  One way to globally declare a variable 3special* is
with 3defvar* ((defvar-fun)).  For instance,
.lisp
(defvar *leaves*)
(defun find-all-leaves (tree)
  (let ((*leaves* nil))		;1Empty set of leaves*
    (find-all-leaves-1 tree)	;1Grovel over the tree*
    *leaves*			;1And return the leaves found*
    ))
(defun find-all-leaves-1 (tree)
  (cond ((atom tree)
	   (cond ((not (memq tree *leaves*))
		  (setq *leaves* (cons tree *leaves*)))))
	(t (find-all-leaves-1 (car tree))
	   (find-all-leaves-1 (cdr tree)))))
.end_lisp
There are more esoteric (or lan{scheme}-like) ways in which the
above could have been performed, without the use of the special
variable 3*leaves**, but the above is fairly straightforward,
fairly efficient, and will run (both interpreted and compiled) compatibly
in lan{maclisp} and lan{zetalisp}.

The above intuitive (or, if you prefer, hand-waving and vague)
description can now be used to more formally define the terms of
term_i{scope} and term_i{extent} which are used to describe the
accessibility and lifetimes of things, of which variable bindings are
one instance.  The 2scope* of something tells 2where* it may
be validly referred to.  To say that something has term_i{lexical
scope} then means that it may be used anywhere "textually" within the
construct which "creates" the object (e.g., the lambda-expression
which binds a variable).  Note that this does not in itself imply that
the reference becomes invalid if that construct is exited.  That
dimension is the term_i{extent} of the object, which tells the
2time* during which the object (e.g., variable binding) is valid.
term_i{dynamic extent} means that the object (reference) is only
valid during the execution of the construct.  term_i{indefinite
extent} means that there is no such limitation.  Variable bindings in
the lan{nil} interpreter (which are not 3special*) have lexical
scope and indefinite extent.  This means upward funarg capability.

term_i{indefinite scope} means that there is no restriction on where
a valid reference may occur from.  This is the case with 3special*
variables;  the "free" references may be made from any piece of code.
The bindings of such variables, however, have only term_i{dynamic
extent};  they become invalid (are "unbound") when the binding
construct is exited.  This combination of scope and extent, which is
quite common, is referred to as term_i{dynamic scope}.

.chapter "Variables and Definitions"

Application of a lambda expression in lan{nil} is much like that of
lan{zetalisp}.  A lambda expression is of the general form
.lisp
(lambda 2lambda-list* {2declaration*}* {2form*}*)
.end_lisp
In the simplest case, 2lambda-list* is a (possibly empty) list of
variable names, which are the formal parameters to the lambda
expression when it is treated as a function.  There must be as many
arguments to the lambda-expression as there are variables.  Thus,
.lisp
((lambda (a b c) (list a b c)) 1 2 (+ 3 4))
 => (1 2 7)
.end_lisp
The lambda-list may also contain special keywords which begin with the
character 3&*.  These 2ampersand-keywords* are used for
various purposes, the most important of which is to allow functions to
take variable numbers of arguments.  They will be ignored here.

.defspec defun name lambda-list {declarations}* forms...
3defun* is pretty much like a lan{maclisp} or lan{zetalisp}
3defun*.  In lan{nil}, in case you are interested, a 3defun*
in the interpreter globally defines the function 2name* as a
closure over the lexical environment in which the 3defun* is
performed.  The 2lambda-list* is a lan{common lisp} compatible
lambda-list, which is mostly the same as that used by lan{zetalisp};
the special keywords 3&optional*, 3&rest*, 3&aux*, and
3&key* are interpreted accordingly, as described above;
3defun* simply associates the function name with a corresponding
lambda-expression constructed from the lambda-list, declarations, and
forms.
.end_defspec

.defmac defmacro name pattern forms...
3defmacro* is used for defining macros...  It is described in the
Maclisp Extensions Manual.
.end_defmac

.defmac defvar variable [init] [documentation]
3defvar* is used for "defining" variables.  It should only be used
"at top level" in a source file, not from within code.  If there is no
2init* form specified, then it simply globally declares
2variable* to be special.  If there 2is* an 2init* form
specified, then, if 2variable* does not have a value already, the
2init* form will be evaluated and 2variable* set to that.
2documentation*, if present, should be a string which "documents"
the variable.  It will be remembered somewhere where no one is likely
to find it.
.end_defmac

.defmac defparameter variable init [documentation]
This is like 3defvar*, except that 2variable* is
unconditionally set to the value of 2init*.  Thus, the 2init*
form must always be specified.
.end_defmac

.defmac defconstant variable init [documentation]
This is like 3defparameter*, but additionally states that
2variable* is a constant.  It is an error to bind or 3setq*
that variable.  Sometimes the lan{nil} compiler may take advantage
of this information.  If, when a 3defconstant* form is evaluated,
2variable* already has a value which is different from what
2init* evaluates to, a correctable error is signalled.

3defconstant* will fail to make 2variable* truly constant if
it already has a value not assigned by 3defconstant*, or even if
there is compiled code which references 2variable*.
.end_defmac

.chapter "Predicates"

.section "Equality"

.defun eq object1 object2
Returns 3t* if 2object1* and 2object2* are "the same".
In general,
.lisp
(setq x (compute-something))
(eq x x)
  => t
.end_lisp
Equal numbers are not necessarily 3eq*, however.  For numeric
equality, one should use 3eql*, or, if arithmetic equality
irrespective of type is desired (i.e., conversion from integer to
floating may be needed), 3=* ((=-fun)) should be used.
.end_defun

.defun eql object1 object2
This predicate is a slight extension of 3eq*.  It is used as the
default equality predicate by many lan{nil} functions.  Essentially,
it is 3equal* for non-structured objects:  two numbers are
3eql* if they are of the same type and numerically equal,
character objects are 3eql* if they represent the same characters,
etc.  However, structured objects, such as lists, strings, vectors,
and arrays, are 3eql* only if they are 3eq*.  Thus,
.lisp
(eql (add1 (sub1 0.0)) 0.0)	=>	t
(eq (add1 (sub1 0.0)) 0.0)	=>	nil
(eql (cons 'a 'b) (cons 'a 'b)) =>	nil
.end_lisp
.end_defun

.defun equal object1 object2
This is the more traditional (and more general, in some sense)
equality predicate.  If 2object1* and 2object2* are not
structured, then they are compared like 3eql* (above) does.
Two lists are 3equal* if their 3car*s and 3cdr*s are
respectively 3equal*.  Otherwise, if they are both arrays (which
includes strings, vectors, and bit-vectors), they are 3equal* if
they have the same rank and dimensions, the same element types (a
string cannot be equal to a non-string array of characters), and
3equal* elements.
.end_defun

.section "Types"

.defun null x
Returns 3t* if 2x* is 3nil*, 3nil* otherwise.
.end_defun

.defun not x
Same as 3null*.  3not* implies that 3nil* is representing
boolean 2false*, 3null* implies that it represents the empty
list.
.end_defun

.defun atom x
3t* if 2x* is not a cons, 3nil* if it is.
.end_defun

.defun listp x
3t* if 2x* is a cons or 3nil* (the empty list), 3nil*
otherwise.  Note that 3listp* does not examine anything but the
type of the object;  it does not verify that 2x* is actually a
"proper list", one whose last 3cdr* is 3nil*.
.end_defun

.defun consp x
3t* if 2x* is a 3cons*, 3nil* otherwise.
.end_defun

.chapter "Control and Program Structure"

.section "Binding"

.defspec let letlist {declaration}* forms...
3let* binds the variables to the values specified in
2letlist*, and evaluates 2forms* in that environment,
returning the value(s) resulting from the evaluation of the last
2form*.  The 2letlist* is a list of the form
.lisp
({2variable* | (2variable*) | (2variable* 2init-form*)}*)
.end_lisp
In the first two variants, the variable will be bound to 3nil*;
in the last, to the evaluation of 2init-form*.  All of the
2init-form*s in the letlist are evaluated before any of the
variables are bound.  For example,
.lisp
(let ((x 1) (y 2))
  (let ((x y) (y x))
    (list x y)))
  ==>  (2 1)
.end_lisp
That form is equivalent to
.lisp
((lambda (x y)
   ((lambda (x y)
      (list x y))
    y x)))
 1 2)
.end_lisp
.end_defspec

.defspec let* letlist {declaration}* forms...
3let** is like 3let* syntactically, but the variables are
bound sequentially rather than in parallel.  That is, first the first
init-form is evaluated and the first variable bound to that, then the
second init-form is evaluated in that new environment, etc.  So,
.lisp
(let* ((x 1) (y 2))
  (let* ((x y) (y x))
    (list x y)))
  => (2 2)
.end_lisp
.end_defspec


.section "Flow of Control"

.defspec cond {(predicate-form {consequent}*)}*
Ordinary everyday lan{lisp} 3cond*.  Each "clause" is examined
in succession:  the predicate-form is evaluated, and if the result is not
3nil*, then the 2consequent*s of that clause are evaluated,
and the value(s) of the last are returned as the value(s) of the
3cond*, without further examination of any other clauses.  If
there are no 2consequent*s in the clause, the value the predicate
form returned is returned instead.  If no predicate-form "succeeds",
3cond* returns 3nil*.
.lisp
(defun fact (n)
   (cond ((= n 0) 1)
	 (t (times n (fact (sub1 n)))))
.end_lisp
.end_defspec

.defspec if predicate-form then-form [else-form]
A simpler binary 3cond*.
.lisp
(defun fact (n)
  (if (= n 0) 1 (times n (fact (sub1 n)))))
.end_lisp
.end_defspec

.defspec case item {(keyspec {consequent}+)}*
This is similar to, but somewhat more general than, the fun_i{caseq}
and fun_i{selectq} macros of lan{maclisp} and lan{zetalisp}
(which lan{nil} define in terms of 3case*).  The
2item* is evaluated, then is matched against 2keyspec* of each
clause in turn.  If it matches, then the 2consequent*s of that
clause are evaluated, and the value(s) of the last returned as the
value of the 3case*;  if none match, the 3case* form evaluates
to 3nil*.

A 2keyspec* may be an atom or a list.  The key matches if
2keyspec* is a list and the value of 2item* is a member (using
the predicate 3eql*) of
that list, or if 2keyspec* is the atom 3t* (allowing an
"otherwise" clause), or if 2keyspec* is an atom and is 3eql*
to the value of 2item*.  3eql* ((eql-fun)) is essentially
3eq* that also "works" on numbers;  in general, 3(eql 1.0 (1+
(1- 1.0)))* is true, but 3(eq 1.0 (1+ (1- 1.0)))* cannot be
depended on.
.lisp
(defun integer-description (n)
  (case n
    (0 "none at all")
    (1 "just one")
    (2 "a couple")
    ((3 4) "a few")
    ((5 6 7) "several")
    (t "many")))
.end_lisp
.end_defspec

.section "Iteration"

.defun mapl function &rest lists
.defun1 mapc function &rest lists
.defun1 maplist function &rest lists
.defun1 mapcar function &rest lists
.defun1 mapcon function &rest lists
.defun1 mapcan function &rest lists
These are the "traditional" functions for iteration down lists.  There
must be at least one list specified;  the iteration terminates when
any list "runs out".  The function is called on as
many arguments as there are lists.  3mapl*, 3maplist*, and
3mapcon* apply the function to successive sublists of the lists;
3mapc*, 3mapcar*, and 3mapcan* to successive elements.

3mapl* and 3mapc* are primarily for effect;  they both return
the first 2list* argument given to them.

3maplist* and 3mapcar* return a new list, the elements of
which are the results of applications of 2function*.  That list
will thus have as many elements as the shortest of the 2lists*.

3mapcon* and 3mapcan* "splice together" the results of the
applications of 2function*, (as if) by 3nconc*.  This allows
multiple new elements (or none) to be returned.

.lisp
(mapc #'print '(a b c))
1prints*
a
b
c
1and returns*
(a b c)
.end_lisp
.lisp
(mapl #'print '(a b c))
1prints*
(a b c)
(b c)
(c)
1and returns*
(a b c)
.end_lisp
.lisp
(mapcar #'(lambda (x y) (plus (times x 2) y)) '(1 2 3) '(4 5 6))
  => (6 9 12)
.end_lisp
.lisp
(defun odd-ones (l)
  (mapcan #'(lambda (x) (and (oddp x) (list x))) l))
(odd-ones '(1 2 3 4))
  => (1 3)
.end_lisp
.lisp
(defun destructively-remove-duplicates (l)
  (mapl #'(lambda (sublist)
	     (rplacd sublist (delq (car sublist) (cdr sublist))))
        l))
(destructively-remove-duplicates '(a b b c b d e c))
 => (a b c d e)
.end_lisp

Note that 3mapl* is the same as the lan{maclisp} and
lan{zetalisp} function 3map*.  In lan{nil}, the function
3map* is a more general sequence iteration function.
.end_defun

.defspec dotimes (var count) {declaration}* body...
Evaluates the forms in 2body* in an environment where 2var* is
stepped from 0 up to (but not including) the value of 2count*.
2body* is actually a 3tagbody* body, and 3dotimes*
establishes an implicit block named 3nil*, thus 3return* may
be used to return a value from the 3dotimes* before the iteration
terminates;  see (block-tagbody-section-page).
.end_defspec

.defspec dolist (var list) {declaration}* body...
2body* is evaluated with 2var* bound to the successive
elements of the value of the form 2list*.   2body* is actually
a 3tagbody* body, and 3dolist* establishes an implicit block
named 3nil*, thus 3return* may be used to return a value from
the 3dolist* before the iteration terminates;  see
(block-tagbody-section-page).
.end_defspec

.defspec dovector (var vector) {declaration}* body...
Similar to 3dolist*, but for vectors.
.end_defspec

.section "Block and Tagbody"
.setq block-tagbody-section-page section-page

3block* and 3tagbody* together implement the flow-of-control
functionality provided by standard 3prog*.  3prog* could have
been implemented as a macro in terms of these and 3let*,
and in fact is described in that fashion by lan{common lisp}.

.defspec block name {declaration}* {form}*
3block* evaluates the 2forms*.  If a lexically apparent
3return-from* is evaluated with a tag of 2name* (or 2name*
is 3nil* and a 3return* is evaluated), then the value(s) of
the form given to 3return* or 3return-from* are returned as
the value of the 3block* form.  Otherwise, the 3block* form
returns the value(s) of the evaluation of the last 2form*.
.end_defspec

.defspec return form
Evaluates 2form*, and returns the value(s) it returns from the
nearest lexically apparent 3block* with a name of 3nil*.  Many
special forms implicitly establish blocks named 3nil*, such as
3do*, 3dolist*, 3dotimes*, 3dovector*.

Note that this differs subtly from lan{zetalisp}.  In
lan{zetalisp}, 3return* returns from the innermost 3prog*
(i.e., block) which is 2not* named 3t*.  In lan{nil} (and
lan{common lisp}), a 3return* to a block name of 3nil* only
matches a block name of 3nil*, and the block name 3t* is not
distinguished in any way.
.end_defspec

.defspec return-from name form
Evaluates 2form*, and returns the value(s) it returns from the
nearest lexically apparent 3block* with a name of 2name*.
2name* is not evaluated.
.end_defspec

.defspec tagbody {tag | form}*
The body of a tagbody is examined sequentially.  If a form is atomic,
then it is a tag and is ignored, otherwise it is evaluated.  If during the
evaluation a lexically apparent call to 3go* is evaluated with an
argument of one of the tags, then control is returned to that point
within the 3tagbody* form, which resumes its interpretation.  If
the interpretation reaches the end of the 3tagbody*, the result is
3nil*.
.end_defspec

.defspec go tag
2tag* is not evaluated.  Control is returned to the nearest
lexically apparent 3tagbody* form with a tag name of 2tag*,
which resumes interpretation of the tagbody at the form following that
tag.
.end_defspec

.defspec prog varlist {declaration}* {tag | form}*
Standard 3prog*.  2varlist* may be a list of variables, or a
list of lists of variables and their initial values.  They will be
bound in parallel.  3prog* can be built from the above primitives:
.lisp
(let 2varlist*
   2the declarations*
   (block nil
     (tagbody 2the tags and forms*)))
.end_lisp

For compatibility with lan{zetalisp}, if the first "argument" to
3prog* is a non-null atom, then that is used as the name of the
block, with the varlist following.
.end_defspec


.defmac loop gubbish...
3loop* is described in another document.  It is noted here because
it deals correctly with the incompatibilities between lan{zetalisp}
and lan{common lisp} blocks and returns.
.end_defmac

.section "Generalized Variables"

.defmac setf place value
3setf* is a general macro which is used to modify things.
2place* is a form which describes the place to be modified;  it
may be something like 3x*, a variable, 3(car
2something*)*, or even a user-defined structure reference.  It
expands into code which will modify that 2place* to be
2value*, additionally guaranteeing that the return value of the
3setf* form is that value.  Thus, one may use
.lisp
(setf (car l) 'foo)
.end_lisp
instead of 
.lisp
(rplaca l 'foo)
.end_lisp
The utility of this is that the special functions (if indeed there are
any) necessary to perform the specified updating need not be known
about.  In fact, lan{common lisp} does not even define most updating
functions, only that the referencing functions may be used with
3setf*.

If 2place* is a variable, then 3setf* is equivalent to
3setq*.  2place* may also be any car/cdr function, sequence
function (such as 3nth*, 3elt*, 3vref*, and 3bit*), or
any structure accessor defined by either 3defflavor* (which is not
described here) or 3defstruct* (in the Maclisp Extensions Manual).
.end_defspec


.chapter "List Manipulation"

.defun car
.defun1 cdr
.defun1 c****r
3car* and 3cdr* combinations to 4 deep, as in lan{maclisp}.
.end_defun

.defun cons x y
.defun1 ncons x
.defun1 xcons x y
.defun list* e1 e2 e3 ... en last-cdr
.defun list e1 e2 e3 ... en
.end_defun

.defun append {list}*
.lisp
(append '(a b c) '(d e f)) => (a b c d e f)
.end_lisp
All but the last of the 2list*s are copied.
.end_defun

.defun nconc {list}*
Concatentates the lists, destructively;  the last 3cdr* of each is
bashed to point to the following list.
.lisp
(setq a '(a b c))
(setq b nil)
(setq c '(d e f))
(nconc a b c)
   => (a b c d e f)
a  => (a b c d e f)
b  => nil
c  => (d e f)
.end_lisp
.end_defun

.defun nth index list
Returns the 2index*th element of 2list*, zero-origined.
3nth* is compatible with the 3nth* of lan{maclisp} and
lan{zetalisp}, and differs from that of lan{interlisp}.  Note that
the argument order differs from that used for most other
sequence-accessing functions defined by lan{nil} and lan{common
lisp}.
.end_defun

.defun nthcdr index list
Returns the result of 3cdr*ing 2list* 2index* times.
.end_defun

.defun last list
Returns the last 3cons* of 2list*, unless 2list* is
3nil* in which case 3nil* is returned.
.end_defun


.defun nreconc list other
This destructively reverses 2list* and bashes its last 3cdr*
to be 2other*;  that is, it is like doing
.lisp
(nconc (nreverse list) other)
.end_lisp
.end_defun

Certain other list operations, such as fun_i{reverse} and
fun_i{nreverse}, are actually generic sequence operations, described
in chapter (sequence-chapter).

.section "Using Lists as Sets"

One common use of lists is as sets of objects.  lan{nil} (and
lan{common lisp}) provide a complement of functions for doing this.

All of the functions take similar arguments.  Normally, they use
3eql* as their predicate, so that they work on numbers properly
also.  If this is not suitable for the purpose, then a predicate may
be specified by giving it as the 3:test* keyworded argument.  For
instance,
.lisp
(union '((a b) (b) (c)) '((d) (e) (a b) (b)) :test #'equal)
  => ((a b) (b) (c) (d) (e))
.end_lisp
The sense of the predicate can be reversed by using 3:test-not*
instead of 3:test*.

Sometimes the elements of the set are datastructures of some sort, and
one desires to only compare one part of the datastructure, but not
write a predicate to compare things.  If the 3:key* keyworded
argument is used, then that is a function which will be applied to
each element as it is tested, and the results of that will be given to
the equality predicate, rather than the elements themselves.  For
example,
.lisp
(union '((a) (b) (c)) '((d) (e) (a) (b)) :key #'car)
  => ((a) (b) (c) (d) (e))
.end_lisp
The ordering of the result may not be depended on;  neither may the
result if either of the inputs contains duplicate elements (as defined
by the predicate).

.defun union list1 list2 &key :test :test-not :key
Returns the union of 2list1* and 2list2*.
.end_defun

.defun intersection list1 list2 &key :test :test-not :key
Returns the intersection of 2list1* and 2list2*.
.end_defun

.defun set-difference list1 list2 &key :test :test-not :key
Returns the set difference of 2list1* and 2list2* (a list of
the elements of 2list1* which are not present in 2list2*,
according to the predicate).
.end_defun

.defun set-exclusive-or list1 list2 &key :test :test-not :key
Returns a list of the elements which occur in either 2list1* or
2list2*, but not both, according to the predicate.
.end_defun


.defun subsetp list1 list2 &key :test :test-not
Returns 3t* if 2list1* is a subset of (but not necessarily a
proper subset of) 2list2*, 3nil* otherwise.
.end_defun


.chapter "Symbols"

.defun get symbol indicator
Although 3get* works on "disembodied property lists" for
lan{maclisp} and lan{zetalisp} compatibility, it treats a first
argument which si neither a symbol nor a list as an error.
(lan{maclisp} 3get* will return 3nil* for other objects.)
.end_defun

.defun putprop symbol value indicator
As in lan{maclisp}, works on both symbols and disembodied property
lists.
.end_defun

.defun remprop symbol indicator
lan{maclisp}-compatible 3remprop*.  If 2symbol* (which may
also be a disembodied property list) has an 2indicator* property,
it is spliced out of the property list, and the subpart of the
property list whose 3car* is (was) the value for that indicator is
returned.  If there is none, 3nil* is returned.
.end_defun

.defun plist symbol
Returns the propertly list of 2symbol*.  Does 2not* work on
disembodied property lists.
.end_defun

.defun setplist symbol new-plist
Bashes the property list of 2symbol* to be 2new-plist*.  Does
2not* work on disembodied property lists.  Use of this should
normally be left to only those functions which carefully interlock
addition and deletion from the property list, to avoid both timing
screws and elimination of properties needed by "someone else".
.end_defun


.chapter "Numbers"

lan{nil} numbers may be integers, floating-point, ratios, or even
complex.  Most arithmetic functions operate on any types, and convert
as necessary;  in general, contagion proceeds from integer -> ratio ->
float -> complex.  For the operations performed on the real and
imaginary parts of complex numbers, the conversion is similar.

Complex numbers in lan{nil} are on the order of days old.  Although
they exist, they will not be supported by most functions in lan{nil}
for some time.

.defun = number &rest more-numbers
.defun1 /= number &rest more-numbers
Return 3t* if all of the numbers (in all pairwise combinations)
are equal or not-equal respectively.  Performs type conversions as
necessary to do the comparisons.
.end_defun

.defun < number &rest more-numbers
.defun1 <= number &rest more-numbers
.defun1 >= number &rest more-numbers
.defun1 > number &rest more-numbers
The numbers must all be real numbers.  Each function returns 3t*
if all consequetive pairs of arguments satisfy the appropriate
comparison.  Type conversions are performed as necessary to do the
comparisons.
.end_defun

.defun zerop number
3t* if 2number* is integer, floating, or complex 30*,
3nil* otherwise.
.end_defun

.defun plusp real-number
.defun1 minusp real-number
.end_defun


.defun 1+ number
.defun1 add1 number
Adds one to 2number*.
.end_defun

.defun 1- number
.defun1 sub1 number
Subtracts one from 2number*.
.end_defun

.defun + &rest numbers
.defun1 plus numbers
Adds together the numbers.
.end_defun

.defun - number &rest more-numbers
3(- 2number*)* performs unary negation on 2number*.
With more than one argument, it subtracts the sum of the rest from the
first.
.end_defun

.defun difference &rest numbers
Subtly different from 3-*; 3difference* is lan{maclisp}
compatible.  If there are no 2numbers*, 30* (the identity) is
returned. Otherwise, the sum of all the numbers but the first is
subtracted from the first.  That is, 3(difference 2x*)* =>
2x*, not 3(- 2x*)*.
.end_defun

.defun * &rest numbers
.defun1 times &rest numbers
Returns the product of all the 2numbers*.  If none are given,
3** returns 31*, the multiplicative identity.
.end_defun

.defun / number &rest more-numbers
3(/ 2number*)* returns the inverse of 2number*.
Otherwise, 3/* divides the first by the product of the rest.  If
all of the involved quantities are integers, then 3/* will produce
a ratio rather than truncating the answer (as 3quotient* does).
.end_defun

.defun quotient &rest numbers
If there are no 2numbers*, then 2quotient* returns 31*,
the multiplicative identity.  Otherwise, it divides the first by the
product of the rest;  with exactly one argument, that argument is
returned.  If all of the involved quantities are integers, then
3quotient* will return a truncated integer result, rather than
convert to either a ratio or a floating result.  This is compatible
with lan{maclisp}.
.end_defun

.defun remainder integer1 integer2
3(remainder 2n1* 2n2*)* => 2r*, such that
.lisp
(plus (times (quotient 2n1* 2n2*) 2n2) 2r*) => 2n1*
.end_lisp
This is lan{maclisp} compatible.
.end_defun

.defun expt base power
Raises 2base* to the power 2power*.  If both are integers the
result will be an integer.  If either are floating, then the result
will be floating, computed by logarithms.
.end_defun

.defun exp number
Raises 2e*, the base of natural logarithms, to the power
2number*.  This currently always uses floating point, and
2number* must be real.
.end_defun

.defun log number &optional base
Returns the logarithm of 2number* in 2base*, which defaults to
2e*.  This currently always uses floating point, so 2number*
and 2base* must be real numbers.
.end_defun

.defun sqrt number
Returns the (principal) square root of 2number*.  This currently
uses only floating point, so 2number* must be real although the
result may be complex.
.end_defun

.defun isqrt integer
Integer square root.  Returns an integer (truncates).
.end_defun

.defun sin radians
.defun1 cos radians
.defun1 tan radians
.defun1 sinh radians
.defun1 cosh radians
.defun1 tanh radians
.defun1 asin real
.defun1 acos real
Standard trig.  Only deal with floating point, hence the arguments
must be real.
.end_defun

.defun atan x &optional y
.end_defun

.section "Logical Operations"

Integers in lan{nil} are all represented in twos-complement
notation.  They may be viewed as a vector of bits extended infinitely;
a negative integer extended with ones, a non-negative integer extended
with zeros.

.defun logbitp bit-number integer
Returns 3t* if the bit at position 2bit-number* is on in
2integer*, 3nil* otherwise.  2bit-number* is
zero-origined, with 0 being the least significant bit.  Thus,
.lisp
(logbitp 0 1)		=>  t
(logbitp 0 -2)		=>  nil
(logbitp 1 1)		=>  nil
(logbitp 259259259 15)  =>  nil
(logbitp 259259259 -2)  =>  t
.end_lisp
.end_defun

.defun logand &rest integers
.defun1 logior &rest integers
.defun1 logxor &rest integers
.defun1 logeqv &rest integers
.defun1 lognand integer1 integer2
.defun1 lognor integer1 integer2
.defun1 logandc1 integer1 integer2
.defun1 logandc2 integer1 integer2
.defun1 logorc1 integer1 integer2
.defun1 logorc2 integer1 integer2
.defun1 lognot integer
These routines supercede the use of the 3boole* function.
.end_defun

.defun integer-length integer
This returns the size of 2integer*.  This is defined such that
2integer* in twos-complement notation can fit in a field that long
plus one.
.lisp
(integer-length 0)	=>  0
(integer-length -1)	=>  0
(integer-length 1)	=>  1
(integer-length -2)	=>  1
.end_defun
.end_defun


.section "Conversions"

.defun float number
Converts number to floating-point.
.end_defun

.defun fix number
Converts 2number* to an integer, by 3floor*ing (rounding
towards negative infinity).  This is compatible with lan{maclisp}.
.end_defun


.chapter "Sequences, Strings, and Arrays"

The parts of lan{nil} dealing with sequences, strings, and arrays,
are gradually being brought up to lan{common lisp} specifications.
If more information is needed than is presented here, either the NIL
Release Notes or a bootleg Common Lisp Manual should be consulted.

.section "Sequences"

A sequence is considered to be either a list or a vector (which is by
definition a one-dimensional array).  A few functions which might be
useful are presented here.

Many sequence function which take an 2start* and
2end* arguments to delimit some subpart of the sequence being
operated on.  As a general rule, the 2start* is 2inclusive*,
and the 2end* is 2exclusive*;  thus the length of the
subsequence is the difference of the 2end* and the 2start*.
The 2start* typically defaults to 30*, and the 2end* to
the length of the sequence.
Also, the 2end*, where it is an optional argument, may be
explicitly specified as 3nil*, and will still default to the
length of the sequence.

.defun elt sequence index
This is the general sequence access function.  It returns the
2index*th element of 2sequence*;  the index is taken to be
zero-origined.  This will work generally on lists, vectors, strings
(which are by definition vectors anyway), etc.  One may modify an
element of a sequence by using 3setf*.  For instance,
.lisp
(setq v (make-vector 10))
  => #(nil nil nil nil nil nil nil nil nil nil)
(setf (elt v 5) 'foo)
  => foo
.end_lisp
And now,
.lisp
v => #(nil nil nil nil nil foo nil nil nil nil)
.end_lisp
.end_defun

.defun length sequence
Returns the length of 2sequence*.
.end_defun

.defun subseq sequence start &optional end
Returns a sequence of the same type as 2sequence*, containing
elements from 2start* up to (but not including) 2end*.
.lisp
(subseq "foo on you" 4)		=>  "on you"
(subseq "foo on you" 4 6)	=>  "on"
(subseq "foo on you" 4 3)	=>  2is an error*
(subseq '(a b c d) 1 3)		=>  (b c)
.end_lisp

.defun copy-seq sequence
Copies the sequence 2sequence*.  This might be necessary if the
result is going to be modified, for instance.
.end_defun

.defun reverse sequence
Returns a copy of 2sequence*, with the elements in the opposite
order.
.end_defun

.defun nreverse sequence
Reverses 2sequence*, destructively;  it does not create a copy.
Note that if 2sequence* is a list, one should always use the
return value of 3nreverse*;  that is, do something like
.lisp
(setq l (nreverse l))
.end_lisp
rather than just
.lisp
(nreverse l)
.end_lisp
This is in general true for all destructive list operations, such as
3sort* and 3delq*.  The reason is that although the cons cells
of the input list are reused, the pointer returned is not necessarily
the same as the original "first" cons of the list.
.end_defun

.defun make-sequence type size &key :initial-element
Makes a sequence of the given type and size.  The types of most
interest are 3list*, 3string*, 3vector*, and
3bit-vector*.  If the 3:initial-element* keyworded argument is
given, then the sequence is initialized with that element.  Otherwise,
the initialization depends on the type of the sequence.  For instance,
.lisp
(make-sequence 'list 5 :initial-element t)
  => (t t t t t)
(make-sequence 'string 5 :initial-element #\*)
  => "*****"
.end_lisp
.end_defun


.defun concatentate result-type &rest sequences
Creates a sequence of type 2result-type* (as might be given to
3make-sequence*), and stores in it the concatenation of all the
elements of 2sequences*.  For instance,
.lisp
(concatentate 'string "foo" "bar" "baz")
  =>  "foobarbaz"
(concatenate 'list "foo" "bar" '(1 2))
  => (#\f #\o #\o #\b #\a #\r 1 2)
.end_lisp
.end_defun

.defun map result-type function &rest sequences
This is the general sequence mapping function.  Note that this is
different from the lan{maclisp} and lan{zetalisp} 3map*
function, which is renamed to 3mapl* by lan{common lisp}.

The result is a new sequence of type 2result-type* (cf.
3make-sequence*), containing the results of applying
2function* to the elements of 2sequences*.  There must be at
least one 2sequence* specified;  2function* gets as many
arguments as their are sequences--first it gets called on all of the
first (index 0) elements, then on all the second elements, etc.  The
iteration terminates when the end of any of the sequences is reached,
so the result will have the same length as the shortest input
sequence.
.lisp
(map 'list #'cons "abc" '(a b c))
  => ((#\a . a) (#\b . b) (#\c . c))
.end_lisp
.end_defun


.defun some predicate &rest sequences
If the result of applying 2predicate* to the corresponding
elements of 2sequences* is not 3nil*, that value is returned;
otherwise, 3nil* is returned.  The predicate is called with as
many arguments as their are sequences;  first on all of the first
(index 0) elements, etc.  Only the parts of the sequences up to the
length of the shortest are considered.
.end_defun

.defun every predicate &rest sequences
Like 3some*, but returns 3t* if the result of applying
2predicate* to the elements of 2sequences* is never 3nil*,
3nil* otherwise.
.end_defun

.defun notany predicate &rest sequences
Returns 3t* if the result of applying 2predicate* to the
corresponding elements of 2sequences* is always 3nil*,
3nil* otherwise.
.end_defun

.defun notevery predicate &rest sequences
...
.end_defun

.defun fill sequence element &key :start :end
Replaces the elements of 2sequence* with 2element*, from
2start* (default 0) up to 2end* (default length of the
sequence).
.lisp
(setq a '(0 1 2 3 4 5 6))
(fill a nil :start 2 :end 4)
  =>  (0 1 nil nil 4 5 6)
.end_lisp
And now,
.lisp
a  =>  (0 1 nil nil 4 5 6)
.end_lisp
.end_defun

.defun replace sequence1 sequence2 &key :start :end :start1 :end1 :start2 :end2
Replaces the elements of the specified subsequence of 2sequence1*
by the elements of the specified subsequence of 2sequence2*.
.lisp
(setq v (make-sequence 'vector 10))
  => #(nil nil nil nil nil nil nil nil nil nil)
(replace v '(1 2 3 4 5 6))
  => #(1 2 3 4 5 6 nil nil nil nil)
v => #(1 2 3 4 5 6 nil nil nil nil)
.end_lisp

2start* and 2end* are used as defaults for 2start1*,
2end1*, 2start2*, and 2end2*, which otherwise default to
0 and the lengths of the corresponding sequences.  The number of
elements transferred is the length of the shorter subsequence.
.end_defun


.section "Strings"

There is a large complement of string functions in lan{nil}, only a
few of which will be mentioned here.  Mostly they are like those used
in lan{zetalisp}.

.defun string-equal string1 string2 &optional start1 start2 end1 end2
This routine is the basic routine for doing case-independent string
equality tests.  That is,
.lisp
(string-equal "foo" "Foo")  =>  t
(equal "foo" "Foo")	    =>  nil
.end_lisp
As usual, the starts default to 0, and the ends to the lengths of the
strings.  If the lengths of the specified substrings differ, then the
strings are not string-equal.  Note that this function takes
positional rather than keyworded optional arguments, for historical
reasons.
.end_defun

.defun string-lessp string1 string2 &optional start1 start2 end1 end2
Returns 3t* if the specified substring of 2string1* is "less
than" that of 2string2*.  The comparison is case-independent;
effectively, lowercase characters are compared as if they were
uppercase.  If the first substring is a prefix of the second, then it
is "lessp".
.end_defun

.defun substring string start &optional end
Like 3subseq* ((subseq-fun)).  If the specified range is the
entire string, the string may not be copied.
.end_defun

.defun string-upcase string
Returns a copy of 2string*, with all lowercase characters
converted to uppercase.
.end_defun

.defun string-downcase string
Returns a copy of 2string*, with all uppercase characters
converted to lowercase.
.end_defun


.section "Arrays"

lan{nil} supports a large portion of the lan{common lisp} array
specification currently.  The lan{maclisp} compatible array routines
have been lost during the conversion, and have not been re-implemented
yet.  What is described here is a simple subset of what is offered.

In lan{nil}, a one-dimensional array is a vector.  Some types of
arrays have restrictions on the types of objects which can be stored
in them.  For example, arrays which can only hold string characters
are 3string-char* arrays, and if they are one-dimensional (and
hence vectors), they are strings.  An array which can hold any type of
object is termed a 3general* array.  At this time, that is the
most useful type of array (other than the very common special types
3string* and 3bit-vector*), so that is all that will be
discussed here.  Also, obscure, esoteric, and non-working features
have been omitted.

In lan{nil}, an array is an object all its own.  They do not need to
be associated with symbols or treated as functions in any strange way
(as had been the case in lan{maclisp} in the past).

.defun make-array dimensions
This creates an array with the specified dimensions.  2dimensions*
may be either a single non-negative fixnum, or a list of dimensions.
If it is a fixnum, then a one-dimensional array (vector) is created;
otherwise, the created array will have a rank of the number of
dimensions specified.  Thus, a 103x*10 array could be created with
.lisp
(make-array '(10 10))
.end_lisp
.end_defun

.defun aref array &rest indices
Returns the element of 2array* selected by the 2indices*.  The
number of indices must equal the rank of the array, and each index
must be a non-negative fixnum less than the size of the corresponding
dimension.

To update an element of an array, use 3setf* with 3aref*:
.lisp
(setf (aref a i j) new-value)
.end_lisp
.end_defun

.defun array-rank array
Returns the rank (number of dimensions) of 2array*.
.end_defun

.defun array-dimension array dimension-number
Returns the size of the 2dimension-number* dimension of
2array*.  The dimensions are numbered zero-origined;
dimension-number must be non-negative, and less than the rank of
2array*.  If an array had been created by 3(make-array '(2 3
4))*, then its 30* dimension is 32*, its 31* dimension
33*, etc.
.end_defun

.defun array-dimensions array
Returns a list of the dimensions of 2array*.  This could then be
given to 3make-array* to make another array with the same
dimensionality.
.end_defun


.chapter "Input and Output"

.section "Basic I/O"

.section "Interacting with the User"

Some functions of potential interest.

.defun format destination control-string &rest arguments
3format* provides ways to produce simple to fancy text output.
A simple call might look like
.lisp
(format t "~&The ~A count was ~D.~%" 'cat 10)
.end_lisp
The 3t* tells format its text to the default output stream (just
like giving 3print* no 2stream* argument).  Within the
2control-string*, a tilde introduces a 3format* directive.
The directives in the above string mean (respectively) go to a new
line if needed, 3princ* an argument (taken from the
2arguments*), print an argument as a decimal number, and output a
newline (3terpri*).  The output from that thus looks like
.lisp
The CAT count was 10.
.end_lisp

3format* is almost entirely compatible with the 3format* used
in lan{maclisp} and lan{zetalisp}.  In fact, it uses the same
source as the one used in both lan{pdp-10} and lan{multics}
lan{maclisp} (and has some of the same bugs).  The only things
missing in the lan{nil} version are the operations which deal with
floating-point numbers.  More details on 3format* may be found in
either the Maclisp Extensions Manual or the Lisp Machine Manual;  the
former documents this version of 3format* more accurately.
.end_defun

.defun y-or-n-p &optional message stream
Prints the string 2message* to the stream, which defaults to the
value of 3query-io*, and then reads a character.  3y-or-n-p*
requires that the character be either 3y* or 3n*, and returns
3t* if it is 3y* or 3nil* if it is 3n*.  It is unusual
to specify the stream argument to 3y-or-n-p*, as the default will
almost always suffice.
.end_lisp

.defun yes-or-no-p &optional message stream
Somewhat like 3y-or-n-p*.  The input, however, is an entire line,
which must be either 3yes* or 3no*.  3yes-or-no-p* is
oriented towards unexpected questions which may have significant
consequences or require thought:  it flushes all typeahead, and beeps.
.end_defun

.defun format-y-or-n-p format-string &rest format-args
Like 3y-or-n-p*, but uses 3format* to display
2format-string* with arguments 2format-args*.
.end_defun

.defun format-yes-or-no-p format-string &rest format-args
Like 3yes-or-no-p*, but uses 3format* like
3format-y-or-n-p*.
.end_defun

.defun readline-with-prompt prompt-string &rest read-args
This is a convenient way to read a line of text from the terminal,
with a prompt string.  It is better than printing the prompt yourself
and calling 3readline*, because the input processor knows about
the prompt string and can reprint it as necessary.  2read-args*
are interpreted like 3read* does;  typically, none need to be
given.
.end_defun

.defun read-with-prompt prompt-string &rest read-args
Similar to 3readline-with-prompt*, but uses 3read*.
.end_defun


.chapter "Interacting with NIL"


