5.3 Lisp

5.3.1 Introduction

Lisp (List processing)³ was developed by John McCarthy and his students at MIT in 1958 for artificial intelligence (McCarthy 1960). (Lisp is, along with Fortran, one of the two oldest programming languages still in use.) An understanding of Lisp will both improve your ability to learn new languages with ease and help you become a more proficient programmer in your language of choice. In this sense, Lisp is the Latin of programming languages.

There are two dialects of Lisp: Scheme and Common Lisp. Scheme can be used for teaching language concepts; Common Lisp is more robust and often preferred for developing industrial applications. Scheme is an ideal programming language for exploring language semantics and implementing language concepts, and we use it in that capacity particularly in Chapters 6, 8, 12, and 13. In this text, we use the Racket programming language, which is based on Scheme, for learning Lisp. Racket is a dialect of Scheme well suited for this course of study.

Much of the power of Lisp can be attributed to its uniform representation of Lisp program code and data as lists. A Lisp program is expressed as a Lisp list. Recall that lists are the fundamental and only primitive Lisp data structure. Because the ability to leverage the power Lisp derives from this uniform representation, we must first introduce Lisp lists (i.e., data).

5.3.2 Lists in Lisp

Lisp has a simple, uniform, and consistent syntax. The only two syntactic entities are atoms and lists. Lists can contain atoms or lists, or both. Lists are heterogeneous in Lisp, meaning they may contain values of different types. Heterogeneous lists are more flexible than homogeneous lists. We can represent a homogeneous list with a heterogeneous list, but the reverse is not possible. Remember, the syntax (i.e., representation) for Lisp code and data is the same. The following are examples of Lisp lists:

Here, 1, 2, 3, x, y, and z are atoms from which these lists are constructed. The lists each contain a sublist.

Formally, Lisp syntax (programs or data) is made up of S-expressions (i.e., symbolic expressions). “[A]n S-expression is either an atom or a (possibly empty) list of S-expressions” (Friedman and Felleisen 1996a, p. 92). An S-expression is defined with BNF as follows:

The following are more examples of S-expressions:

Conceptual Exercises for Section 5.3

Exercise 5.3.1 Are arrays in C++ homogeneous? Explain.

Exercise 5.3.2 Are arrays in Java heterogeneous? Explain.

Exercise 5.3.3 Describe an using English, not BNF. Be complete.

3. Some jokingly say Lisp stands for Lots of Irritating Superfluous Parentheses.