I don't understand this business about the end-marker yet.
It's probably easiest to grasp if you think of it as a list containing zero
elements, the limiting case of the operation of removing the first element
from a list. If you apply the cdr procedure to a list
containing, say, six elements, you get a list containing five elements:
If you apply the same procedure to the list of five elements, you get a list of four; and if you apply it again to the list of four, you get a list of three:> (define list-of-six (list 6 5 4 3 2 1)) > (cdr list-of-six) (5 4 3 2 1)
Eventually, you get down to a list of one element; and if you apply the> (define list-of-five (cdr list-of-six)) > (cdr list-of-five) (4 3 2 1) > (define list-of-four (cdr list-of-five)) > (cdr list-of-four) (3 2 1)
cdr procedure to that one, you get the empty list:
But the empty list can't be a pair, since there's nothing left to put into it; it has to be some different kind of a value. This ``empty list'' value could be anything that can easily be distinguished from valid data. In fact, before Scheme was standardized, there were some implementations of the language that used the Boolean false value as the end-marker, so that the expressions> (define list-of-one (cdr list-of-two)) > list-of-one (1) > (cdr list-of-one) ()
#f and '() were used
interchangeably. But the current Scheme standard guarantees that they are
distinct; the value of '() is not a Boolean. But what is it, then? That's what I don't understand.
There's nothing one can really say about it, except ``It's the empty list.'' Most implementations represent it internally with a sequence of bits that are all clear (that is, ``off''), together with some arbitrary integer that designates the null data type. But such internal representations are invisible to the Scheme programmer.
Next topic
Previous topic
Table of contents
This document is available on the World Wide Web as
http://www.math.grin.edu/~stone/scheme-web/null-type.html