A Curious Programmer

It can be tempting when learning a new language to start with basic tutorials and only when some level of mastery has been achieved to try and use it for real work. The drawback with this approach, is that by the time it becomes clear that a particular task you need to solve is very difficult with a particular language, you have already invested a huge amount of time. Consider a language eco-system: syntax, libraries, tools and community are all part of a language and need to be learned in order to become adept.

I find Ocaml an exceptionally impressive piece of software: It bootstraps a very fast native-code compiler using just a C compiler on a variety of platforms, it includes a fast bytecode virtual machine, it has an extensive standard library and it includes a number of extremely useful tools that aren’t necessary included with other minority languages such as a debugger and a profiler. Additionally, although I’ve only been using it a few weeks, I’ve found it a nice language to use. I really like developing with a REPL and I definitely like something about static-typing. I like dynamic typing too and list scheme and perl among languages I enjoy using. Of course, like every language, it has its drawbacks, but are there any deal-breakers?

As a software developer, I (usually) much prefer to use good code that someone else has written than write code myself, or (perhaps in manager-speak) to “leverage” third-party code. Even in the biggest software universes available, .NET or the Java platform, it is highly likely that someone outside the core development teams will have produced something I will find useful. Additionally, despite being very much a Unix developer, I frequently want my code to run on both Windows and Linux.

Note that the following experience should be taken with a large pinch of salt as I have only tried to install one extension, that extension is implicitly advertised as being of beta-quality with a version number of less than 1 and I have asked for no help on the Ocaml mailing-list. I do believe that it should be possible to install extensions without assistance.

I tried to install the ostap parser combinators extension. This library is available here. I could have easily solved my problem using GenLexer from the standard library but I thought I might as well find out how painful it is to install extensions as I will probably do it one day. ostap relies on two other libraries from the same author: Logger and TypeUtil, both of which (as far as I can remember) use camlp4 which is the Ocaml syntax extension tool.

I have a basic MinGW / MSYS setup on my Windows box so I thought I would use that to install the extensions despite the fact that it wasn’t the recommended approach. The extensions use the configure/automake stuff to generate the makefile which didn’t work so well.

During the configure stage it appears to have got confused about which slash is correct for pathnames:

checking for CamlP4 library path... C:\Program Files\Objective Caml\lib/camlp4

And then it hung while making:

make[1]: Leaving directory `/tmp/logger-0.3/regression'
make[1]: Entering directory `/tmp/logger-0.3'
/bin/sh: mktemp: command not found
/bin/sh: $tmp_version: ambiguous redirect
/bin/sh: $tmp_version: ambiguous redirect

Drat! Okay fair enough – it isn’t the recommended method. I thought I’ll try to install it on linux/x86 which must be the best supported platform and then transplant the compile commands used onto Windows. However, that didn’t work out either. It complained about missing .cma files which actually did exist within the Ocaml build tree and I needed to manually copy them across into the install directory. Then, when trying to build the sample.ml I got this:

Warning: File "sample.ml", line 12, chars 31-32: Invalid backslash escape in string
Warning: File "sample.ml", line 12, chars 45-46: Invalid backslash escape in string

And then:

ocamlopt.opt -w p -I <ocaml-root>/lib/ocaml/site-lib/typeutil -I <ocaml-root>/lib/ocaml/camlp4 -I ../src -o sample.opt typeutil.cmxa camlp4.cmxa str.cmxa ostap.cmxa sample.cmx
Cannot find file camlp4.cmxa

$ find <ocaml-root> | egrep 'camlp4\.'
<ocaml-root>/man/man1/camlp4.1
<ocaml-root>/man/man1/mkcamlp4.1
<ocaml-root>/lib/ocaml/camlp4/camlp4.cma

