Don't Call Us, We'll Call You

Saturday, January 7, 2017 · 3 min read

Look. I get it. Monad tutorials are a meme, memes about monad tutorials are a meme, and we’re almost at the point where memes about memes about monad tutorials are a meme. Before we go any farther down this infinite stack of turtles, though, I want to share one way to think about monads that doesn’t involve burritos or boxes or any Haskell code at all. I present to you, the Sugarloaf Transformation.

The overall idea makes sense to me because I’m a fan of visual metaphors. Your mileage may vary.

Consider the dataflow programming paradigm (think of Quartz Composer or LabView-G). A dataflow language takes the idea of an abstract syntax tree and extends it to the tree’s close relative, the directed acyclic graph. A dataflow program is a DAG where the edges entering and leaving each node are ordered. Each edge is associated with a value, and a node computes the values of its out-edges based on the values of its in-edges. Nodes with no in-edges are called sources, and nodes with no out-edges are called sinks. The program below computes the difference between 3 and 1, and prints the number 2. The two nodes on the left are sources that return constants; the print node is a sink.

+---+
| 3 |--+
+---+  |   +-------+
       +-->|       |   +-------+
           | minus |-->| print |
       +-->|       |   +-------+
+---+  |   +-------+
| 1 |--+
+---+

To interpret a dataflow program, we have a variety of strategies. We could begin at sinks and recursively descend into in-edges until we reach sources, which can be evaluated with no further work. This corresponds to a recursive-descent interpreter of an AST. Alternatively, we could begin by collecting the set of sources, evaluating them, assigning the results to the respective out-edges. Then, we iteratively find and evaluate nodes whose in-edges have all been assigned values, until at last we have evaluated the entire program.

The point I wish to make is that the order in which nodes are evaluated is nondeterministic. Thus, the following “obvious” program to subtract two numbers is not well-defined. If given inputs “3, 1” by a human, it may output “2” or “-2” depending on the order in which the two read nodes were evaluated.

+------+
| read |--+
+------+  |   +-------+
          +-->|       |   +-------+
              | minus |-->| print |
          +-->|       |   +-------+
+------+  |   +-------+
| read |--+
+------+

The problem is that nondeterministic evaluation order for IO results in the evaluator potentially diverging. This is really bad! How can we force a deterministic order of execution for IO primitives? Well, notice that the only way to force node x to evaluate before node y is to make y depend on the output of x. We can have each node output an “ordering sentinel” that becomes the input to future nodes: this allows us to impose a partial ordering on node evaluation, as shown below.

+-------+   +------+     +------+
| start |-->|      |---->|      |
+-------+   | read |     | read |
            |      |-+   |      |-+
            +------+ |   +------+ |
                     |            |   +-------+
                     |            +-->|       |   +-------+
                     |                | minus |-->| print |
                     +--------------->|       |   +-------+
                                      +-------+

The start node simply emits an ordering sentinel, to kick off the computation.

This looks really good: this program is, in fact, well-defined in its execution order. Sadly, a partial ordering still allows divergent programs. Why? It’s because, in the words of Philip Wadler, “Truth is free.” Once you have computed a sentinel, you can use it wherever you want. What prevents us from doing this?

               +------+
           +-->|      |
           |   | read |      +-------+
           |   |      |----->|       |   +-------+
+-------+  |   +------+      | minus |-->| print |
| start |--+             +-->|       |   +-------+
+-------+  |   +------+  |   +-------+
           +-->|      |  |
               | read |  |
               |      |--+
               +------+

Nothing. Yikes.

If the problem is that “truth is free,” we might be able to solve the problem by simply restricting the flow of information created by IO primitives. One solution is to sandbox all computation that uses the output of an IO node. An easy way to do this is to “lock” the output of an IO node in a special pipe that can only be unlocked by entering a sandbox. Of course, sandboxes must only allow locked values to exit—otherwise you can trivially pass a value through the null sandbox to unlock it. Our program then becomes the following (the dotted boxes denote sandboxes, and fat arrows are locked).

            .................................................
+------+    :                                               :
| read |===>@---------------+                               :
+------+    :               |                               :
            :             ..|............................   :
            :             : |                           :   :
            :             : |   +-------+               :   :
            :             : +-->|       |   +-------+   :==>:==> ...
            : +------+    :     | minus |-->| print |==>:   :
            : | read |===>@---->|       |   +-------+   :   :
            : +------+    :     +-------+               :   :
            :             :                             :   :
            :             :.............................:   :
            :                                               :
            :...............................................:

Notice that since a sandbox only unlocks one pipe at a time, and does not allow the unlocked value to escape, our previous divergence hack becomes impossible. minus takes two unlocked inputs, so they must be computed in nested sandboxes which ensure sequential execution. Indeed, by generalizing, it is not hard to see that now there is only one way to compute the contents of a locked pipe. This means that the result of a locked pipe is literally the same as the computation that goes into evaluating its contents—and so our programs must have a well-defined execution order.

In Haskell, locked pipes correspond to values “boxed” in a value of type IO a (this is where the burrito metaphor stems from). Sandboxes are lambdas, and the unlocking mechanism @ is the monadic binding operator >>=. The return function in Haskell is simply a node that locks its input—this lets us return an arbitrary value from a sandbox. Finally, do-notation is just syntactic sugar to save programmers from reasoning about lots of nested sandboxes, in the same spirit that C has in letting you write 1+2+3+4 instead of 1+(2+(3+4)).

P.S. The title of this post refers to the idea that this transformation in a way inverts the traditional flow of control. Normally, minus would call read twice to get the values of its inputs. Here, however, the reads are calling minus to create their output. “Don’t call us, we’ll call you.”