Day dreams to grow great.

Write safe Scheme procedure that handles only proper list January 3, 2010

Filed under: Uncategorized — day @ 17:28

C does not have a string type, thus a string is actually constructed via an array of characters, with a special NUL character marking its end. Similarly, Scheme does not have a list type, a list is actually consed recursively from pairs, with a special constant nil marking its end. The lack of a true list type results in the distinction of “proper list” (consed pairs ended with a nil) and “improper list” (consed pairs not ended with a nil), for example, (0 1 2) is a pretty printed form for (0 . (1 . (2 . nil))), and more primitively (cons 0 (cons 1 (cons 2 nil))), while (0 1 . 2) for (0 . (1 . 2)), in turn (cons 0 (cons 1 2)). Although improper list is rarely used in Scheme (as a dialect of Lisp, it of course does a lot of (proper) list processing), we can not presume that one will call a procedure intended to handle a proper list with indeed a proper one. So when writing a procedure that expects to handle a proper list, we need to take care of the extreme case.

SRFI-1 provides a pair of procedures proper-list? and improper-list? for testing whether a list is proper or not respectively. Thus when we write a procedure to handle proper list, we can first check to see if the passed in argument is a proper list before we actually deals with it. For example, the standard length procedure could be defined as follows:

   (define (length l)
     (cond ((improper-list? l) (print "Error: passed in an improper list"))
           ((null? l) 0)
           (else (+ 1 (length (cdr l))))))

It’s easy to see that both proper-list? and improper-list? need to traverse the list before they can tell whether the list is proper or not. To avoid this unnecessary traversal, we can embed the test inline as shown below:

   (define (length l)
     (cond ((pair? l) (+ 1 (length (cdr l))))
           ((null? l) 0)
           (else (print "Error: passed in an improper list"))))

This version of length seems better than the first one, however, it may not generally be true. For a general procedure on list, the late coming info about the proper/improper attribute of the list (we don’t till the end) may make us do much useless work on every element of the list except the last.