[r6rs-discuss] [Formal] Disallow redefinitions macros/variables

From: Andre van Tonder <andre>
Date: Tue Mar 27 15:20:46 2007

On Mon, 26 Mar 2007, Abdulaziz Ghuloum wrote:

> On Mar 26, 2007, at 3:03 PM, AndrevanTonder wrote:
>
>> - I suspect that it may make certain optimizations
>> (such as detecting possibilities for inlining or direct
>> substitution) more difficult.
>

> I don't see how outlawing multiple returns gains you anything as far as
> optimizations are concerned.

Here is an example: Assume the following snippet occurs in a higher-order
procedure, of which f, g, h, and v are unknown parameters. With
the proposed single-assignment restriction, this:

  (let ()
    (define x (f))
    (define y (g x))
    (define c y)
    (define z (h x))
    (define a y)
    (define b (v x))
    (write (list (* y y y y y y y) a c)) (newline)
    (b 3)
    (write (list (* y y y y y y y) a c)) (newline))

is always equivalent to, and can be optimized to:

  (let ()
    (define x (f))
    (define y (g x))
    (define z (h x))
    (define b (v x))
    (let ((common (* y y y y y y y)))
      (write (list common y y)) (newline)
      (b 3)
      (write (list common y y)) (newline)))

by simple copy propagation and common subexpression elimination
based on immutability of y. I suspect that immutability could
also improve register allocation decisions.

With the current draft, however, both the copy propagation and the
mutability analysis would become invalid, as can be see by taking

  (define (f) (call/cc (lambda (k) (list 0 k values))))
  (define g car)
  (define (h x) ((caddr x) #f))
  (define (v x)
    (lambda (v)
      (call/cc (lambda (k) ((cadr x) (list v (cadr x) k))))))

and observing the differences.

> 1. the compiler has to insert additional runtime checks in order to stop you
> from returning twice (which you almost always never do in practice). So,
> you end up paying for a useless feature.

Not if the requirement is "should" or "may", instead of "must".
It would not be the only "should" affecting an aspect of the semantics of
internal definitions - in chapter 8, "must" is used to decribe
the programmer's responsibility, while "should" is used to decribe the
implementation's responsibility, for detecting when "A definition in the
sequence of forms must not define any identifier ...." (and that is not
even runtime, where efficiency would provide a better excuse for
using "should").

In any case, implementing such a "should" should require a single extra
runtime comparison per DEFINE if we translate the latter to something like
SET!-IF-UNDEFINED with the obvious semantics. It does not seem as if
this would often matter in comparison to time taken on typical
right-hand-sides, but I am not pretending to any competency in efficiency
issues, so feel free to correct me...

Cheers
Andre
Received on Tue Mar 27 2007 - 15:20:09 UTC