[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Everything is a list (Or: When you've got a hammer...)
I 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.
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
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
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.