# CS 307: Avoiding Scheme Pitfalls

### Variables Must Be Bound.

In general, every variable name that you use must be either:
1. an argument of the function
2. 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):
1. List recursion
2. 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)))
```
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.