Lazy evaluation and IO side effect confusion

Question

This code (taken from Learn You A Haskell):

main = do   putStr "Hey, "  
            putStr "I'm "  
            putStrLn "Andy!"  

apparently desugars to

main =        putStr "Hey, " >>=  
       (\_ -> putStr "I'm "  >>= 
       (\_ -> putStrLn "Andy!"))

Which, as I understand it can be interpretted as saying "In order to putStrLn "Andy!" I first need to putStr "I'm ", and in order to do that I first need to putStr "Hey, ";

I disagree with this interpretation, which is annoying because the compiler obviously doesn't and leaves me feeling confused. The problem I have with it is that the lambdas ignore their arguments, during lazy evaluation isn't this sort of thing supposed to be recognised and short-circuited?

Also, sure, the binding returns an IO action, and when that IO action falls into main it gets executed. But what's to stop it from printing "Hey, Andy!I'm "? I suspect it's whatever bind is doing.

Also, how does an IO action of type "IO ()" carry enough information to allow the runtime system to print "Hey, I'm Andy!"? How is that IO () different to an IO () than prints "Hello World!" or writes to a file?

Consider another, from the wikipedia page for monad:

Sugared version:

do
  putStrLn "What is your name?"
  name <- getLine
  putStrLn ("Nice to meet you, " ++ name ++ "!")

Desugared version:

putStrLn "What is your name?" >>= 
   (\_ ->
      getLine >>=
         (\name ->
            putStrLn ("Nice to meet you, " ++ name ++ "!")))

Similar story here.

I think I just need to see the definition of bind for IO and then it will be all clear. Something else that would help a lot is if someone could help me step through how the program actually gets evaluated and identify the exact moments when the side effects occur.

Protestantism

"The lambdas ignore their arguments, during lazy evaluation isn't this sort of thing supposed to be recognised and short-circuited?" You bet! The second argument to (>>=) is a particularly lazy function here, but the (>>=) function itself is not lazy. – Pinnatiped

Answer 1

Read the "Tackling the awkward squad" paper by Simon Peyton Jones.

For related questions, see

• What does "pure" mean in "pure functional language"? ,
• Is Haskell truly pure (is any language that deals with input and output outside the system)?
• In what sense is the IO Monad pure?
• Haskell: actual IO monad implementation, in different language?
• Why does Haskell not have an I Monad (for input only, unlike the IO monad)?
• References for learning the theory behind pure functional languages such as Haskell?

Take any such explanation including mine with a grain of salt - no hand-waving can replace a rigorous peer-reviewed paper, and the explanations are necessarily over-simplifications.

A very rough perspective is that >>= can be seen as a list constructor:

data IO = [Primitive] 

and IO subsystem deconstructs the value of main and consumes that list. I.e. main is just a list. So you may want to take a look at the definition of Haskell entry point above main, bind is rather uninteresting.

You can also read papers on history of haskell and look at earlier versions of IO subsystem for insight of what is going on.

Also look at C language is purely functional satiric post by Conal Elliott.

The definition of functional purity is non-trivial and I remember a paper elaborating on the definition, but I don't remember the title.

Lehmann

It's interesting that everyone always explains >>= on IO values by analogy. Doesn't it have a definition somewhere in the prelude? Why does no one ever quote it? Is bind over IO where the magic is happening? I'm reading the awkward squad paper right now and even SPJ shys away from actually defining bind – Protestantism

The IO type is abstract, so there's no one definition of >>= in the Haskell standard. Depending on how you implement IO you'll have different implementations of >>=. If you delve into ghc you'll find that IO is a state monad and >>= is simply bind for a state monad. (There's more magic inside the compiler to make this efficient.) – Gamopetalous

@ThelronKnuckle It is not an analogy on 'values'. It is an analogy on another implementation of pure IO using the old main :: [Request] -> [Response] idea. Also the most interesting part is not of the bind, but of the runIO for IO monad. As IO monad is abstract, we must either provide an abstract explanation as SPJ did, or use some implementation strategy as I did. – Lehmann

Answer 2

Looking at IO in a real Haskell implementation will probably confuse more than it enlightens. But think of IO as being defined like this (this assumes you know GADTs):

data IO a where
    Return a :: IO a
    Bind :: IO a -> (a -> IO b) -> IO b
    PutStr :: String -> IO ()
    GetLine :: IO String

instance Monad IO where
    return = Return
    (>>=) = Bind

putStr :: String -> IO ()
putStr = PutStr

getLine :: IO String
getLine = GetLine

So when you evaluate a program (of type IO ()) all it does is to build a data structure of type IO () that describes how the interaction with the world will happen once you execute it. You can then imagine the execution engine being written in, e.g., C, and there is where all effects happen.

So

main = do   putStr "Hey, "  
            putStr "I'm "  
            putStrLn "Andy!"  

is the same as

main = Bind (PutStr "Hey, ") (\ _ -> Bind (PutStr "I'm ") (\ _ -> PutStr "Andy!"))

And the sequencing of these comes from the way the execution engine works.

That said, I know of no Haskell implementation that actually does it this way. Real implementations tend to implement IO as a state monad with a token representing the real world being passed around (this is what guarantees sequencing), and primitives like putStr are just calls to C functions.

Gamopetalous

