[plt-scheme] to define, or to let

From: Bradd W. Szonye (bradd+plt at szonye.com)
Date: Mon Mar 22 18:41:32 EST 2004

Bradd W. Szonye wrote:
>> Note that a compiler *cannot* reorganize code with side effects if
>> you specify left-to-right evaluation. It cannot even reorganize
>> CONSes, because the compiler cannot determine whether it's safe to
>> move allocations.

Matthias Felleisen wrote:
> This is of course complete nonsense. Sorry but I have no other words 
> for that.
> 
> A language comes with an observational equivalence relation, which the 
> evaluator and the language syntax define. If two statements are 
> interchangeable and the compiler can prove it, then it can exchange the 
> two. Period ....

Mea culpa; I made too strong a claim.

That said, I don't see how a compiler can prove whether it's safe to
switch two CONSes. For example, consider

    (f1 (f2 memory-hog-expr cheap-expr) memory-hog-expr)

where the "memory hog" subexpressions require working storage close to
the limit of available memory, and where f2 releases most of the
storage. This expression is safe if executed as written but will fail if
you evaluate the arguments to f1 in reverse order.

Now, if a programmer can prove that they're safe, then theoretically so
can a compiler or a static analysis tool. However, I don't think it's
even remotely practical to find this with a general-purpose analyzer, so
compilers must choose between "can't move CONSes" or "some optimizations
are unsafe." There may be a reasonable middle ground, but I expect that
most implementors would just write off the problem as unsolveable.
-- 
Bradd W. Szonye
http://www.szonye.com/bradd


Posted on the users mailing list.