Jason Plumb
5/2/99
Concepts of Programming Languages
Texas Tech University
The programming language LISP, a pseudo acronym for LISt Processing, was born from the work of John McCarthy in the late 1950's. As its name implies, LISP is centered on the concept of list manipulation. List manipulation plays an important role, either directly or indirectly, in nearly all significant programming languages. LISP's powerful list manipulation capabilities have led it to be used in important research in the fields of artificial intelligence and natural language processing. This document will aim to provide a brief overview of the features and attributes of LISP.
All data objects that LISP can manipulate are called symbolic expressions, or simply s-expressions. An s-expression can be thought of as any expression from which LISP can derive some meaning or value. Lists and atoms, the two basic building blocks of LISP programs, can be thought of as s-expressions. In LISP, all programs and program statements are lists. In this context, a list is defined to be an ordered set of zero or more elements surrounded on each side by parenthesis and separated by spaces. Each element in a list can either be a list or an atom. An atom, or atomic element, is the most primitive s-expression and is usually thought of as a variable. It should be noted that both numeric values, such as the numeric "5", or symbolic text style names, such as "FOO", are both considered to be atoms. To demonstrate, consider the expression (ONE (TWO 3) ((4 5) (6 7) (8 9))) to be a list. This list is comprised of three elements: the atom ONE, the list (TWO 3), and the list ((4 5) (6 7) (8 9)). This example demonstrates that a list can be comprised of both atoms and lists, and that lists can be elements of other lists to create levels of list nesting.
Special attention should be called to the empty list, which is represented by (). The empty list is defined as a list that has no elements. In LISP, the atom NIL is tied to the empty list and as such they are interchangeable. The notion of an empty list is highly important in problem solving and is appropriately included in the language definition.
LISP can be classified as a functional programming language. Unless told otherwise, LISP assumes that the first item in a list is a function name and the following items are the function parameters. The quote character (') is used to instruct LISP not to interpret the subsequent list as a function. To demonstrate, the expression (FOO (1 2)) would be interpreted as a call to the function FOO with a single parameter being the list (1 2), whereas the expression '(BAR (1 2)) would bypass evaluation and remain as a symbolic expression of a list with two parameters: BAR and the list (1 2).
Every programming language must have a means to perform arithmetic operations, and LISP is no exception. The designers of LISP have chosen to implement a prefix expression evaluation scheme that does not utilize the symbolic arithmetic operators +, -, *, and /. Rather, LISP recognizes a set of function names that represent the corresponding symbolic operations. The basic arithmetic operations (addition, subtraction, multiplication, and division) are performed by using the functions PLUS, DIFFERENCE, TIMES, and QUOTIENT. The PLUS and TIMES functions can take any number of parameters, whereas the DIFFERENCE and QUOTIENT functions must take exactly two parameters. Thus, the expression (QUOTIENT (PLUS 2 2) 2) would be evaluated to the value 2.
In addition to the four basic operations described above, LISP includes functions to perform more advanced operations. This includes the square root (SQRT), exponent evaluation (EXPT), increment (ADD1), decrement (SUB1), maximum value selection (MAX), absolute value (ABS), and sign conversion (MINUS).
When manipulating lists, it is often important to select portions of a list for other purposes. For example, if a portion of code needs to add a number to the first item in a list, it will first need to extract the item before performing the addition. There are several vital functions in LISP that allow direct manipulation of lists: CAR, CDR, CONS, APPEND, and LIST. The first function, CAR, returns the first item, or head, of a list. Similarly, the CDR function returns the tail, or all items excluding the head, of a list. CONS, which can be thought of as CONStruction for a list, takes a list and inserts an element at the head. APPEND takes an arbitrary number of lists as input and creates a new list that is comprised of all the elements from the input lists. The function LIST will create a new list out of its arguments. The reader should note the similarity and difference between APPEND and LIST. These 5 list-processing functions are extremely important in LISP and are used frequently by programmers.
Similar list processing functions that will not be discussed in detail are LENGTH, REVERSE, SUBST, and LAST. These functions determine the length of a list, generate the reverse of a list, replace a matched element in the list, and return the last element in a list, respectively.
Input and output functions are built into LISP to allow the programmer to obtain and display expressions. Specifically, the READ and PRINT functions handle these tasks. READ, when expressed by itself in a list as (READ) halts until the user has entered an expression. The PRINT function takes a single argument, evaluates the argument expression, and displays the result on a new line. As expected, these two functions are used liberally in interactive LISP programs.
Often, programmers need to execute certain portions of code based on an existing condition. Most programming languages use the infamous IF statement to evaluate an expression and execute a series of instructions only if the expression is evaluated to be true. Conditional program execution in LISP can be achieved with the COND function. COND takes an arbitrary number of arguments that are called clauses. The first element in each clause is evaluated until a non-NIL value is obtained. The first clause that contains this non-NIL value as the first element will return the last element in the clause as the COND result. If there are more than 2 elements in the clause, then the "middle" elements will be evaluated before the COND value is returned. Effectively, the COND function is a more flexible version of the classical IF-THEN-ELSE or SWITCH constructs.
A modern programming language would be difficult to use if it did not have a mechanism to allow the programmer to develop custom functions. LISP, like all other languages, allows functions to be defined. This is accomplished by means of the DEFUN function. DEFUN takes 3 parameters: the function name, a list of parameters, and a function body (usually a list of operations to be performed). The following example shows a function named DOUBLE that will return two times the input parameter:
(DEFUN DOUBLE (INVAL) (TIMES 2 INVAL))
Naturally, LISP will allow a function to call other functions or to call itself. This leads to the notion of recursion. Recursion is performed when a function calls itself within its definition. Often, recursion can yield a small and elegant solution to a large and complicated problem. In order for a recursive function to end properly, there is usually a terminating condition. Recursive functions in LISP will often use the COND function (as seen above) to check for the terminating condition.
On a similar note, LISP also allows a type of basic iteration via the MAPCAR function. The MAPCAR function takes the following parameters: A function name and a series of lists of arguments to be passed to the function. The number of lists following the function name must correspond with the number of function arguments. LISP will call the given function repeatedly until all items in the set of lists have been used. Thus, the expression (MAPCAR 'PLUS '(0 1 2) '(3 4 5)) would yield the result (3 5 7). Note the use of the quote character to prevent further interpretation of the ADD element. A more complex example that accomplishes the same result is
(MAPCAR (CAR '(PLUS MINUS TIMES)) ('0 1 2) '(3 4 5)).
Special attention should be given to the concept of LISP atoms and their relation to the classical view of variables. In most common programming languages, variables are defined to be of a specific declared type. During program execution, each variable is said to be in a certain state. Although this state value may change during the life of a program, the variable nonetheless resides in a state. The type of the variable is constant throughout the life of the program. When a variable is assigned a value, the state of the machine changes to reflect the new value.
Because LISP is founded on the idea of processing symbolic expressions, the variable situation is quite different. Atoms are the variables of LISP. Atoms cannot reside in a specific state because they, by definition, represent s-expressions. More specifically, it is said that atoms are bound to symbolic expressions. Atoms can be bound to numeric values, function names, or any arbitrary list. Thus, it can be said that LISP has created a computing environment in which there is an elimination of state. Atoms, in contrast to the classical view of program variables, are not restricted to a predefined data type. When a atom is bound to an s-expression, the machine state is not relevant.
LISP was developed with the intention of creating a new tool to perform list processing and symbolic expression manipulation. The result is an amazing programming language with enormous potential for revolutionizing computer science. In the fields of artificial intelligence and natural language processing alone, significant advancement has been accomplished with LISP.
LISP provides the programmer with an entirely new paradigm for solving problems. The higher level of abstraction that LISP provides allows the programmer to separate him/herself from the lower level workings of the machine hardware or operating system. The single fact that programmers can work with true symbolic terms in LISP to solve problems should itself be considered revolutionary.
A philosophical argument can be made that humans deal only with symbolic terms. From our development of language to the way our mind understands mathematics, we deal purely with symbols. The word APPLE on a printed page is a symbol (or actually a set of symbols that combine to form a larger symbol) to which the human mind attaches some meaning. It seems only natural that humans would want to interact with computers in a symbolic manner. Rather than having a strict set of rules that the programmer must obey, LISP gives the programmer freedom. This freedom is the ability to manipulate symbolic expressions and solve problems in a more natural way.
After performing research to write this document and becoming familiar with the LISP language, it is the author's opinion that LISP is superior to most languages in many regards. Compared to LISP, other programming languages seem highly limited and restrictive. Once one has become comfortable with programming in LISP and has adopted the appropriate mindset or philosophy, numerous possibilities will unfold. As a programmer who has a fair amount of experience programming in popular languages and using the object oriented approach, the author finds LISP to be truly amazing.
Most programming languages in wide use today are firm and abrasive. LISP is soft and pliable.
Wilensky, Robert, LISPcraft, W. W. Norton & Company, 1984.
Winston, Patrick Henry and Horn, Berthold Klaus Paul, LISP, Addison-Wesley Publishing Company, 1981.