There was a problem when proofreading this page.

Steele and Sussman


The Art of the Interpreter

same arguments produces the same result, since the bindings of X and Y will make copies anyway. We may, however, consider this variant:

       (CAR (CONS 'A '(B C))))

Puzzle #2a

Here we have simply substituted the expressions (cons 'A '(B C)) for the occurrences of X and Y. If CONS always returns the same object for the same inputs, then Puzzle #2 and Puzzle #2a have different answers if bindings copy, but may have the same answers if bindings do not copy (they may not have the same answer if CONS notices that we have pulled the rug out from under it and produces a new version because the old one was changed!). There is also in quibble as to whether the passing of an argument to RPLACA in itself constitutes a binding — if so, RPLACA must be completely ineffectual, because it always receives a copy! We must then regard RPLACA as a built-in system primitive; the user would have no way to define such a thing. This would be most unfortunate.

We have examined many of the design decisions for the meaning of RPLACA, CONS, and equality. If side effects are to be usable at all, the references to things denoted by variables must not make copies of those things. If the user is to be able to write procedures which produce lasting side effects on their arguments (as system-supplied primitive operators do), then there must be a variable binding mechanism which does not make copies. (LISP's binding mechanism in fact does not copy. Algol 60's call-by-value mechanism does copy structured data, but its call-by-name mechanism does not; we will study this in Part Three.) If the variable binding (or assignment) mechanism does not make copies, then CONS must generate a new, distinct object on each call.

The reader may have noted that we have been talking in circles for the last several paragraphs: in attempting to elucidate the meaning of sameness, we have discussed side effects, and in so doing used to word "same" nearly every other sentence. The point is that it is not possible to define them separately; The meanings of "equality" and "side effect" simultaneously constrain each other. With this in mind, we will investigate the choice of a primitive equality predicate.

The equality predicate we choose should be sufficiently finely grained to distinguish any two objects which have potentially distinct behavior, yet should not be so finely grained as to distinguish entities which otherwise would have the same behavior. Thus we have two desiderata:

[1] Two objects which are observed to behave differently must not be equal.
[2] Conversely, we would like two objects which are adjudged unequal to exhibit differing behaviors under suitable circumstances.