CSC 153: Computer Science Fundamentals  Grinnell College  Spring, 2005 
Laboratory Exercise Reading  
This lab provides practice with lists in Scheme, including the basic operations (cons, car, cdr), list literals, the empty list, and several common builtin procedures.
In Scheme, a list is written by enclosing the elements of the list in parentheses. Here are some simple examples:
(+ x y) (this is a list) (sqrt x) ()
These lists have 3, 4, 2, and 0 components, respectively. The list () with 0 components also is called the empty list or the null list.
Any or all components of a list can, in turn, be lists:
(* pi (expt r 2)) (+ (* x x) (* 3 x) 2) (all x (if (human x) (mortal x))) ( () ) ((())) ((()())())
In reviewing the second of these examples, (+ (* x x) (* 3 x) 2) is a list with four components:
+ (* x x) (* 3 x) 2
Parts of lists can be extracted by car and cdr:
(car '(a b c)) = a (car '((a) b c)) = (a) (car (car '((a) b c))) = a (car 'a) error: a is not a list. (car '()) error: () is not a pair. (cdr '(a b c)) = (b c) (cdr '((a) b c)) = (b c) (cdr (cdr '(a b c))) = (c) (cdr (car '((a) b c))) = () (cdr 'a) error: a is not a list. (cdr '()) error: () is not a pair.In each of these examples, note that car and cdr are applied to a list which is introduced with a quote. Since parentheses are used both to group data into a list and to call procedures, the Scheme interactive interface needs to see a single quote at the front of a list literal, so that it will treat it as a datum instead of evaluating it.
Since combinations of car and cdr are frequently used, all combinations up to four uses of car and cdr are defined as functions of the form cxxxr:
(caar x) = (car (car x)) (cadr x) = (car (cdr x)) (caddr x) = (car (cdr (cdr x)))
(cons 'a '(b c)) = (a b c) (cons 'a '()) = (a) (cons '(a) '(b)) = ((a) b)The list function makes a list out of the elements that follow:
(list 'a 'b 'c 'd) = (a b c d) (list 'a '(b c)) = (a (b c)) (list 'a '()) = (a ()) (list '(a) '(b)) = ((a) (b))
(append '(a) '(b)) = (a b) (append '(a b) '(c d)) = (a b c d) (append '(a) '(b) '(c)) = (a b c)reverse makes a new list that is the reverse of the top level of the list given as its argument.
(reverse '(a b)) = (b a) (reverse '((a b)(c d))) = ((c d)(a b))length returns the number of components in the [top level] of a list.
(length '(a)) = 1 (length '(a b)) = 2 (length '((a b))) = 1 (length '(+ (* x x) (* 3 x) 2)) = 4
This document is available on the World Wide Web as
http://www.walker.cs.grinnell.edu/courses/153.sp05/readings/readinglists.shtml
created January 22, 1997 last revised January 25, 2005 

For more information, please contact Henry M. Walker at walker@cs.grinnell.edu. 