Sunday, October 30, 2011

Quick and dirty reinversion of control

It's taken for granted by many people that Haskell and static types are incompatible with prototyping and quick-and-dirty hacks.

I wanted to put together some OpenGL code that had a script for how a bunch of graphics should be displayed. It was essentially an imperative specfification for my program. For quick and dirty hacks, GLUT is tolerable. But even when programming in C/C++, it's not supportive of programming in a straightforward imperative style because it uses inversion of control. Many graphics applications are written in a state machine style where the state machine gets to tick once each time there is an event callback. This really doesn't fit the imperative script style.

But it is possible to reinvert inversion of control in any language that supports continuations. And that includes languages like Python that support linear continuations in the form of generators. But I'm using Haskell here.

Continuations reify the remainder of a computation. Or in more down to earth language: they allow you to grab the stuff you're about to do as a function, put it on ice for a while, and then carry on doing it later. So imagine we had a block of imperative code and that we'd like, at each GLUT callback, to make some progress through this block. We can use continuations like this: each time we want to yield control back to the main loop we simply grab the remainder or our 'script' as a continuation and make it the callback to be executed next time GLUT is ready.

The slight wrinkle is that OpenGL/GLUT calls use IO. To combine IO and continuations we need the ContT monad transformer.

I'll do everything except the yield function first and get back to that at the end.

Some standard library imports:

> import Graphics.UI.GLUT
> import Control.Monad.Cont

Some simple code to draw a line from left to right:

> display :: GLdouble -> IO ()
> display y = do
>   clear [ColorBuffer]
>  
>   renderPrimitive LineStrip $ do
>     vertex (Vertex2 (-1) (-y))
>     vertex (Vertex2 1 y)

>   swapBuffers
>   postRedisplay Nothing

Some standard OpenGL/GLUT setup:

> main = do
>   (progname, _) <- getArgsAndInitialize
>   initialWindowSize  $= Size 500 500
>   initialDisplayMode $= [DoubleBuffered, RGBMode]
>   createWindow "Bounce!"

>   matrixMode $= Modelview 0
>   loadIdentity

>   matrixMode $= Projection
>   loadIdentity
>   ortho (-1) 1 (-1) 1 (-1) 1

Our script is called before the main loop.

>   imperative
>   mainLoop

And now comes the actual script. Apart from the liftIO calls this should be almost as easy to read as BASIC programming from the days of yore:

> imperative = flip runContT return $ do

>   liftIO $ print "Start!"

>   forever $ do

>     forM_ [-1, -0.992 .. 1.0] $ \y -> do
>       render $ display y
>       yield

>     liftIO $ print "Bounce!"

>     forM_ [-1, -0.992 .. 1.0] $ \y -> do
>       render $ display (-y)
>       yield

>     liftIO $ print "Bounce!"
>     yield

The first thing to note is that render doesn't actually do any rendering. At the end of the day we can't tell GLUT when to render, it only calls you. So instead render tells GLUT what to do next time it's in the mood for a bit of rendering:

> render f = liftIO $ displayCallback $= f

That leaves one thing to explain: yield. It needs to grab the remainder of the script and package it up in a form suitable for installation as an idle callback. But there's a catch: continuations are notorious for making your head explode. If you're throwing together a quick and dirty hack, that's the last thing you need. Here's where static types come to the rescue. As Conor McBride points out, we want to just do the easy thing and follow gravity downwards.

So first we try to guess the type of yield. We know we're working with the ContT IO monad. So its type is going to be ContT IO a for some a. There's no particular type of data we want to get out of yield, it's just a thing we want executed. So we can guess the type is ContT IO (), the type () being the generic filler type when we don't actually have any data.

Let's look at the definition of ContT:

newtype ContT r m a = Cont {
    runContT :: (a -> m r) -> m r
}

The type r is the final return type from our continuation. We're not interested in a return value, we just want to *do* stuff. So we expect r to be () as well.

So yield must essentially be of type (() -> IO ()) -> IO ().

So we want to concoct something of this type using GLUT's idleCallback function. As yield must take a function as argument it must look something like:

yield = ContT $ \f -> ...

We know that f is of type () -> IO (). So there's only one thing we can do with it: apply it to (). That gives us something of type IO (). That's precisely the type of GLUT's idleCallback. So we put it all together:

> yield = ContT $ \f -> idleCallback $= Just (f () )

The code now works. I didn't have to spend even a moment thinking about the meaning of a continuation. Implementing yield was about as hard as putting together a jigsaw puzzle with three pieces. There's only so many ways you can put the pieces together.

And that's a simple example of why I often like to write quick-and-dirty code with a statically typed language.

