Page:AIM-514.djvu/3

---

Just as the linear vector stored-program-computer model leads to a variety of specific architectures, so with the linked record model. For concreteness we present here one specific architecture based on the linked record model which has actually been constructed.

List Structure and Programs

One of the central ideas of the LISP language is that storage management should be completely invisible to the programmer, so that he need not concern himself with the issues involved. LISP is an object-oriented language, rather than a value-oriented language. The LISP programmer does not think of variables as the objects of interest, bins in which values can be held. Instead, each data item is itself an object, which can be examined and modified, and which has an identity independent of the variahle(s) used to name it.

In this section we discuss LISP data structures at the conceptual level; the precise form of LISP data ubjects is not of concern here. Later we will discuss specific representations within the machine. LISP data is collectively referred to as S-expressions (S for symbolic). For our purposes we will need only the special cases of S-expressions called atoms and lists. An atom is an indivisible data object, which we denote by writing a string of letters and digits; if only digits are used, then the atom is considered to be a number. Many special characters such as -, +, @, and * are considered to be letters; we will see below that it is not necessary to specially reserve them for use as operator symbols. A list is a (possibly empty) sequence of LISP data objects, notated by (recursively) notating the objects in order, between a set of parentheses and separated by blank space. A list of the atoms FOO, 43, and BAR would be written (FOO 43 BAR). Notice that the definition of a list is recursive. For example,

(DEFINE SECOND (LAMBDA (X) (CAR (CDR X))))

is a list of three things: the atomic symbol DEFINE, the atomic symbol SECOND, and another list of three things LAMBDA, (X), and (CAR (CDR X)).

A convenient way use lists to represent algebraic expressions is to use Cambridge Polish notation, essentially a parenthesized version of prefix Polish notation. Numeric constants are encoded as numeric atoms; variables are encoded as non-numeric atoms (which henceforth we will call symbols); and procedure invocations (function calls) are encoded as lists, where the first element of the list represents the procedure and the rest represent the arguments. For example, the algebraic expression $a*b+c*d$ can be represented as (+ (* a b) (* c d)). Notice that LISP does not need the usual precedence rules concerning whether multiplication or addition is performed first; the parentheses (or rather, the structure of the lists) explicitly define the order. Also, all procedure invocations have a uniform syntax, no matter how many arguments are involved. Infix, superscript, and subscript notations are not used; thus the expression $J_{p}(x^{2}+1)$ would be written (J p (+ (↑ x 2) 1)).