Everything is a list (Or: When you've got a hammer...)

*Olin Shivers*18 Feb 1999 03:55 UTCI have going over the discussions by Stone, Currie, and others, as to distinctions between proper lists, improper lists, circular lists, etc. This has led me to thinking about definitions, base cases, and so forth. The results of this thinking is partially reflected in some of the text in the recent "issues" msg I just sent to the SRFI-1 list. But I would like to set down the following bit of text stating the definitions used, and how they are derived. The rather unusual conclusion to which I have come is that *every* value in Scheme is a list, rather in the same spirit that every value in APL is an array, even scalar values. So my intent is to put the following definitional essay and the three predicates it introduces into the prologue of the list-lib spec. -Olin ------------------------------------------------------------------------------- I would like to set out some definitions for basic kinds of list structure in Scheme. The main problem derives from the fact that Scheme does not have a list type -- just as C does not have a string type. 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 unbounded trees and lists. You can view these two properties as sleazy or fun, depending upon which direction you face when you kneel to pray. In fact, as we'll shortly discuss, a more generous comparison would be to state that lists in Scheme are pervasive -- everything is a list -- just as arrays in APL are pervasive. Let's consider the notion of lists from a fairly high and general level. A Scheme list is described by enumerating its elements, and, if it is finite, specifying the list terminator. This description shows us we have, basically, three fundamental kinds of list in Scheme, depending on the termination: - Infinite (circular) lists (no termination); - nil-terminated lists (which are necessarily finite); Examples: (a b) (a) () - finite non-nil-terminated lists. Examples: (a b . c) (a . c) c Nil-terminated lists are the most standard kind of lists. Note that any non-pair, non-nil Scheme value has an interpretation as a 0-element non-nil-terminated list. Hence, it is useful to define the following predicates: circular-list? x -> boolean True if X is a circular list. A circular list is a value such that for every n >= 0, cdr^n(x) is a pair. The opposite of circular is finite. proper-list? x -> boolean A proper list is a nil-terminated list (necessarily finite). If there exists an n >= 0 such that cdr^n(X) = (), then X is a nil-terminated list. Thus only zero-length proper list is (). Nil-terminated lists are called "proper" lists by R5RS and Common Lisp. The opposite of proper is improper. R5RS binds this function to the variable LIST?, which is somewhat confusing. dotted-list? x -> boolean True if X is a finite, non-nil-terminated list. That is, there exists an n >= 0 such that cdr^n(x) is neither a pair nor (). This includes non-pair, non-() values (e.g. symbols, numbers), which are considered to be dotted lists of length 0. Common Lisp has a similar definition of dotted lists, but Common Lisp's excludes non-nil, non-pair values. This, I believe, is a bolted-on exception; the "grammar" for dotted lists is most naturally and simply defined to include these cases, as is recursive code that processes them. While I am aware one can make an argument against 0-element dotted lists on the grounds of error checking, I don't buy it. The natural definition includes these values; you are fighting the structure to exclude them. What one is doing with dotted lists, essentially, is stating that *all* finite binary trees have an interpretation as a list, not simply the ones whose right-spine terminates in (). Well, leaf nodes are binary trees.