Happstack and Streaming: Part 2: Lazy IO

Two Haskell features complicate our attempt at streaming data from Happstack: lazy evaluation, and its handling of IO.

Laziness

Unlike more mainstream languages, Haskell evaluates expressions lazily; it doesn’t actually compute the value until it’s actually used. This has some interesting benefits. For example, it’s quite easy to create infinitely long lists without requiring infinite amounts of memory. For example, the expression [1 ..] is a list of all positive integers. Haskell code can pass that infinite list around like any other value, and as long as we don’t do something that requires actually trying to evaluate the entire list (such as trying to compute its length), we’re perfectly safe.

We can even do computations where we create multiple infinitely long lists and do operations on the entire thing, as long as we never try to use the entire result. For example, here we take the aforementioned infinitely long list, split it up into evens and odds, add the two infinitely long lists pairwise, and look for the first element greater than 5,000:

foo :: Integer
foo = head greaterThan5000
    where greaterThan5000 = filter (> 5000) sums
          sums            = zipWith (+) odds evens
          odds            = filter odd positives
          evens           = filter even positives
          positives       = [1 ..]

The five lists defined in the where clause above are all infinitely long, but that’s OK because the program never needs to evaluate more than a finite part of any of them to compute the value of foo. (For the record, it’s 5003.)

So, problem solved, right? The application server just needs to give Happstack a ByteString, which after all is just a compacted list of Word8s or Chars, and that list can evaluate to the data we eventually want to send to the browser, once we figure out in the future what it needs to be.

Sadly, it’s not that easy; you’re forgetting another key property of Haskell that lets lazy evaluation work.

Pure Functional IO

Lazy evaluation works because Haskell is a purely functional language: expressions do not have side effects. As a result, functions in Haskell are much like functions in mathematics: their output is entirely determined by their input parameters, and their only result is producing a new value. Haskell functions can’t reference any values whose value might change, since values in a Haskell program never change. This is why lazy evaluation works: it doesn’t matter when the program gets around to evaluating an expression, if ever, since its result will always be exactly the same.

However, this seems to prevent a Haskell program from interacting with the outside world, since the system running a Haskell program, much like the rest of the universe, is not purely functional. Any operation that interacts with the world outside the Haskell program could be affected by whatever happens to be going on at the time the operation is run.

As a simple example, consider the time() function in C programming on Linux. time() returns the current time on the system, and will obviously return a different result depending on what time it is when it gets called. Reading from a file is similar; the result returned will depend on what’s stored in the file at the time it’s read, which could change if something else writes to the file.

Interaction with the outside world is needed for a program to do anything useful, so how does Haskell get around this? Via a bit of trickery known as the IO monad. Monads can be a bit tricky to get your head around initially, but basically they’re just a way to sequence operations, with the monad doing something to take the output on one operation and give it as input to the next. The particular monad being used gets to decide what “sequencing operations” means, as though you could redefine what the semicolon means in C. Although most monads have a way to both put values into and take values out of a monad, the IO monad only lets you put values in. Although you can also run a function on the value inside the IO monad, the result will itself also be in the IO monad. There is no escape from the IO monad.

What’s the point? Conceptually, the IO monad is just another type of state monad, which carries another value (the state) from one operation to the next. In the IO monad’s case, that state is merely the state of the entire universe outside the Haskell program. Anything needing to interact with the outside world runs inside the IO monad, which as a result orders those operations into a particular sequence.

What does this have to do with anything? Recall from earlier that our use case is streaming the current state of an interactive game as it changes over time in response to input from the players over a network. That input-over-a-network is IO and thus runs inside the IO monad, and thus too must anything that uses the result. So really, our hypothetical function that creates the data to stream back to the browser doesn’t — can’t — just return a result of type ByteString. No, it has to return a result of type IO ByteString.

The good news is, the function the application server implements for Happstack to create a Response runs in the IO monad, so this is legal. The bad news is that the IO monad truly sequences operations: the entirety of our hypothetical result-creating function has to execute before the result can be given to Happstack to send it to the browser. Either the result-creating function returns right away, and thus can never see the result of other players’ actions later, or it waits until those are handled, and can’t return anything until the game is over.

