perm filename MCMAN1.S78[206,LSP]1 blob sn#345119 filedate 1978-03-31 generic text, type T, neo UTF8
**DRAFT**                         The Language                         **DRAFT**

                             Part 1 - The Language

                               Table of Contents

1.      General Information  . . . . . . . . . . . . . . . . . . . . . . . . 1-1
1.1     The Maclisp Language . . . . . . . . . . . . . . . . . . . . . . . . 1-1
1.2     Structure of the Manual  . . . . . . . . . . . . . . . . . . . . . . 1-3
1.3     Notational Conventions . . . . . . . . . . . . . . . . . . . . . . . 1-4

2.      Data Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1-7

3.      The Basic Actions of LISP  . . . . . . . . . . . . . . . . . . . . .1-13
3.1     Binding of Variables . . . . . . . . . . . . . . . . . . . . . . . .1-13
3.2     Evaluation of Forms  . . . . . . . . . . . . . . . . . . . . . . . .1-15
3.3     Application of Functions . . . . . . . . . . . . . . . . . . . . . .1-17
3.4     Special Forms  . . . . . . . . . . . . . . . . . . . . . . . . . . .1-21
3.5     Binding Context Pointers . . . . . . . . . . . . . . . . . . . . . .1-24

December 5, 1977                                                        Page 1-1
**DRAFT**                     General Information                      **DRAFT**

1.  General Information

1.1  The Maclisp Language

   Maclisp is a dialect of  Lisp developed at M.I.T.'s Project MAC  and M.I.T.'s
Artificial Intelligence Laboratory  for use in artificial  intelligence research
and  related fields.   Maclisp  is descended  from the  commonly-known  Lisp 1.5
dialect; however, many features of the language have been changed or augmented.

   This document is intended both as a reference source for the language  and as
a user's guide to three implementations.  These are, in chronological order, the
M.I.T. Artificial Intelligence Lab's  implementation on the DEC  pdp-10 computer
under  their  operating   system  ITS,  hereafter   referred  to  as   "the  ITS
implementation,"  Project MAC's  implementation  on Honeywell's  version  of the
Multics system, hereafter referred  to as "the Multics implementation,"  and the
version  that runs  on  the DEC  pdp-10  under DEC's  TOPS-10  operating system,
hereafter  called "the  DEC-10 implementation."  The DEC-10  implementation also
runs under  TENEX by  means of  a TOPS-10  emulator.  Since  the ITS  and DEC-10
implementations are closely related, they are sometimes referred to collectively
as  the  pdp-10  implementation.    There  are  reputed  to  be   several  other

   These implementations  are mostly  compatible; however,  some implementations
have extra features designed to exploit peculiar features of the system on which
they run, and some implementations are temporarily missing some  features.  Most
programs  will work  on any  implementation, although  it is  possible  to write
machine-dependent code if you try hard enough.

   The Maclisp system  is structured as an  environment, which is  essentially a
set  of  names and  bindings  of those  names  to data  structures  and function
definitions.   The  environment contains  a  large number  of  useful functions.
These functions can be used through an interpreter to define other functions, to
control the environment, to do useful work, etc.

   The interpreter is the basic user  interface to the system.  This is  how the
user enters "commands." When Maclisp is not doing anything else, such as running
a program, it waits for the user  to enter a Lisp form.  This form  is evaluated
and  the value  is  printed out.   The  form may  call  upon one  of  the system

December 5, 1977                     ∪1-1.                              Page 1-1
**DRAFT**                   Maclisp Reference Manual                   **DRAFT**

functions (or a user-defined function,  of course) to perform some  useful task.
The evaluation  of a  form may  initiate the  execution of  a large  and complex
program,  perhaps never  returning to  the "top  level" interpreter,  or  it may
perform some  simple action and  immediately wait for  the user to  type another

   It is also possible to get  into the interpreter while a program  is running,
using  the break  facility.  This  is primarily  used in  debugging  and related
programming activities.

   The functions invoked by the top-level interpreter may be  executable machine
programs, or they may themselves  be interpreted.  This is entirely a  matter of
choice and convenience.  The system functions are mostly machine programs.  User
functions are usually first used interpretively.  After they work,  the compiler
may be applied  to them, turning  them into machine  programs which can  then be
loaded into the environment.

   All of this is done  within a single consistent language, Lisp,  whose virtue
is that the data structure is simple and general enough that programs may easily
operate on programs, and that the program structure is simple and general enough
that it can be used as a command language.

Page 1-2                             ∪1-1.1                     December 5, 1977
**DRAFT**                     General Information                      **DRAFT**

1.2  Structure of the Manual

   The manual is generally  structured into sections on particular  topics; each
