Understanding the Haskell IO Monad.

By Building a Toy Model in Scheme

Somehow or another, this blog ended up being about two basic things: Lisp and Functional Programming. I've talked about almost every Lisp species there is, but there is an Elephant in the Functional Programming room, which has only come up every so often, which is the programming language Haskell.

Lisp is the Tao, at least to awesome hippies like Mark Tarver. Image borrowed from here.

I'm quite fond of Haskell, in principle. If Lisp is the Tao -- a kind of informal, flexible cloud around the locus of the ideal programming language -- then Haskell might be a rather rigidly specified diamond right near that locus' center. Haskell trades a lot of the looseness of Lisp for a rigid semantics, but it seems there is a good argument that these semantics are much closer to the ideal of Functional Programming.

I don't have much opportunity to program in Haskell, and so I don't write a lot about it. I do program in Lisp a lot, and I think I've subconsciously been engaged in a long term project to improve my understanding of Haskell by implementing toy models of parts of it in Lisp. Hence all the posts about monads. I've recently started writing a book about pure functional programming in Scheme/Racket and initial exploratory writing has produced a few insights about Haskell's IO Monad.

The IO Monad seems to be among Haskell's most mysterious monads for new programmers. Monad tutorials and explications rarely talk about it. Haskell tutorials introduce it as an ad-hoc: they show you how to use it syntactically, but its rarely made naked. And there is a reason for this: whatever it is, precisely, that the IO Monad does isn't expressable in regular old safe Haskell.

But its pretty important, and not just because its the only kosher way for a Haskell programmer to communicate with the outside world. In a sense, a Haskell program can be viewed as a description of some IO actions. The Haskell run time can be thought of as constructing that IO action, and then, somehow, executing it. If you've heard programmers say that, even when using the IO Monad, one is still writing "pure" code, this is what they mean: the Haskell program itself simply constructs an IO action from smaller, and ultimately primitive IO actions. The actions are never run in the code itself, just constructed. Eventually the Haskell runtime executes them, but the construction of the IO commands is itself purely a matter of functional programming, without side effects.

(Note that the programmer can bail out of this paradigm using thigns like unsafePerformIO, but that is frowned upon, for the most part).

So its important, I think, to develop a mental model of what is going on here.

Enter Scheme

I Love Lisp/Scheme, because using Lisp is a great way to understand language constructs. Lisp is a kind of programming language lab, where a crappy, ad-hoc and slow implementation of a language feature is always a few hundred lines of code away. It takes serious effort to design a non-standard language on top of Lisp for an "industrial strength" application, but if you just want to understand something, Lisp can take you there. It is a great way to get to know unusual semantics.

Today we're going to use Racket, which really isn't a Scheme anymore, so much as a Scheme superset, to build a toy model of the IO monad. The bird's eye view is that we'll build a lexicon of IO actions, which will be regular old functions which take the IO state and maybe do something with it, and return a value, and then we'll build some machinery to construct more complex IO actions from simpler ones.

We'll also build an external library to execute these IO actions once they've been built, but the intent is that the user is segregated from this execution. They don't know anything about it, and all they do is build IO actions and hand them off.

Bundling Up IO

Let's start with our "low level" IO. One possibility is that we bundle up standard-input and standard-output into a type of some kind. IO actions will just, then, be functions which take this pair of standard input and output and return values. I'd like to do something a little more fun. Let's build a graphical user interface that has an input window and and output window and build an IO Monad over them, instead. This will give us a change to play around with Racket's GUI classes, which is a nice thing to get acquainted with.

Sketch

We'll write a function run-io which will take an IO action, pop up a window, and execute that action. It will have the type:

type io-action = io -> a
run-io :: io-action -> a

Where we mean by a that the function returns the type a, which can be anything. Our function takes a single value of type io-action, which we will get specific about in a bit.

This function has to do a few things. It needs to initialize a frame%, put some editor's in it with a layout of some kind, and then it needs to create the io object, pass it to the action, and then return the result of the io action. The window will be broken into an output area and an input area. The output area will have no special behavior, except, of course, that we'll be able to write to it and clear it. The input area will be a kind of "command line," - we want it to only accept one line at a time, which it detects by looking for a newline. Somehow, we want each command to end up being readable from within the monad.

Text windows are represented by two classes working in tandem in Racket, a text% class and an editor% class. We can accomplish our goals by subclassing the text% part.

(require racket/gui
     (only-in srfi/13 string-trim-both))

