[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

S&I's idea of EQ?



[We've had some trouble with our network phone lines to the East Coast,
so the following may seem out of date.]

I, too, am tired of moving targets and would like to have a stable
definition of Scheme, but I don't think Gerry should be unhappy with
what's going on because the consensus, at least as I perceive it, is
consistent with S&ICP and with the various existing implementations.
As I saw it, the result of the earlier EQ? discussion was a consensus that

    (1)  it is not an error for EQ? to be called with procedural arguments.
    (2)  EQ? as used in S&ICP ought to work.
    (3)  "splitting" was a no-no.
         (E.g. (let ((x (lambda () 0))) (eq? x x)) --> #!false is a no-no.)
    (4)  "coalescing" was ok.
         (E.g. (eq? (lambda () 0) (lambda () 0)) --> #!true is ok.)

These points are in decreasing order of consensus, and in particular
the consensus for (4) was not as strong as for (1) through (3).  Thus
(4) is still a major topic for discussion.

As I perceived it, Jonathan's poll was primarily intended to determine the
semantics of EQV?, and secondarily to determine the status of (4) above.
So far as I know, nothing in S&ICP will break if EQV? is made
implementation-independent, or if "coalescing" is permitted for EQ?.
Jonathan's insight is that although the semantics of EQ? is hopelessly
implementation-dependent (primarily because of numbers, and secondarily
because of coalescing if coalescing is allowed), it is still possible
to make EQV? implementation-independent even in the presence of coalescing.
The price to be paid is that it would be an error to call EQV? with
procedure arguments -- not "signal an error", but "be an error", so no
one would have to change their implementation.

If we don't allow coalescing for procedures and EQ?, then there is no price
at all.  That's why the issue of coalescing for procedures and EQ? is
inseparable from the semantics of EQV?.  So far as I can tell, however,
nothing being considered will break S&ICP or force anyone to change their
implementation.  If anyone can show me a truly useful piece of existing code
that will break if coalescing is allowed, I'd sure like to see it.

I would hate to have TWO forms for creating procedures.  Yes, I dearly wish
that procedure values did not have to be associated with pointers, just as
I dearly wish that numbers did not have to be associated with pointers,
but our earlier discussion convinced me that it is too late to fix either
problem.  (In Scheme, that is.  I think we can warn designers of new
languages not to make the same mistakes.)  What Yale, TI, and Tek want in
Scheme is not the utopia of pointer-free procedures, but sanction for
coalescing.

Why do we want coalescing?  It allows optimizing compilers to generate
more efficient code.  Examples have been given before, but some people
remain unconvinced so I will repeat one of them.  Consider the following
procedure:

    (define (foo x) (map (lambda (n) (+ n 3)) x))

If coalescing is not allowed, then a new closure must be created every
time foo is called, and any optimizing compiler that transforms the above
into

	(define foo
	  (let ((bar (lambda (n) (+ n 3))))
	    (lambda (x) (map bar x))))

is indisputably incorrect.  (Unless, of course, the compiler happens to
know the value of map and can prove that map will never be assigned, which
is pretty unlikely in practice.)  I think this sort of transformation ought
to be allowed in Scheme, because (1) it makes a fairly big difference in how
fast your programs run; (2) it has been allowed in Scheme historically, so
disallowing it would be a change in the language; for example, Guy Steele's
Rabbit compiler is based on such transformations; and (3) the opponents of
coalescing have yet to give any examples to show why coalescing is bad.

I didn't understand Jonathan's remark to the effect that Common Lisp
requires two different kinds of LAMBDA, one that associates a pointer
and another one that doesn't.  I also can't tell from CLtL whether
the optimization illustrated above is supposed to be legal in Common
Lisp.  (I assume it is supposed to be legal, but CLtL isn't precise
enough to give much guidance and there is no formal semantics for CL that
I can turn to for answers to such questions.)  At any rate, I hardly think
the designers of Common Lisp have devoted more thought to these issues than
we have, so I don't see why we should look to Common Lisp for guidance.

Thanks for hearing me out.  Peace, Will