(Oh, and I'm not trying to take part in a war. I like to prototype in many different languages, some of which are dynamically typed.)

PS Note also that the above code illustrates one way to avoid IORefs in GLUT code.

13 comments:

  1. Nice!

    I usually use my operational package for stuff like this, as it makes the implementation of "yield" a single-piece jigsaw puzzle.

    ReplyDelete
  2. Hello! You end your post tantalisingly with "PS Note also that the above code illustrates one way to avoid IORefs in GLUT code." Can this technique be used to avoid IORefs not just in GLUT code but in general, and would you be willing to provide a small example?

    ReplyDelete
  3. As easy to read as BASIC code perhaps, but when Haskell hits Doubles you may fear for correctness, because in BASIC you won't get this little problem.

    Prelude> last [-1, -0.992 .. 1.0]
    1.0000000000000018

    ReplyDelete
  4. Barak,

    Many would argue that the list [-1, ..., 1.0000000000000018] is a better approximation to [-1, ..., 1.0] than [-1, ..., 0.9980000000000018]. I recommend avoiding enumFromThenTo with floating point types in production code.

    ReplyDelete
  5. Yeah well they'd be *wrong*. It violates the basic invariant of what an interval means. Note that they were not insane enough to use that logic on integer intervals, because then [0,3..5] would be [0,3,6] but it isn't because that would be crazy.

    *Main> [0,3..5]
    [0,3]
    *Main> [0,3..5.0] -- CRAZY!
    [0.0,3.0,6.0]

    Here is a simple but painful example. We define piA to approximate pi by naive numeric integration of the area of a 1/4 pie slice of the unit circle.

    integrate f x0 x1 dt = dt * sum (map f [x0,x0+dt..x1])

    piA dt = 4 * integrate (\x -> sqrt (1 - x^2)) 0 1 dt

    *Main> piA 0.0012
    3.144014392676234
    *Main> piA 0.0011
    3.143797733660182
    *Main> piA 0.0010
    NaN
    *Main> piA 0.0009
    3.143398824144525
    *Main> piA 0.0008
    NaN
    *Main> piA 0.0007
    NaN
    *Main> piA 0.0006
    NaN
    *Main> piA 0.0005
    3.142579506573141
    *Main> piA 0.0004
    3.1423832463242594
    *Main> piA 0.0003
    3.142195370951823
    *Main> piA 0.0002
    3.141989327745062
    *Main> piA 0.0001
    3.141791477784763
    *Main> piA 0.00005
    3.1416922379085954
    *Main> piA 0.00004
    NaN
    *Main> piA 0.00003
    3.1416527395202114
    *Main> piA 0.00002
    NaN
    *Main> piA 0.00001
    3.1416126164823903
    *Main> piA 0.000009
    3.141610659755495
    *Main> piA 0.000008
    3.141608627038413
    *Main> piA 0.000007
    3.141606659811757
    *Main> piA 0.000006
    NaN
    *Main> piA 0.000005
    NaN
    *Main> piA 0.000004
    3.1416006441926987
    *Main> piA 0.000003
    3.1415986563239593
    *Main> piA 0.000002
    NaN
    *Main> piA 0.000001
    NaN

    ReplyDelete
  6. Barak,

    Yes, it's a bit crap. At some point someone decided that Float and Double are instances of Enum and had to make up some semantics for a bunch of functions that don't really make sense for Float and Double. It's easy to see why they chose the implementation they did, but I agree it's not good. Some of the bad type class decisions in the standard prelude are getting addressed and I hope this one will be too.

    ReplyDelete
  7. Anonymous,

    This code avoids IORefs by exploiting a particular feature of the structure of GLUT applications. Avoiding them in general is a different matter entirely. There are too many different ways to structure Haskell code to give a one size fits all solution.

    ReplyDelete
  8. IO already supports linear continuations, but they aren't necessary here.

    yield = do
    ....mvar <- newEmptyMVar
    ....idleCallBack $= Just (tryPutMVar mvar () >> return ())
    ....takeMVar mvar

    You can eliminate all the liftIO and ContT stuff, and simply replace runContT with forkIO.

    ReplyDelete
  9. Very neat!

    You can easily "yield for input" as well:
    https://gist.github.com/1639205

    ReplyDelete
  10. @anders

    Keep writing code along those lines and I wonder if you eventually implement something like iteratees. I haven't thought about iteratees much yet.

    ReplyDelete
  11. I just compiled this with ghc 7.4.1 on Ubuntu 12.04...and it instantly turned my desktop into a static image. Very cool!

    ReplyDelete
  12. Ignore previous comment. Works fine after reboot. Something screwy in Ubuntu desktop.

    ReplyDelete
  13. I don't know what idleCallback does, but this seems like you're using ContT to simulate CoroutineT?

    ReplyDelete