[Haskell-cafe] Re: evaluation semantics of bind

[Lennart Augustsson]

Perhaps you meant the type correct expression
  return 7 >>= \ x -> return 42
which the compiler will probably optimize to return 42, because by
seeing the definition of return the compiler can see that it has no
effects in the monad.  This expression is very different from
  getChar >>= \ x -> return 42
Assuming getChar is some kind of primitive operation, the compiler
does not know that it has no effects, so it has to remain.

There's nothing special about IO in this respect.  If IO is
implemented as a state monad the compiler can just unfold the
definitions of return and >>= and do its usual job.  Some
subexpressions (like return 7) do not touch the RealWord state and can
be optimized away, some operations (like getChar) take and return a
RealWorld, so they cannot be removed.

  -- Lennart

On Thu, Feb 5, 2009 at 8:55 PM, Gregg Reynolds <dev at mobileink.com> wrote:
> 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
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>