section contains  explanatory text and  function definitions,  interspersed.  In
general,  each  section  contains both  elementary  and  complex  material, with
complexity increasing toward the end of the section.  An axiomatic, step-by-step
development is not used.  Frequently  the more complex information in  a section
will assume knowledge from other sections which appear later in the manual.  The
new user is advised to skip around, reading early chapters and early sections of
chapters first.

   Often descriptions of Lisp functions will be given not only in prose but also
in terms of other Lisp functions.  These are as accurate as possible, but should
not be  taken too  literally.  Their  main purpose is  to serve  as a  source of

   Accessing information in the manual is dependent on both the user's  level of
ability and the purpose for which  she or he is using the manual.   Though cover
to cover reading is not recommended (though not excluded), it is  suggested that
someone who has  never previously seen this  manual browse through  it, touching
the beginning of each  subdivision that is listed  in the Table of  Contents, in
order to familiarize himself or herself with the material that it  contains.  To
find an answer  to some particular  question, one must  use one of  the provided
access methods.  Since the manual is structured by topics one can use  the Table
of Contents that is found at the beginning of the manual, and the  more detailed
tables of contents  found at the  beginning of each of  the six major  parts, to
find where information of a general class will be found.  Entry into  the manual
is also facilitated by  the Glossary and the  Concept Index, which are  found at
the end.   Also at  the end of  the manual  are a Function  Index and  an Atomic
Symbol Index which are  probably most useful to  a regular and repeated  user of
the dialect, or to  an experienced user of  another dialect, who wishes  to find
out the answer to a question about a specific function.  When one section of the
manual assumes knowledge of another section a page number reference to the other
section will generally be given.

December 5, 1977                     ∪1-1.2                             Page 1-3
**DRAFT**                   Maclisp Reference Manual                   **DRAFT**

1.3  Notational Conventions

   There are some conventions of  notation that must be mentioned at  this time,
due to their being used in examples.

   Most numbers are in octal  radix (base eight).  Numbers with a  decimal point
and spelled-out numbers are in decimal radix.  It is important to  remember that
by default Maclisp inputs and outputs  all numbers in octal radix.  If  you want
to change this, see the variables base and ibase.

   A combination  of the characters  equal sign and  greater than  symbol, "=>",
will be used in examples of  Lisp code to mean evaluation.  For instance,  "F =>
V" means that evaluating the form F produces the value V.

   All uses of the phrase "Lisp reader," unless further qualified, refer to that
part of the Lisp  system which reads input, and  not to the person  reading this

   The terms  "S-expression" and "Lisp  object" are synonyms  for "any  piece of
Lisp data."

   The character "$" always stands for dollar-sign, never for "alt mode," unless
that is specifically stated.

   The two characters  accent acute, "'", and  semi-colon, ";", are  examples of
what are called macro characters.  Though the macro character facility, which is
explained in Part 5, is not of immediate interest to a new user of  the dialect,
these two macro characters come preset by the Lisp system and are  useful.  When
the Lisp reader encounters an accent acute, or quote mark, it reads in  the next
S-expression and encloses it in  a quote-form, which prevents evaluation  of the
S-expression.  That is:


                                  turns into:

                               (quote some-atom)


                                 '(cons 'a 'b)

Page 1-4                             ∪1-1.3                     December 5, 1977
**DRAFT**                     General Information                      **DRAFT**

                                   turns into

                       (quote (cons (quote a) (quote b)))

   The semi-colon (;) is used  as a commenting character.  When the  Lisp reader
encounters it, the remainder of the line is discarded.

   The  term  "newline"  is used  to  refer  to that  character  or  sequence of
characters which indicates the end of a line.  This is implementation dependent.
In Multics Maclisp, newline is the Multics newline character, octal 012.  In ITS
Maclisp, newline  is carriage  return (octal 015),  optionally followed  by line
feed (octal  012.)  In dec-10  Maclisp, newline is  carriage return  followed by
line feed.

   All  Lisp  examples  in  this  manual  are  written  according  to  the  case
conventions of the Multics implementation, which uses both upper and  lower case
letters  and spells  the names  of most  system functions  in lower  case.  Some
implementations of  Maclisp use only  upper case letters  because they  exist on
systems which are not, or have not always been, equipped with  terminals capable
of  generating and  displaying  the full  ascii character  set.   However, these
implementations will accept input in lower case and translate it to  upper case,
unless the user has explicitly said not to.

December 5, 1977                     ∪1-1.3                             Page 1-5
**DRAFT**                   Maclisp Reference Manual                   **DRAFT**

Page 1-6                             ∪1-1.3                     December 5, 1977
**DRAFT**                         Data Objects                         **DRAFT**

2.  Data Objects

   Lisp works with pieces of data called "objects" or "S-expressions." These can
