Lambda the Ultimate

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]

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 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.