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.
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.
(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))))(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 sharesxsas its tail; nothing is copied. Adding to the front of a list is constant time.(cons xs 4)is not a longer list: itscdris 4, not a list, so it prints as a dotted pair.cadrmeans "thecarof thecdr", the second element. Combinations up to two letters deep (caar,cadr,cdar,cddr) are in(scheme base); deeper ones such ascaddrare in(scheme cxr).list?is true only for proper lists.pair?of the empty list is false:'()is not a pair.list-refandlengthmust walk the list, so they take time proportional to its length.appendcopies every list except the last.reversereverses only the top level; the inner list(2 3)is untouched.memvandmemberreturn the tail of the list starting at the element found, or#f. Because any non-#fvalue is true, the result works as a test.
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.
(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)108
(1 2 3 4)
(d c b a)
(a b (x) c)
(1 2 3 4 5 6)
6my-appendrebuilds the first list pair by pair and then points the last new pair atb. So appending costs time proportional to the length of the first list, andbis shared, not copied. Repeatedly appending to the end of a growing list is therefore quadratic; build it backwards withconsand reverse once instead.my-reverseuses an accumulator, so it is iterative and linear. Pushing each element onto the front ofaccreverses the order.remove-allremoves only top-level elements equal tox: the(x)inside a sublist stays.flattenandcount-leavestreat a list as a tree: a pair has two subtrees, itscarand itscdr. 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.
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".
(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)))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'xis shorthand for(quote x). The reader turns the quote mark into that two-element list, which is why(car ''x)is the symbolquote. Chibi-Scheme prints such a list as(quote x); some implementations print it back as'x.- A symbol is a name as data.
string->symbolandsymbol->stringconvert between symbols and strings, and the same spelling always gives the same symbol, soeq?works. - Quasiquote, the backquote, is a template: everything is quoted except what follows a comma.
,exprinserts the value ofexpr;,@exprsplices 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
| Predicate | Asks | Use 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.
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.
(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)(+ (* 1 x) (* y 0)) => x
(* (+ 2 3) (- z (+ 0 z))) => 0
(+ (* 2 x) (* (- 5 4) y)) => (+ (* 2 x) y)
27
27simplify 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 , and 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.
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!andset-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 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
1. Pairs, lists, symbols and quoting
Warm-upComputationalWhat does (write (cons '(1) '(2))) print?
2. Pairs, lists, symbols and quoting
CoreComputationalWhat does (write (cons 1 (cons 2 3))) print?
3. Pairs, lists, symbols and quoting
Warm-upComputationalWhat does (write (cadr '(a (b c) d))) print?
4. Pairs, lists, symbols and quoting
CoreComputationalUsing the lesson's count-leaves, what is (count-leaves '(1 (2 3) ((4))))?
5. Pairs, lists, symbols and quoting
CoreComputationalWhat does this print?
(let ((x 5) (ys '(a b)))
(write `(x ,x ys ,ys ,@ys)))
6. Pairs, lists, symbols and quoting
CoreComputationalWhich 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? '())
7. Pairs, lists, symbols and quoting
Warm-upComputationalWhat does (write (memv 'c '(a b c d))) print?
8. Pairs, lists, symbols and quoting
StretchHumanA 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?
Further reading and resources
- R7RS-small, section 6.4: Pairs and listsEvery list procedure in the standard, with exact definitions.
- R7RS-small, section 4.2.8: QuasiquotationThe rules for backquote, unquote and unquote-splicing.
- SRFI 1: List libraryThe widely implemented library of list procedures (fold, filter, delete, iota and many more).
- Structure and Interpretation of Computer Programs, chapter 2 · Harold Abelson and Gerald Jay Sussman with Julie SussmanBuilding abstractions with data, including symbolic data.