A Gentle Introduction to ANSI Common Lisp

Original article was published by Ashok Khanna on Artificial Intelligence on Medium


A Gentle Introduction to ANSI Common Lisp

Part 1 of 5

LISP (LISt Processor), developed by John McCarthy in 1958 for symbolic computation, is the second oldest programming language still in widespread use (the oldest being FORTRAN). It is a prefix, parenthesised functional programming language:

  • Prefix Notation: Lisp uses prefix notation where operators precede their arguments, e.g. 2 +3 is written as (+ 2 3). Operators can take a varying number of arguments, e.g. we can add all numbers from 2 to 6 by (+ 2 3 4 5 6). This will return 20.
  • Parenthesised: Because the number of arguments in a lisp expression, such as the one above, may not be fixed, parentheses are used to punctuate the start and end of a lisp expression.

Lisp was developed to manipulate symbolic data and lisp programs are themselves treated as symbolic data and can be manipulated within Lisp. This makes Lisp a very powerful language, especially in the field of artificial intelligence. The purpose of this and subsequent articles is to give you a gentle introduction to this powerful language.

Building from the Ground Up

Lisp is a very unique language. To best understand it, we need to take a step back and build our understanding from the ground-up, paying particularly close attention to its central concepts of lists and s-expressions. This will make you read lisp code in the way the compiler evaluates it, and consequently make it much easier to understand the language.

Below are the topics we will sequentially cover:

  1. Lists & Atoms (covered here)
  2. S-Expressions & Evaluation (covered here)
  3. Functions & Functional Programming (Part 2)
  4. Printing & Reading (Part 2)
  5. Conditionals & Predicates (Part 3)
  6. Loops & Other Operators (Part 3)
  7. Symbols & Variables (Part 4)
  8. Specialised Data Structures (Part 4)
  9. List Manipulation (Part 5)
  10. Indentation & Concluding Remarks (Part 5)

Lists & Atoms

Lists are the most important concept in Lisp, so it is natural we will start here. In fact, every Lisp program is itself a list.

There are three important concepts to understand: cons, lists and atoms. In very general terms:

  • Atoms are singular objects like a number, a symbol, a string and so on. They appear stand-alone and not enclosed in parentheses.
  • Lists are a collection of atoms or other lists, separated by spaces and are enclosed in parentheses. E.g. (1 2 3) is a list and so is ((1 2 3) 4 5 6).

However, to program Lisp effectively, it is important to understand the technical definitions of these terms and this requires an understanding of cons cells.

Cons — the building block of lists

Cons are a pair of pointers, the first is called thecar and the second the cdr. The car points to some data structure (e.g. an integer, string, or even another list), while the cdr points to either another cons or to the empty list nil.

Lists are recursively defined to be either empty lists or cons whose cdr components are lists. In other words, lists are chains of conses linked by their cdr components and terminated by nil, the empty list. Atoms in Lisp are defined as all data types that are not cons.

An example of a single element and a three element list is illustrated below (Source: Paul Graham, ANSI Common Lisp).

Lists are built on a recursive set of cons linked together until an empty cdr is encountered

S-Expressions & Evaluation

The syntax of Lisp is comprised of s-expressions. Both programs and data are represented as s-expressions and an s-expression may be either an atom or a list. nil is the only s-expression that is considered to be both an atom and a list.

When given a list, the Lisp evaluator attempts to interpret the first element of the list as the name of a function and the remaining elements as its arguments.

Special Forms

A form is an s-expression that is intended to be evaluated. In Common Lisp, a special form is a Lisp expression that is treated specially by the Lisp interpreter and not by the above evaluation rule. For example, defun is used to define functions, if is used for conditionals and do is used for loops.

These special forms help alter the flow of the program and allow for more complex programs to be built. They are the core expressions to build meaningful lisp programs and will be discussed in subsequent parts of this guide. And whilst you cannot define your own special operators, you can do something almost as good, using macros.

Evaluation Rules

The following rules apply when evaluating an s-expression. An understanding of these rules is core to reading and writing Lisp code.

  • If the s-expression is an atom such as a number or a string, then return its value
  • Similarly, if the s-expression is an atomic symbol, return the value bound to that symbol; if it is not bound, it is an error
  • If the s-expression is a list, evaluate the second through the last arguments and apply the function indicated by the first argument to the results
  • The rules for evaluating a special form depend on the particular special function being called

Lisp represents both programs and data as s-expressions. Not only does this simplify the syntax of the language but also, when combined with the ability to control the evaluation of s-expressions, it makes it easy to write programs that treat other Lisp programs as data.

Controlling Evaluation

There are times where we do not want to evaluate an expression, but rather keep it as data. The ability to prevent evaluation of programs and manipulate them as data is an important feature of Lisp.

This is achieved with the quote operator, whose shorthand is '. In the below example, we do not evaluate the form (+ 3 5) but rather return it as is.

> (quote (+ 1 2 3))
(+ 1 2 3)

Quote will protect whole expressions, including expressions within it:

> '(the list (a b c) has 3 elements)
(THE LIST (A B C) HAS 3 ELEMENTS)

As a complement to quote, Lisp also provides the eval function that allows the programmer to evaluate an s-expression at will:

> (eval '(+ 1 2 3))
6

Functions as Data

Functions are regular objects in lisp, like symbols or strings or lists. We can prevent the evaluation of a function with function operator (shorthand #'):

> (function +)
#<Compiled-Function> (just a system message representing the function as-is)

We can use apply to evaluate a function passed to it. Now you can start to see how we could programatically build our own lists that represent functions (covered later in this guide) and then evaluate them within our lisp program:

> (apply #'+ '(1 2 3))
6

If we did not protect the above, the lisp evaluator would try to evaluate (1 2 3) and + and run into an error as these are not valid expressions on their own). Rather we want the apply operator to evaluate (+ 1 2 3).

Lambda Expressions

In Common Lisp, we express functions as lists, but they are represented internally as distinct function objects. To refer to a function literally, we use lambda expressions, which can be considered as the name of the function and allow us to use functions without naming them. An example combining lambda expressions with funcall (a slightly different version of apply that does not require the arguments to be a list):

> (funcall #'(lambda (x) (+ x 100)) 1)
101

Continue to Part 2

This concludes part one of our five-part introduction to Common Lisp. We introduced the important concepts of lists and s-expressions, the central elements for building lisp code. Importantly, you can start to see, that the ability to re-use code as data through operators such as apply and eval allow us to write code that can write its own code and execute that code without human intervention.

In the next article, we will take a step back and discuss functional programming before delving into functions and some basic lisp code (including the important functions of reading and printing).

Part 2 coming soon (link will be added here once published)