Sunday, April 26, 2009

Sudoku in ocamljs, part 1: DOM programming

Let's make a Sudoku game with ocamljs and the Dom library for programming the browser DOM. Like on the cooking shows, I have prepared the dish we're about to make beforehand; why don't you taste it now? OK, it is not yet Sudoku, lacking the important ingredient of some starting numbers to guide the game--we'll come back to that next time.

module D = Dom
let d = D.document
We begin with some definitions. The Dom module includes class types for much of the standard browser DOM, using the ocamljs facility for interfacing with Javascript objects. Dom.document is the browser document object.
let make_board () =
  let make_input () =
    let input = (d#createElement "input" : D.input) in
    input#setAttribute "type" "text";
    input#_set_size 1;
    input#_set_maxLength 1;
    let style = input#_get_style in
    style#_set_border "none";
    style#_set_padding "0px";
    let enforce_digit () =
      match input#_get_value with
        | "1" | "2" | "3" | "4" | "5"
        | "6" | "7" | "8" | "9" -> ()
        | _ -> input#_set_value "" in
    input#_set_onchange (Ocamljs.jsfun enforce_digit);
    input in
We construct the Sudoku board in several steps. First, we make an input box for each square. Notice that you can call DOM methods (e.g. createElement) with OCaml object syntax. But what is the type of createElement? The type of the object you get back depends on the tag name you pass in; OCaml has no type for that. So createElement is declared to return #element (that is, a subclass of element). If you need only methods from element then you usually don't need to ascribe a more-specific type, but in this case we need an input node. (Static type checking with Javascript objects is therefore only advisory in some cases--if you ascribe the wrong type you can get a runtime error--but still better than nothing.)

We next set some attributes, properties, and styles on the input box. Properties are manipulated with specially-named methods: foo#_get_bar becomes foo.bar in Javascript, and foo#_set_bar baz becomes foo.bar = baz. Finally we add a validation function to enforce that the input box contains at most a single digit. To set the onchange handler, you need to wrap it in Ocamljs.jsfun, because the calling convention of an ocamljs function is different from that of plain Javascript function (to accomodate partial application and tail recursion).

  let make_td i j input =
    let td = d#createElement "td" in
    let style = td#_get_style in
    style#_set_borderStyle "solid";
    style#_set_borderColor "#000000";
    let widths = function
      | 0 -> 2, 0 | 2 -> 1, 1 | 3 -> 1, 0
      | 5 -> 1, 1 | 6 -> 1, 0 | 8 -> 1, 2
      | _ -> 1, 0 in
    let (top, bottom) = widths i in
    let (left, right) = widths j in
    let px k = string_of_int k ^ "px" in
    style#_set_borderTopWidth (px top);
    style#_set_borderBottomWidth (px bottom);
    style#_set_borderLeftWidth (px left);
    style#_set_borderRightWidth (px right);
    ignore (td#appendChild input);
    td in
Next we make a table cell for each square, containing the input box, with borders according to its position in the grid. Here we don't ascribe a type to the result of createElement since we don't need any td-specific methods.
  let rows =
    Array.init 9 (fun i ->
      Array.init 9 (fun j ->
        make_input ())) in

  let table = d#createElement "table" in
  table#setAttribute "cellpadding" "0px";
  table#setAttribute "cellspacing" "0px";
  let tbody = d#createElement "tbody" in
  ignore (table#appendChild tbody);
  ArrayLabels.iteri rows ~f:(fun i row ->
    let tr = d#createElement "tr" in
    ArrayLabels.iteri row ~f:(fun j cell ->
      let td = make_td i j cell in
      ignore (tr#appendChild td));
    ignore (tbody#appendChild tr));

  (rows, table)
Then we assemble the full board: make a 9 x 9 matrix of input boxes, make a table containing the input boxes, then return the matrix and table. Notice that we freely use the OCaml standard library. Here the tbody is necessary for IE; the cellpadding and cellspacing don't work in IE for some reason that I have not tracked down. This raises an important point: the Dom module is the thinnest possible wrapper over the actual DOM objects, and as such gives you no help with cross-browser compatibility.
let check_board rows _ =
  let error i j =
    let cell = rows.(i).(j) in
    cell#_get_style#_set_backgroundColor "#ff0000" in

  let check_set set =
    let seen = Array.make 9 None in
    ArrayLabels.iter set ~f:(fun (i,j) ->
      let cell = rows.(i).(j) in
      match cell#_get_value with
        | "" -> ()
        | v ->
            let n = int_of_string v in
            match seen.(n - 1) with
              | None ->
                  seen.(n - 1) <- Some (i,j)
              | Some (i',j') ->
                  error i j;
                  error i' j') in

  let check_row i =
    check_set (Array.init 9 (fun j -> (i,j))) in

  let check_column j =
    check_set (Array.init 9 (fun i -> (i,j))) in

  let check_square i j =
    let set = Array.init 9 (fun k ->
      i * 3 + k mod 3, j * 3 + k / 3) in
    check_set set in

  ArrayLabels.iter rows ~f:(fun row ->
    ArrayLabels.iter row ~f:(fun cell ->
      cell#_get_style#_set_backgroundColor "#ffffff"));

  for i = 0 to 8 do check_row i done;
  for j = 0 to 8 do check_column j done;
  for i = 0 to 2 do
    for j = 0 to 2 do
      check_square i j
    done
  done;
  false
Now we define a function to check that the Sudoku constraints are satisfied: that no row, column, or heavy-lined square has more than one occurrence of a digit. If more than one digit occurs then we color all occurrences red. The only ocamljs-specific parts here are getting the cell contents (with _get_value) and setting the background color style. However, it's worth noticing the algorithm: we imperatively clear the error states for all cells, then set error states as we check each constraint. I'll revisit this in a later post about functional reactive programming.
let onload () =
  let (rows, table) = make_board () in
  let check = d#getElementById "check" in
  check#_set_onclick (Ocamljs.jsfun (check_board rows));
  let board = d#getElementById "board" in
  ignore (board#appendChild table)

;;

D.window#_set_onload (Ocamljs.jsfun onload)
Finally we put the pieces together: make the board, insert it into the DOM, call check_board when the Check button is clicked, and call this setup code once the document has been loaded. See the full source for build files.

By writing this in OCaml rather than directly in Javascript, we've gained the assurance of static type checking; we get to use OCaml's syntax, pattern matching, and standard library; we have a for loop that's not broken. On the flip side we have to worry about type ascription and Ocamljs.jsfun. If you don't already think that OCaml is a better language than Javascript, this won't convince you. But perhaps the followup posts, in which I'll show how to use RPC over HTTP with orpc and functional reactive programming with froc, will tip the scales for you.

Thursday, April 23, 2009

Monadic functional reactive AJAX in OCaml

Yesterday I released three related projects which I've been working on for a long time:
  • ocamljs, a Javascript backend for ocamlc, along with some libraries for web programming
  • orpc, a tool for generating RPC stubs from OCaml signatures, either ONC RPC for use with Ocamlnet's RPC implementation, or RPC over HTTP for use with ocamljs
  • froc, a library for functional reactive programming that works with ocamljs
The idea of all this is to build a platform for client-side web programming like Google Web Toolkit (but better, of course :). There is still a lot of work to get there, but already we use ocamljs and orpc for production work at Skydeck. In my next few posts I'll work through some examples using ocamljs, orpc, and froc: