================================================================== Hunk D starts here: ==================================================================
I've been talking about "objects," but most of the objects we've seen don't have interesting structure.
One of the most important kinds object in Scheme is the pair,
which you can create with the built-in procedure cons.
A pair is a simple kind of structured object, like a Pascal
record or a C struct. It has two fields, called the car and
the cdr, and you can extract their values with the standard
procedures car and cdr.
cons takes two arguments, which it uses as the initial values
of the car and cdr fields of the pair it creates. (cons is
called that because it constructs a pair; the name is short
because it's a common operation. In Lisp, pairs are called "cons cells"
because you make them with cons.)
I'll show you some simple examples of playing with pairs, just to show you what they are. Be warned that these are bad examples, in that there are usually cleaner ways to do things, which we'll discuss later when we get to lists. (Lists are made of pairs.)
Scheme>(cons 1 2) (1 . 2)
What happened here was that the call to cons created a pair,
and returned (a pointer to) it. Scheme printed out a textual
representation of the pair, showing the values of its car and cdr
fields, separated by a dot and enclosed in parentheses.
(The printed representation looks sort of like a Scheme expression,
because of the parentheses, but it's not--it's just the way Scheme
prints this kind of data structure. We're looking at the value
returned by the expression (cons 1 2). Don't be confused
by the similarity between written Scheme expressions and the textual
representation of data structures--they're very different things.)
We didn't do anything with the pair except let Scheme print it, so we've lost it--we didn't save a pointer to it, so we can't refer to it. (The garbage collector will take back its space, so we don't have to worry that we've lost storage space.)
Let's try again, defining (and binding) a variable, and initializing it
with the pointer that cons returns.
Scheme>(define my-pair (cons 1 2)) #void Scheme>my-pair (1 . 2)
Now try extracting the values of the pair's fields, using car and
cdr.
(In Scheme, (car foo) is equivalent to C's foo->car,
dereferencing a pointer to an object and extracting the value of the
car field. Likewise, (cdr foo) is like foo->cdr.
The operators that access fields of a pair are just procedures.)
Scheme>(car my-pair) 1 Scheme>(cdr my-pair) 2
We don't need to use any special pointer syntax to dereference the pointer to the pair---car and cdr expect a pointer, and return the field values of the pair it points to.
car and cdr only work on pairs. If you try to take the
car or cdr of anything else, you'll get a runtime type error.
Try it:
Scheme>(car #t) ERROR: attempt to take the car of a non-pair #t break>,top Scheme>
The messages you'll see vary from system to system, but the basic idea
is the same. We tried to take the car of the boolean #f,
which makes no sense because it has no car field--it doesn't have
any fields. Scheme told us it didn't work, and gave us a break
prompt for sorting it out. Then we just used the ,top command
(or whatever works on your system) to tell Scheme to give up on
evaluating that expression and go back to normal interaction.
car and cdr don't work on the empty list. The empty
list doesn't have car and cdr fields. (This may be surprising to
Lisp programmers, who expect the empty list to behave like Lisp's
nil. It doesn't, in this respect.)
Scheme also supplies procedures to change the values of a pair's fields,
called set-car! and set-cdr!. They take two arguments,
a pair and a value for the field being set.
Scheme>(set-car! my-pair 4) #void Scheme>my-pair (4 . 2) Scheme>(set-cdr! my-pair 5) #void Scheme>my-pair (4 . 5)
The value of the variable my-pair hasn't actually changed, even
though it prints differently. my-pair still holds a pointer to the
same object, the pair we created with cons. What has
changed is the contents of that object. Its fields are like
variable bindings, in that they can hold (pointers to) any kind of
object, and we've assigned new values to them. (They're value cells.)
We can refer to the same object by another name if we just define
another variable and initialize it with my-pair's value.
Scheme> (define same-pair my-pair) #void Scheme>same-pair (4 . 5)
Now suppose we assign a new value to the car of the pair, referring
to it via my-pair
Scheme>(set-car! my-pair 6) #void Scheme>my-pair (6 . 5) Scheme>same-pair (6 . 5)
Notice that the change is visible through same-pair as well as
my-pair, because we've changed the object that both of them
point to.
Now let's make another pair with the same field values.
Scheme>(define different-pair (cons 6 5)) different-pair Scheme>different-pair (6 . 5) Scheme>my-pair (6 . 5) Scheme>same-pair (6 . 5)
Notice that we have two different pairs, but Scheme prints them out
the same way, because it just shows us the structure of
data structures. We can't tell that they're different just by
looking at the printed output. From the printed representation,
we can't tell whether or not my-pair, same-pair, and
different-pair hold the same values.
Scheme provides a predicate procedure, eq?, to tell whether
two objects are the exact same object.
Scheme>(eq? my-pair same-pair) #t Scheme>(eq? my-pair different-pair) #f Scheme>(eq? same-pair different-pair) #f
eq? tests object identity, like pointer comparisons
in C (using ==) or Pascal (using =).
It may be confusing, but in programming language terminology, two objects are called identical only if they are the very same object, not just two objects that look alike, like "identical" twins. When the government issues "identity" cards, this is the kind of "identity" we're talking about. Two so-called identical twins have different identities, because they're actually different people. A pointer is like a a social security number, because it uniquely identifies a particular individual object.
Scheme also has a test to see whether objects "look the same,"
that is, have the same structure. It's called equal?.
We call this a structural equivalence test.
Scheme>(equal? my-pair same-pair) #t Scheme>(equal? my-pair different-pair) #t Scheme>(equal? same-pair different-pair) #t
different-pair is equal? to my-pair and same-pair
because it refers to the same kind of object, and its field values
are equal?. Notice that that's a recursive definition, which
we'll discuss more when we get to lists.
If we didn't have eq?, we could still figure out whether two
objects were exactly the same object, by changing one and seeing if
the other changed, too.
Scheme>(set-car! my-pair 4) #void Scheme>my-pair (4 . 5) Scheme>same-pair (4 . 5) Scheme>different-pair (6 . 5)
Now I should warn you about set-car! and set-cdr!. The
reason we put an exclamation point in the name of a procedure that
side-effects data is because it's dangerous. If you have two
pointers to the same data from different places, i.e., different
variable bindings or data structures, it's hard to reason about how
changes from one of those places affect things at the other place.
In normal Scheme programming style, it is very common to create new data structures that have pointers to other data structures, or parts of data structures. If you modify a shared part of one data structure, it will affect the other data structure that shares that part. This can be very confusing, and leads to subtle bugs.
You should only use side effects when you have a very good reason to, and make it clear that that's what you're doing. Later examples will show how to program in a style that uses very few side effects, and only where they make sense.
Notice that cons is not considered a side-effecting
operation, because it returns a new object that has never
been seen before. Somewhere in the implementation of the language,
cons side-effects memory to initialize it, but you don't
see that--from your program's point of view, you're getting
a new piece of memory that magically has values in place.
Creating a pair doesn't modify any data structure that already exists, so the installation of its initial values is not considered a side-effect.
================================================================== This is the end of Hunk D. At this point, you should go back to the previous chapter and read Hunk E before returning here and continuing this tutorial. ==================================================================
(Go BACK to read Hunk E, which starts at section The Empty List (Hunk E).)