Monthly Archives: March 2008

IO Monad: The Continuation Presentation

I’ve been programming Haskell for several years now, and I have not yet partaken in the rite of passage: writing a monad tutorial. Well, finally I can come of age, for I am giving a monads tutorial talk to the CU ACM group next Thursday.

I’m thinking of starting with the IO monad, since that was the motivation for adding monads to Haskell in the first place. It also gives people something concrete to think about before I segue into more abstract monads. But I don’t want to use GHC’s IO monad as an example:

newtype IO a = IO (RealWorld -> (a, RealWorld))

Because it’s too “low-level”. I barely want to talk about laziness, so a construction which is just there to force evaluation order seems kind of hacky. If you don’t think of it as a construction to force evaluation order, then it is too abstract: what do you mean a function which takes the whole world as an argument? Also, it uses a function as its primary data structure, and the talk will be given to people who are still a little uncomfortable with first-class functions (it will have to introduce them at some point though, but I want to ease into it).

My current plan is to eventually get to the GADT form:

data IO a where
    PutChar :: Char -> IO ()
    GetChar :: IO Char
    Bind    :: IO a -> (a -> IO b) -> IO b
    Return  :: a -> IO a

And then focus on Bind and Return as a segue into the idea of a monad. But yes, you heard me right, to explain an advanced feature, I’m going to use an even more advanced feature! That’s only because I find GADTs very intuitive; in fact, when I was first learning Haskell on the Pugs project, seeing a GADT helped me to understand normal ADTs.

But of course I must ground this GADT. Bind is a weird-looking function, how the hell did I come up with that? I want to arrive at it by necessity, so I’m going to start with a simpler ADT form. I’ll introduce purely-functional IO as a data structure, initially looking like this:

data IOTree
    = PutChar Char
    | IOTree `Then` IOTree
    | NoOp

And then realize that we have no way to do input. At this point I expected to have to switch to the polymorphic variant to handle input, but then this hit me:

data IOTree
    = PutChar Char
    | IOTree `Then` IOTree
    | NoOp
    | GetChar (Char -> IOTree)

To my surprise, with this I was capable of writing all the IO functions that I could using the polymorphic variant, but with some slightly strange-looking type signatures.

getLine :: (String -> IOTree) -> IOTree
getLine f = getLine' id
    getLine' s = GetChar $ \ch ->
        case ch of
            '\n' -> f (s "")
            _ -> getLine' (s . (ch :))

And then I saw it. That type signature looks awfully familar. If I replace the types with variables it’s completely obvious: (a -> r) -> r. I’m working explicitly in the continuation monad. Sure enough, I can build a monad out of IOTree.

newtype IO a = IO { runIO :: (a -> IOTree) -> IOTree }
instance Monad IO where
    return x = IO ($ x)
    IO m >>= f = IO $ \c -> m (\a -> runIO (f a) c)

That’s a unique presentation of the IO monad that I’ve never seen before. It feels “smooth”, there are no huge leaps anywhere except for where the hell we came up with the idea of a monad. But that reason is enough for me not to want to use it. Another reason against it is that the implementation of >>= was not at all obvious to me (it took some typechecker runs), so how are FP noobs going to understand it?

So I’m still not sure how I’m going to motivate the polymorphic form. Probably something like introducing the idea of IO “holding” a value, and then we need a variable for the type of value it holds. That would also allow me to introduce Functors, which I want to do as a “monad indicator”; i.e. functors are pretty easy to intuitively spot, and there’s a decent chance that if you have a functor, you have a monad.

Stepping away from pedagogy for a moment, I find it very interesting what continuation passing style did to this example. It seems that CPS is a nice way to build up data structures “procedurally” without hand-crafting a different monad for each one. For instance, Writer can be naturally specified as:

type Writer w a = Cont w a
tell :: (Monoid w) => w -> Writer w ()
tell w = Cont $ \c -> w `mappend` c ()

Anyway, I’d love to hear any advice anyone has about presenting the IO monad, or monads in general. The focus is not so much “so you’re trying to learn Haskell but are perpexed by monads, here’s how to understand them”, but more “you’ve barely heard of Haskell, here’s why monads are awesome”. I plan to talk about IO, List, Suspend[1], and close with STM (where Haskell rocks everyone else’s world).

[1]The Suspend monad is what Fregl‘s Event monad is built on. It’s a type of coroutine which only consumes values:

data Suspend v a
    = Return a
    | Suspend (v -> Suspend v a)

Another Session with Bob

Here’s the session from March 5th, with Bob Mulligan on drums. This was the first session I recorded with three tracks; the sound is much, must cleaner than last time.

  • 01 – light and fluffy
  • 02 – gets good and funky by the end
  • 03 – a fantastic space out jam, very subtle with lots of interesting textures
  • 04 – some eccentric piano jazz
  • 05 – almost tribal funk
  • 06 – an interesting polyrhythmic piece
  • 07 – happy and chilled-out

My favorites are 1,3, and 5.

SVK, you’re not wanted here, git it?

After trying and failing to restore the soylent repository from my svk mirror, svk broke. It wouldn’t let me push or pull from any of my mirrors, for no discernable reason. Instead of hacking it out, I decided to get my hands dirty with git, which I have heard good things about. So far so good, after the usual new SCM ritual (create new repository, whoops, “oh, that’s how that works”, delete, create new, whoops, “oh, pull doesn’t mean pull”, delete, …).

My old svn misc repository will be hanging around, since I have links into it floating around, but it will go unmaintained. Behold the new git misc repository!

Gui Half-Epigram

Here’s just a quick jot of an idea before I give my bed a much-needed visit.

Recently I’ve become interested in dependent types, a la Epigram and Agda. I like Agda’s concise style more, but Epigram definitely has an appeal from a user interface perspective. Let’s not be fooled, Epigram’s user interface is terrible, but it shows an amazing amount of potential.

So I got to thinking, what could you do in a Epigram-inspired style for a non-dependent language as far as GUI-based programming. It wouldn’t be as powerful, of course, because the compiler has far less information in languages like that, but you still might be able to get away with something. In particular, when I’m implementing very general functions, such as Arrow instances, I often do type-directed programming. Essentially I just find a series of functions which typechecks and there’s a high chance that it will be the correct implementation.

Here’s the GUI idea. You have a list of all the types you “have” (labeled with what they are of course), and a list of types you “need”. Then, say, you’d click on something you have and it would show you everything you could do to it; i.e. all functions which accept that type as an argument. There would naturally be very many of these things, so you’d need some sort of smart search. You click on one of those things, and it would add the return type of the function to the list of things you have, and add the other arguments to the list of things you need.

It would work in the other direction too: you could click on one of the types you need, and it would show you all the functions which return that type.

This is essentially Epigram’s method, but with a bottom-up component as well. Epigram can be precise about it, this interface would be less precise, more of a helper tool. I think it deserves a prototype though, since it represents a leap from textual information to spatial information (if you presented it right), and brains are very much better at manipulating spatial information.

The Return of Strange New Worlds

By now, Eric is fleeing to Venezuela to go make some latin band down there awesome, and do God-knows-what else. Meanwhile, Evan and I have been playing with a drummer named Bob Mulligan, who is too good for us. Still, it’s a great opportunity to play with him, and I think given a few months after we find each other’s buttons we could rock.

Eric was our recording engineer, too, so we’ll have to make do with the room mic again. Still, with some post-processing, it’s not too bad.