It seems that the rules of the IO monad prevent us from making this work.

Screw the rules, I have money lazy IO!

Lazy IO

Lazy IO lets a program bend the rules of lazy evaluation and IO sequencing a bit. For example, consider the readFile function in the Haskell standard library, whose type is the following:

readFile :: FilePath -> IO String

Superficially, this seems to read the entire file in memory before returning, per the rules of the IO monad. Which would make the following program extremely ill-advised:

import Data.Char (ord)
 
main :: IO ()
main = do zeroes <- readFile "/dev/zero"
          print . take 20 $ map ord zeroes

It reads in the contents of the file /dev/zero, converts the characters to their Unicode code point values, and prints the first 20 of them. However, on any Unix-ish system, /dev/zero is a file that contains an infinite number of zero bytes. A program can read from it as long as it wants, and never reach the end.

The Haskell program, of course, doesn’t know about this property of /dev/zero, yet readFile doesn’t try to read an endless series of bytes into memory. Why not? Because readFile is a bit special; it does its IO lazily.

readFile isn’t alone. The getChanContents function is similar:

getChanContents :: Chan a -> IO [a]

It takes an object of type Chan a — a thread-safe unbounded queue of objects of an arbitrary type — and returns an infinite list of all items that are currently in the channel, as well as all items which will ever be written to the channel in the future. It, too, does lazy IO.

How can this be? If you dig into the source code of how these and similar functions are implemented (thanks to the Glasgow Haskell Compiler’s open-source license, you can easily do this), and trace through the calls they make, you ultimately come to this interesting little function:

unsafeInterleaveIO :: IO a -> IO a

The unsafeInterleaveIO function converts any normal IO computation into a lazy one: one that executes not when the IO action would normally run, but instead when its value is actually used. It is implemented using the deeply magic function named unsafePerformIO, which takes that “nothing ever escapes the IO monad” rule and punches it in the face:

unsafePerformIO :: IO a -> a

As you might guess from the fact that their names both start with the word “unsafe”, and that they’re in the module named System.IO.Unsafe, these functions are dangerous, since they let you bypass Haskell’s usual efforts to make lazy evaluation and IO not stab each other in the back. In certain cases, lazy IO can be mostly safe. For example, with readFile, you’re usually in trouble anyway if program A is reading a file while program B is writing it. As long as nothing is actively writing to a file, it doesn’t matter whether it gets read eagerly or lazily, since the data will be the same either way.

Of course, you’re better off using the functions that use unsafeInterleaveIO and friends rather than using them directly. As a general rule, you’re taking matter into your own hands when you use functions prefixed by the word “unsafe”. As the saying goes, if it breaks, you get to keep the pieces.

However, the existence of lazy IO offers a few possibilities for how we might try to make streaming work without modifying Happstack, thanks to lazy IO.

  1. Use an OS-level pipe. Pipes have two ends: one for writing data into it, and one for reading data out of it. Once they’re created, each end of a pipe can be treated like any other file. Fork a thread to write data to the pipe, which the original thread lazily reads back out as a ByteString.
  2. Use a Chan. Fork a thread to write data to the channel, which the original thread lazily reads and builds a ByteString from.
  3. Use unsafeInterleaveIO directly to lazily generate the ByteString as needed.

You know, this is starting to look like it might actually work. I won’t mention the crippling flaw shared by each of these options, however, at least not just yet. (They also each share a second, non-crippling but still significant flaw; a careful reading of RFC 2616 might give you a clue what it is, if you can’t bear the suspense.) It’s better if we try implementing them and experience how and why they each fail, as will any approach that doesn’t involve modifying Happstack somehow.

We’ll start doing precisely that in Part 3.

2 Responses

  1. Hello,

    Great post, thanks for it.

    About lazy IO unsafeness have you looked at safe-lazy-io?

    http://www.haskell.org/pipermail/haskell/2009-March/021133.html

  2. I hadn’t, but it does look interesting. However, Part 4 of this series will show how any attempt to use lazy IO to solve this problem is fundamentally flawed, so safe-lazy-io wouldn’t be of any help.

Comments are closed.