# 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`.
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`.