A functional game loop for GLUT in Scheme using continuations

Lately I have decided to learn more about functional programming. I've become very attracted to the elegance of ideas about lazy evaluation and immutability and expression of a program in terms of pure functions. In particular I am drawn to the idea of describing a program in terms of streams, also called lazy lists. I think about simulation problems a lot—game loops, if you want—and I wanted to see how I might write “time step”-oriented programs in a functional language. I really like the idea of expressing the whole thing literally as a function of time—the simulation as a single giant function applied to an infinite list of time steps.

Anyways, I decided to do this using Scheme, after reading SICP. Actually, things like lazy evaluation and immutability are much more innate in either Haskell or Clojure. I would like to learn more about both these languages, but for the moment I'm using Scheme: I don't want to code for the JVM for now (this is just a personal bias), and I don't feel like expending the effort to learn Haskell—I just want to code. I'll probably learn it eventually, but Scheme is so minimal that I picked it up pretty much right away, and so I'm going with it for now. Additionally there are a bunch of compilers for it that can produce native code and call out to C libraries, which is an environment I'm just much more comfortable with compared to going the JVM route. I'm using Gambit-C at the moment. I'd love a compile-to-machine-code Lisp more similar to Clojure, but as far as I can tell no such thing exists. I tried Liskell but the site is down and I can't get it to compile.

In any case, this post is not about choice of language, so I'll move on. Basically, I decided to use Scheme, but try to avoid any of its imperative features. This means no set! and no usage of multi-line begin statements. The first problem I immediately ran into when learning how to open a GLUT window was that its callback-oriented nature makes it almost impossible to avoid using global variables to pass state around, which is exactly what I wanted to avoid.

I asked on Stack Overflow how I might keep my program strictly functional and still deal with a callback-based API, but didn't get any satisfactory answers. However, very soon after posing the question I came up with something that I think is quite elegant, and keeps set! usage to an absolute minimum.

Basically this solution can be summarized as using co-routines to separate GLUT from the rest of my program, and hiding the communication between them in a lazy list. This makes the program appear to be a function applied to a list, but accessing this lazy list blocks the program until a GLUT callback wakes it up again.

I won't include all the code here, just the main loop. I used the glut.scm and opengl.scm files from David St-Hilaire's Space Invaders clone. Also, I defined some fairly standard lazy list functions using delay and force, which was quite a good exercise to figure out. As part of this little lazy toolkit, I defined a function called lazy-stream which takes an initial item and a function to generate the next item.

(define (lazy-stream i f . u)
  (cons i (delay (let ((x (f i u)))
                    (lazy-stream (car x) f (cdr x))))))

This allowed me to define the event list as follows:

(define event-list
  (lazy-stream '((io-state . 0)
                 (pos . (10. . 10.))
                 (vel . (2 . 1)))
               get-next-glut-event))

So we can see that the event-list is a lazy list that starts with a state (an associative list, here it just has a position and velocity, as well as this mysterious io-state which will be explained later), and then calls a function get-next-glut-event to produce a list of events. This is of course going to be a blocking function with side-effects. The whole program is then simply a reduce operation on this list:

(lazy-reduce
  handle-event
  event-list)

This call to lazy-reduce doesn't finish until the program is ready to exit.

So the program is nothing but a function to “reduce” the event list to the program exit event! It must be a reduce of course, map here would not make sense since the events are ordered and map is not an ordered operation. On the other hand, by definition reduce (also known as left-fold) must process the previous list item before applying the next.

