Thank you Gerald, your praise means a lot!
Regarding your concern about eqv? I agree wholeheartedly.
I know that you (as well as Andy and the others discussing this),
understand the issues perfectly well, but there's a lot of
abbreviation and references so I'd like to take this chance to explain
what this is all about for others (and for myself because I keep
forgetting) in simple terms before suggesting what we can do about it.
This is a change from R5RS made in R6RS and retained in the 9th R7RS
draft, which is to make the equivalence of procedures unspecified,
i.e. to remove the clause
(let ((p (lambda (x) x)))
(eqv? p p)) ==> #t
or as in R6RS/R7RS to specifically mark it unspecified for clarity:
(let ((p (lambda (x) x)))
(eqv? p p)) ==> <unspecified>
This looks extremely unintuitive and is in no way of use to
programmers. Rather, the motivation lies in opportunities it opens
for compiler writers.
The terms thrown around here are the lambda calculus operations "beta
reduction" and "eta conversion."[1] Beta reduction just means function
application by substituting the actual parameters in the function
body, for example given
((lambda (x) (* x x)) 2)
or equivalently
(let ((x 2)) (* x x))
the beta reduction is
(* 2 2)
An even simpler way of stating this is that it's "inlining."
Compilers can and do perform such inlining when they can prove it
doesn't change the meaning of the program, which is not always because
unlike lambda calculus Scheme has state and object identity.
The above example is safe for a variety of reasons but most notably
because it's inlining a constant value. Another case is that it's
safe to inline a referentially transparent (side-effect-free,
including all lambdas) let-bound value which is only referenced once.
Also, it's always safe to inline a local, non-mutated lambda in
operator position.
So a lot of the transformations here involve lambdas, i.e. local
procedure inlining.[2] The example Will Clinger gives in his post to
the r6rs-discuss is the following admittedly contrived code:
(define (f m n)
(define (g i)
(define (h j)
(if (= j 0)
#t
(g (- j 1))))
(if (= i 0)
(if (= i m)
(list h) ; closure must be allocated here
#f)
(h (- i 1))))
(g n))
To fill in the blanks, the issue is whether or not h can be inlined,
which determines whether or not a closure for h must be allocated on
entry to g. Now, this is actually a bad example as Andy points out,
because the second call to h can always be inlined because its in an
operator position.[3] Once you've removed the second call to h,
there's only one call left so it's also safe to inline. You would
need two non-operator references, where both might or might not be
called to h as in:
(define (f m n)
(define (g i)
(define (h j)
(if (= j 0)
#t
(g (- j 1))))
(when (= i n)
(debug h))
(if (= i 0)
(if (= i m)
(list h)
#f)
(h (- i 1))))
(g n))
So now under R5RS even though we can inline the operator call to h we
can't get rid of both the (debug h) and (list h), because the former
may store the value somewhere which may later be compared with the
result returned by list.
However, and this is the whole point of the change, if procedure
identity is not guaranteed we can just make this substitution anyway,
and the closure goes away!
[Note instead of a new substitution rule, you can view this as first
making an eta conversion, which just means interchanging f with
(lambda (x) (f x)), by converting the non-operator h references to
(lambda (x) (h x)). This becomes perfectly legal once we remove
procedure identity, and after this conversion all h's are in operator
position and can be inlined.]
Now this has gotten very contrived, but what the original code does a
good job of is to serve as a minimal example of optimization case,
where there's no real work being done, so it gives a rough upper bound
on the gains to be achieved. In this case, according to Clinger's
benchmark it was about twice as fast.
To consider a more realistic argument, one could consider something
like the reference implementation of map which has a fast-path call to
the proc in operator position and another reference as a first-class
argument to apply.
All of this is the weak form of the argument in favor of the change.
I don't want to argue against a straw man so I will restate the strong
form of the argument which no one has seemed to express.
What this is really about is the programmer's right to freely build
higher order abstractions without fear that it will ever slow down
your program. Without making such guarantees you actually encourage
programmers to perform manual inlining and avoid higher-order
procedures, resulting in uglier code.
The caveat is that in practice you may not only see much less benefit,
it could even be a pessimization. Specifically because it breaks
memoization you could end up recomputing the same value for an
arbitrarily large slowdown.
The counter argument is not this caveat, nor the fact that smart
compilers can already optimize the common cases (and in the case of
Stalin all cases). The counter argument is that it's not worth it, at
any cost. It's not the job of the language to specify surprising and
confusing semantics to the programmer to make life easier for the
compiler writer.
Specifically, in this case it the result is that procedures are no
longer first class. They cannot be used as light-weight objects, they
cannot be memoized, they cannot be reasoned about. One of the
crowning enlightenments of Scheme, the realization of the Actor model
through closures, can no longer be achieved as the Actors are found to
be imposters!
****
These are both powerful arguments, and unfortunately people tend to
identify themselves as "for performance" or "for expressivity" and not
budge easily. If I could go back I'd re-argue my case and point out
that they are both the wrong arguments.
This got strong consideration to begin with because R6RS introduced
it, but this was an innovation on R6RS's part. No existing
implementations performed this optimization (because it was not
allowed), and it's not the job of the standard to prescribe new
changes which break existing code in the hopes that compilers might
become a little faster. It's the job of the compiler writers who
really care about this to provide declarations and extensions for
their users to opt-in to such optimizations, as they do for other
unsafe optimizations. When and if the optimization has proved its
worth in real-world Scheme code and been widely implemented can it be
brought up for standards consideration.
Unfortunately, we've passed the formal comments period and people have
already started voting on ratification - changing anything now would
be unfair and confusing. Short of some huge gesture like a reversal
of all WG1 members who voted in favor of this, and general support of
the community, I can't change this now no matter how much (or rather
because of how much) I'd like to.
The good thing is that no R5RS implementation performs this
optimization, and we can discourage them from doing so, and hopefully
reverse the decision in R8RS.
--
Alex
[1] Note there was mention of a car vs. primitive-car distinction
earlier, please disregard that. Open-coding primitives without
breaking eqv? is old hat and already done by most R5RS compilers.
[2] Global procedure inlining can also be useful but is unrelated to
the motivation of this change because global procedure references
don't generate closures.
[3] Barring some sort of stack introspection which is outside the
scope of the standard.