Sunday, 6 May 2012

Easy parallelism in OCaml


Use the following invoke combinator to apply a function to a value in another (forked) process and then block waiting for its result when the () value is applied:
  let invoke (f : 'a -> 'b) x : unit -> 'b =
    let input, output = Unix.pipe() in
    match Unix.fork() with
    | -1 -> (let v = f x in fun () -> v)
    | 0 ->
        Unix.close input;
        let output = Unix.out_channel_of_descr output in
        Marshal.to_channel output (try `Res(f x) with e -> `Exn e) [];
        close_out output;
        exit 0
    | pid ->
        Unix.close output;
        let input = Unix.in_channel_of_descr input in
        fun () ->
          let v = Marshal.from_channel input in
          ignore (Unix.waitpid [] pid);
          close_in input;
          match v with
          | `Res x -> x
          | `Exn e -> raise e

Which functional language for use with LLVM?


OCaml is the only functional language with bindings in the LLVM distro itself and documentation on llvm.org such as the Kaleidoscope tutorial. If you have OCaml installed when you build and install LLVM then it will automatically build and install the LLVM bindings for OCaml as well. Moreover, these OCaml bindings have been in use for years so they are mature and reliable.
I have been developing HLVM in OCaml using the standard LLVM bindings and found OCaml+LLVM to be an extremely powerful combination. HLVM provides tuples, arrays, unions, TCO of all tail calls, generic printing, FFI to C, JIT compilation and parallel garbage collection with a VM weighing in at under 2kLOC of OCaml code that took only a few man-weeks to develop from scratch. HLVM's numerical performance already far exceeds that of today's fastest open source FPLs including OCaml itself. I have published articles in the OCaml Journal describing how LLVM can be used from OCaml for everything from basic expression evaluation to advanced topics such as parallelism and garbage collection. You may also like this mini example.

Friday, 4 May 2012

Map and fold functions that are generic over the kind of collection


There are two main solutions in OCaml:
  1. Jacques Garrigue already implemented a syntactically-light but inefficient approach for many data structures several years ago. You just wrap the collections in objects that provide a map method. Then you can do collection#map to use the map function for any kind of collection. This is general because it allows different kinds of data structures to be substituted at run time. However, this is not very useful in practice so the approach was never widely adopted.
  2. A syntactically-heavier but efficient, robust and static solution is to use functors to parameterize your code over the data structure you are using. This makes it trivial to reuse your code with different data structures. See Markus Mottl's OCaml translations of Okasaki's book "Purely Functional Data Structures" for some great examples.
If you aren't looking for that kind of power and just want brevity then, of course, you can just create a module alias with a shorter name (e.g. module S = String).