2.4.3 Language Overview
2.4.3.1 Data Structures
Pure LISP has only two kinds of data structures: atoms and lists. Atoms are
either symbols, which have the form of identifiers, or numeric literals. The con-
cept of storing symbolic information in linked lists is natural and was used in
IPL-II. Such structures allow insertions and deletions at any point, operations
that were then thought to be a necessary part of list processing. It was eventu-
ally determined, however, that LISP programs rarely require these operations.
Lists are specified by delimiting their elements with parentheses. Simple
lists, in which elements are restricted to atoms, have the form(A B C D)Nested list structures are also specified by parentheses. For example, the list(A (B C) D (E (F G)))is composed of four elements. The first is the atom A; the second is the sublist
(B C); the third is the atom D; the fourth is the sublist (E (F G)), which has
as its second element the sublist (F G).
Internally, lists are stored as single-linked list structures, in which each
node has two pointers and represents a list element. A node containing an
atom has its first pointer pointing to some representation of the atom, such
as its symbol or numeric value, or a pointer to a sublist. A node for a sublist
element has its first pointer pointing to the first node of the sublist. In both
cases, the second pointer of a node points to the next element of the list. A list
is referenced by a pointer to its first element.
The internal representations of the two lists shown earlier are depicted in
Figure 2.2. Note that the elements of a list are shown horizontally. The last
element of a list has no successor, so its link is NIL, which is represented in
Figure 2.2 as a diagonal line in the element. Sublists are shown with the same
structure.2.4.3.2 Processes in Functional Programming
LISP was designed as a functional programming language. All computation in a
purely functional program is accomplished by applying functions to arguments.
Neither the assignment statements nor the variables that abound in imperative
language programs are necessary in functional language programs. Furthermore,
repetitive processes can be specified with recursive function calls, making itera-
tion (loops) unnecessary. These basic concepts of functional programming make
it significantly different from programming in an imperative language.2.4 Functional Programming: LISP 49