Java, Java, Java

One of the very earliest computer languages, and the one that’s most of- ten associated with artificial intelligence (AI), is LISP, which stands for LISt Processor. LISP has been, and still is, used to build programs for hu- man learning, natural language processing, chess playing, human vision processing, and a wide range of other applications.

The earliest (pure) versions of LISP had no control structures and the only data structure they contained was the list structure. Repetition in the language was done by recursion. Lists are used for everything in LISP, including LISP programs themselves. LISP’s unique syntax is simple. A LISP program consists of symbols, such as 5 and x, and lists of symbols, such as (5), (1 2 3 4 5), and ((this 5) (that 10)), where a list is anything en- closed within parentheses. The null list is represented by ().

Programs in LISP are like mathematical functions. For example, here’s a definition of a function that computes the square of two numbers:

,,

J

The expression (square x) is a list giving the name of the function and its parameter. The expression (* x x) gives the body of the function.

LISP uses prefix notation, in which the operator is the first symbol in the expression, as in (* x x). This is equivalent to (x * x) in Java’s infix notation, where the operator occurs between the two operands. To run this program, you would simply input an expression like (square 25) to the LISP interpreter, and it would evaluate it to 625.

LISP provides three basic list operators. The expression (car x) returns the first element of the (nonempty) list x. The expression (cdr x) returns the tail of the list x. Finally, (cons z x) constructs a list by making z the head of the list and x its tail. For example, if x is the list (1 3 5), then (car x) is 1, (cdr x) is (3 5), and (cons 7 x) is (7 1 3 5).

Given these basic list operators, it is practically trivial to define a stack in LISP:

,,

J

The push operation creates a new stack by forming the cons of the element x and the previous version of the stack. The pop operation returns the car of the stack but first changes the stack (using setf) to the tail of the original stack.

These simple examples show that you can do an awful lot of computa- tion using just a simple list structure. The success of LISP, particularly its success as an AI language, shows the great power and generality inherent in recursion and lists.