+1 for the GADT approach and the 'Looking at IO in a real Haskell implementation will probably confuse more than it enlightens' thing. – Lehmann

Answer 3

I think I just need to see the definition of bind for IO and then it will be all clear.

Yes, you should do that. It's actually quite easy, and if I remeber correctly it goes like

newtype IO = IO (RealWorld -> (a, RealWorld))

(IO f) >>= g = ioBind f g
    where
       ioBind :: (RealWorld -> (a, RealWorld)) -> (a -> IO b) -> RealWorld -> (b, RealWorld)
       ioBind f g rw = case f rw of
            (a, rw@RealWorld) -> case g a of
                IO b -> b rw

The "trick" is that every IO value is actually basically a function, but to evaluate it you would need a token of type RealWorld. There is only one instance that can supply such a value - the runtime system running main (and, of course, the function that must not be named).

Quixotic

Answer 4

I think this is more understandable if you think of the actions again as functions. Your binding example (do { foo <- getLine ; putStrLn foo ; }) is intuitively similar to the following function:

apply arg func = func (arg)

Except that the function is a transaction. So our call func(arg) is evaluated, if any only if (arg) completes successfully. Otherwise we fail in our action.

This is different from ordinary functions because then Haskell really doesn't care if (arg) computes fully or at all, until the point it needs a bit of func(arg) to continue the program.

Wide

Answer 5

I think I just need to see the definition of bind for IO and then it will be all clear.

 -- ghc-8.6.5/libraries/base/GHC/Base.hs; line 1381
bindIO :: IO a -> (a -> IO b) -> IO b
bindIO (IO m) k = IO (\ s -> case m s of (# new_s, a #) -> unIO (k a) new_s)

 -- ghc-8.6.5/libraries/base/GHC/Base.hs; line 1387
unIO :: IO a -> (State# RealWorld -> (# State# RealWorld, a #))
unIO (IO a) = a

The IO type is declared in a separate module:

 -- ghc-8.6.5/libraries/ghc-prim/GHC/Types.hs; line 169
newtype IO a = IO (State# RealWorld -> (# State# RealWorld, a #))

(More examples of IO and the bind operator can be found in How to Declare an Imperative by Philip Wadler.)

---

Something else that would help a lot is if someone could help me step through how the program actually gets evaluated and identify the exact moments when the side effects occur.

Let's rewrite bindIO:

• using let-expressions and bang-patterns instead of case:

• to extract the action from its first parameter using unIO:

  bindIO :: IO a -> (a -> IO b) -> IO b
  bindIO m k = IO (\ s -> let !(# new_s, a #) = unIO m s in unIO (k a) new_s)
  

Now for your expanded version of that Learn You A Haskell example:

main =        putStr "Hey, " >>=  
       (\_ -> putStr "I'm "  >>= 
       (\_ -> putStrLn "Andy!"))

1. Replace (>>=) with bindIO, switching to prefix-notation along the way:

   main = bindIO (putStr "Hey, ")
                 (\_ -> bindIO (putStr "I'm ")
                               (\_ -> putStrLn "Andy!"))
   

2. Now for the finicky part - expanding all the calls to bindIO; all going well, the program would eventually resemble:

   main = IO (\s0 -> let !(# s1, _ #) = unIO (putStr "Hey, ") s0 in
                     let !(# s2, _ #) = unIO (putStr "I'm ") s1 in
                     unIO (putStrLn "Andy!") s2)
   

3. One other change - it's optional, but it helps to clarify what's going on here:

   main = IO (\s0 -> let !(# s1, _ #)  = unIO (putStr "Hey, ") s0 in
                     let !(# s2, _ #)  = unIO (putStr "I'm ") s1 in
                     let !(# s3, a3 #) = unIO (putStrLn "Andy!") s2) in
                     (# s3, a3 #))
   

   • Which, as I understand it can be interpreted as saying: In order to putStrLn "Andy!" I first need to putStr "I'm ", and in order to do that I first need to putStr "Hey, ".

   Correct: because of how s0, s1, s2 and s3 are being used (once) in the program, which establishes an order of evaluation. That ordering allows putStr and putStrLn to use effects directly to print out their respective arguments.

So, unlike e.g. Standard ML (which uses syntactic ordering), Haskell relies on data dependencies to ensure I/O happens in the required order - the do-notation is merely a convenience.

---

The problem I have with it is that the lambdas ignore their arguments, during lazy evaluation - isn't this sort of thing supposed to be recognised and short-circuited?

If we also "over-expand" your other example:

  IO (\ s0 -> let !(# s1, _ #)    = unIO (putStrLn "What is your name?") s0 in
              let !(# s2, name #) = unIO getLine s1 in
              let !(# s3, a3 #)   = unIO (putStrLn ("Nice to meet you, " ++ name ++ "!")) s2 in
              (# s3, a3 #))

we can clearly see in both that what's actually being ignored are outputs - namely () :: () from using putStr and putStrLn - but not states, which maintain ordering.

---

How does an IO action of type IO () carry enough information to allow the runtime system to print "Hey, I'm Andy!" - how is that IO () different to an IO () that prints "Hello World!" or writes to a file?

The same way (+), (-) and (*) are treated differently, even though they have the same type (Num a => a -> a -> a) - by having different names.

Backswept