[Scheme-reports] Procedural equivalence: the last debate

[will@x]

The following proposal combines all the advantages of both the
R5RS and R6RS semantics, while avoiding all the disadvantages
mentioned by John Cowan for either R5RS or R6RS semantics.
This proposal would also enable boxing/unboxing optimizations
that John Cowan didn't mention because they aren't feasible
with either the R5RS or R6RS semantics.

Proposal:

1.  Retain the notion of location tags for procedures, which
are allocated and attached to procedures when lambda expressions
are evaluated.

2.  Require eqv? to return #t when its arguments are procedures
that have the same location tag.

3.  Require eqv? to return #f when its arguments are procedures
that would behave differently for some arguments.

4.  Require eq? to return #f on procedure arguments unless eqv?
returns #t on those same arguments.

5.  Allow eq? to return #f on procedure arguments regardless of
what eqv? returns on those same arguments.

Notes on proposal:

Parts 1 through 4 of the proposal are consistent with the R5RS
semantics, including the (let ((p (lambda (x) x))) (eqv? p p))
example.

Any implementation that conforms to the R5RS requirements would
conform to all requirements of this proposal as well.  As I'll
explain below, I also believe that any implementation that
satisfies the requirements of this proposal would also conform
to the requirements of the R5RS *except* possibly for the two
examples noted below.

Although part 5 would allow eq? to return #f whenever both of
its arguments are procedures, just as eq? may return #f whenever
both of its arguments are numbers or characters, implementing
eq? as a simple pointer comparison would satisfy all requirements
of this proposal, so that would remain the most popular technique
for implementing eq?.

Although John Cowan has claimed otherwise, I believe part 5 is
also consistent with the R4RS/R5RS/IEEE semantics of eq? and
eqv? (modulo two examples).  Here's what John Cowan wrote:

    In all reports, `eq?` is the same as `eqv?` except on numbers
    and characters.

I don't know how John Cowan inferred that eq? and eqv? behave
exactly the same on procedures in R4RS/R5RS/IEEE Scheme.  The
description of eq? given in IEEE Std 1178 omits procedures from
the list of things on which eq? and eqv? are required to behave
the same, just as it omits procedures from the list of things
on which eq? and eqv? may behave differently.

IEEE Std 1178 offers the following rationale for eq? and its
behavior:

    Rationale:  It will usually be possible to implement eq?
    much more efficiently than eqv?, for example, as a simple
    pointer comparison instead of as some more complicated
    operation....Eq? may be used like eqv? in applications
    using procedures to implement objects with state since
    it obeys the same constraints as eqv?.

Note that "obeys the same constraints as eqv?" is not the same
as "behaves the same as eqv?".

I may be missing something, but I suspect that the widespread
belief that the R5RS requires eq? and eqv? to behave the same
is based at least in part on the following examples given for
eq?:

    (eq? car car)                ==>  #t
    (let ((p (lambda (x) x)))
      (eq? p p))                 ==>  #t

Note, however, that those two examples do not actually require
eq? and eqv? to behave the same whenever their arguments are
procedures.  My proposal would relax both of these examples to
allow them to evaluate to either #t or #f.

The R6RS definitely requires eq? and eqv? to behave the same
on procedure arguments, but I regard this requirement as a
mistake and would like to see it rectified in the R7RS.  I
regard the two examples above (from R5RS) as less damaging
versions of essentially the same mistake, and would like to
see them fixed in the R7RS.

The benefit of my proposal is that it combines the advantages
John Cowan listed for the R5RS and R6RS semantics, while adding
the boxing/unboxing flexibility the R6RS semantics was intended
to provide but didn't.  (The R6RS required eq? to behave the
same as eqv? on procedures, which created a conflict between
boxing/unboxing optimizations and implementation of eq? as a
fast pointer comparison.)

The *only* disadvantage of my proposal is that programmers who
want to realize the advantages of the R5RS semantics as listed
originally by Alex Shinn and repeated by John Cowan would have
to be careful to use eqv? when comparing procedures instead of
using eq?.

On my reading of the R5RS, programmers are already required to
use eqv? instead of eq? in order to realize those advantages,
so it's questionable whether this disadvantage is real at all.

I have already explained this proposal to G J Sussman, who
said he would be okay with it.  He may express a different or
more detailed opinion if he joins this discussion, and I hope
he does.

Will

_______________________________________________
Scheme-reports mailing list
Scheme-reports@x
http://lists.scheme-reports.org/cgi-bin/mailman/listinfo/scheme-reports