The development of Lisp as a symbol-manipulation language (SICP)

“Despite its inception as a mathematical formalism, Lisp is a practical programming language. A Lisp interpreter is a machine that carries out processes described in the Lisp language. The first Lisp interpreter was implemented by McCarthy with the help of colleagues and students in the Artificial Intelligence Group of the MIT Research Laboratory of Electronics and in the MIT Computation Center. Lisp, whose name is an acronym for LISt Processing, was designed to provide symbol-manipulating capabilities for attacking programming problems such as the symbolic differentiation and integration of algebraic expressions. It included for this purpose new data objects known as atoms and lists, which most strikingly set it apart from all other languages of the period.

Lisp was not the product of a concerted design effort. Instead, it evolved informally in an experimental manner in response to users’ needs and to pragmatic implementation considerations. Lisp’s informal evolution has continued through the years, and the community of Lisp users has traditionally resisted attempts to promulgate any “official” definition of the language. This evolution, together with the flexibility and elegance of the initial conception, has enabled Lisp, which is the second oldest language in widespread use today (only  Fortran is older), to continually adapt to encompass the most modern ideas about program design. Thus, Lisp is by now a family of dialects, which, while sharing most of the original features, may differ from one another in significant ways.”

Structure and Interpretation of Computer Programs, ‘Chapter 1: Building Abstractions with Procedures

List-eating functions in Lisp

“Since the Lisp philosophy strongly emphasizes the use of lists to store and manipulate information, it will come as no surprise that the design of Common Lisp favors behaviors that make it easy to slice and dice such lists. The most profound design decision made in Common Lisp, with regard to lists, is that it automatically treats an empty list as a false value when evaluating a condition […]  when we pass the empty list () into an if form, it evaluates as a false value, whereas a list that contains an item evaluates as true.

Because we can easily detect an empty list, we can process lists using recursion. With this technique, we can take items from the front of a list and send the rest of the list back to the same function until the list is empty. (It’s a good thing that detecting empty lists is so easy, because so many functions in Lisp end up being list-eaters.)

Let’s look at a common list-eating function, which calculates the length of a list:

> (defun my-length (list)
     (if list
         (1+ (my-length (cdr list)))

> (my-length '(list with four symbols))

This function is written in classic Lisp style. It calls itself recursively as it chomps items off the front of the list. Calling yourself in this way is not only allowed in Lisp, but is often strongly encouraged. Lists in Lisp are recursive (conses of conses of conses . . .), so the act of consuming a list maps naturally onto functions that are recursive.”

— Conrad Barski, The Land of Lisp: Learn to Program in Lisp, One Game at a Time (No Starch Press, 2011)