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) x scm> (define y (+ 10 x)) y scm> y 13 scm> (define (foo x y) (cond ((> x y) 1) ((< x y) -1) (else 0))) foo scm> 'foo foo scm> (eval '(foo y x)) 1 scm> ((lambda (x y) (if (< x y) 'less-than 'greater-than)) y x) greater-than 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 takes in two arguments and creates a pair out of them.
The elements in a pair are separated by a dot. To retrieve the first element, use
car. To retrieve the second element, use
The entries in a pair can be other pairs.
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!
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.
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
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 takes in an arbitrary number of arguments and will simply create a well formed list of them.
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!
You can check whether a list is empty using
(null? lst). This is like asking whether
(= lst nil).
- A list is a pair whose second entry is another list.
- To construct a pair, use
- 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.
- To construct a list using
list, pass through every element in the list.
- To retrieve the first element of a pair or list, call
- 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