LISP
for Dr. Hunter
Computer Science 401: Programming Languages
April 28, 1997
1. History/Brief Overview
LISP was developed in the 1950's by mathematician John McCarthy. Its purpose was to explore Artificial Intelligence and to do list processing. It paved the way for pure, functional programming languages that did not follow the linear, algorithmic fashion of procedural languages.
There are numerous versions of LISP. An attempt was made in the 1980's to bring together popular dialects under the idea of "Common LISP." However, each version has so many syntactical differences alone, that this idea was hard to implement. Scheme will be used for the examples in this paper, unless otherwise noted. The Scheme interpreter uses "=>" as its prompt, preceded by a line number (e.g. "1 ]"). In non-Scheme examples in this paper, the prompt will be used by itself and the response will be based on older versions of LISP.
2. Data types/Syntax
2-1. Atoms
Atoms are the building blocks of LISP. An atom is a symbol representing anything that the programmer wants. It is a scalar item that cannot be broken down into any smaller elements. An atom can consist of letters, numbers, and/or certain punctuation marks. Examples of atoms are:
2-2. Lists
A list is a sequence of atoms or other lists enclosed by parentheses. An empty list is representing by the open and closed parentheses: (). Lists are important because they provide a structure to group symbols together. A list can have elements added to, removed from, or manipulated by other functions.
Examples of lists are:
In LISP, code and data are both lists. In Figure 2b, the fourth example shows a function call that is also a list.
The third example in Figure 2b illustrates that lists can be members of lists. At quick glance, there seems to be 11 elements, however, there are only two: music and (jazz (smooth cool bop) classical pop R&B (soul current funk)). This can be seen using the function written in Figure 4a:
The secondinlist function displays the second element of the list. Similarly, we can examine the result of the secondinlist function call and apply the secondinlist call on it:
Lists are stored in cons cells, a structure similar to singly-linked lists. In a cons cell, the atom is stored as well as a pointer to the next item or the beginning of the next list. A list from above can be visualized as follows:
-- missing image --
All variables (code or data) are pointers and, therefore, the same size. Memory allocation is implicitly dynamic in LISP.
In LISP, every symbol has an associated property list. A property list can be built by giving a symbol (an atom or list, for example) a property that has a name and particular value. Here we use the PUTPROP function, one used in some older version of LISP, to give a symbol a property:
This gives the symbol "harvey" a property called "iq" with a value of 80. The DEFPROP function is similar, but doesn't evaluate the following expressions. This means that one can do the same thing without using the ' marks. Properties are retrieved with the GET function:
would return "80." Properties can be likewise manipulated and edited.
2-3. Data Objects
Each object carries run-time information on its type and other attributes. If an object is "structured," one with components, then a pointer is used rather than the actual data. An example of this can be seen in the diagram of list storage.
Direct assignment does not play as large of a part in LISP as it is in procedural languages. Assignments are used within PROG segments, and LISP interprets it in the procedural sequence-of-statements form. The basic assignment operator is SETQ, where (SETQ X VAL) assigns X the value of VAL.
Vectors and arrays are available in LISP, but like direct assignment, do not play a major role. The unimportance is obvious from the little uniformity in the treatment of implementations.
2-4. Data Control
Basic list processing
CAR and CDR are basic list processing functions. The CAR function returns the first member of a list while CDR returns everything a list contains but its first member.
2-4-2. Predicates
Predicates take arguments as other function calls. However, predicates return information about their arguments. This information is either nil or a non-nil value. Earlier versions of LISP contain functions called ATOM and LISTP. The ATOM predicate returns a t(rue) or nil (also represented as empty set) based on whether the argument is an atom or not. The LISTP predicate acts similarly for lists.
Predicates can test for true/false comparisons, too. The ZEROP, EQUAL, >, and < functions do this. EQUAL and ZEROP are used only in older versions of LISP. In Scheme, EQUAL is simply =. The ZEROP function is represented as (= 0 x) where is the expression to be evaluated.
3. Subprograms: Defining Functions
User-defined functions are created with the DEFINE function. The following is an example of how to define a function:
Older versions of LISP used "defun" rather than "define" as an abbreviation for "define function." Defining functions that already exist (e.g. "+") will overwrite the built-in definition.
4. Recursion/Iteration
4-1. Recursion
Recursion is a central idea in functional languages since loop constructs are not used in the purest forms. LISP's use of recursion illustrates this. Assume the following user-defined function that sums all the numbers up to N.
Here, sending in 5 for N, the function will work itself down to 0, and then recoil, adding all the numbers back up to 5, resulting in a value of 15. This is an example of numeric recursion.
The above example also illustrates LISP's dynamic data typing. Since LISP is an interpreted language with dynamic data typing, a runtime error would occur if a list was sent to N rather than an integer.
List recursion is used to iterate through all the items in a list. Taking the CAR of a CDR of a list will return the second element of the list. With this in mind, the following example shows how to traverse a list in a manner similar to figuring the summation of a number in the above example.
Here, sending in a list of '(5 4 3 2 1), the function works it down to a single-item list of (1), and then recoils back up to 5, adding the number to the current sum. The final result here, predictably, is 15.
4-2. Iteration
Recursion is LISP's main form of repetition. Pure LISP does not have an iterative loop structure, however, most later versions of LISP have a "PROG" feature. Combining this previously mentioned structure with the "go" statement, a primitive loop structure can be formed. The following example is from an early loop-implementing version of LISP not named in its source:
5. Closing Evaluation of LISP
As the model for functional programming, LISP succeeded as a list-processing language ideal for Artificial Intelligence applications.
"Pure LISP," LISP with strictly function calls, is not used frequently today. Other versions of LISP have been developed, such as Scheme, INTERLISP, Common LISP, and MACLISP. Computer Science students that have learned programming through algorithms can have trouble adapting to LISP's purely functional fashion. However, many universities such as Stanford and MIT use LISP as their primary language to teach programming. In this case, LISP is considered especially easy to learn.
Support for LISP is still substantial. The Web has many sites for all versions of LISP and the Usenet has numerous newsgroups for discussions about the languages.
McCarthy continues to work with functional programming and do talks and papers on Artificial Intelligence and LISP. He is currently at work on a new mathematical programming language named Elephant 2000-1992.
Works Consulted
Anderson, John R., Albert T. Corbett, Brian J. Reiser. Essential LISP. Reading, Massachusetts: Addison-Wesley, 1987.
Hanson, Chris. "MIT Scheme Reference." The Scheme Programming Language. http://www-swiss.ai.mit.edu/emacs-html.local/scheme_toc.html (28 Apr. 1997).
Hunter, David. Class Notes: Computer Science 401: Programming Languages.
McCarthy, John. John McCarthy. http://www-formal.stanford.edu/jmc/ (28 Apr. 1997).
Pratt, Terrence W.. Programming Languages: Design and Implementation. Englewood Cliffs, New Jersey: Prentice-Hall, 1984.
Steele, Jr., Guy L.. Common LISP: The Language. Digital Press, 1990.
Stoyan, Herbert. LISP History. http://www8.informatik.uni-erlangen.de/html/lisp/histlit1.html
Touretzky, David S.. LISP: A Gentle Introduction to Symbolic Programming. New York: Harper & Row, 1984.
Tucker, Jr., Allen B.. Programming Languages:. New York: McGraw-Hill, 1986.