MTS 8: LISP and SLIP in MTS
Page Revised February 1979 June 1976
Arrays
LISP also supports arrays, where the value of an array element can
be any LISP structure. The subsection "Arrays" describes the
creation and use of arrays.
S-Expressions _____________
The basic LISP structure is a binary tree with atomic terminal nodes.
To represent these trees syntactically, symbolic expressions, called
S-expressions, are used. An S-expression consists of one of the
following:
(1) an atom,
(2) a dotted pair of S-expressions (S1 . S2), or
(3) a list of S-expressions (S1...SN)
Examples:
Syntax Tree Structure ______ ______________
(1) A .A
(2) (A . B) *
. .
A. .B
(3) ((A . B) . (C . (D . E))) *
. .
* *
. . . .
A. .B C. *
. .
D. .E
CAR and CDR
For any S-expression, the CAR is defined to be its entire lefthand
branch and its CDR to be its entire righthand branch. Thus the CAR
of ((A . B) . (C . (D . E))) is (A . B) and its CDR is (C . (D .
E)). Similarly, the CAR of (A . B) is A and its CDR is B. The
CAR of an atom is its VALUE, and the CDR of a literal atom is its
PLIST.
Lists
The list notation defined in LISP provides a convenient shorthand
which allows a subset of binary trees to be viewed as a list
structure. The prototype of a LISP list is the following
structure:
12 LISP

MTS 8: LISP and SLIP in MTS
June 1976
*
. .
A. *
. .
B. *
. .
C. .NIL
This represents the list (A B C). According to the definitions
given of CAR and CDR, the CAR of a list is always its first
element, and the CDR of a list is always the rest of the list. The
end of a list is always signified by a CDR of NIL, which indicates
that there are no more elements. Of course, an element of a list
need not be an atom; thus, the structure
*
. .
A. *
. .
* *
. . . .
B. * D. .NIL
. .
C. .NIL
represents the list (A (B C) D). The CAR of this list is A. The
CDR is ((B C) D).
It should be noted that the dotted-pair notation for (A B C) is
(A . (B . (C . NIL))), and that these two LISP expressions are
entirely equivalent. Any list can be written as a dotted pair;
however, the converse is not true.
For structures similar to lists that have terminating atoms which
are not NIL, a special syntax is available. The structure:
*
. .
A. *
. .
B. *
. .
C. .D
is represented by the expression (A B C . D).
Note: In general, the expression "element" refers to a top-level
element of a list, "sublist" refers to a substructure which may be
obtained by repeated CDRs, and a "substructure" indicates any
subtree of the LISP structure. For example, the elements of the
list (A B (C (D E)) F) are A, B, (C (D E)), and F. The sublists
are (B (C (D E)) F), ((C (D E)) F), etc. The substructures,
LISP 13