be simple "atomic" objects or  complex objects compounded out of  other objects.
Functions,  the basic  units of  a Lisp  program, are  also objects  and  may be
manipulated as data.

   Objects  come in  several types.   All  types are  manifest; that  is,  it is
possible for a  program to tell what  type an object is  just by looking  at the
object itself, so it  is not necessary to declare  the types of variables  as in
some other languages.  One can  make declarations, however, in order to  aid the
compiler in producing optimal code.  (See part 4.2.)

   It is important to know that  Lisp represents objects as pointers, so  that a
storage cell (a  "variable") will hold  any object, and  the same object  may be
held by several different storage cells.  For example, the same identical object
may be a component of two different compound objects.

   The data-types are divided into  three broad classes:  the atomic  types, the
non-atomic types, and  the composite types.  Objects  are divided into  the same
three classes  according to their  type.  Atomic objects  are basic  units which
cannot be broken down by ordinary chemical means (car and cdr), while non-atomic
objects are structures constructed out of other objects.  Composite  objects are
indivisible, atomic,  entities which  have other  objects associated  with them.
These other objects may be examined and replaced.

   The atomic data types are numbers, atomic symbols, strings, and subr-objects.
Atomic symbols can also be regarded as composite.  See below.

   In Lisp numbers can be represented by three types of atomic objects: fixnums,
flonums, and bignums.  A fixnum  is a fixed-point binary integer whose  range of
values  is  machine-dependent.   A  flonum  is  a  floating-point  number  whose
precision and range of values  are machine-dependent.  A bignum is  an infinite-
precision integer.  It is impossible to get "overflow" in bignum  arithmetic, as
any  integer  can  be  represented by  a  bignum.   However,  fixnum  and flonum
arithmetic is faster than bignum arithmetic and requires less memory.  Sometimes
the  word  "fixnum"  is used  to  include  both fixnums  and  bignums  (i.e. all
integers); in  this manual,  however, the word  "fixnum" will  never be  used to
include bignums unless that is explicitly stated.

December 5, 1977                     ∪1-2.                              Page 1-7
**DRAFT**                   Maclisp Reference Manual                   **DRAFT**

   The  printed  representations  for  numbers  are  as  follows:  a  fixnum  is
represented  as a  sequence of  digits in  a specified  base, usually  octal.  A
trailing decimal point indicates a  decimal base.  A flonum is represented  as a
set of digits containing an embedded or leading decimal point and/or  a trailing
exponent.  The exponent is introduced by  an upper or lower case "e".   A bignum
looks like a fixnum except that it has enough digits that it will not fit within
the range available to  fixnums.  Any number may be  preceded by a + or  - sign.
Some examples of fixnums are 4,  -1232, -191., +46.   An example of a  bignum is
1565656565656565656565656565656565.  Some  examples of  flonums are:   4.0, .01,
-6e5, 4.2e-1.

   One of the most important Lisp data types is the atomic symbol.  In fact, the
word "atom" is often used to mean just atomic symbols, and not the  other atomic
types.  An atomic symbol has associated with it a name, a value, and  possibly a
list  of "properties".   The name  is  a sequence  of characters,  which  is the
printed representation  of the  atomic symbol.   This name  is often  called the
"pname," or  "print-name." A pname  may contain any  ascii character  except the
null character, which  causes trouble in  some implementations.  For  example, a
certain atomic symbol  would be represented externally  as foo; internally  as a
structure containing the value, the pname "foo", and the properties.

   There are  two special atomic  symbols, t and  nil.  These always  have their
respective selves as values and their values may not be changed.  nil is used as
a  "marker"  in many  contexts;  it is  essential  to the  construction  of data
structures  such as  lists.  t  is usually  used when  an antithesis  to  nil is
required for some purpose, e.g.  to represent the logical conditions  "true" and
"false." Another property of the special  atomic symbol nil is that its  car and
its cdr are always nil.

   The value  of an  atomic symbol  can be any  object of  any type.   There are
functions to set  and get the  value of a  symbol.  Because atomic  symbols have
values associated with them,  they can be used  as variables in programs  and as
"dummy arguments"  in functions.  It  is also possible  for an atomic  symbol to
have no value, in which case it is said to be "undefined" or "unbound."

   The property list of an atomic symbol is explained on page 2-52.  It  is used
for such things  as recording the fact  that an atomic symbol  is the name  of a

   An atomic symbol  with one or  no characters in its  pname is often  called a
"character object" and used to represent an ascii character.  The  atomic symbol
with a zero-length  pname represents the ascii  null character, and  the symbols

Page 1-8                             ∪1-2.                      December 5, 1977
**DRAFT**                         Data Objects                         **DRAFT**

with  one-character  pnames  represent  the  character  which  is  their  pname.
Functions which take character objects as input usually also accept a string one
character long  or a  fixnum equal to  the ascii-code  value for  the character.
Character objects are always interned on the obarray (see page 2-58).

   Another  Lisp data  type is  the string.   This is  a sequence  of characters