(define (string-contains-newline? str)
  (let loop ((chars (string->list str)))
    (match chars 
      [(list) #f]
      [(cons #\newline rest) #t]
      [(cons x rest)
       (loop rest)])))

(define input-text% 
  (class text% 
    (field (command #f))
    (define/public (text-substring start len)
      (let loop ((acc '())
                 (i 0))
        (if (< i len) (loop (cons (send this get-character (+ start i)) acc) (+ i 1))
            (list->string (reverse acc)))))
    (define/augment (after-insert start len) 
      (let ((string (send this text-substring start len)))
        (if (string-contains-newline? string) 
            (let ((a-command (send this text-substring 2 (+ start len))))
              (set! command (string-trim-both a-command))
              (send this erase)
              (send this insert "> "))
            #f)))
    (define/public (grab-command) 
      (let ((c command))
        (set! command #f)
        c))
    (super-new)
    (send this insert "> ")))

We've added a field to store the current command, with #f no command, and augmented the after-insert method to detect command entry and act appropriately. The new method grab-command fetches the current command and sets the internal command to #f again.

There is no easy way to make setting up a GUI look nice, as far as I know, so here is the gory details:

(define (setup-window)
  (let* ((frame (new frame% 
                     [label "io toy"]
                     [width 640]
                     [height 480]))
         (pane (new vertical-pane% 
                    [min-width 640]
                    [min-height 480]
                    [parent frame]))
         (output-text (new text%))
         (output (new editor-canvas% 
                      [parent pane]
                      [style '(no-hscroll)]
                      [editor output-text]
                      [min-width 640]
                      [min-height 400]))
         (input-text (new input-text%))
         (input (new editor-canvas%
                     [parent pane]
                      [style '(no-hscroll)]
                      [editor input-text]
                      [min-width 640]
                      [min-height 40]))
         (io (lambda (input)
               (match input
                 [(? string? x) (send output-text insert input)]
                 ['clear (send output-text erase)]
                 ['fetch-command
                  (let loop 
                    ((command (send input-text grab-command)))
                    (yield)
                    (if command command (loop (send input-text
                                                    grab-command))))]))))
    (send frame show #t)
    io))

The IO Window in All Its Splendor

This does the business of setting up our window and constructing our "io" value, which is apparently a function which can take either arbitrary text, which it inserts into the output buffer, or the symbols clear and fetch-command. clear, straightforwardly enough, clears the output region with the erase method. fetch-command enters a loop and doesn't return until a command is entered by the user, although it does call yield in order to let the GUI thread check for new events.

With this function, we can easily define:

(define (run-io action) 
 (let ((io (setup-window)))
    (action io)))

Now our users can concern themselves entirely with IO action construction. They trust us to execute the action later. What does an action look like?

Well:

(define (clear io) (io 'clear))
(define (get-command io) (io 'fetch-command))
(define (insert text) (lambda (io) (io text)))

Are three such commands. In fact, they are going to be our "atomic" commands, from which we'll build everything else.

One wrinkle: insert isn't itself an io action, it is a function which returns an io action which inserts the indicated piece of text. insert is a simple kind of io-action builder. We'll see how to integrate io actions together in a bit.

Let's wrap this all up in a module, only exporting our low level interface:

(provide run-io clear get-command insert)

Saving the file as toy-io.rkt will create a module. You can also download this code from my github account.

You've got to place that file somewhere where Racket can get to it, and then you can fire up Racket and say:

(require blog/toy-io)
(run-io (insert "Testing, 1, 2, 3!"))

And press go. What this should do is pop up a window with an interaction area and an output area with "Testing, 1, 2, 3!" in it. Great. Now we should focus on building up IO actions.

The IO Monad

Monads always have an associated monadic value of a particular type. In this case, our monadic values are functions which accept an IO object and return any old thing. The get-command is a monadic value - it accepts the io object and returns the command received from the user. What if you wanted a get-two-commands which read two commands and returned them as a list?

(define (get-two-commands io)
  (let ((c1 (get-command io))
        (c2 (get-command io)))
    (list c1 c2)))

Simple enough. get-two-commands is, itself, a monadic value.

Now for the monad part: what if you want to define a monadic value which gets one command, and then determines what to do based on the result of that command. We can represent the choice we'll make about what to do next with a function which is waiting for the previously read command and will eventually return an io action. Think of a lambda expression as a computation with some unbound variable which will calculate a value when that variable is provided or bound. Hence, consider the function:

(define (io-bind io-action io-action-producer)
  (lambda (io)
    (let* ((result (io-action io))
           (next-io-action
            (io-action-producer result)))
     (next-io-action io))))

io-bind is our io action construction work horse. It builds up a new io action from an io action and an io-action-producer, which is waiting for the result of the previous io action before it can decide what to do. io-bind returns an io action, of course. That io action executes the first argument to io-bind when it receives the io object. It then passes the result of that action to the producer, and executes the resulting io action on the io object.

This is sufficient to build up a large family of complex io actions which depend on the results of querying the input. We need one more function to build our monad, though:

(define (io-return value)
  (lambda (io)
     value))

This function makes the simplest kinds of io actions. They don't do anything, but they do return whatever value was specified when io-return was called. io-return, in other words, inserts values into the io monad.

Building IO Actions

Let's build an io action that checks for the command "exit." If "exit" is encountered, then the io action simply returns, but if it isn't encountered, it reads another command and so on.

(define exit-flagger 
  (io-bind get-command 
           (lambda (command)
             (if (equal? command "exit") 
                 (io-return 'exit-detected)
                 exit-flagger))))

If you then execute (run-io exit-flagger), you'll get a window which will keep accepting inputs until you type "exit," at which point, control will return to the command line.

Here we use io-bind to construct a new io action directly, but Haskell provides special syntax for monadic behavior. Let's build a version of that syntax here.

"Do" Notation

We'll create a do-io form which accepts a list of expressions of two varieties. An expression must either evaluate to an io action, or it must specify that a value should be bound to the result of an io action in the following way:

(command <- get-command)

We'd rather not get into a deep discussion about macros in Scheme, so we'll use regular old syntax-rules. Not much error handling, but its pretty simple to understand.

Consider:

(define-syntax do-io 
  (syntax-rules (<-)
   [(do-io (id <- io-action) expr ...)
     (io-bind io-action 
        (lambda (id)
          (do-io expr ...)))]
   [(do-io io-action expr ...)
    (io-bind io-action 
     (lambda (_) 
       (do-io expr ...)))]
   [(do-io io-action) io-action]))

Our syntax-extension has three cases. The most specific appears first, where we detect an expression indicating a monadic binding. We pass the monadic value io-action to io-bind along with a lambda expression consisting of the rest of the do-expression in a context where the id is bound to the result of the action. When we don't have a binding expression of the form (id <- io-action), expand the macro the same way, but don't even bother creating a variable visible in the rest of the expressions. If we only have a single expression, then we just return its value.

We can now write our exit-flagger io action as:

(define exit-flagger
 (do-io 
  (command <- get-command)
  (if (equal? command "exit") 
      (io-return 'exit-detected)
      exit-flagger)))

This resembles Haskell notation, where the same thing might look something like:

exitFlagger = do
  command <- getCommand
  if equal? command "exit" 
     then
       return "exit-detected"
     else
       exitFlagger

A Simple Example

Let's write some brains into our command interpreter.

(define (read-command str)
  (with-handlers ([exn:fail? (lambda (e) 'error)])
    (with-input-from-string 
     (string-append "(" str ")")
     (lambda () (read)))))

This function converts a string into a list of values. If it doesn't receive a string which, when wrapped with "()" evaluates to a piece of Scheme code, it just returns error. We use it to make dispatching on commands easier:

(define symbolic-command
  (do-io 
    (cmd <- get-command)
    (io-return (read-command str))))

Now we can write:

(define (repeat-char n char)
  (let loop ((n n)
             (acc '()))
     (if (<= n 0) (list->string acc)
         (loop (- n 1) (cons char acc)))))

(define dispatch
  (do-io
   (c <- symbolic-command)
   (match c
     ['error 
      (do-io
       (insert "Error reading command string.")
       dispatch)]
     [(list 'stars (? number? n))
      (do-io 
       clear
       (insert (repeat-char n #\*))
       dispatch)]
     [(list 'exit) (io-return 'exit-detected)]
     [_ (do-io
         clear
         (insert "unknown command.")
         dispatch)])))

dispatch is pretty easy to understand. It is an io action which grabs a command, converts it to a list of atoms and lists, matches that list for known commands, and loops, unless the command read is (exit). Note that dispatch is defined without ever explicitely referencing the io state that is threaded through all its parts. We've liberated the programmer from thinking about what that state is or how it is managed. They simply build up io actions like any other kind of data.

Dispatch in action!

Conclusions

Ok, so we built a low level interface which non-functionally handles input and output operations for us. Because input and output is inherently stateful, there is no real way to avoid side effects in this part of our code.

However, we then realized that we could "encapsulate" input and output operations in a few primitive io actions and provide a monadic context wherein the user can build more complex actions from simpler ones. Up until the moment the user calls run-io, she maintains complete purity. Constructing io actions can be done completely without side effects.

For bonus, we implemented a syntax mimicing Haskell's do notation in terms of the function io-bind. This gave us a toy model of Haskell's io monad, which we used to build some simple io actions.

Glazed over in all this discussion were the implications of Haskell's lazy semantics, type system, and error handling mechanisms. We might also begin to wonder how we combine this stateless io programming with other, apparently stateful tasks. We'll see how we can do that in a later post (or in the book, if I ever write it), and how these considerations relate to monad transformers!

This code is up on my github. If you are interested in monads, you can also check out my better-monads library on Planet Racket. It doesn't include an IO monad because that is kind of ridiculous in Scheme!

Thanks for reading!