[r6rs-discuss] [Formal] Remove double phase semantics

From: dyb_at_cs.indiana.edu <dyb>
Date: Sun Nov 26 13:49:07 2006

[I'm responding as a user/developer rather than as an editor.]

> It has been pointed out to me that the fact that foo-f is local may inhibit
> some optimizations that are directly possible in the shared-binding model.

Having done the pointing out, I feel I should clarify. The obvious
problem with Andre's transformation is that it introduces additional local
variables and indirects, so the claim that the multi-phase model can be
implemented as efficiently as the single-phase model is wrong. A more
subtle and potentially more costly problem is that it will cause closures
to become larger and/or more deeply nested (with more indirects).
Furthemore, it will also inhibit closure elimination, and optimization
that Chez Scheme and possibly some other systems do. For example, in:

   (letrec ([even? (lambda (x) (or (= x 0) (odd? (- x 1))))]
            [odd? (lambda (x) (and (not (= x 1)) (even? (- x 1))))])
     ---)

each procedure has only the other as a free variable---if - and = are
top-level (global) references whose locations can be embedded in the code
stream. Thus, each needs its closure only to access the closure of the
other, so neither is really needed. Once the closure is eliminated, we
have what amounts to C code with no overhead for closure creation, passing
of closures among procedures, or indirects to obtain the closure to pass.

In Andre's model, - and = would become free lexical variables, and the
optimization would be defeated.

> However, in the most common case where f does not mutate any free variables, or
> refer to any procedure that does, the first encoding can be simplified to the
> second.

For the simplification to take place, f cannot even reference a mutable
variable or call a procedure that either mutates or references a mutable
variable. I'm not certain that this is the common case for all or even
most of the libraries that people are going to write. I'm not sure if
it's even true for most primitives. Consider - and =, used in the example
above. Both can end up calling raise in certain circumstances, and raise
probably references a mutable variable holding the current exception
handler. Thus neither - nor = would be subject to the simplification.

Even if it were true for most exported variables, all it takes is one
reference to one variable that does access mutable state, directly or
indirectly, in one of a group of mutually recursive procedures to inhibit
the closure-elimination optimization for all of them.

> Whether compiler writers wish to spend time on this optimization is a
> separate question, though.

Yes, it is. One of the goals of the library subsystem is to support the
generation of efficient code. I consider increasing the size and/or
nesting of closures and inhibiting useful optimizations that are already
performed in practice poor support indeed. Even if your claim that the
overhead can be eliminated in most cases turns out to be true, a developer
has only so much time to spend on optimizations and can add only so much
complexity to a compiler before it becomes unwieldy or inefficient. If we
have to spend time trying to overcome hurdles placed in front of us by the
library system, the end result will necessarily be less efficient code.

Kent
Received on Sun Nov 26 2006 - 13:48:32 UTC