(possibly zero-length).  Strings are used  to hold messages to be typed  out and
to manipulate text when the structure of the text is not appropriate for the use
of "list processing."  The printed representation of  a string is a  sequence of
characters enclosed in double-quotes, e.g. "foo".   If a " is to be  included in
the string, it is written twice, e.g. "foo""bar" is foo"bar.  In implementations
without strings,  atomic symbols are  used instead.  The  pdp-10 implementations
currently lack strings.

   A "subr-object" is a special atomic data-type whose use is normally hidden in
the  implementation.  A  subr-object  represents executable  machine  code.  The
functions built  into the Lisp  system are subr-objects,  as are  user functions
that have been compiled.  A  subr-object has no printed representation,  so each
system function has an atomic symbol  which serves as its name.  The  symbol has
the subr-object as a property.

   One composite  data type  is the  array.  An  array consists  of a  number of
cells, each of  which may contain  any Lisp object.  The  cells of an  array are
accessed by subscripting; each cell is  named by a tuple of integers.   An array
may have one or more dimensions; the upper limit on the number of  dimensions is
implementation-defined.  An array is not always associated with an atomic symbol
which is its name.  Rather,  an array is always designated by  an array-pointer,
which is  a special kind  of atomic Lisp  object.  Frequently,  an array-pointer
will be placed on  the property list of a  symbol under the indicator  array and
then that symbol will be used as  the name of the array, since symbols  can have
mnemonic names and  a reasonable printed representation.   See page 2-89  for an
explanation of how to create, use, and delete arrays.

   Another composite data  type is the file-object,  which is described  on part

   The  sole  non-atomic  data  type  is the  "cons."   A  cons  is  a structure
containing  two  components,  called  the "car"  and  the  "cdr"  for historical
reasons.  (These are  names of fields  in an IBM  7094 machine word.)  These two
components may be any Lisp object,  even another cons (in fact, they  could even
be the same cons).  In this way complex structures can be built up out of simple
conses.  Internally a cons is represented in a form similar to:

December 5, 1977                     ∪1-2.                              Page 1-9
**DRAFT**                   Maclisp Reference Manual                   **DRAFT**

               |                 |                 |
               |     car         |      cdr        |

where the boxes represent  cells of memory large  enough to hold a  pointer, and
"car" and "cdr"  are two pointers to  objects.  The printed representation  of a
cons is the "dotted-pair" notation (A . B) where A is the car and B is the cdr.

   Another way  to write the  internal representation of  a cons, which  is more
convenient for large structures, is:

                ---λ> o -----> cdr

   There are three  Lisp functions associated with  conses: cons, car,  and cdr.
The  function cons  combines its  two  arguments into  a cons;  (1 .  2)  can be
generated by evaluating (cons 1 2).  The function car returns the  car component
of its argument, and the function cdr returns the cdr component of its argument.

   One type of structure, built out of conses, that is used quite often,  is the
"list."  A  list is  a row  of objects, of  arbitrary length.   A list  of three
things 1, 2, and 3  is constructed by (cons 1 (cons  2 (cons 3 nil))); nil  is a
special atom that is used  to mark the end of  a list.  The structure of  a list
can be diagrammed as:

                ---λ> o ----> o ----> o ----> nil
                    |       |       |
                    |       |       |
                    V       V       V
                    1       2       3

   From this it can be  seen that the car of  a list is its first  element, that
the cdr of a list is a list  of the elements after the first, and that  the list
of no elements is the same as nil.

   This list of 1,  2, and 3 could be  represented in the dot-notation  used for
conses as  (1 . (2 . (3  . nil))).  However, a more convenient notation  for the

Page 1-10                            ∪1-2.                      December 5, 1977
**DRAFT**                         Data Objects                         **DRAFT**

printed representation of lists has been defined:  the "list-notation" (1  2 3).
It is  also possible to  have a hybrid  of the two  notations which is  used for
structures which are almost  a list except that they  end in an atom  other than
nil.  For example, (A . (B . (C . D))) can be represented as (A B C . D).

   A list not  containing any elements is  perfectly legal and  frequently used.
This zero-length list is  identified with the atom nil.   It may be typed  in as
either nil or ().

December 5, 1977                     ∪1-2.                             Page 1-11
**DRAFT**                   Maclisp Reference Manual                   **DRAFT**

Page 1-12                            ∪1-2.                      December 5, 1977
**DRAFT**                  The Basic Actions of LISP                   **DRAFT**

3.  The Basic Actions of LISP

3.1  Binding of Variables

   The  basic  primitives  of  programming in  Lisp  are  variables,  forms, and
