Go to the first, previous, next, last section, table of contents.

Objects on the Heap

Most Scheme objects only have fields that are general-purpose value cells---any field can hold any Scheme value, whether it's a tagged immediate value or a tagged pointer to another heap-allocated object. (Of course, conceptually they're all pointers, so the type of a field is just "pointer to anything.")

So, for example, a pair (also known in Lisp terminology as a "cons cell") is a heap-allocated object with two fields. Either field can hold any kind of value, such as a number, a text character, a boolean, or a pointer to another heap object.

The first field of a pair is called the car field, and the second field is called the cdr field. These are among the dumbest names for anything in all of computer science. (They are just a historical artifact of the first Lisp implementation and the machine it ran on.)

Pairs can be created using the procedure cons. For example, to create a pair with the number 22 as the value of its car field, and the number 15 as the value of its cdr field, you can write the procedure call (cons 22 15).

The fields of a pair are like variable bindings, in that they can hold any kind of Scheme value. Both bindings and fields are called value cells---i.e., they're places you can put any kind of value.

In most implementations, each heap-allocated object has a hidden "header" field that you, as a Scheme programmer, are not supposed to know about. This extra field holds type information, saying exactly what kind of heap allocated object it is. So, laid out in memory, the pair looks something like this:

        +-----------+
  header| <PAIR-ID> |
        +===========+
     car|     +-----+----->22
        +-----------+
     cdr|     +-----+----->15
        +-----------+

In this case, the car field of the pair (cons cell) holds the integer 22, and the cdr field holds the integer 15.

The values stored in the fields of the pair are drawn as arrows, because they are pointers to the numbers 22 and 15.

(The actual representation of these values might be a 30-bit binary number with a two-bit tag field used to distinguish integers from real pointers, but you don't have to worry about that.)

Scheme provides a built-in procedure car to get the value of the car field of a pair, and set-car! to set that field's value. Likewise there are functions cdr and set-cdr! to get and set the cdr field's values.

Suppose we have a top-level variable binding for the variable foo, and its value is a pointer to the above pair. We would draw that situation something like this:

                                       +---------+ 
              +---------+        header| <PAIR>  |
          foo |    *----+------------->+=========+
              +---------+           car|    *----+---->22
                                       +---------+
                                    cdr|    *----+---->15
                                       +---------+

Most other objects in Scheme are represented similarly. For example, a vector (one-dimensional array) is typically represented as a linear array of value cells, which can hold any kind of value.

Even objects that aren't actually represented like this can be thought of this way, since conceptually, everything's on the heap and referred to via a pointer.


Go to the first, previous, next, last section, table of contents.