The Little Schemer: Chapter 1
Chapter notes from The Little Schemer, which I am reading as part of my self-study CS curriculum and exploration into functional programming. In particular, I’m aiming to better understand recursion and symbolic manipulation, key topics in functional languages.
Not everything written here is covered in the chapter—some of it I had to research to make better sense of the material. As such, the notes are not purely a summary but also include supplementary explanations.
Primitive Data Types
Atom
An atom is any indivisible value in Scheme, meaning it is not a list or pair. Atoms include numbers, strings, booleans, and symbols:
123
"word"
#t
x
List
Lists are collections of symbolic expressions (S-expressions) wrapped in parentheses. Lists can contain other lists as well as atoms:
'(123 word)
'(protein (carbs fat))
'('(we) '(live) '(in) '(a) '(society))
This includes the null or empty list () .
Unquoted lists are evaluated:
(+ 1 2 3) ;; 6
Quoted lists are treated as data and not evaluated:
'(+ 1 2 3) ;; (+ 1 2 3)
Pair
Pairs allow us to combine two Scheme objects into a single entity.
As the GNU reference states:
Pairs are used to combine two Scheme objects into one compound object. Hence the name: A pair stores a pair of objects.
The data type pair is extremely important in Scheme, just like in any other Lisp dialect. The reason is that pairs are not only used to make two values available as one object, but that pairs are used for constructing lists of values.
The syntax for pairs uses parentheses and a dot to separate the two objects. There must be whitespace on either side of the dot:
'(1 . "a") ;; (1 . "a")
'("hello" . ()) ;; ("hello")
We can test if an object is a pair using the pair? primitive:
(pair? '("The" . "Simpsons")) ;; #t
(pair? "The Simpsons") ;; #f
(pair? '()) ;; #f
Symbolic Expressions
An S-expression (short for symbolic expression) is a way of representing data in Scheme, as well as in LISP and computer science in general. Both atoms and lists are S-expressions.
The uniform structure of S-expressions makes them especially convenient for representing recursive data, which will become very useful as we explore more of Scheme’s power.
Procedures
car returns the first element of a list and cannot be applied to atoms:
(car '(12 24 36)) ;; 12
(car (car '((1 2 3 4) (5 6 7)))) ;; 1
(car '(+ (* 2 2) (/ 3 3))) ;; +
The Law of Car: The primitive car is only defined for non-empty lists.
cdr (“could-er”) removes the first element of the list and returns the rest:
(cdr '(x y z)) ;; (y z)
(cdr (cdr '(x y z))) ;; (z)
(cdr '(gone)) ;; ()
The Law of Cdr: The primitive cdr is only defined for non-empty lists. The cdr of any non-empty list is always another list.
cons takes an S-expression (which can be an atom or list) and a list as parameters, appending the S-expression to the front of the list:
(cons 'zoo '(lake forest)) ;; (zoo lake forest)
(cons '+ '(1 2)) ;; (+ 1 2)
The Law of Cons: The primitive cons takes two arguments. The second argument to cons must be a list. The result is a list.
null? takes a list and returns #t (true) if it is empty, otherwise #f (false):
(null? '()) ;; #t
(null? (/ 7 1)) ;; #f
(null? 1) ;; #f
The Law of Null?: The primitive null? is defined only for lists.
eq? takes in two non-numeric atoms and tests them for equality
(eq? 'abc 'xyz) ;; #f
(eq? 'same 'same) ;; #t
(eq? (car (car '((first) second third))) (car (cons 'first '()))) ;; #t
The Law of Eq?: The primitive eq? takes two arguments. Each must be a non-numeric atom.
Note: In some Scheme implementations, eq? may behave unexpectedly with numbers and strings. For numeric equality, use =.
Binding
To bind a symbol to a value, we use the define procedure:
(define one-hundred 100)
(define name "Lyndon")
(define age one-hundred)
(define empty-list ())
(define pod '("pea" . "another pea"))
All the procedures we’ve seen so far can work with symbols that have been bound to values in this way:
(null? empty-list) ;; #t
(cons 1 empty-list) ;; (1)
(eq? name "Lyndon") ;; #t
We can also define procedures. The first argument is the procedure signature (name and parameters), and the second argument is the procedure body:
(define (square x) (* x x))
(square 2) ;; 4
Alternatively, we can use lambda to define anonymous procedures:
(define add-one
(lambda (n) (+ n 1)))
(add-one 99) ;; 100
Putting it All Together
As a helper function in the book, the authors suggest defining an atom? procedure that returns a boolean indicating whether an object is an atom:
(define atom?
(lambda (object)
(and (not (pair? object)) (not (null? object)))))
This definition serves as a useful summary of many of the constructs we’ve covered, and providing a clearer understanding of what an atom actually is.
Here, the and and not procedures act as logical operators, functioning as you would expect.