functions.  A variable is an atomic symbol which has a value associated with it;
the symbol is said to  be bound to that value.   The value may of course  be any
Lisp object whatsoever.  The  atomic symbol acts simply  as a name by  which the
program may refer to the value while it is processing it.

   This is similar to the  concept of variables in other  programming languages.
However, Lisp's concept of the scope  of names is subtly different from  that of
most "block-structured" languages.  At  a given moment, a variable  may actually
have several bindings in existence.   Only the most recent, or  current binding,
can be used.  When a new binding  is created, the previous one is pushed  onto a
stack.  It will become accessible again when the binding which superseded  it is
removed.   Creation  and removal  of  bindings is  synchronized  with subroutine
calling  (and with  certain  special forms  described below)  so  this mechanism
corresponds  closely  to  the "local  variables"  concept  of  other programming
languages.   However,  Lisp considers  that  there is  only  one  variable whose
binding changes, rather than several separate variables which happen to have the
same  name.  Any  reference  to a  variable,  even from  outside  the particular
program which gave it its current binding, gets the current binding and  not one
determined by "scope  rules."  It is possible  to simulate the other  concept of
scope of names by using binding context pointers, which are described later (see
page 1-22).

   Unlike many other languages, Lisp  does not combine the concepts of  name and
storage.  Many languages associate with  a variable (a name) a piece  of storage
which can hold one object of a particular type, such as a floating point number.
The variable's  value resides in  this storage.  It  is then impossible  for two
variables to really have "the same" value; one could have a copy of the value of
another but not the same identical object.

   The situation in Lisp is quite  different.  Binding a variable to a  value is
not copying the value into storage associated with that variable.   Values exist
as separate objects  in their own  right and in  their own storage.   Binding is
simply an association between a  variable and a value; consequently there  is no

December 5, 1977                     ∪1-3.                             Page 1-13
**DRAFT**                   Maclisp Reference Manual                   **DRAFT**

reason why two variables cannot have truly identical values.  Similarly, erasing
the binding between a variable and its value does not destroy or throw  away the
value; it simply breaks  the association.  Of course,  if there is no  other use
for the value the storage it occupies will eventually be reclaimed by the system
and put to more productive use.

   Often these processes of creating a new binding of a variable to a  value and
reverting to  a previous binding  are referred to  as binding and  unbinding the
variable, respectively.

   A slightly different way of creating a binding between a variable and a value
is assignment.  When  a variable is  bound to a  value, the previous  binding is
saved and can be restored, but when  a variable has a value assigned to  it, the
previous binding  is not  saved, but is  simply replaced.   Thus binding  may be
regarded  as creating  a new  level  of usage  of a  variable,  while assignment
switches a variable to a different value within the same level.  For instance, a
subroutine  or function  may bind  a variable  to an  initial value  when  it is
entered, and  then proceed to  make use of  that variable, possibly  assigning a
different value to it  from time to time.   The initial binding of  the variable
establishes the (temporary) ownership of that variable by the subroutine.

   Due to the subtlety of  the distinction between binding and  assignment, some
people  have  proposed that  assignment  be eliminated  wherever  possible.  The
Maclisp do function can often be useful in this regard.

   There are several program constructs by which a variable can be bound.  These
will be explained after forms and functions have been introduced.

Page 1-14                            ∪1-3.1                     December 5, 1977
**DRAFT**                  The Basic Actions of LISP                   **DRAFT**

3.2  Evaluation of Forms

   The  process of  "executing" a  Lisp program  consists of  the  evaluation of
forms.  Evaluation takes a form and produces from it a value (any  Lisp object),
according to  a strict  set of  rules which  might be  regarded as  the complete
semantics of Lisp.

   If the form  is atomic, it is  evaluated in a way  which depends on  its data
type.  An atomic symbol is a variable; it evaluates to the value to which  it is
currently bound.  If it is not bound, an error occurs.  (See part 3.4.) A number
or a string is a literal  constant; it evaluates to itself.  The  special atomic
symbols t and nil are also treated as constants.  A constant can also be created
by use of the quote special form; the value of (quote x) is x.

   If  the form  is a  list, its  first element  specifies the  operation  to be
performed, and its remaining elements specify arguments to that operation.  Non-
atomic forms  come in  two types:   special forms,  which include  the necessary
programming  operations  such  as  assignment  and  conditionals,  and  function
references,  in which  the "operation"  is a  function which  is applied  to the
specified  arguments.   Thus  functional  composition  is  the  method  by which
programs are built up out of  parts - as distinguished from composition  of data
structures, for  example.  Lisp functions  correspond closely to  subroutines in
other programming languages.

   A function  may be  either a primitive  which is  directly executable  by the