It is inherently a non-lazy operation: it must process the whole list before returning. Also by definition, the function provided must take as input the previously calculated value. (Think of reducing a list of integers using +. It takes the previous value and a new argument, producing the value to be passed to the next list item.) So it can safely act as our game loop driver, since it imposes well-ordered, driven processing of the simulation event list. Since the state is “passed along”, there is no need for global variables, and the state can remain completely immutable. (I'm sure there exist plenty of previous examples of people using reduce in such a way, but I was happy to have thought of it.)

We'll discuss handle-event later, but first let's talk a bit about GLUT. We have this function get-next-glut-event which returns the next requested action from GLUT. Wait a minute, if you have any C experience with GLUT you'll know that this isn't traditionally how GLUT works. You register callbacks with GLUT, and it calls these functions when it wants something to happen. You can register display events to draw on the screen, and optionally timer events, keyboard and mouse input events, etc. Then you call glutMainLoop which never returns. So how did we “invert” things like this, and call out to GLUT?

The answer is using Scheme's call/cc to set up a co-routine which handles GLUT for us, effectively isolating its imperative nature from the rest of our program. Let's look at get-next-glut-event:

(define return-to-glut 0)
(define return-to-main 0)

(define (get-next-glut-event x u)
  (list
   (call/cc (lambda (c) (set! return-to-main c) (return-to-glut)))))

We store the co-routine pointer (a function which, when called, starts immediately after the call/cc line) in a variable called return-to-main. We then call a previously initialized function called return-to-glut. This basically ends the current co-routine—the call to call/cc will never return. However, since we stored our current continuation in return-to-main, someone can call it and resume where we left off. When this eventually happens, the result is returned in a list, so that it gets tacked onto the lazy event-list and then processed by lazy-reduce. This is exactly why it's okay to have side-effects at this point in the program: lazy-reduce ensures the correct ordering of their evaluation by its functional definition, rather than by relying on Scheme's imperative evaluation rules.

Immediately before calling lazy-reduce, we set up a seperate continuation for the GLUT side of the co-routine:

(call/cc (lambda (c)
            (set! return-to-main c)
            (init-glut)
            (glutMainLoop)))

init-glut simply initializes GLUT. At this point the program is still sort of in an “imperative” set-up phase, so I let the fact that this routine uses imperative programming slide a little. We'll worry about how to deal with this properly when we discuss handle-event. Note that the c-declare and c-lambda calls are part of Gambit-C's FFI and are taken from the Space Invaders program. They simply set up some required arguments for glutInit, which is a C function.

; GLUT initialization
(c-declare "int argc = 0;")
(define (init-glut)
  (let ((argc ((c-lambda () (pointer int) "___result_voidstar = &argc;"))))
    (glutInit argc '())
    (glutInitDisplayMode (bitwise-ior GLUT_DOUBLE GLUT_RGBA))
    (glutInitWindowPosition 100 100)
    (glutInitWindowSize 300 300)
    (glutCreateWindow "gltest")
    (glutReshapeFunc reshape)
    (glutDisplayFunc display)
    (glutTimerFunc 1000 timer 0)
    (yield-to-main 'reshape 300 300)))

At the end of this function yield-to-main is called with some arguments.

(define (yield-to-main . x)
  (call/cc (lambda (c) (set! return-to-glut c) (return-to-main x))))

This function allows GLUT code to jump back into the functional part of the program. (Notice how ''call/cc'' is a bit like a goto.) We can see that it calls the main program with the arguments, which is how we can pass information between the co-routines.

Let's look at the GLUT event callback handlers. They are quite short:

; GLUT display event
(c-define (display) () void "display" ""
          (yield-to-main 'display))

; GLUT reshape event
(c-define (reshape w h) (int int) void "reshape" ""
          (yield-to-main 'reshape w h))

; GLUT timer event
(c-define (timer i) (int) void "timer" ""
          (yield-to-main 'timer))

So here you can see that the GLUT callbacks are simply used to grab events, and put them on the event-list, which is then processed in parallel by the main program. Co-routines are sort of like threads that must explicitly yield to each other, but their state is maintained within themselves, not globally. Only a tiny bit of global information is needed to pass continuations back and forth. In this way, GLUT sort of takes a back seat to the main program, which from its point of view remains “purely” functional. It's nice how this technique lets you invert the way GLUT usually takes over and becomes the main driver for your program, and instead flips it over and turns it into something that your main program requests events from. This idea of turning push into pull and vice-versa seems to be a common theme in functional programming.

I'll hold off on providing the complete code until next time, when I describe the handle-event function, in which I used a different method to handle side effects.