A Problem With I/O

“Functional languages have a … problem with I/O”, notes Rob Pike.

Actually, almost all languages have a problem with I/O. The vast majority, including many that are called “functional”, simply give up and assume side effects can happen at any time. In those that are decent enough to provide static typing, a function that claims to return an int might return an int, or it might launch some missiles and return an int.

Thus Rob Pike’s statement is misleading, as it suggests ignoring a problem is equivalent to solving it.

There are a few languages that confine themselves to pure functions. In Coq, for example, one never has to worry about side effects. Admittedly, I/O in Coq seems peculiar to most programmers: instead of printing "Hello, World!" directly, we output a program, which if interpreted correctly, prints "Hello, World!".

Haskell compromises brilliantly, by fencing off pure and impure functions from one another in a manner akin to the const keyword of C/C++, and tricks us into believing impure functions are actually pure by pretending the real world is a value that can be threaded through them.

The effectiveness of this solution has drawbacks. The illusion is so good that programmers are fooled into thinking I/O is pure in Haskell. And now that we can write mostly pure code with occasional impure wrappers, researchers have mostly stopped seeking superior alternatives. May we one day escape this uncanny valley.

Hello, World!

Consider a function call that prints a string:

puts("Hello, World!")

We know it doesn’t just take a string and return nothing. There are side effects, that is, something noticeable happens in the real world.

This suggests introducing a type that represents the real world. The puts function should take an input world and a string, and output a whole new world: a world where the given string has been printed. Similarly, a gets function that reads a string should take an input world, then output a string and a new world: a world where a string has been consumed from standard input.

In Go, it might go something like this:

func puts(s string, w world) world

func gets(w world) (string, world)

func main(w world) world {
  w1 := puts("Enter a string:", w)
  s, w2 := gets(w1)
  return puts("You typed: " + s, w2)
}

We’ve purified our code. Everything is immutable. Variable assignments only occur during initialization. I/O is no problem.

How does the compiler deal with the world type? Easy! The compiler initially treats it like any other type, then after applying optimizations that work only for pure functions, it discards objects of type world.

However, the syntax is clumsy. Must we clutter our source with world parameters?

How to Change the World

Before long, we notice any sensible function that outputs a world must also expect an input world, and vice versa. Moreover, there must be exactly one input world and one output world, the former representing the old world and the latter the new. To describe side effects is to describe the world before and after they transpire. [The real world is a global object, both literally and in computer science parlance.]

This inspires us to define a family of types to represent world-changing functions, and to redefine puts and gets as follows:

type IO       func(w world) (        world)
type IOString func(w world) (string, world)
type IOInt    func(w world) (   int, world)
...

func puts(s string) IO
func gets() IOString

We’ve added a layer of indirection. Before, the puts function took a world and a string, then returned a changed world. Now, it takes a string and returns a world-changing function, which must eventually be run.

It’s like Unix pipes, but instead of transforming text, we chain together functions that transform the world. More accurately, it’s like MS-DOS fake pipes, because each stage must finish completely before the next can begin.

func main(w world) world {
  s, w1 := gets() (puts("Enter a string:") (w))
  return puts("You typed: " + s) (w1)
}

The End of the World

We’ve reduced some clutter, but the Go code still looks odd. Worse yet, nothing prevents us writing bad code that reuses a stale version of the world: a rift in the space-time continuum!

It’s better in Haskell. Firstly, thanks to parameterized types, we can just define IO (which is actually predefined by the Haskell Prelude), and all else will follow:

puts :: String -> IO ()
gets :: IO String

Secondly, Haskell makes us pass the world parameter implicitly:

main :: IO ()
main = puts "Enter a string:" >> gets >>= (\s -> puts "You typed: " ++ s)

The tacit world parameter is more than a mere convenience. It ensures we can never do silly things like destroy the world or return the wrong world. The world is automatically threaded correctly through our code. Again, we’re reminded of Unix pipelines, which send the output of one program to the input of the next even though standard input and standard output are implied without being stated. Hiding them prevents us from messing them up.

The presence of the IO type constructor means a function is impure, just as the absence of the const keyword in C/C++ means data might be modified.

Using Haskell’s do notation, we can mimic conventional languages:

main = do
  puts "Enter a string:"
  s <- gets
  puts ("You typed: " ++ s)

Loosely speaking, within a do block, the output of one line becomes the input of the next.

The above isn’t merely theoretical, by the way. We can turn our code into a working program by adding:

puts = putStrLn
gets = getLine

Haskell syntax is clean, yet powerful. We have mixed pure and impure code with ease, yet we can distinguish between the two at a glance.

Purity Test

One might argue IO functions are pure; it’s just that we inconveniently lack the power to create and destroy worlds so we cannot do things we often do with pure functions, such as run them multiple times on the same input.

