Lists of Arbitrary Length

Infinite Loops

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) #f] 
   [else (cond 
           [(eq? (first los) 'doll) #t] 
           [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)) #f] 
   [else (cond 
           [(eq? (first (cons 'ball empty)) 'doll) #t] 
           [else (contains-doll? (cons 'ball empty))])])) 
= (cond 
    [(eq? (first (cons 'ball empty)) 'doll) #t] 
    [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 on 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 Loops 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, hit the Break button as soon as possible.

Once DrScheme starts using disk space for memory, it might become addicted to using the disk. In that case, 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.