EQ? and procedures, numbers, etc

[Guy Steele <gls@THINK-AQUINAS.ARPA>]

KMP is right in identifying the question of object identity
as a key issue.  But there are two separate issues here:

(1) Are two evaluations, of the same LAMBDA-expression, that are
distinct in time permitted to produce objects that are not distinct as
determined by "EQ?"?  In simpler terms, may two things that you might
expect to be different turn out to be the same?  (Call this property
"coalescence".)

(2) Once a single object has been produced and named, is the
implementation allowed to duplicate it at will in such a way as to cause
two distinct references to its name to result in values that are
distinct to "EQ?"?  In simpler terms, may one thing turn out to be two
different things?  (Call this property "splitting".)

Now Common Lisp permits splitting for characters and numbers with
respect to "EQ" (but not with respect to "EQL").  It permits coalescing
for numbers, characters, and closures of lambda expressions.

I feel that splitting is a semantically bad thing to have in a LISP-like
language, because I think name-reference should be free of side effects!
It was introduced into Common Lisp only for the sake of certain
implementational efficiencies.  If one removes EQ from the language and
leaves only EQL, then there is no splitting.  I would have preferred for
EQ to have the current semantics of EQL, but it was too ingrained into
everyone's mind (including mine) that EQ means "compare the pointers",
which is an implementation notion rather than a language notion.

On the other hand, I feel that coalescing is a perfectly legitimate
optimization.  If two objects cannot be distinguished, then it should be
legitimate to merge them.  If there are no RPLACA or RPLACD operations
on CONS cells, then hash-consing is a legitimate optimization (and,
indeed, perhaps EQ should be required to behave as EQUAL on CONS cells
in the absence of such side effects!).  It is important to have some
means of generating distinct objects, but it is not clear that
lambda-expressions need to be that means.

It is not always legitimate to coalesce two closures, but frequently a
static analysis can determine that no distinguishing side effects are
possible and that therefore two closures would be operationally
identical.

In short, my feelings are: splitting, no: (EQ? X X) should always be true;
coalescing, maybe: it can be a legitimate optimization.

--Guy