CS 307: Avoiding Scheme Pitfalls

This page contains advice to help you write correct Scheme programs. Most of the advice is based on common errors that are seen in student programs on exams.

Variables Must Be Bound.

In general, every variable name that you use must be either:

an argument of the function
a let variable.

If you see a variable used in your code that is not one of these, it is an error.

Know the Design Patterns

It is likely that most exam questions will involve one of our design patterns (perhaps with some slight modification):

List recursion
Tree recursion

Choose the Right Design Pattern

Using tree recursion on a problem that should be list recursion is a recipe for disaster. Ask yourself: Is the function argument a list of things that all look the same? If so, it is probably list recursion.

Tree Recursion should be Symmetric

Using list recursion as part of tree recursion usually doesn't work well. Tree recursion should do the same thing to car and cdr.

   (define (occurs? item tree)
     (if (pair? tree)
         (or (occurs? item (car tree))
             (occurs? item (cdr tree)))
         (eqv? item tree) ) )

Solve the General Case

The example input and output given with a problem are just that: an example. If you write a function that only handles an input that is almost exactly like the example, you are sure to lose a lot of points.

Know the Lookup Functions

It is important to know all the basic Scheme functions, but especially the lookup functions member and assoc.

(member item list) can be used to test whether item appears in list (#f if not).
```
(member 'math '(cs physics math chemistry))
    =>  (math chemistry)
```
Since this is not #f, it is logically true: math is a member of the list.
(assoc item alist) will both test whether item appears in alist (#f if not) and also will retrieve information associated with item.
```
(assoc 'bread '((eggs .69) (milk 1.89) (bread 1.39)))
    =>  (bread 1.39)
```
Remember to use cadr if what you want is the price of the item.

Look at the inputs to see whether they look like natural arguments to member or assoc:

member: a list of symbols: (cs physics math chemistry)
assoc: a list of sublists: ((eggs .69) (milk 1.89) (bread 1.39))

If you write an extra recursion to do what could be done by member or assoc, you are working too hard and inviting errors.

Avoid Global Variables

Global variables should be used sparingly in any case; they will almost never be needed on exam problems. If you find yourself wanting to use a global variable to accumulate something, consider whether you can do the same thing by returning values from a recursive function.

Don't Drop the Ball

Remember that functions, such as +, cons, or your own functions, return a value. If you don't do something with that value, it will be lost. Consider:

   (+ item sum)

If this is the return value of the function, fine; but if you want to add to sum, you must use set!:

   (set! sum (+ item sum))

Don't Drop the Ball during Recursion

Each time a function is entered, there is a fresh copy of argument variables and let variables on the stack; when the function exits, these vanish, along with their values.

Suppose we want to count the number of symbols is a list:

Wrong:   (define (nsymbols lst)
           (let ((n 0))
             (if (pair? lst)
                 (begin
                   (if (symbol? (car lst))
                       (set! n (+ n 1)) ) )
                   (nsymbols (cdr lst)) )
             n))

This function doesn't work. The author is expecting the recursive call to nsymbols to increment n for the rest of the list, but what it does is to increment a new copy of n, which then is lost. There is a disconnect between the function and its recursive calls, and the value gets dropped.

We can use the value of the recursive call to hold the value of n on the way back:

Right:   (define (nsymbols lst)
           (if (pair? lst)
               (if (symbol? (car lst))
                   (+ 1 (nsymbols (cdr lst)))
		   (nsymbols (cdr lst)))
               0))

We can use tail recursion and send the value of n down:

Right:   (define (nsymbols lst) (nsymbolsb lst 0))
         (define (nsymbolsb lst n)
           (if (pair? lst)
               (nsymbolsb (cdr lst)
                          (+ n (if (symbol? (car lst))
                                   1
                                   0)))
               n))

We can use iteration, so there is only one value of n:

Right:   (define (nsymbols lst)
           (let ((n 0))
             (dolist (item lst)
               (if (symbol? item)
                   (set! n (+ n 1)) ) )
             n ))

Avoid Unnecessary Assignments

If you are going to use a computed value immediately (and not use it otherwise), just nest the computation in your function call. Compare:

   (set! n (+ n 1))
   (myfunction n)

with the simpler code:

   (myfunction (+ n 1))

Use Begin inside If

If the true (or false) branch of an if does more than one thing, be sure to enclose them in a begin.