Skip to content
LumenaryAcademy
Practice 60 min

Pairs, lists, symbols and quoting

One tiny data structure, the pair, builds lists, trees and Scheme code itself; quotation lets programs treat code as data.

Code tested · 4AI-draftedAwaiting review by a computer scientist
MotivationH

Everything from one small piece

Most languages offer a menu of built-in collection types. Lisp began with just one: a pair of two values. Put pairs in a chain and you have a list. Let the elements themselves be lists and you have a tree. And because Lisp code is written as nested lists, the same structure represents programs. A procedure that walks a list can walk a program; a procedure that builds a list can build code.

This lesson takes that idea apart from the bottom up. You will see how lists are made of pairs, write the classic list procedures yourself (because understanding how append and reverse work is the best way to understand their cost), and then meet symbols and quotation, which let a program talk about names and code as data. The lesson ends with a program that simplifies and evaluates algebraic expressions, a first step toward the interpreter you will write in lesson 8.

DefinitionsH

Pairs and lists

Definition— Pair

A compound value holding two values, made by (cons a b). car returns the first and cdr (pronounced "could-er") the second. The names come from instructions on the IBM 704, the machine the first Lisp ran on. A pair is written with a dot: (1 . 2).

Definition— List

Either the empty list '(), or a pair whose cdr is a list. So (list 1 2 3) is (cons 1 (cons 2 (cons 3 '()))). A chain of pairs that ends in something other than '() is an improper list, written with a dot before the last element: (1 2 . 3).

Definition— Symbol

An atomic value that is a name, such as apple or +. Two symbols with the same spelling are the same object, so they can be compared quickly with eq?. Symbols are written in programs with a quote: 'apple.

123
Box-and-pointer diagram of the list (1 2 3). Each pair is a box with two cells; the left cell (car) points to an element and the right cell (cdr) points to the next pair. The final cdr is the empty list, drawn as a diagonal line.
scheme
(import (scheme base) (scheme write))

(define (show x) (write x) (newline))

(define p (cons 1 2))
(show p)
(show (list (car p) (cdr p)))