machine,  called a  subr  (short for  "subroutine"),  or a  function  defined by
composition  of  functions  and  special  forms,  called  an  expr   (short  for
"expression.") Most subrs are built in to the language, but it is possible for a
user to convert his exprs into  subrs by using the compiler (see part  4.)  This
gains speed and compactness at some cost in debugging features.

   There is additional complexity because special forms are actually implemented
as if they were function references.  There is a special type of subr  called an
fsubr  which is  used  for this  purpose.  An  fsubr  is permitted  to  make any
arbitrary  interpretation  of  its  argument  specification  list,   instead  of
following the standard procedure which is described below.  It is  also possible
to define a special form by an expr, which is then called a fexpr.  Most  of the
built-in special forms are handled specially by the compiler.  They are compiled
as the appropriate code rather than as a call to the fsubr.

   Other types  of functions are  lsubr, which  is just a  subr with  a variable

December 5, 1977                     ∪1-3.2                            Page 1-15
**DRAFT**                   Maclisp Reference Manual                   **DRAFT**

number  of  arguments,  lexpr,  which  is an  expr  with  a  variable  number of
arguments, and  macro, which is  a type of  special form whose  result is  not a
value, but another form; this allows a "transformational" type of semantics.

   Consider the form

                                (F A1 A2 ... An)

   The evaluator first  examines F to  see if it is  a function which  defines a
special form, i.e. an fsubr, a fexpr, or a macro.  If so, F is consulted  and it
decides how to produce  a value.  If not, F  must be an ordinary  function.  The
sub-forms  A1 through  An are  evaluated, producing  n arguments,  and  then the
definition of F is applied  to the arguments.  (Application is described  in the
following section.) This yields a result (some Lisp object), which is then taken
as the value of the form.

   An atomic  form of some  random type, such  as a subr-object,  a file,  or an
array-pointer, evaluates to  something random, often  itself; or else  causes an
error depending on the convenience  of the implementation.  Note that  an array-
pointer is different from  an atomic symbol which happens  to be the name  of an
array; such an atomic symbol is evaluated the same as any other atomic symbol.

Page 1-16                            ∪1-3.2                     December 5, 1977
**DRAFT**                  The Basic Actions of LISP                   **DRAFT**

3.3  Application of Functions

   When a non-atomic form is  evaluated, the function specified by that  form is
combined with  the arguments specified  by that form  to produce a  value.  This
process  is  called application;  the  function is  said  to be  applied  to the

   The first  step in application  is to convert  the function-specifier  into a
functional  expression  (sometimes  confusingly  called  a  functional  form.) A
functional expression is a Lisp object  which is stylized so that Lisp  can know
how to apply it to arguments.   The rules for this conversion will  be described
after the types of functional expressions have been explained.

   There are basically two types of functional expression.   A lambda-expression
