Re: [Scheme-reports] Procedural equivalence: the last debate

[will@x]

John Cowan quoting me:

> > Although some people have suggested that implementations must
> > actually allocate a fresh location every time the lambda is
> > evaluated, they're wrong.
> 
> I don't see how this claim can be made consistent with the plain language
> of R5RS 4.1.4:  "Each procedure created as the result of evaluating a
> lambda expression is (conceptually) tagged with a storage location",
> unless we are to understand that these location tags need not be distinct.

The (conceptual) location tags are certainly distinct.  If you
thought I was arguing otherwise, I wasn't clear.

What I was saying is that the location tags are conceptual, and
need not correspond to allocating actual locations within an
implementation, and do not prevent implementations from merging
procedures that differ only in their (conceptual) location tags.
I believe that was Shiro's concern, and I was trying to reassure
him.

The plain language of the R3RS/R4RS/R5RS/IEEE rationale for eqv?
also says "implementations are free either to detect or to fail
to detect that two procedures or two literals are equivalent to
each other, and can decide whether or not to merge representations
of equivalent objects by using the same pointer or bit pattern to
represent both."  There is also this example:

    (eqv? (lambda (x) x) (lambda (y) y))  ==>  unspecified

which shows that the (conceptually) distinct location tags of the
two lambda expressions in that example aren't intended to prevent
implementations from merging their results into a single procedure.

> Well, I suppose this means that `eq?` is inlined and `eqv?` is not.

Yes.  Of course, the whole purpose of eq? is to provide a slightly
broken but still useful version of eqv? whose code is small enough
to inline.

> However, a system that breaks down `eqv?` into an inlined `eq?` test
> followed, if the test fails, by an inlined type test and a fallback
> to a non-inlined version of `eqv?` that handles the outside cases
> would presumably show a much smaller difference.

In Larceny/IA32, inlining the type tests for only the most common
safe cases (symbols, booleans, the empty list, pairs) would require
at least 11 machine instructions in addition to the 4 instructions for
a fast call to eqv?.  To justify inlining the type test, you'd have
to argue that the cost of increased instruction cache misses is less
than the benefit of the inlining.

Looking at Larceny's code for eqv? tells me it isn't as fast as it
should be, so the quick-and-dirty benchmark I wrote will probably
show less of a difference in other systems.  The slower the system,
the smaller the relative difference is likely to be.

Will

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