TCEA State 1998 Slides

Ketchup and Caviar

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)
    ((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;
    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))
If a student types in
2 + 3
at the prompt printed by his test program in the C version, does this test the function with the value 5? Of course not!


Last modified at 17:04:44 CST on Thursday, January 11, 2001