is a functional expression which specifies some variables which are to  be bound
to the arguments, and  some forms which are  to be evaluated.  One  would expect
the forms to depend on the variables.  The value of the last form is used as the
value  of the  application of  the lambda-expression.   Any preceding  forms are
present purely for their side-effects.  A lambda-expression looks like:

                     (lambda (a b c d)

   Here a,  b, c,  and d  are the variables  to be  bound to  the values  of the
arguments,  called the  lambda-variables.  If  at a  certain moment  the current
binding of a was the one  created by this lambda-expression, a would be  said to
be lambda-bound.   Clearly this  lambda-expression is  a function  which accepts
four arguments.  The application of the functional expression to  four arguments
produces a value by evaluating form1, then form2, and then form3.  The  value of
form3 is the value of the whole form.  For example, the value of the form

                    ((lambda (a b) b) 3 4)

is 4.  The  functional expression used  is a very  simple one which  accepts two
arguments and returns the second one.

   If we grant the existence of a primitive addition operation, whose functional
expression may be designated by +, then the value of the form

December 5, 1977                     ∪1-3.3                            Page 1-17
**DRAFT**                   Maclisp Reference Manual                   **DRAFT**

                    ((lambda (a b) (+ a b)) 3 4)

is 7.  Actually,

                    (+ 3 4)

evaluates to the same thing.

   The  second basic  type of  functional  expression is  the subr,  which  is a
program  directly executable  by the  machine.  The  arguments of  the  form are
conveyed  to  this  program  in a  machine-dependent  manner,  it  performs some
arbitrary computation, and it returns a result.  The built in primitives  of the
language are subrs, and the user may write lambda-expressions which make  use of
these subrs to define  his own functions.  The  compiler may be used  to convert
user functions into subrs if extra efficiency is required.

   It  is  extremely  convenient  to  be  able  to  assign  names  to functional
expressions.  Otherwise the  definition of a function  would have to  be written
out in full each time it was used, which would be impossibly cumbersome.

   Lisp uses atomic symbols to name functions.  The "property list" mechanism is
used to associate an atomic symbol with a functional expression.  (See page 2-52
for an  explanation of  property lists.)  Because the  binding mechanism  is not
used, it is  possible for the  same name to  be used for  both a variable  and a
function with no conflict.  Usually the defun special form is used  to establish
the association between a function name and a functional expression.

   Thus, the car of a form  may be either a functional expression itself,  or an
atomic symbol which names a functional expression.  In the latter case, the name
of  the  "property"  which  associates  the  symbol  with  the  expression gives
additional information:

   A lambda-expression is normally placed under the expr property.  This defines
an ordinary expr.

   If  a lambda-expression  is placed  under the  fexpr property,  it  defines a
special form.  In that  case, the first lambda-variable  is bound to the  cdr of
the form being evaluated.  For example, if foo is a fexpr, and (foo (a b) (c d))
is evaluated, then  foo's lambda-variable would  be bound to  ((a b) (c  d)).  A
second lambda-variable may optionally be included in a fexpr.  It will  be bound
to a "binding  context pointer" to  the context of  the evaluation of  the form.
(See page 1-22 for the details of binding context pointers.)

Page 1-18                            ∪1-3.3                     December 5, 1977
**DRAFT**                  The Basic Actions of LISP                   **DRAFT**

   If a  lambda-expression with  one lambda-variable is  placed under  the macro
property,  it defines  the "macro"  special form  mentioned above.   The lambda-
expression is applied to the entire form, as a single argument, and the value is
a new form that is evaluated in place of the original form.

   If a subr-object is placed under the subr property, it defines a subr.   If a
subr-object is placed  under the fsubr property,  it defines a special  form.  A
subr-object  under  the lsubr  property  defines a  subr  which  accepts varying
numbers of arguments.

   There  are some  additional refinements.   A lambda-expression  which accepts
varying numbers of arguments, called a lexpr, looks as follows:

                    (lambda n

The  single,  unparenthesized,  lambda-variable  n is  bound  to  the  number of
arguments.  The function arg, described on page 2-12, may be used to  obtain the

   Another  property  which  resembles a  functional  property  is  the autoload
property.  If Lisp encounters an autoload property while searching  the property
list of a  symbol for functional  properties, it loads  in the file  of compiled
functions  specified by  the property,  then searches  the property  list again.
Presumably the file would contain  a definition for the function  being applied,
and  that  definition would  be  found the  second  time through.   In  this way
packages  of  functions  which  are  not  always  used  can  be  present  in the
environment only when needed.

   An array may also  be used as a  function.  The arguments are  the subscripts
and the  value is the  contents of the  selected cell of  the array.   An atomic
symbol  with an  array property  appearing in  the function  position in  a form
causes that array to be used.

   If the function-specifier of a form doesn't meet any of the above tests, Lisp
evaluates it and tries again.  In this way, "functional variables" and "computed
functions" can  be used.   However, it is  better to  use the  funcall function.
(See page 2-13.)

   There are some other cases of lesser importance:

December 5, 1977                     ∪1-3.3                            Page 1-19
**DRAFT**                   Maclisp Reference Manual                   **DRAFT**

   There is an obscure type of functional expression called  a label-expression.
It looks like
                        (label name (lambda (...) ...))

The  atomic symbol  name  is bound  to  the enclosed  lambda-expression  for the
duration of the application of the label-expression.  Thus if name is used  as a
functional variable this temporary definition  will be used.  This is  mostly of
historical interest and is rarely used in actual programming.

   Another type  of functional  expression is the  funarg.  A  funarg is  a list
beginning with the atomic symbol  funarg, as you might expect, and  containing a
function and a binding context pointer.  Applying a funarg causes  the contained
function to  be applied in  the contained binding  context instead of  the usual
context.  funargs are created by the *function special form.

   An expr property may be an atomic symbol rather than a lambda-expression.  In
this case, the atomic  symbol is used as  the function.  The original  symbol is
simply a synonym for it.

   In  addition to  the variety  of application  just described,  which  is used
internally by  the evaluation procedure,  there is a  similar but  not identical
application procedure available through the function apply.  The main difference
is that the function and the arguments are passed to apply separately.  They are
not encoded into a form, consequently macros are not accepted by this version of
application.  Note that what  is passed to apply is  a list of arguments,  not a
list of expressions which, evaluated, would yield arguments.

Page 1-20                            ∪1-3.3                     December 5, 1977
**DRAFT**                  The Basic Actions of LISP                   **DRAFT**

3.4  Special Forms

   This section  briefly describes some  of the special  forms in  Maclisp.  For
full details on a specific special form, consult the Function Index in the back.


     (quote x) evaluates to the S-expression x.

     (function x)  evaluates to  the functional expression  x.  There  is little
     real  difference  between  quote  and function.   The  latter  is  simply a
     mnemonic reminder to anyone who reads the program - including  the compiler
     - that the specified expression is supposed to be some kind of function.


     Conditionals control whether or not certain forms are  evaluated, depending
     on the results of evaluating other forms.  Thus both the value and the side
     effects of the conditional form can be controlled.

        (cond (predicate form1 form2...) (predicate form1 form2...)...)

     is a general conditional form.  The lists of a predicate and some forms are
     called clauses.  The  cond is evaluated by  considering the clauses  one by
     one in the order they are written.  The predicate of a clause is evaluated,
     and if the result is true, that is, anything other than nil, then the forms
     in that clause are evaluated and the cond is finished without examining the
     remaining clauses.  If the result is not true, i.e. if it is nil,  then the
     next clause is examined in the same way.  If all the clauses are exhausted,
     that is not an error.  The value of a cond is the value of the last form it
     evaluates, which could be  nil if no predicate is  true, or the value  of a
     predicate if that predicate is true but has no forms in its clause.

     (and form1 form2 form3...) evaluates  the forms in succession until  one is
     nil or the  forms are exhausted,  and the result is  the value of  the last
     form evaluated.

     (or form1 form2 form3...) evaluates  the forms until one is non-nil  or the
     forms  are  exhausted,  and  the  result is  the  value  of  the  last form

December 5, 1977                     ∪1-3.4                            Page 1-21
**DRAFT**                   Maclisp Reference Manual                   **DRAFT**

Non-Local Exits

     (catch form tag) evaluates the  form, but if the special form  (throw value
     tag)  is encountered,  and the  tags are  the same,  the  catch immediately
     returns the value without further ado.  See page 2-44 for the full details.


     (prog  (variable...)  form-or-tag ...)  allows  Fortranoid  "programs" with
     goto's, local variables, and return's to be written.

     (do ...) is the special form for iteration.  See page 2-38 for  the details
     of prog and do.

Defining Functions

     (defun  name  (arg1  arg2...)  form1  form2...)  defines  an  (interpreted)
     function.  See page 2-60 for full details.

Error Control

     (break name t) causes ";bkpt name"  to be typed out and gives control  to a
     read-eval-print loop so that the  user can examine and change the  state of
     the world.  When he is satisfied, the user can cause the break to  return a
     value.  See page 3-5 for the details of break.

     (errset form) evaluates the form, but if an error occurs the  errset simply
     returns nil.  If no error occurs, the value is a list whose  single element
     is what the value of the form would have been without errset.


     (setq var1 value1 var2 value2...) assigns the values to the variables.  The
     values are forms which are evaluated.

     (store (array  subscript1 subscript2...)  value) assigns  the value  to the
     array cell selected by subscripting.  See part 2.8 for  further information
     on arrays.

Page 1-22                            ∪1-3.4                     December 5, 1977
**DRAFT**                  The Basic Actions of LISP                   **DRAFT**

Miscellaneous Parameters

     (status  name -optional  args-) returns  miscellaneous parameters  of LISP.
     name is a mnemonic name for what is to be done.

     (sstatus name -optional args-) sets miscellaneous parameters.

     See part 3.7 for the details of status and sstatus.


     (grindef x) prettily prints the  value and function definition (if  any) of
     the atomic symbol  x.  Indentation is used  to reveal structure,  the quote
     special form is represented by ', etc. See part 6.3 for the details.


     (trace name)  causes the function  name to print  a message whenever  it is
     called and whenever  it returns.  See page  3-34 for the many  features and
     options of trace.

December 5, 1977                     ∪1-3.4                            Page 1-23
**DRAFT**                   Maclisp Reference Manual                   **DRAFT**

3.5  Binding Context Pointers

   There  is a  special type  of  object called  a binding  context  pointer, or
sometimes an "a-list pointer", which can  be used to refer to a  binding context
(a set  of bindings of  variables and  values which was  extant at  a particular
instant.) Due to the stack implementation of Maclisp, a binding  context pointer
is only valid while control is  nested within the binding context it  names.  It
is not  possible to exit  from within a  binding context but  keep it  around by
retaining a pointer to it.

   A binding context pointer is either a negative fixnum or nil.  nil  means the
"global" or "top level" binding context.  The negative fixnum is a special value
of implementation dependent  meaning which should be  obtained only from  one of
the four following sources:  the function evalframe, the function  errframe, the
special form *function, or the second lambda-variable of a fexpr.

   The only use for  binding context pointers is  to pass them to  the functions
eval and  apply to  specify the  binding context  in which  variables are  to be
evaluated  and  assignments  are  to  be  performed  during  that  evaluation or
application.  Binding  context pointers are  also used internally  by *function.
When it generates a funarg, it  puts in the funarg the functional  expression it
was  given and  a binding  context pointer  designating the  binding environment
current at the time *function was called.

Page 1-24                            ∪1-3.5                     December 5, 1977