Section 9

Compound Data, Part 2: Lists

9.1  Lists

The first and rest operators work only on lists created with cons, i.e., non-empty lists. So

(first empty)

gives the error message:
first: expects type <non-empty list> as 1st arg: given empty

9.2  Data Definitions for Lists of Arbitrary Length - no notes

No DrScheme notes for this section.

9.3  Processing Lists of Arbitrary Length

Infinite Reductions

When writing recursive programs, it is easy to create an expression that never produces a value. For example, consider the following program:

(define (contains-doll? los)
  (cond
   [(empty? los) false]
   [else (cond
           [(symbol=? (first los) 'doll) true]
           [else (contains-doll? los)])]))

The above program is wrong; it contains the expression (contains-doll?_los) instead of (contains-doll?_(rest los)). As a result, the evaluation (contains-doll?_(cons 'ball empty)) proceeds as follows:
  (contains-doll? (cons 'ball empty))
= (cond
   [(empty? (cons 'ball empty)) false]
   [else (cond
           [(symbol=? (first (cons 'ball empty)) 'doll) true]
           [else (contains-doll? (cons 'ball empty))])]))
= (cond 
    [(symbol=? (first (cons 'ball empty)) 'doll) true]
    [else (contains-doll? (cons 'ball empty))])]))
= (contains-doll? (cons 'ball empty))
= ...

DrScheme is stuck evaluating the same expression forever -- or until the Break button is hit.

When DrScheme takes suspiciously long to evaluate an expression, click the Break button and inspect your program. Look for a missing rest in a recursive call, or for some other bug that makes it impossible to reduce an expression to a value.

Infinite Reductions using Infinite Memory

In the above example, (contains-doll?_(cons 'ball empty)) eventually reduces to itself. In a few bad programs, an expression can ``reduce'' to an ever larger expression. For example, if (contains-doll?_los) is changed in the above program to (add1 (contains-doll?_los)), then the reduction steps include

  (contains-doll? (cons 'ball empty))
= ...
= (add1 (contains-doll? (cons 'ball empty)))
= ...
= (add1 (add1 (contains-doll? (cons 'ball empty))))
= ...

In this case, not only does the expression fail to reduce to a value, but the overall expression grows forever. Since DrScheme performs the reductions very quickly, it can produce an exceedingly large expression in a short time, requiring more and more memory from your computer to store the expression.

Eventually, DrScheme would comsume all the memory on your computer, and then die. However, before this happens, you would probably notice that you machine's disk starts running constantly as DrScheme starts to use disk space for memory. If this happens, click the Break button as soon as possible.

Once DrScheme starts using disk space for memory, it might become addicted to using the disk, so that DrScheme continues to use the disk even after recovering from Break. If that happens, quit DrScheme (in the normal way, using the File|Quit menu) and start over to break DrScheme's addiction and get better performance.

9.4  Designing Functions for Self-Referential Data Definitions - no notes

No DrScheme notes for this section.

9.5  More on Processing Simple Lists - no notes

No DrScheme notes for this section.