Sunday, May 3, 2009

Sudoku in ocamljs, part 2: RPC over HTTP

Last time we made a simple user interface for Sudoku with the Dom module of ocamljs. It isn't a very fun game though since there are no pre-filled numbers to constrain the board. So let's add a button to get a new game board; here's the final result.

I don't know much about generating Sudoku boards, but it seems like it might be slow to do it in the browser, so we'll do it on the server, and communicate to the server with OCaml function calls using the RPC over HTTP support in orpc.

The 5-minute monad

But first I'm going to give you a brief introduction to monads (?!). Bear with me until I can explain why we need monads for Sudoku, or skip it if this is old hat to you. We'll transform the following fragment into monadic form:

let foo () = 7 in
bar (foo ())
First put it in named form by let-binding the result of the nested function application:
let foo () = 7 in
let f = foo () in
bar f
Then introduce two new functions, return and bind:
let return x = x
let bind x f = f x

let foo () = return 7 in
bind (foo ()) (fun f ->
  bar f)
These functions are a bit mysterious (although the name "bind" is suggestive of let-binding), but we haven't changed the meaning of the fragment. Next we would like to enforce that the only way to use the result of foo () is by calling bind. We can do that with an abstract type:
type 'a t
val return : 'a -> 'a t
val bind  : 'a t -> ('a -> 'b t) -> 'b t
Taking type 'a t = 'a, the definitions of return and bind match this signature. So what have we accomplished? We've abstracted out the notion of using the result of a computation. It turns out that there are many useful structures matching this signature (and satisfying some equations), called monads. It's convenient that they all match the same signature, in part because we can mechanically convert ordinary code into monadic code, as we've done here, or even use a syntax extension to do it for us.

Lightweight threads in Javascript

One such useful structure is the Lwt library for cooperative threads. You can write Lwt-threaded code by taking ordinary threaded code and converting it to monadic style. In Lwt, 'a t is the type of threads returning 'a. Then bind t f calls f on the value of the thread t once t has finished, and return x is an already-finished thread with value x.

Lwt threads are cooperative: they run until they complete or block waiting on the result of another thread, but aren't ever preempted. It can be easier to reason about this kind of threading, because until you call bind, there's no possibility of another thread disturbing any state you're working on.

Lwt threads are a great match for Javascript, which doesn't have preemptive threads (although plugins like Google Gears provide them), because they need no special support from the language except closures. Typically in Javascript you write a blocking computation as a series of callbacks. You're doing essentially the same thing with Lwt, but it's packaged up in a clean interface.

Orpc for RPC over HTTP

The reason we care about threads in Javascript is that we want to make a blocking RPC call to the server to retrieve a Sudoku game board, without hanging the browser. We'll use orpc to generate stubs for the client and server. In the client the call returns an Lwt thread, so you need to call bind to get the result. In the server it arrives as an ordinary procedure call.

To use orpc you write down the signature of the RPC interface, in Lwt and Sync forms for the client and server. Orpc checks that the two forms are compatible, and generates the stubs. Here's our interface (

module type Sync =
  val get_board : unit -> int option array array

module type Lwt =
  val get_board : unit -> int option array array Lwt.t
The get_board function returns a 9x9 array, each cell of which may contain None or Some k where k is 1 to 9. We can't capture all these constraints in the type, but we get more static checking than if we were passing JSON or XML.

Generating the board

On the server, we implement a module that matches the Sync signature. (You can see that I didn't actually implement any Sudoku-generating code, but took some fixed examples from Gnome Sudoku.) Then there's some boilerplate to set up a Netplex HTTP server and register the module at the /sudoku path. It's pretty simple. The Proto_js_srv module contains stubs generated by orpc from, and Orpc_js_server is part of the orpc library.

Using the board

The client is mostly unchanged from last time. There's a new button, "New game", that makes the RPC call, then fills in the board from the result.

let (>>=) = Lwt.(>>=)
The >>= operator is another name for bind. If you aren't using pa_monad (which we aren't here), it makes a sequence of binds easier to read.
module Server =
    let with_client f = f (Orpc_js_client.create "/sudoku")
This sets up the RPC interface, so calls on the Server module become RPC calls to the server. The Proto_js_client module contains stubs generated from, and Orpc_js_client is part of the orpc library. (In the actual source you'll see that I faked this out in order to host the running example on Google Code--there's no way to run an OCaml server, so I randomly choose a canned response.)
let get_board rows _ =
    (Server.get_board () >>= fun board ->
      for i = 0 to 8 do
        for j = 0 to 8 do
          let cell = rows.(i).(j) in
          let style = cell#_get_style in
          style#_set_backgroundColor "#ffffff";
          match board.(i).(j) with
            | None ->
                cell#_set_value "";
                cell#_set_disabled false
            | Some n ->
                cell#_set_value (string_of_int n);
                cell#_set_disabled true
      Lwt.return ());
This is the event handler for the "New game" button. We call get_board, bind the result, then fill in the board. If there's a number in a cell we disable the input box so the player can't change it. Here's the full code.

Doing AJAX programming with orpc and Lwt really shows off the power of compiling OCaml to Javascript. While Google Web Toolkit has a similar RPC mechanism (that generates stubs from Java interfaces), it's much clumsier to use, because you're still working at the level of callbacks rather than threads. Maybe you could translate Lwt to Java, but it would be painfully verbose without type inference.

This monad stuff will come in handy again next time, when we'll revisit the problem of checking the Sudoku constraints on the board, using froc.

No comments:

Post a Comment