But time passes while the computer is waiting for user input, that is, the real world changes even after it is passed to getLine, so there is something imprecise about viewing IO functions as pure.

Perhaps we can tolerate these discrepancies in a single-threaded program. However, functions such as forkIO also live in IO. What does it mean to give 2 threads 2 copies of the world? Didn’t we say the world is unique so copying is impossbile? And even if we could, what happens when the threads join? How can two different worlds merge?

An alternative solution

The Clean programming language solves the I/O problem with a uniqueness type system.

Monads

We achieved simplicity making the world arguments implicit, and using do notation to replace nested function calls with a sequence of function calls.

We can generalize this technique to eliminate code duplication in other contexts. When we do, we call it a monad.

If you’ve been studying denotational semantics. then sooner or later this trick will occur to you, and from this point of view, "monads are just as interesting and important as parentheses"

Otherwise, to paraphrase a famous movie quote, some believe that unfortunately, no one can be told what a monad is; you have to write one for yourself. To this end, we replace our CodeJam module with a monad. Our goal is to be able to hide details so we can write something like:

-- In this hypothetical Google Code Jam problem, each case consists of
-- two integers separated by a space, and we're to output their product.

import Jam

main = jam $ do
  [m, n] <- getints
  return $ show $ m * n

While debugging, I found it useful to be able to extract a particular set of cases from an input file, so I added a second list of strings to the state: this second list holds the input read so far for a single test case. Suppose we want to generate a new input file that consists of the first, third and sixth cases of another file. Then we want to be able to temporarily modify our solution to print test inputs instead:

import Jam

main = jamCases [1,3,6] $ do
  [m, n] <- getints
  return $ show $ m * n

We imagine there are other applications: perhaps we want to print input-output pairs for each case.

The idea is to surreptitiously attach two lists of strings to everything we do. One list holds the input that is about to be read, and the other holds the input we have already read. Our code is just like the IO monad except instead of tacitly modifying a world, we’re tacitly modifying two lists of strings.

module Jam (
  jam, jamOff, jamCases,
  gets, getsn, getints, getintsn, getintegers, getdbls
) where

import Control.Monad
import Data.List

data Jam a = Jam (([String], [String]) -> (a, ([String], [String])))

instance Functor Jam where
  fmap = liftM

instance Applicative Jam where
  pure k = Jam (\s -> (k, s))
  (<*>) = ap

instance Monad Jam where
  Jam c1 >>= fc2 = Jam (\s0 -> let
    (r, s1) = c1 s0
    Jam c2 = fc2 r
    in c2 s1)
  return = pure

gets :: Jam String
gets = Jam (\(x:xs, ys) -> (x, (xs, ys++[x])))

getsn :: Int -> Jam [String]
getsn n = replicateM n gets

getints :: Jam [Int]
getints = getem

getintegers :: Jam [Integer]
getintegers = getem

getintsn :: Int -> Jam [[Int]]
getintsn = getemn

getdbls :: Jam [Double]
getdbls = getem

jamOff offset f = interact $ \s -> let
  Jam fun = f
  (_n:inp) = lines s
  n = read _n
  in unlines $ zipWith (++) (map (\k -> "Case #" ++ show (k+offset) ++ ": ") [1..n])
    $ unfoldr (\(xs, _) -> Just $ fun (xs, [])) (inp, [])

jam f = interact $ \s -> let
  Jam fun = f
  (_n:inp) = lines s
  n = read _n
  in unlines $ zipWith (++) (map (\k -> "Case #" ++ show k ++ ": ") [1..n])
    $ unfoldr (\(xs, _) -> Just $ fun (xs, [])) (inp, [])

jamCases idxs f = interact $ \s -> let
  Jam fun = f
  (_n:inp) = lines s
  n = read _n
  cases = take n $ unfoldr (\xy -> let
    (_, (xs, ys)) = fun xy in Just (ys, (xs, []))) (inp, [])
  in unlines $ (:) (show $ length idxs) $ concatMap ((cases!!) . (+ (-1))) idxs

It turns out we often want to attach some kind of state to a sequence of functions. This is exactly why the State monad was written, and in fact, we could have just defined:

data Jam a = State ([String], [String])

But we should write out a monad in full (even if it is copied from elsewhere!) at least once while learning Haskell.

Our code resembles what we might write if we had stuck with the IO monad.

iogetints :: IO [Int]
iogetints = do
  s <- getLine
  return $ map read $ words s

main = do
  [m, n] <- iogetints
  putStrLn $ show $ m * n

However, it’s good form to steer clear of IO as much as possible. Especially if it’s as easy as swapping out the IO monad with a State monad. Besides feeling good about ourselves, we can, for example, trivially feed a string to our program instead of reading from standard input. We lose this flexibility if we use the IO monad everywhere.


Ben Lynn blynn@cs.stanford.edu 💡