[Haskell-cafe] Re: evaluation semantics of bind

[Gregg Reynolds]

On Thu, Feb 5, 2009 at 11:22 AM, Gleb Alexeyev <gleb.alexeev at gmail.com> wrote:
> Gregg Reynolds wrote:
>
>> Are you saying that using equations to add a level of indirection
>> prevents optimization?  I still don't see it - discarding x doesn't
>> change the semantics, so a good compiler /should/ do this.  How is
>> this different from optimizing out application of a constant function?
>>
>
> Perhaps my example doesn't work, so I'll try another example.
> As you know, (>>=) is just an (overloaded) higher-order function.
> Let's consider another higher-order function, map. The expression
>> map (\x -> 42) [1..3]
> evaluates to [42, 42, 42].
> As you can see, the function (\x -> 42) passed to map ignores its first
> argument. Would you expect the compiler to discard the call to map?

No, but I might expect it to discard the function application and just
replace each element of the list with 42.  Which it may do at compile
time.  Plus, it will only be evaluated once, no matter how many times
the expression occurs, since lazy evaluation memoizes results.
>
> Can you see the analogy? The shapes of the two expressions, map (\x -> 42)
> [1..3] and (>>=) getChar (\x -> getChar) are similar.
>
> (>>=) is a combinator just like map, you cannot optimize it away in general.

Ok, I see what you're getting at, but I have to think about it some more.

Here's a restatement that might make my puzzlement more clear.  Suppose we have

   f = \x -> 42

Then I would expect the compiler to replace each expression of the
form f x with 42, for all x.

Now suppose we write  7 >>= \x -> 42.  It seems to me that a compiler
could examine that expression, conclude that it is constant, and
replace it with the expression 42.  So far as I know, there's nothing
in the semantics of Haskell to forbid this, so why not do it?  There
are no side effects, and an optimizer can always substitute equals for
equals, no?  (Let's disregard the fact that such optimizations may be
hard or expensive.)

This is different from map, because unlike map it doesn't need to
perform a computation (i.e. execute the function) to arrive at the
final value; it only has to analyze the function (which is computation
but not computation of the function itself.)

Now getChar is a value of type IO Char, by definition.  That means
mathematical value - "an action that does some IO" won't cut it in a
formal semantics, since there is no way to express "does some IO"
formally.  Values is values; they don't "do" anything.  So we should
be able to replace 7 and 42 above by getChar, and do the same
optimization.

Do you see why this is problematic for me?  In any case, you're
responses (and the others) have been quite useful and have helped me
work through some problems with a rather radical idea I have to
address this that I hope to write up this weekend.

Thanks,

gregg