This page is under construction!


Scheme, a dialect of another language called Lisp, is a very powerful functional programming language. In this class, we are only concerned with a very basic subset of the Scheme language which includes writing basic procedures, manipulating pairs and lists, writing tail recursive procedures, and working with streams.

This guide assumes you know basic Scheme, including primitives, variable and procedure definitions, and call expressions. For a quick review, what would Scheme output after each of the following lines are input?

scm> (define x 3)  
scm> (define y (+ 10 x))  
scm> y
scm> (define (foo x y)  
    (cond ((> x y) 1)
        ((< x y) -1)
        (else 0)))
scm> 'foo
scm> (eval '(foo y x))
scm> ((lambda (x y) (if (< x y) 'less-than 'greater-than)) y x)
scm> '(a b c)
(a b c)


If you had any trouble with this, take time to review the Scheme lab.


Lists in Scheme are a lot like Linked Lists in Python. Whereas a Linked List in Python is comprised of several Links, a list in Scheme is made up of pairs.


A pair is the fundamental sequential unit in Scheme. To create one, use cons. cons takes in two arguments and creates a pair out of them.

scm> (cons 3 5)
(3 . 5)

The elements in a pair are separated by a dot. To retrieve the first element, use car. To retrieve the second element, use cdr.

scm> (define lst (cons 2 3))
scm> (car lst)
scm> (cdr (cons 4 5))

The entries in a pair can be other pairs.

scm> (define lst (cons 3 (cons 4 5)))
scm> lst
(3 4 . 5)
scm> (car lst)
scm> (cdr lst)
(4 . 5)
scm> (cdr (cdr lst))
scm> (cons (cons 4 5) (cons 6 7))
((4 . 5) 6 . 7)

When Scheme sees a . immediately followed by an open parenthesis, it removes the dot, the open parenthesis, and the corresponding close parenthesis. This way, we can construct what’s known as a well-formed list from a bunch of pairs!

Well-formed lists

A well-formed list is actually just a pair whose first argument is the first element of the list and the second argument is another well-formed list. The last list argument is an empty list, or nil, to signify the end of the sequence.

scm> (cons 5 nil) ; one-element list
scm> (cons 1 (cons 2 (cons 3 nil))) ; three-element list
(1 2 3)
scm> (cons 1 (cons 2 (cons 3 '()))) ; same as previous
(1 2 3)

The take-away is this: cons can be used to create a list if and only if the first arugument is the first element of the list and the second argument is another list, which can be nil.

scm> (define first 1)
scm> (define rest '(2 3 4 5)) 
scm> (cons first rest)
(1 2 3 4 5)

Notice above that it is possible to also create lists with '. Keep in mind that this will create the exact list that comes after it, which means we can’t do something like '(1 (cons 2 nil)).

Scheme provides us with an alternate to cons that is much more succinct and readable: list. list takes in an arbitrary number of arguments and will simply create a well formed list of them.

scm> (list 1 2 3 4)
(1 2 3 4)

Be careful, though; whereas with cons you can pass through the rest of the list as the second argument, passing lists through to list will create nested lists!

scm> (list 1 2 (list 3 4) 5)
(1 2 (3 4) 5)
scm> (list 1 2 (cons 3 (cons 4 nil)) 5)
(1 2 (3 4) 5)

You can check whether a list is empty using (null? lst). This is like asking whether (= lst nil).

scm> (null? nil)
scm> (null? (list 1 2 3))
scm> (null? '())


  1. A list is a pair whose second entry is another list.
  2. To construct a pair, use cons.
  3. To construct a list using cons, pass through its first element as the first argument and the rest of the list as the second argument.
  4. To construct a list using list, pass through every element in the list.
  5. To retrieve the first element of a pair or list, call car.
  6. To retrieve the second element of a pair or the rest of a list, call cdr. 7. Check whether a list is empty using the predicate null?.