$ find <ocaml-root> | egrep '\.cmxa$'
<ocaml-root>/lib/ocaml/threads/threads.cmxa
<ocaml-root>/lib/ocaml/nums.cmxa
<ocaml-root>/lib/ocaml/str.cmxa
<ocaml-root>/lib/ocaml/stdlib.cmxa
<ocaml-root>/lib/ocaml/bigarray.cmxa
<ocaml-root>/lib/ocaml/dbm.cmxa
<ocaml-root>/lib/ocaml/camlp4/gramlib.cmxa
<ocaml-root>/lib/ocaml/stdlib.p.cmxa
<ocaml-root>/lib/ocaml/unix.cmxa
<ocaml-root>/lib/ocaml/site-lib/typeutil/typeutil.cmxa
<ocaml-root>/lib/ocaml/site-lib/ostap/ostap.cmxa

I did try to compile the appropriate missing files into cmxa variants manually but this stumped me too. So, what next? If I can’t getI haven’t given up on Ocaml quite yet, but I am disappointed with some of the problems I encountered. I’ll probably take a break and go back to PLT Scheme for a while, now I’ve discovered that it is more like 20 times slower than C++ than 300 (just for certain tasks of course)! Then I’ll try to install some more mature extensions and if that fails then Ocaml is not for me.

Read Full Post »

Jon Harrop spotted that the Ocaml code was calling is_threatened 64515 times compared to the C++ calling is_threatened just 1915 times. I eventually spotted the bug in the C++ code: next_valid_posn was not correctly iterating through the x positions. The fix was straight-forward:

    Posn next_valid_posn(const Posn& p) const {
        for (int y = p.y_; y < size_; y++) {
            int initX = (y == p.y_) ? (p.x_ + 1) : 0;
            for (int x = initX; x < size_; x++) {
                if (ref(x, y) == Safe) { return Posn(x, y); }
            }
        }

        return Posn(-1, -1);
    }

and now the C++ and Ocaml are much more closely matched. The fixed C++ completes 100 solutions in 9.5 seconds and the Ocaml completes 100 solutions in 19.3 seconds.

Andrej Bauer on the Ocaml mailing list came up with an attractive translation from my C++ which duplicates the bug of not covering all of the x positions. I’ve attached it below.

Thanks for the help to everyone on the Ocaml mailing list.

(* Andrej Bauer's solution *)
type square = Qu | Safe | At

(* A board is an array of arrays of squares *)
type board = square array array

type posn = int * int

let string_of_square = function
  | Qu   -> "Qu"
  | Safe -> "#f"
  | At   -> "At"

let init_pos = (0,0)

let get board (x,y) = board.(y).(x)

let display board =
  Array.iter
    (fun row ->
       Array.iter (fun square -> print_string (string_of_square square ^ " ")) row ;
       print_newline ()
    )
    board

let build size f =
  Array.init size (fun y -> Array.init size (fun x -> f (x,y)))

let is_threatened (x1,y1) (x2,y2) =
  x1 = x2 || y1 = y2 || (x2 - x1) = (y2 - y1) || (x1 - y2) = (x2 - y1)

let add_queen board p =
  build
    (Array.length board)
    (fun q ->
       if q = p then
	 Qu
       else
	 match get board q with
	   | Safe when is_threatened q p -> At
	   | square -> square)

exception No_solution

(* This function is the equivalent of Board::placement. *)
let rec solve board p rem =
  let size = Array.length board in
  let next_posn (px,_) (x,y) =
      if x + 1 < size then (x+1, y)
      else if y + 1 < size then (px, y+1)
      else raise No_solution
  in
  let next_valid_posn p =
    let rec loop q =
      match get board q with
	| Safe -> q
	| _ -> loop (next_posn p q)
    in
      loop p
  in
    if rem = 0 then
      board
    else
      let p' = next_valid_posn p in
	try
	  solve (add_queen board p') init_pos (rem-1)
	with No_solution -> solve board (next_posn p p') rem

let main =
  try
    let size = int_of_string Sys.argv.(1) in
    let times = int_of_string Sys.argv.(2) in
    let empty_board = build size (fun _ -> Safe) in
      for i = 2 to times do
	ignore (solve empty_board (0,0) 8 )
      done ;
      display (solve empty_board (0,0) 8 )
  with
    | No_solution -> print_endline "No solution."
    | _ -> print_endline ("Usage: " ^ Sys.argv.(0) ^ " [size] [times]")

Read Full Post »