(define xs (cons 1 (cons 2 (cons 3 '()))))
(show xs)
(show (equal? xs (list 1 2 3)))
(show (list (car xs) (cdr xs) (car (cdr xs)) (cadr xs)))
(show (cons 0 xs))
(show (cons xs 4))
(show (list (pair? '()) (null? '()) (list? xs) (list? p)))
(show (list (length xs) (list-ref xs 2) (list-tail xs 1)))
(show (append '(a b) '(c) '() '(d e)))
(show (reverse '(1 (2 3) 4)))
(show (list (memv 3 '(1 2 3 4)) (member "b" '("a" "b" "c")) (memv 9 '(1 2))))
text
(1 . 2)
(1 2)
(1 2 3)
#t
(1 (2 3) 2 2)
(0 1 2 3)
((1 2 3) . 4)
(#f #t #t #f)
(3 3 (2 3))
(a b c d e)
(4 (2 3) 1)
((3 4) ("b" "c") #f)
  • (cons 0 xs) makes a new list that shares xs as its tail; nothing is copied. Adding to the front of a list is constant time.
  • (cons xs 4) is not a longer list: its cdr is 4, not a list, so it prints as a dotted pair.
  • cadr means "the car of the cdr", the second element. Combinations up to two letters deep (caar, cadr, cdar, cddr) are in (scheme base); deeper ones such as caddr are in (scheme cxr).
  • list? is true only for proper lists. pair? of the empty list is false: '() is not a pair.
  • list-ref and length must walk the list, so they take time proportional to its length. append copies every list except the last.
  • reverse reverses only the top level; the inner list (2 3) is untouched.
  • memv and member return the tail of the list starting at the element found, or #f. Because any non-#f value is true, the result works as a test.
Worked examplesH

Procedures that follow the shape of lists

A list is defined recursively (empty, or a first element and a rest that is a list), so procedures on lists are naturally recursive, with one case for each part of the definition.

scheme
(import (scheme base) (scheme write))

(define (sum-list lst)
  (if (null? lst)
      0
      (+ (car lst) (sum-list (cdr lst)))))

(define (my-append a b)
  (if (null? a)
      b
      (cons (car a) (my-append (cdr a) b))))

(define (my-reverse lst)
  (let loop ((lst lst) (acc '()))
    (if (null? lst)
        acc
        (loop (cdr lst) (cons (car lst) acc)))))

(define (remove-all x lst)
  (cond ((null? lst) '())
        ((equal? x (car lst)) (remove-all x (cdr lst)))
        (else (cons (car lst) (remove-all x (cdr lst))))))

(define (flatten tree)
  (cond ((null? tree) '())
        ((pair? tree) (append (flatten (car tree)) (flatten (cdr tree))))
        (else (list tree))))

(define (count-leaves tree)
  (cond ((null? tree) 0)
        ((pair? tree) (+ (count-leaves (car tree)) (count-leaves (cdr tree))))
        (else 1)))

(write (sum-list '(4 8 15 16 23 42))) (newline)
(write (my-append '(1 2) '(3 4))) (newline)
(write (my-reverse '(a b c d))) (newline)
(write (remove-all 'x '(x a x b (x) c))) (newline)
(write (flatten '(1 (2 (3 4)) ((5)) 6))) (newline)
(write (count-leaves '((a b) (c (d e)) f))) (newline)
text
108
(1 2 3 4)
(d c b a)
(a b (x) c)
(1 2 3 4 5 6)
6
  • my-append rebuilds the first list pair by pair and then points the last new pair at b. So appending costs time proportional to the length of the first list, and b is shared, not copied. Repeatedly appending to the end of a growing list is therefore quadratic; build it backwards with cons and reverse once instead.
  • my-reverse uses an accumulator, so it is iterative and linear. Pushing each element onto the front of acc reverses the order.
  • remove-all removes only top-level elements equal to x: the (x) inside a sublist stays.
  • flatten and count-leaves treat a list as a tree: a pair has two subtrees, its car and its cdr. Recursing on both is tree recursion, and every non-pair, non-empty value is a leaf.

These procedures show the standard patterns: map-like (build a new list element by element, like remove-all), reduce-like (combine elements into one value, like sum-list), and tree-walking (recurse into both car and cdr). The next lesson turns the first two patterns into reusable higher-order procedures.

Worked examplesH

Symbols and quotation

Evaluation turns (+ 1 2) into 3. Sometimes you want the list (+ 1 2) itself: the operator symbol and two numbers, as data. Quotation says "do not evaluate this".

scheme
(import (scheme base) (scheme write))

(define (show x) (write x) (newline))

(show 'hello)
(show (quote hello))
(show '(+ 1 2))
(show (+ 1 2))
(show (list 'quote 'x))
(show (car ''x))
(show (list (symbol? 'hello) (symbol? "hello") (string? "hello")))
(show (eq? 'apple 'apple))
(show (string->symbol "kiwi"))
(show (symbol->string 'mango))
(show (eq? (string->symbol "kiwi") 'kiwi))

(define n 3)
(define extras '(4 5))
(show `(1 2 ,n))
(show `(n is ,n and n squared is ,(* n n)))
(show `(1 ,@extras 6))
(show `(nested (list ,@(map (lambda (k) (* k 10)) extras))))

(show (list (eq? '() '()) (eqv? 2.5 2.5) (eqv? (string-copy "ab") (string-copy "ab")) (equal? "ab" "ab")))
(show (list (eq? (list 1 2) (list 1 2)) (equal? (list 1 2) (list 1 2))))
(let ((a (list 1 2)))
  (show (eq? a a)))
text
hello
hello
(+ 1 2)
3
(quote x)
quote
(#t #f #t)
#t
kiwi
"mango"
#t
(1 2 3)
(n is 3 and n squared is 9)
(1 4 5 6)
(nested (list 40 50))
(#t #t #f #t)
(#f #t)
#t
  • 'x is shorthand for (quote x). The reader turns the quote mark into that two-element list, which is why (car ''x) is the symbol quote. Chibi-Scheme prints such a list as (quote x); some implementations print it back as 'x.
  • A symbol is a name as data. string->symbol and symbol->string convert between symbols and strings, and the same spelling always gives the same symbol, so eq? works.
  • Quasiquote, the backquote, is a template: everything is quoted except what follows a comma. ,expr inserts the value of expr; ,@expr splices in the elements of a list. Quasiquote is the everyday way to build code and structured data, and macros (lesson 7) use it constantly.

Three kinds of sameness

PredicateAsksUse it for
eq?are these the very same object?symbols, '(), booleans, checking identity
eqv?same object, or the same number or character?numbers and characters (what memv, assv and case use)
equal?do these have the same structure and contents?lists, strings, vectors (what member and assoc use)

Two lists built separately with the same contents are equal? but not eq?. Two strings made separately are not eqv?. When in doubt, use equal?; reach for eq? only when you mean identity or are comparing symbols.

Worked examplesH

Code as data: a symbolic simplifier

Because expressions are lists, a program can take them apart and rebuild them. Here are two procedures over arithmetic expressions written as lists such as (+ (* 2 x) y): one simplifies them using algebraic rules, the other evaluates them given values for the variables, stored as a list of pairs.

scheme
(import (scheme base) (scheme write) (scheme cxr))

(define (simplify expr)
  (if (not (pair? expr))
      expr
      (let ((op (car expr))
            (a (simplify (cadr expr)))
            (b (simplify (caddr expr))))
        (cond ((and (number? a) (number? b))
               (case op ((+) (+ a b)) ((*) (* a b)) ((-) (- a b))))
              ((and (eq? op '+) (eqv? a 0)) b)
              ((and (eq? op '+) (eqv? b 0)) a)
              ((and (eq? op '*) (or (eqv? a 0) (eqv? b 0))) 0)
              ((and (eq? op '*) (eqv? a 1)) b)
              ((and (eq? op '*) (eqv? b 1)) a)
              ((and (eq? op '-) (equal? a b)) 0)
              (else (list op a b))))))

(define (evaluate expr env)
  (cond ((number? expr) expr)
        ((symbol? expr) (cdr (assq expr env)))
        (else
         (let ((a (evaluate (cadr expr) env))
               (b (evaluate (caddr expr) env)))
           (case (car expr)
             ((+) (+ a b))
             ((-) (- a b))
             ((*) (* a b)))))))

(define e1 '(+ (* 1 x) (* y 0)))
(define e2 '(* (+ 2 3) (- z (+ 0 z))))
(define e3 '(+ (* 2 x) (* (- 5 4) y)))

(for-each (lambda (e) (write e) (display "  =>  ") (write (simplify e)) (newline))
          (list e1 e2 e3))

(write (evaluate e3 '((x . 10) (y . 7)))) (newline)
(write (evaluate (simplify e3) '((x . 10) (y . 7)))) (newline)
text
(+ (* 1 x) (* y 0))  =>  x
(* (+ 2 3) (- z (+ 0 z)))  =>  0
(+ (* 2 x) (* (- 5 4) y))  =>  (+ (* 2 x) y)
27
27

simplify works bottom-up: it simplifies both operands first, then applies the first rule that matches. Constant subexpressions are folded ((- 5 4) becomes 1, then (* 1 y) becomes y), and identities such as x+0=xx + 0 = x, x⋅0=0x \cdot 0 = 0 and z−z=0z - z = 0 remove terms. The second example collapses entirely, because (+ 0 z) simplifies to z and then (- z z) to 0.

evaluate is a tiny interpreter: numbers evaluate to themselves, symbols are looked up in an environment (a list of name-value pairs searched with assq, which lesson 6 covers), and a list is an operation applied to its evaluated operands. Evaluating before and after simplification gives the same 27, a quick sanity check that the rules preserve meaning. Compilers do exactly this kind of rewriting, called constant folding and algebraic simplification, on a much larger scale.

History & global context

Code as data, then and now

The idea that programs and data share one notation goes back to the very beginning of Lisp. In his 1960 paper Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I, John McCarthy defined S-expressions as the data of his language and then showed that Lisp programs could themselves be written as S-expressions. To demonstrate, he wrote eval, a Lisp function that evaluates any Lisp expression given as data. When his student Steve Russell realised that this definition could simply be translated into machine code, the first Lisp interpreter was born. A language whose programs are ordinary data structures of the language is often called homoiconic.

That property explains several things you have already seen. The reader turns text into lists before the evaluator ever sees it, which is why 'x becomes (quote x). A REPL can print a value in a form that can be typed back in. And programs that write programs, such as the simplifier above or the macros of lesson 7, need no special parser: they use car, cdr, cons and quasiquote like any other list code.

In everyday Scheme today, lists remain the default sequence type, but with some judgment:

  • Lists are ideal for data processed front to back, built up recursively, or shared between versions (a new head can share an old tail).
  • Vectors are better when you need fast access by position or a fixed-size table (lesson 6).
  • Association lists are fine for small maps, such as an environment with a handful of variables; larger tables use hash tables from a SRFI or the implementation (lesson 6).
  • Most Scheme programmers treat lists as immutable by convention, even though set-car! and set-cdr! exist. Sharing structure is safe only when nobody mutates it.

The SRFI process ("Scheme Requests for Implementation") is how the community standardises libraries between reports. SRFI 1, the list library, adds dozens of well-designed list procedures such as fold, filter, delete and iota, and is available in almost every implementation, including Chibi-Scheme as (srfi 1). This course writes its own versions of the most important ones, because building them is how you learn what they cost.

Common misconceptionsH

Common mistakes

Misconception

Confusing cons, list and append. (cons '(1) '(2)) is ((1) 2), a list whose first element is a list. (list '(1) '(2)) is ((1) (2)). (append '(1) '(2)) is (1 2). cons adds one element to the front; list makes a list of its arguments; append joins lists.

Misconception

Modifying a quoted literal. A quoted list like '(1 2 3) is a constant, and R7RS says it is an error to modify it (with set-car!, for example). Some implementations allow it, others raise an error, and the results can be baffling because literals may be shared. Build mutable lists with list or list-copy.

Misconception

Using eq? on numbers or strings. Whether (eq? 100000000000 100000000000) is true depends on the implementation's internal representation. Use eqv? or = for numbers and equal? or string=? for strings.

Misconception

Calling length or list-ref inside a loop over the same list. Each call walks the list from the start, which turns a linear loop into a quadratic one. Walk the list once with car and cdr, or use a vector (lesson 6) when you need indexing.

Exercises

Exercises

1. Pairs, lists, symbols and quoting

Warm-upComputational

What does (write (cons '(1) '(2))) print?

2. Pairs, lists, symbols and quoting

CoreComputational

What does (write (cons 1 (cons 2 3))) print?

3. Pairs, lists, symbols and quoting

Warm-upComputational

What does (write (cadr '(a (b c) d))) print?

4. Pairs, lists, symbols and quoting

CoreComputational

Using the lesson's count-leaves, what is (count-leaves '(1 (2 3) ((4))))?

5. Pairs, lists, symbols and quoting

CoreComputational

What does this print?

(let ((x 5) (ys '(a b)))
  (write `(x ,x ys ,ys ,@ys)))

6. Pairs, lists, symbols and quoting

CoreComputational

Which of these evaluate to #t? List their letters.

  • A: (eq? 'a 'a)
  • B: (equal? (list 1 2) '(1 2))
  • C: (eq? (list 1) (list 1))
  • D: (eqv? 1.5 1.5)
  • E: (pair? '())

Write elements separated by commas. Order and repeats don’t matter — just like in a set!

7. Pairs, lists, symbols and quoting

Warm-upComputational

What does (write (memv 'c '(a b c d))) print?

8. Pairs, lists, symbols and quoting

StretchHuman

A loop builds a list of n results by doing (set! results (append results (list item))) for each new item. How does its total running time grow with n?

Choose one

Further reading and resources