[Haskell-cafe] evaluation semantics of bind

[Lennart Augustsson]

Just to clarify a little.
If you implement the IO monad in a sane way (as some kind of state
monad or continuation monad) then the compiler can optimize e>>=f even
for the IO monad.  The implementation of >>= will ensure the
sequencing of effects in e before effects in f.
The IO monad is less magic than you seem to think it is. :)

  -- Lennart

2009/2/9 Gregg Reynolds <dev at mobileink.com>:
> 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
>
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
>