large imperative code --> functional

(note the complementary thread)

Given an imperatively styled program in C, with complex shared state, how would people suggest converting it to functional style?

The program I'm working with is Chromium, which implements a stream-processing model over the OpenGL API, so that the calls from a graphics program (e.g. Quake) get turned into a stream of function calls that can be filtered/modified.

To do this, Chromium contains a "state machine" which tracks all state contained in OpenGL: lighting, raster-position, textures, matrix-stacks, etc. etc.

Via google I found HOGL, a functionalish Haskell binding for OpenGL that lets you do things like:

demo0 = runGraphics ( do
    w <- openWindow "Demo 0" (400, 400)
    print "Demo0 a very simple Hogl program"
    print "press any key to quit"
    draw w (WithColor blue
            (Translate (0,0,-50)
             (Scale (80,80,80)
              (Rotate 36 (1,1,0)
               (cube 1)))))
    getKey w
    closeWindow w

- that is, you can do some state-changes (here setting the current color and changing the modelview matrix) in a functional style.

..anyway, how would people suggest to deal with a large state-machine like that in OpenGL? Are there tools out there for semi-automation of the process?

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

more state components

Here are some other parts of the OpenGL state, just to give an idea of its complexity:

* depth-cueing settings
* buffer/vertex objects
* shading programs & variables
* display-lists
* settings for the various buffers (accumulation, stereo, stencil, ..)
* material definitions
* antialiasing settings
* 3D-to-2D rasterization settings (clipping, viewports, etc.), and some window control
* NURBS surface-equations/programs/"evaluators"
* the "attribute" stacks, allowing pushing/popping of various subsets of the state.

These each effect various parts of the rendering pipeline:
* rasterization and texture-assembly
* pixel, per-vertex and per-fragment operations
* writing into the framebuffer(s).

Chromium also manages the merging of various OpenGL CONTEXTS into a single context. Contexts contain window-system specific state (context-management, visuals, windows, direct-rendering (DRI), swap/framelocking, pbuffers, OpenGL extensions, etc.)

Calculations - Poor Man's Monad

This is a poor man's monad (it exposes state / doesn't use type classes) I use in ML - I still need to clean up the code though, and uhm, actually forgot how most of it works ;-). A calculation is a function which takes a state, and returns a value and a new state.
The nret is equivalent to the monadic return, the nseq is equivalent to the monadic bind. If you can't figure out how it works, please ask and I'll show an example.


type ('m, 'r) calc = 'm -> ('r * 'm)

let nret:'a -> ('m, 'a) calc =

    function a -> function m -> (a,m)

let nseq:(('m, 'a) calc) -> ('a->(('m, 'b) calc)) -> (('m, 'b) calc) =

    function f -> function g -> function m0 ->

        (function (a,m1) -> g a m1) (f m0)

let nseq_discard:(('m, 'a) calc) -> (('m, 'b) calc) -> (('m, 'b) calc) =

    function f -> function g -> nseq f (function _ -> g)

let napply:(('m, 'a) calc) -> ('a -> 'b) -> (('m, 'b) calc) =

    function f -> function g -> nseq f (function x -> nret (g x))

let (<*  ) = nseq

let (<<* ) = nseq_discard

let (<+  ) = napply

let nite:(('m, bool) calc) -> (('m, 'a) calc) -> (('m, 'a) calc) -> (('m, 'a) calc) =

    function i -> function t -> function e ->

        i <* (function b -> if b then t else e)

let rec nwhile:(('m, bool) calc) -> (('m, 'a) calc) -> (('m, unit) calc) =

    function c -> function l -> 

        nite c (l <<* nwhile c l) (nret ())

let rec nforeach:('a list) -> ('a -> (('m, 'b) calc)) -> (('m, unit) calc) =

    function l -> function f -> match l with 

        []      -> nret ()

    | (x::xx) -> f x <<* nforeach xx f


let rec niterate:int->('a->('m, 'a) calc)->('a->('m, 'a) calc) =

    function n -> function f -> function m ->

        if n = 0 then f m else (f m) <* function mm -> niterate (n-1) f mm

let nrun:('m, 'a) calc->'m->'a =

    function n -> function m -> (function (a,m) -> a) (n m)


[Edit:] If you make OpenGL's state abstract and add some functions which operate on the state (see Tim's post) you can use the above combinators to express sequential calculations.

[Replaced it with HTML stuff since it didn't display right]

Display Lists

Immediate mode OpenGL is gratuitously imperative. Keep in mind that the approach described above isn't functional; it's an imperative program abstracted over Haskell's IO Monad.

A pure functional approach would be to regard graphics rendering as a pure operation Render :: DisplayList -> FrameBuffer, where a DisplayList is a list of elements of an algebraic datatype describing all OpenGL operations, and FrameBuffer is perhaps a 2D array of RGBA pixel values. Rendering, at that level, is purely functional, in that the output of Render should (at least for a sane device) be a referentially transparent function of its parameter.

display lists vs. "primitives"

Yes, DisplayList -> FrameBuffer is a functional description, but I was thinking of a richer one.

As a concrete example, rendering a scene might consist of specifying a drawing buffer, camera, lighting, and specular + diffuse color components for a material, followed by passing some polygons.

Without passing the polygons, the camera, lighting, etc. are essentially a No-Op: they do nothing to the buffer.

Thus we could say those OpenGL functions which change the framebuffer are the "primitives", and the others just specify parameters to those primitives.

Or, looking at the actual hardware implementation of OpenGL, there are several stages of the "graphics pipeline". Some API calls affect the higher-level (upstream) operations (e.g. transformation matrices), some mid-level (e.g. lighting), some lower (raster-position, pixel operations).

More generally, its a very complex imperative system where operations can have very non-local side-effects. [Edit: basically there are lots of global variables]
I'm interested in how one might convert this to a side-effect-free model, without always specifying the ENTIRE state of the system.

I could of course simulate an entire GPU (graphics processing unit) in a functional language. This is what Chromium does, but imperatively; I just want to reuse this existing code (without writing a functional C interpreter :).

So here's what I'd do. Note t

So here's what I'd do. Note that I don't know a whole lot about OpenGL in particular, but I do have some experience functionalizing stateful APIs.

First, at the bottom level, I'd use a monad to encapsulate the state of the state machine. At this level, I would look at the state transition diagram for the API, and then try to capture that in the monadic API using phantom types. This would let you do more compile time error-checking than the C API to help ensure that procdures are only being called at the right times (eg, you can call certain functions only after initialization).

Then, I'd look for things that would let the programmer operate at a higher level. There are two big patterns here.

First, there are the "with-foo" API patterns, which look like this:

1. You call an initialization function to go into a certain mode foo.
2. You call operations to build up something and eventually run it.
3. You then call a cleanup function to leave the foo state and return to your original mode.

These APIs are the ones that are most easily "functionalized". Write a single function that takes some data and then does the mode switching "under the covers".

Secondly, imperative APIs often have iterator APIs, which let you statefully traverse some data structure. Encapsulate these, giving the programmer a fold or a map with a purer type. This lets you drop the iterator state from the API.

After doing this, hide the low-level functions from the user API, and simplify the transition diagram, and see if you can't repeat the process. Eventually, you'll converge on something that looks somewhat functional.

Then, try writing some programs, and keep an eye out for common patterns of use. Use these to build additional combinators. One of the key advantages of a monadic interface is that you can treat commands as first-class values, and this lets you write custom control structures very easily.


[This was supposed to be a reply to neelk's post]

Can you point me to an example of the result of this kind of process?

thanks for all the replies, BTW.