Now that we've seen examples of Scheme's syntax, let's see a more interesting program. (The title of this portion of the talk will eventually make sense: we promise.) Let's consider the function member, which takes an item and a list, and checks whether the item is contained in the list. To motivate this for students, we could suggest the list consists of people invited to a party; the party is so large, the student writes programs to handle the invitations; and the student wants to write a program that checks whether certain friends are on the list or not. Here's an algebraic definition of member:
| false | if l is empty | |
| member (x, l) = | true | if x = first(l) |
| member (x, rest(l)) | otherwise |
Now here's a Scheme function that corresponds to this definition. The
Scheme code introduces a new (our second!) keyword, cond,
which is used for conditional definitions. Note that the
cond has as many branches as the conditional definition
above.
(define (member x l)
(cond
((empty? l) false)
((equal? x (first l)) true)
(else (member x (rest l)))))
Okay, so there's one more keyword, else, which is used in
the last branch of a cond as the ``fall-through'' condition.
What does this program look like in a language like C? In a slightly different context, a group of Scheme educators once said that their approach could be taught with a more traditional language, except it would be ``a little like pouring ketchup over caviar''. This obscure joke is the basis of the color scheme in the following code (apologies to those who don't have the ability to view colors): the code in black (caviar) represents the parts essential to the computation, while that in red (ketchup) is the inessential detail that must be specified to keep the system happy.
bool member (int x, list l) {
if (l == NULL)
return false;
else if (x == (l -> first))
return true;
else
return member (x, l -> rest);
}
The careful reader will have observed that we underlined the two uses
of ==. Why? Because a
very typical error that students commit is to write =
instead, which is an assignment rather than a comparison. It can lead
to terrible and hard-to-detect errors.
We also underlined the two uses of ->. A programmer tends to think of
this as meaning, ``go to the location referred to by the pointer, look
for the named field, and extract its contents''. In reality, it
means, ``go to the location referred to by the pointer, increment by a
fixed offset, and return whatever is there''. For example, if a
student is hasty and forgets to test for the base case, then the first
-> really goes to the location of the NULL
pointer, offsets by some distance, and returns what is effectively
rubbish.
That's not all. (You knew that.) To get this to work, we need some
more ketchup:
#include <stdio.h>
typedef struct listCell * list;
struct listCell {
int first;
list rest;
};
Okay, but are we done yet? No! In the Scheme version, we can test
this function out right away using the Interactions window. In C, we
must also write a bunch of i/o code to test it out:
int main (int argc, char ** argv) {
list l1, l2, l3 = NULL; int x;
l1 = (list) malloc (sizeof (struct listCell));
l2 = (list) malloc (sizeof (struct listCell));
l2 -> first = 3; l2 -> rest = l3;
l1 -> first = 2; l1 -> rest = l2;
scanf ("%d", &x);
printf ("%d\n", member (x, l1));
}
(Don't forget to teach your student about casts and address-of
operators---the underlined bits---along the way!)
Okay, so we're all even, right? No! The student's program still tests only one value at a time. (Remember, looping constructs usually show up only after eight to ten weeks.) So for each value he wants to test, he needs to run the program again. Does that encourage experimentation?
There's one more nail for the coffin. Recall that in the DrScheme interaction example, we could test a function on not just values, but also expressions, such as
(f (+ 2 3))
2 + 3
5? Of course not!
PLT / scheme@cs.rice.edu
Last modified at 17:04:44 CST on Thursday, January 11, 2001