2.2.4.3 Improper Lists

Scheme does not properly have a list type, just as the C language does not have a string type. Rather, Scheme has a binary–tuple type, from which one can build binary trees. There is an interpretation of Scheme values that allows one to treat these trees as lists. Further complications ensue from the fact that Scheme allows side–effects to these tuples, raising the possibility of lists of unbounded length, and trees of unbounded depth (that is, circular data structures).

However, there is a simple view of the world of Scheme values that considers every value to be a list of some sort. That is, every value is either:

• a “proper list” (a finite, nil–terminated list) such as:

  (a b c)
  ()
  (32)
  

• a “dotted list” (a finite, non–nil terminated list) such as:

  (a b c . d)
  (x . y)
  42
  george
  

• or a “circular list” (an infinite, unterminated list).

Note that the zero–length dotted lists are simply all the non–null, non–pair values.

This view is captured by the predicates proper-list?, dotted-list?, and circular-list?. This list library users should note that dotted lists are not commonly used, and are considered by many Scheme programmers to be an ugly artifact of Scheme’s lack of a true list type. However, dotted lists do play a noticeable role in the syntax of Scheme, in the “rest” parameters used by n–ary lambdas:

(lambda (x y . rest) ...)

Dotted lists are not fully supported by this list library. Most procedures are defined only on proper lists, that is: finite, nil–terminated lists. The procedures that will also handle circular or dotted lists are specifically marked. While this design decision restricts the domain of possible arguments one can pass to these procedures, it has the benefit of allowing the procedures to catch the error cases where programmers inadvertently pass scalar values to a list procedure by accident, e.g., by switching the arguments to a procedure call.