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.

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 (proto.ml):

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

module type Lwt =
sig
val get_board : unit -> int option array array Lwt.t
end
```
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 `proto.ml`, 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 `bind`s easier to read.
```module Server =
Proto_js_clnt.Lwt(struct
let with_client f = f (Orpc_js_client.create "/sudoku")
end)
```
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 `proto.ml`, 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 _ =
ignore
(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
done
done;
Lwt.return ());
false
```
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.