A Problem With I/O

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

This was true years ago, when functional programming languages were fixated on pure functions. Useful programs must interact with the real world, for example, by printing a string, playing a sound, or reading network packets. How can we define pure functions for such tasks?

We cannot, by definition. Because of this, some languages became functional only in spirit; they encourage a certain kind of syntax, but like conventional languages, they assume side effects could occur almost anywhere.

Researchers since discovered a genuine solution: a simple yet powerful solution that accommodates impure functions without compromising the hard-won pure function core. Modern Haskell can fence off pure and impure functions from one another in a manner akin to the const keyword of C/C++.

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.

One could 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.

An alternative solution

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

The Jam Monad

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. I’ll refrain from explaining monads; 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.

Amusingly, our code resembles what we might write if we had stuck with the IO monad from the beginning:

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