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

Most Implementations Optimize Away Many Pointers

You might think that making every value a pointer to an object would be expensive, because you'd have to have space for all of the pointers as well as the things they point to, and you'd have to use extra instructions to access things via pointers.

Everything's a pointer at the language level--i.e., from the programmer's point of view--but a Scheme system doesn't actually have to represent things the way they appear at the languages level.

Most Scheme implementations optimize away a lot of pointers. For example, it's inefficient to actually represent integer values as pointers to integer objects on the heap. Scheme implementations therefore use tricks to represent integers without really using pointers. (Again, keep in mind that this is just an implementation trick that's hidden from the programmer. Integer values have the semantics of pointers, even if they're represented differently from other things.)

Rather than putting integer values on the heap, and then passing around pointers to them, most implementations put the actual integer bit pattern directly into variables--after all, a reasonable-sized integer will fit in a machine word.

A short value (like a normal integer) stored directly into a variable is called an immediate value, in contrast to pointers which are used to refer to objects indirectly.

The problem with putting integers or other short values into variables is that Scheme has to tell them apart from each other, and from pointers which might have the same bit patterns.

The solution to this is tagging. The value in each variable actually has a few bits devoted to a type tag which says what kind of thing it is--e.g., whether it's a pointer or not. The use of a few bits for a tag slightly reduces the amount of storage available for the actual value, but as we'll see next, that usually isn't a problem.

It might seem that storing integer bit patterns directly in variables would break the abstraction that Scheme is supposed to present--the illusion that all values are pointers to objects on the heap. That's not so, though, because the language enforces restrictions that keep programmers from seeing the difference.

In the case of numbers and a few other types, you can't change the state of the object itself. There's no way to side-effect an integer object and make it behave differently. We say that integers are immutable, i.e., you can't mutate (change) them.

If integers were actually allocated on the heap and referred to via pointers, and if you could change the integer's value, then that change would be visible through other pointers to the integer.

(That doesn't mean that a variable's value can't be one integer at one time, and another integer at another--the variable's value is really a pointer to an integer, not the integer itself, and you're really just replacing a pointer to one integer with a pointer to another integer.)


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