A Brief Introduction to Lisp

Lisp is a functional programming language with imperative features. By functional we mean that the overall style of the language is organized primarily around expressions and functions rather than statements and subroutines. Every Lisp expression returns some value. Every Lisp procedure is syntactically a function; when called, it returns some data object as its value. By imperative we mean that some Lisp expressions and procedures have side effects, such as storing into variables or array positions. Thus Lisp procedures are not always functions in the "pure" sense of logicians, but in practice they are frequently referred to as "functions" anyway, even those that may have side effects, in order to emphasize that a computed result is always returned. Imperative features are usually used sparingly; while it is possible to transliterate, say, Fortran code directly into Lisp, the result would not exhibit typical Lisp programming style.

Here is a simple Lisp procedure that concatenates two lists of items, producing a new list:

(define (append x y) (cond ( (null x) y) (t (cons (car x) (append (cdr x) y)))))

This may be read as follows: To produce a list consisting of the items of y appended to the items of x, the computation is conditional (cond). If the list x is empty (null), then the result is equal to y. Otherwise, construct (cons) a new list by placing the first item (car) of x before the result of appending y to the rest of the items (cdr) of list x.

This illustrates several points of "good" Lisp style. Procedures are usually small and specialized, performing a single conceptual task; a complete Lisp program may consist of hundreds of small procedures, each no more than thirty to sixty lines of code. Recursion (a procedure calling itself) is often used to traverse complex data structures. While parentheses indicate precedence and program structure, code is usually indented in a conventional style to aid the eye.

We confess that the names car and cdr are obscure at best, but go back to the very beginnings of Lisp and are regarded fondly by many Lisp programmers as remnants of an ancient tradition not to be discarded lightly. They also allow a convenient abbreviation for composition; for example, (caddr x) means (car (cdr (cdr x) ) ). That the shorter abbreviations are distinctly pronounceable (cadr = "CADder" and cdar = "kuhDAR") has aided their survival.

We should note that there are hundreds of dialects of Lisp, differing in many tiny details but recognizably all of the same family. For example, some dialects have replaced car and cdr with the friendlier names first and rest. Some provide an if construct as an alternative to cond. Two principal Lisp dialects, Common Lisp and Scheme, have been the subject of recent standardization efforts by ANSI and IEEE. This language summary borrows features of each in an attempt to simplify the presentation while preserving historical flavor.

The data objects of Lisp include atomic symbols and lists. All practical Lisp implementations include other types of objects as well, notably arrays and numbers. Nearly all Lisp dialects support both floating-point arithmetic and integers of varying size (not limited to the size of a machine word). The Lisp programmer who tries to calculate 47!, the product of the integers from 1 to 47, fully expects to obtain a completely accurate answer:

(define (factorial n) (cond ((= n 0) 1) (t (* n (factorial (- n 1)))))) (factorial 47) => 258623241511168180642964355153611979969197632389120000000000

While these other data types have been important to the practical success of the language, they are not central to the theoretical character of the language. But symbols and lists are essential.

 

Symbols are written as strings of letters, digits, and many special characters including +, -, *,1, and =. Symbols serve as identifiers when used in Lisp programs, but they have a deeper existence as data structures of the language for example, their names are available at run time.

A list is a sequence of Lisp data objects, notated by notating its elements within parentheses and separated by spaces. Thus (michelangelo artist (born 1475) (died 1564))is a list of four items; the first two are symbols, and the last two are lists, each containing a symbol and an integer. The list () is empty, containing zero items; (() ()) is a list of two empty lists.

We can apply our sample function append to two lists as follows:

(append '(fee fie) '(foe fum)) =>; (FEE FIE FOE FUM)

(The metanotation "=>" is not part of the Lisp language, but conventionally indicates that the result of executing the Lisp expression on the left is the Lisp data object on the right. Most dialects of Lisp are not case-sensitive. Input is usually shown in lowercase, output in uppercase.)

Lisp lists serve as generic, all-purpose, heterogeneous aggregate data structures. There is a standard I/O representation for lists as character strings, so it is very easy using Lisp to prototype programs that operate on complex data structures; it is not necessary first to define data types for the data structures and to code parsing and printing routines for them.

Lisp defines a standard representation for programs as Lisp data structures. The definition of append shown above actually is a Lisp list, whose first element is the symbol define; whose second element is the list of the three items append,x, and y; and so on. This makes Lisp a congenial environment for writing prograrns that manipulate the source code of other programs.

When a Lisp data structure is regarded as a program, symbols serve as identifiers naming variables. In the definition of append, the symbols x and y stand for variables. Lists are divided into two categories. If the first element of the list is one of a certain set of symbols, then the list is a special form, having peculiar syntax. Otherwise the list is a function call; the first item in the list indicates a procedure (which might be named or computed), and the remaining items are expressions whose values become arguments to the called procedure.

The cond special form means if-then-elseif-then-...-elseif-then. The global variable t has a non-lalse value and is conventionally used in a cond form to mean Uelse."

The quote special form allows one to mention constant values in a Lisp program. The value of (quote x) is:, where x may be any Lisp data object. Most Lisp systems support a convenient syntactic abbreviation: ‘x means (quote x). Only symbols and lists can be confused with program structure, so most Lisp systems treat other objects, most notably numbers, as self evaluating they may stand for themselves in representations of programs, so one may write, for example,

(/ (* (- fahrenheit 32) S) 9) instead of (/ (* (- fahrenheit '32) '5) '9)

The lambda special form allows one to mention a procedure without having to specify a name for it. Thus

(lambda (a b c) (- (* b b) (* 4.0 a c))) evaluates to a function that accepts three arguments (presumably numerical) and computes the quadratic discriminant b2 - 4ac.

The use of high-order procedures–procedures that accept other procedures as arguments– has been an important facet of Lisp programming style from the beginning. Consider the function map, which applies a function to every element of a list and returns a list of the results:

(define (map f x) (cond ((null x) '()) (t (cons (f (car x)) (map f (cdr x)))))) (map (lambda (x) (list x x)) '(chitty bang)) => ((CHITTY CHITTY) (BANG BANG))

In Common Lisp and Scheme, procedures are first class objects, allowing fully general use of functions that return functions as values.

–Gerald Jay Sussman, Guy L. Steele Jr., and Richard P. Gabriel

From: ACM SIGPLAN Notices, V28, N3, 1993.