: Learning GNU Emacs, 3rd Edition

11.5.2 More Lisp Basics: Lists

11.5.2 More Lisp Basics: Lists

A Reverse Polish Notation calculator uses a data structure called a stack. Think of a stack as being similar to a spring-loaded dish stack in a cafeteria. When you enter a number into a RPN calculator, you push it onto the stack. When you apply an operator such as plus or minus, you pop the top two numbers off the stack, add or subtract them, and push the result back on the stack.

The list, a fundamental concept of Lisp, is a natural for implementing stacks. The list is the main concept that sets Lisp apart from other programming languages. It is a data structure that has two parts: the head and tail. These are known in Lisp jargon, for purely historical reasons, as car and cdr respectively. Think of these terms as "the first thing in the list" and "the rest of the list." The functions car and cdr, when given a list argument, return the head and tail of it, respectively.[81] Two functions are often used for making lists. cons (construct) takes two arguments, which become the head and tail of the list respectively. list takes a list of elements and makes them into a list. For example, this:

(list 2 3 4 5)

makes a list of the numbers from 2 to 5, and this:

(cons 1 (list 2 3 4 5))

makes a list of the numbers from 1 to 5. car applied to that list would return 1, while cdr would return the list (2 3 4 5).

These concepts are important because stacks, such as that used in the calculator mode, are easily implemented as lists. To push the value of x onto the stack calc-stack, we can just say this:

(setq calc-stack (cons x calc-stack))

If we want to get at the value at the top of the stack, the following returns that value:

(car calc-stack)

To pop the top value off the stack, we say this:

(setq calc-stack (cdr calc-stack))

Bear in mind that the elements of a list can be anything, including other lists. (This is why a list is called a recursive data structure.) In fact (ready to be confused?) just about everything in Lisp that is not an atom is a list. This includes functions, which are basically lists of function name, arguments, and expressions to be evaluated. The idea of functions as lists will come in handy very soon.

: 0.701. /Cache: 3 / 1