[Haskell-cafe] evaluation semantics of bind

[Gregg Reynolds]

On Sun, Feb 8, 2009 at 6:25 PM, Richard O'Keefe <ok at cs.otago.ac.nz> wrote:

>
> On 6 Feb 2009, at 4:20 am, Gregg Reynolds wrote:
>
>>  However, consider:
>>
>>    getChar >>= \x -> getChar
>>
>> An optimizer can see that the result of the first getChar is discarded and
>> replace the entire expression with one getChar without changing the formal
>> semantics.
>>
>
> But the result of the first getChar is *NOT* discarded.
> **As an analogy**, think of the type IO t as (World -> (t,World))
> for some hidden type World, and
>        getChar w = (c, w')
>                -- get a character c out of world w somehow,
>                -- changing w to w' as you go
>        (f >>= g) w = let (v,w') = f w in (g v) w'
>
> In this analogy, you see that the result of getChar is a value of
> type IO Char (not of type Char), and that while the character
> part of the result of performing the result of getChar may be
> discarded, the "changed world" part is NOT.


That's an implementation detail.  It doesn't account for other possible IO
implementations.

My original question was motivated by the observation that a human reader of
an expression of the form "e >>= f" , on seeing that f is constant, may pull
the constant value out of f, disregard e and dispense with the application f
e.  So can a compiler, unless IO expressions are involved, in which case
such optimizations are forbidden.  I wondered if that was due to the
semantics of >>= or the semantics of IO.

To summarize what I've concluded thanks to the helpful people on
haskell-cafe:

The compiler can optimize e >>= f except for any IO expressions in e and f.
IO expressions must be evaluated, due to the semantics of IO.  The may not
be disregarded, memoized, or substituted.  IO semantics may be implemented
in different ways by different compilers; these implementation techniques
are not part of the formal semantics of the language, which may be expressed
as above:  IO expressions must be evaluated wherever and whenever they
occur.

The bind operator >>= enforces sequencing on arguments containing IO
expressions, but does not force evaluation.  Even bind expressions involving
IO may be optimized.  For example:

  getChar >>= \x -> ...<monster computation>... putChar 'c'

The compiler may discard <monster computation> (assuming it contains no IO
expressions), but it must evaluate getChar and putChar (due to IO semantics)
in the correct order (due to bind semantics).

Thanks all,

gregg
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090209/f72f89d8/attachment.htm