Showing posts with label ocaml. Show all posts
Showing posts with label ocaml. Show all posts

Monday, December 23, 2013

Gen_server in Ocaml

Note, this post is written against the 2.0.1 version of gen_server

Erlang comes with a rich set of small concurrency primitives to make handling and manipulating state easier. The most generic of the frameworks is the gen_server which is also the most commonly used. A gen_server provides a way to control state over multiple requests. It serializes operations and handles both synchronous and asynchronous communication with clients. The strength of a gen_server is the ability to create multiple, lightweight, servers inside an application where each operation inside of it runs in serial but individually the gen_servers run concurrently.

While it is not possible to provide all of the Erlang semantics in Ocaml, we can create something roughly analogous. We can also get some properties that Erlang can not give us. In particular, the implementation of gen_server provided here:

Tuesday, July 9, 2013

Experimenting in API Design: Riakc

Disclaimer: Riakc's API is in flux so not all of the code here is guaranteed to work by the time you read this post. However the general principles should hold.

While not perfect, Riakc attempts to provide an API that is very hard to use incorrectly, and hopefully easy to use correctly. The idea being that using Riakc incorrectly will result in a compile-time error. Riakc derives its strength from being written in Ocaml, a language with a very expressive type system. Here are some examples of where I think Riakc is successful.

Siblings

In Riak, when you perform a GET you can get back multiple values associated with the a single key. This is known as siblings. However, a PUT can only associate one value with a key. However, it is convenient to use the same object type for both GET and PUT. In the case of Riakc, that is a Riakc.Robj.t. But, what to do if you create a Robj.t with siblings and try to PUT? In the Ptyhon client you will get a runtime error. Riakc solves this by using phantom types. A Robj.t isn't actually just that, it's a 'a Robj.t. The API requires that 'a to be something specific at different parts of the code. Here is the simplified type for GET:

val get :
  t ->
  b:string ->
  string ->
  ([ `Maybe_siblings ] Robj.t, error) Deferred.Result.t

And here is the simplified type for PUT:

val put :
  t ->
  b:string ->
  ?k:string ->
  [ `No_siblings ] Robj.t ->
  (([ `Maybe_siblings ] Robj.t * key), error) Deferred.Result.t

The important part of the API is that GET returns a [ `Maybe_siblings ] Riak.t and PUT takes a [ `No_siblings ] Riak.t. How does one convert something that might have siblings to something that definitely doesn't? With Riakc.Robj.set_content

val set_content  : Content.t -> 'a t -> [ `No_siblings ] t

set_content takes any kind of Robj.t, and a single Content.t and produces a [ `No_siblings ] Riak.t, because if you set contents to one value obviously you cannot have siblings. Now the type system can ensure that any call to PUT must have a set_content prior to it.

Setting 2i

If you use the LevelDB backend you can use secondary indices, known as 2i, which allow you to find a set of keys based on some mapping. When you create an object you specify the mappings to which it belongs. Two types are supported in Riak: bin and int. And two query types are supported: equal and range. For example, if you encoded the time as an int you could use a range query to find all those keys that occurred within a range of times.

Riak encodes the type of the index in the name. As an example, if you want to allow people to search by a field called "foo" which is a binary secondary index, you would name that index "foo_bin". In the Python Riak client, one sets an index with something like the following code:

obj.add_index('field1_bin', 'val1')
obj.add_index('field2_int', 100000)

In Riakc, the naming convention is hidden from the user. Instead, the the name the field will become is encoded in the value. The Python code looks like the following in Riakc:

let module R = Riakc.Robj in
let index1 =
  R.index_create
    ~k:"field1"
    ~v:(R.Index.String "val1")
in
let index2 =
  R.index_create
    ~k:"field2"
    ~v:(R.Index.Integer 10000)
in
R.set_content
  (R.Content.set_indices [index1; index2] content)
  robj

When the Robj.t is written to the DB, "field1" and "field2" will be transformed into their appropriate names.

Reading from Riak results in the same translation happening. If Riakc cannot determine the type of the value from the field name, for example if Riak gets a new index type, the field name maintains its precise name it got from Riak and the value is a Riakc.Robj.Index.Unknown string.

In this way, we are guaranteed at compile-time that the name of the field will always match its type.

2i Searching

With objects containing 2i entries, it is possible to search by values in those fields. Riak allows for searching fields by their exact value or ranges of values. While it's unclear from the Riak docs, Riakc enforces the two values in a range query are of the same type. Also, like in setting 2i values, the field name is generated from the type of the value. It is more verbose than the Python client but it enforces constraints.

Here is a Python 2i search followed by the equivalent search in Riakc.

results = client.index('mybucket', 'field1_bin', 'val1', 'val5').run()
Riakc.Conn.index_search
  conn
  ~b:"mybucket"
  ~index:"field1"
  (range_string
     ~min:"val1"
     ~max:"val2"
     ~return_terms:false)

Conclusion

It's a bit unfair comparing an Ocaml API to a Python one, but hopefully this has demonstrated that with a reasonable type system one can express safe and powerful APIs without being inconvenient.

Thursday, July 4, 2013

Riakc In Five Minutes

This is a simple example using Riakc to PUT a key into a Riak database. It assumes that you already have a Riak database up and running.

First you need to install riakc. Simply do: opam install riakc. As of this writing, the latest version of riakc is 2.0.0 and the code given depends on that version.

Now, the code. The following is a complete CLI tool that will PUT a key and print back the result from Riak. It handles all errors that the library can generate as well as outputting siblings correctly.

(*
 * This example is valid for version 2.0.0, and possibly later
 *)
open Core.Std
open Async.Std

(*
 * Take a string of bytes and convert them to hex string
 * representation
 *)
let hex_of_string =
  String.concat_map ~f:(fun c -> sprintf "%X" (Char.to_int c))

(*
 * An Robj can have multiple values in it, each one with its
 * own content type, encoding, and value.  This just prints
 * the value, which is a string blob
 *)
let print_contents contents =
  List.iter
    ~f:(fun content ->
      let module C = Riakc.Robj.Content in
      printf "VALUE: %s\n" (C.value content))
    contents

let fail s =
  printf "%s\n" s;
  shutdown 1

let exec () =
  let host = Sys.argv.(1) in
  let port = Int.of_string Sys.argv.(2) in
  (*
   * [with_conn] is a little helper function that will
   * establish a connection, run a function on the connection
   * and tear it down when done
   *)
  Riakc.Conn.with_conn
    ~host
    ~port
    (fun c ->
      let module R = Riakc.Robj in
      let content  = R.Content.create "some random data" in
      let robj     = R.create [] |> R.set_content content in
      (*
       * Put takes a bucket, a key, and an optional list of
       * options.  In this case we are setting the
       * [Return_body] option which returns what the key
       * looks like after the put.  It is possible that
       * siblings were created.
       *)
      Riakc.Conn.put
        c
        ~b:"test_bucket"
        ~k:"test_key"
        ~opts:[Riakc.Opts.Put.Return_body]
        robj)

let eval () =
  exec () >>| function
    | Ok (robj, key) -> begin
      (*
       * [put] returns a [Riakc.Robj.t] and a [string
       * option], which is the key if Riak had to generate
       * it
       *)
      let module R = Riakc.Robj in
      (*
       * Extract the vclock, if it exists, and convert it to
       * to something printable
       *)
      let vclock =
 Option.value
   ~default:"<none>"
   (Option.map ~f:hex_of_string (R.vclock robj))
      in
      let key = Option.value ~default:"<none>" key in
      printf "KEY: %s\n" key;
      printf "VCLOCK: %s\n" vclock;
      print_contents (R.contents robj);
      shutdown 0
    end
    (*
     * These are the various errors that can be returned.
     * Many of then come directly from the ProtoBuf layer
     * since there aren't really any more semantics to apply
     * to the data if it matches the PB frame.
     *)
    | Error `Bad_conn           -> fail "Bad_conn"
    | Error `Bad_payload        -> fail "Bad_payload"
    | Error `Incomplete_payload -> fail "Incomplete_payload"
    | Error `Notfound           -> fail "Notfound"
    | Error `Incomplete         -> fail "Incomplete"
    | Error `Overflow           -> fail "Overflow"
    | Error `Unknown_type       -> fail "Unknown_type"
    | Error `Wrong_type         -> fail "Wrong_type"

let () =
  ignore (eval ());
  never_returns (Scheduler.go ())

Now compile it:

ocamlfind ocamlopt -thread -I +camlp4 -package riakc -c demo.ml
ocamlfind ocamlopt -package riakc -thread -linkpkg \
-o demo.native demo.cmx

Finally, you can run it: ./demo.native hostname port

...And More Detail

The API for Riakc is broken up into two modules: Riakc.Robj and Riakc.Conn with Riakc.Opts being a third helper module. Below is in reference to version 2.0.0 of Riakc.

Riakc.Robj

Riakc.Robj defines a representation of an object stored in Riak. Robj is completely pure code. The API can be found here.

Riakc.Conn

This is the I/O layer. All interaction with the actual database happens through this module. Riakc.Conn is somewhat clever in that it has a compile-time requirement that you have called Riakc.Robj.set_content on any value you want to PUT. This guarantees you have resolved all siblings, somehow. Its API can be found here.

Riakc.Opts

Finally, various options are defined in Riakc.Opts. These are options that GET and PUT take. Not all of them are actually supported but support is planned. The API can be viewed here.

Hopefully Riakc has a fairly straight forward API. While the example code might be longer than other clients, it is complete and correct (I hope).

Sunday, March 17, 2013

[ANN] Riakc 0.0.0

Note, since writing this post, Riakc 1.0.0 has already been released and merged into opam. It fixes the below issue of Links (there is a typo in the release notes, 'not' should be 'now'. The source code can be found here. The 1.0.0 version number does not imply any stability or completeness of the library, just that it is not backwards compatible with 0.0.0.

Riakc is a Riak Protobuf client for Ocaml. Riakc uses Jane St Core/Async for concurrency. Riakc is in early development and so far supports a subset of the Riak API. The supported methods are:

  • ping
  • client_id
  • server_info
  • list_buckets
  • list_keys
  • bucket_props
  • get
  • put
  • delete

A note on GET

Links are currently dropped all together in the implementation, so if you read a value with links and write it back, you will have lost them. This will be fixed in the very near future.

As with anything, please feel free to submit issues and pull requests.

The source code can be found here. Riakc is in opam and you can install it by doing opam install riakc.

Usage

There are two API modules in Riakc. Examples of all existing API functions can be found here.

Riakc.Conn

Riakc.Conn provides the API for performing actions on the database. The module interface can be read here.

Riakc.Robj

Riakc.Robj provides the API for objects stored in Riak. The module interface can be read here. Riakc.Conn.get returns a Riakc.Robj.t and Riakc.Conn.put takes one. Robj.t supports representing siblings, however Riakc.Conn.put cannot PUT objects with siblings, this is enforced using phantom types. A value of Riakc.Robj.t that might have siblings is converted to one that doesn't using Riakc.Robj.set_content.

[ANN] Protobuf 0.0.2

Protobuf is an Ocaml library for communicating with Google's protobuf format. It provides a method for writing parsers and builders. There is no protoc support, yet and writing it is not a top goal right now. Protobuf is meant to be fairly lightweight and straight forward to use. The only other Protobuf support for Ocaml I am aware of is through piqi, however that was too heavy for my needs.

Protobuf is meant to be very low level, mostly dealing with representation of values and not semantics. For example, the fixed32 and sfixed32 values are both parsed as Int32.t's. Dealing with being signed or not is left up to the user.

The source code can be viewed here. Protobuf is in opam, to install it opam install protobuf.

The hope is that parsers and builders look reasonably close to the .proto files such that translation is straight forward, at least until protoc support is added. This is an early release and, without a doubt, has bugs in it please submit pull requests and issues.

https://github.com/orbitz/ocaml-protobuf/tree/0.0.2/

Examples

The best collection of examples right now is the tests. An example from the file:

let simple =
  P.int32 1 >>= P.return

let complex =
  P.int32 1           >>= fun num ->
  P.string 2          >>= fun s ->
  P.embd_msg 3 simple >>= fun emsg ->
  P.return (num, s, emsg)

let run_complex str =
  let open Result.Monad_infix in
  P.State.create (Bitstring.bitstring_of_string str)
  >>= fun s ->
  P.run complex s

The builder for this message looks like:

let build_simple i =
  let open Result.Monad_infix in
  let b = B.create () in
  B.int32 b 1 i >>= fun () ->
  Ok (B.to_string b)

let build_complex (i1, s, i2) =
  let open Result.Monad_infix in
  let b = B.create () in
  B.int32 b 1 i1                 >>= fun () ->
  B.string b 2 s                 >>= fun () ->
  B.embd_msg b 3 i2 build_simple >>= fun () ->
  Ok (B.to_string b)

Thursday, February 7, 2013

[ANN] ocaml-vclock - 0.0.0

I ported some Erlang vector clock code to Ocaml for fun and learning. It's not well tested and it hasn't any performance optimizations. I'm not ready yet but I have some projects in mind to use it so it will likely get fleshed out more.

Vector clocks are a system for determining the partial ordering of events in a distributed environment. You can determine if one value is the ancestor of another, equal, or was concurrently updated. It is one mechanism that distributed databases, such as Riak, use to automatically resolve some conflicts in data while maintaining availability.

The vector clock implementation allows for user defined site id type. It also allows metadata to be encoded in the site id, which is useful if you want your vector clock to be prunable by encoding timestamps in it.

The repo can be found here. If you'd like to learn more about vector clocks read the wikipedia page here. The Riak website also has some content on vector clocks here.

Friday, January 4, 2013

Experiences using Result.t vs Exceptions in Ocaml

Disclaimer: I have not compiled any of the example code in this post. Mostly because they are snippets meant to illustrate a point rather than be complete on their own. If they have any errors then apologies.

Previously I gave an introduction to return values vs exceptions in Ocaml. But a lot of ideas in software engineering sound good, how does this particular one work out in real software?

I have used this style in two projects. The first is a project that was originally written using exceptions and I have converted most of it to using return values. The second is one that was written from the start using return values. They can be found here and here. I make no guarantees about the quality of the code, in fact I believe some of it to be junk. These are just my subjective opinions in writing software with a particular attribute.

The Good

Expected Result

The whole system worked as expected. I get compile-time errors for all failure cases I do not handle. This has helped me catch some failure cases I had forgotten about previously, some of which would require an unlikely chain of events to hit, which would have made finding in a test harder, but obviously not impossible. In particular, ParaMugsy is (although the current rewrite does not cover this yet) meant to run in a distributed environment, which increases the cost of errors. Both in debugging and reproducing. In the case of opass, writing the DB is important to get right. Missing handling a failure here can mean the users database of passwords can be lost, a tragic event.

Not Cumbersome

In the Introduction I showed that for a simple program, return-values are no more cumbersome than exceptions. In these larger projects the same holds. This shouldn't really be a surprise though, as the monadic operators actually simulate the exact flow of exception code. But the 'not cumbersome' is half of a lie, which is explained more below.

Refactoring Easier

Ocaml is a great language when it comes to refactoring. Simply make the change you want and iterate on compiler errors. This style has made it even easier for me. I can add new failures to my functions and work through the compiler errors to make sure the change is handled in every location.

Works No Matter The Concurrent Framework

The original implementation of ParaMugsy used Lwt. In the rewrite I decided to use Core's Async library. Both are monadic. And both handle exceptions quite differently. Porting functions over that did return-values was much easier because they didn't rely on the framework to handle and propagate failures. Exceptions are tricky in a concurrent framework and concurrency is purely library based in Ocaml rather than being part of the language, which means libraries can choose incompatible ways to handle them. Return-values give one less thing to worry about when porting code or trying to get code to work in multiple frameworks.

The Bad

Prototyping Easier With Exceptions

The whole idea is to make it hard to miss an error case. But that can be annoying when you just want to get something running. Often times we write software in such a way that the success path is the first thing we write and we handle the errors after that. I don't think there is necessarily a good reason for this other than it's much more satisfying to see the results of the hard work sooner rather than later. In this case, my solution is to relax the ban on exceptions temporarily. Any place that I will return an Error I instead write failwith "not yet implemented". That way there is an easily grepable string to ensure I have replaced all exceptions with Error's when I am done. This is an annoyance but thankfully with a fairly simple solution.

Cannot Express All Invariants In Type System

Sometimes there are sections of code where I know something is true, but it is not expressible in the type system. For example, perhaps I have a data structure that updates multiple pieces of information together. I know when I access one piece of information it will be in the other place. Or perhaps I have a pattern match that I need to handle due to exhaustiveness but I know that it cannot happen given some invariants I have established earlier. In the case where I am looking up data that I know will exist, I will use a lookup function that can throw an exception if it is easiest. In the case where I have a pattern match that I know will never happen, I use assert. But note, these are cases where I have metaphysical certitude that such events will not happen. Not cases where I'm just pretty sure they work.

Many Useful Libraries Throw Exceptions

Obviously a lot of libraries throw exceptions. Luckily the primary library I use is Jane St's Core Suite, where they share roughly the same aversion of exceptions. Some functions still do throw exceptions though, most notably In_channel.with_file and Out_channel.with_file. This can be solved by wrapping those functions in return-value ones. The problem comes in: what happens when the function being wrapped is poorly documented or at some point can throw more exceptional cases than when it was originally wrapped. One option is to always catch _ and turn it into a fairly generic variant type. Or maybe a function only has a few logical failure conditions so collapsing them to a few variant types makes sense. I'm not aware of any really good solution here.

A Few Examples

There are a few transformations that come up often when converting exception code to return-value code. Here are some in detail.

Building Things

It's common to want to do some work and then construct a value from it. In exception-land that is as simple, just something like Constructor (thing_that_may_throw_exception ()). This doesn't work with return-values. Instead we have to do what we did in the Introduction post. Here is an example:

let f () =
  let open Result.Monad_infix in
  thing_that_may_fail () >>= fun v ->
  Ok (Constructor v)

Looping

Some loops cannot be written in their most obvious style. Consider an implementation of map that expects the function passed to it to use Result.t to signal failures. The very naive implementation of map is:

let map f = function
  | []    -> []
  | x::xs -> (f x)::(map xs)

There are two ways to write this. The first requires two passes over the elements. The first pass applies the function and the second one checks which value each function returned or the first error that was hit.

let map f l =
  Result.all (List.map f l)

Result.all has the type ('a, 'b) Core.Std.Result.t list -> ('a list, 'b) Core.Std.Result.t

The above is simple but could be inefficient. The entire map is preformed regardless of failure and then walked again. If the function being applied is expensive this could be a problem. The other solution is a pretty standard pattern in Ocaml of using an accumulator and reversing it on output. The monadic operator could be replaced by a match in this example, I just prefer the operator.

let map f l =
  let rec map' f acc = function
    | []    -> Ok (List.rev acc)
    | x::xs -> begin
      let open Result.Monad_infix in
      f x >>= fun v ->
      map' f (v::acc) xs
    end
  in
  map' f [] l

I'm sure someone cleverer in Ocaml probably has a superior solution but this has worked well for me.

try/with

A lot of exception code looks like the following.

let () =
  try
    thing1 ();
    thing2 ();
    thing3 ()
  with
    | Error1 -> handle_error1 ()
    | Error2 -> handle_error2 ()
    | Error3 -> handle_error3 ()

The scheme I use would break this into two functions. The one inside the try and the one handling its result. This might sound heavy but the syntax to define a new function in Ocaml is very light. In my experience this hasn't been a problem.

let do_things () =
  let open Result.Monad_infix in
  thing1 () >>= fun () ->
  thing2 () >>= fun () ->
  thing3

let () =
  match do_things () with
    | Ok _ -> ()
    | Error Error1 -> handle_error1 ()
    | Error Error2 -> handle_error2 ()
    | Error Error3 -> handle_error3 ()

Conclusion

Using return-values instead of exceptions in my Ocaml projects has had nearly the exact output I anticipated. I have compile-time guarantees for handling failure cases and the cost to my code has been minimal. Any difficulties I've run into have had straight forward solutions. In some cases it's simply a matter of thinking about the problems from a new perspective and the solution is clear. I plan on continuing to develop code with these principles and creating larger projects. I believe that this style scales well in larger projects and actually becomes less cumbersome as the project increases since the guarantees can help make it easier to reason about the project.

Thursday, January 3, 2013

Introduction to Result.t vs Exceptions in Ocaml

This post uses Jane St's Core suite. Specifically the Result module. It assumes some basic knowledge of Ocaml. Please check out Ocaml.org for more Ocaml reading material.

There are several articles and blog posts out there arguing for or against return values over exceptions. I'll add to the discussion with my reasons for using return values in the place of exceptions in Ocaml.

What's the difference?

Why does the debate even exist? Because each side has decent arguments for why their preference is superior when it comes to writing reliable software. Pro-return-value developers, for example, argue that their code is easier identify if the code is wrong simply by reading it (if it isn't handling a return value of a function, it's wrong), while exception based code requires understanding all of the functions called to determine if and how they will fail. Pro-exception developers argue that it is much harder to get their program into an undefined state because an exception has to be handled or else the program fails, where in return based code one can simply forget to check a function's return value and the program continues on in an undefined state.

I believe that Ocaml has several features that make return values the preferable way to handle errors. Specifically variants, polymorphic variants, exhaustive pattern matching, and a powerful static type system make return values attractive.

This debate is only worth your time if you are really passionate about writing software that has fairly strong guarantees about its quality in the face of errors. For a majority of software, it doesn't matter which paradigm you choose. Most errors will be stumbled upon during debugging and fairly soon after going into production or through writing unit and integration tests. But, tests cannot catch everything. And in distributed and concurrent code rare errors can now become common errors and it can be near impossible to reconstruct the conditions that caused it. But in some cases it is possible to make whole classes of errors either impossible or catchable at compile-time with some discipline. Ocaml is at least one language that makes this possible.

Checked exceptions

A quick aside on checked exceptions, as in Java. Checked exceptions provide some of the functionality I claim is valuable, the main problem with how checked exceptions are implemented in Java (the only language I have any experience in that uses them), is they have a very heavy syntax, to the point where using them can seem too burdensome.

The Claim

The claim is that if one cares about ensuring they are handling all failure cases in their software, return-values are superior to exceptions because, with the help of a good type system, their handling can be validated at compile-time. Ocaml provides a fairly light, non intrusive, syntax to make this feasible.

Good Returns

The goal of a good return value based error handling system is to make sure that all errors are handled at compile-time. This is because there is no way to enforce this at run-time, as an exception does. This is a good reason to prefer exceptions in a dynamically typed language like Python or Ruby, your static analyzers are few and far between.

In C this is generally accomplished by using a linting tool that will report an error if a function's return value is ignored in a call. This is why you might see printf casted to void in some code, to make it clear the return value is meant to be ignored. But a problem with this solution is that it only enforces that the developer handles the return value, not all possible errors. For example, POSIX functions return a value saying the function failed and put the actual failure in errno. How, then, to enforce that all of the possible failures are handled? Without encoding all of that information in a linting tool, the options in C (and most languages) are pretty weak. Linting tools are also separate from the compiler and vary in quality. Writing code that takes proper advantage of a linting tool, in C, is a skill all of its own as well.

Better Returns

Ocaml supports exceptions but the compiler provides no guarantees that the exceptions are actually handled anywhere in the code. So what happens if the documentation of a function is incomplete or a dependent function is changed to add a new exception being thrown? The compiler won't help you.

But Ocaml's rich type system, combined with some discipline, gives you more power than a C linter. The primary strength is that Ocaml lets you encode information in your types. For example, in POSIX many functions return an integer to indicate error. But an int has no interesting meaning to the compiler other than it holds values between INT_MIN and INT_MAX. In Ocaml, we can instead create a type to represent the errors a function can return and the compiler can enforce that all possible errors are handled in some way thanks to exhaustive pattern matching.

An Example

What does all of this look like? Below a contrived example. The goal is to provide a function, called parse_person that takes a string and turns it into a person record. The requirements of the code is that if a valid person cannot be parsed out, the part of the string that failed is specified in the error message.

Here is a version using exceptions, ex1.ml:

open Core.Std

exception Int_of_string of string

exception Bad_line of string
exception Bad_name of string
exception Bad_age of string
exception Bad_zip of string

type person = { name : (string * string)
              ; age  : Int.t
              ; zip  : string
              }

(* A little helper function *)
let int_of_string s =
  try
    Int.of_string s
  with
    | Failure _ ->
      raise (Int_of_string s)

let parse_name name =
  match String.lsplit2 ~on:' ' name with
    | Some (first_name, last_name) ->
      (first_name, last_name)
    | None ->
      raise (Bad_name name)

let parse_age age =
  try
    int_of_string age
  with
    | Int_of_string _ ->
      raise (Bad_age age)

let parse_zip zip =
  try
    ignore (int_of_string zip);
    if String.length zip = 5 then
      zip
    else
      raise (Bad_zip zip)
  with
    | Int_of_string _ ->
      raise (Bad_zip zip)

let parse_person s =
  match String.split ~on:'\t' s with
    | [name; age; zip] ->
      { name = parse_name name
      ; age  = parse_age age
      ; zip  = parse_zip zip
      }
    | _ ->
      raise (Bad_line s)

let () =
  (* Pretend input came from user *)
  let input = "Joe Mama\t25\t11425" in
  try
    let person = parse_person input in
    printf "Name: %s %s\nAge: %d\nZip: %s\n"
      (fst person.name)
      (snd person.name)
      person.age
      person.zip
  with
    | Bad_line l ->
      printf "Bad line: '%s'\n" l
    | Bad_name name ->
      printf "Bad name: '%s'\n" name
    | Bad_age age ->
      printf "Bad age: '%s'\n" age
    | Bad_zip zip ->
      printf "Bad zip: '%s'\n" zip

ex2.ml is a basic translation of the above but using variants. The benefit is that the type system will ensure that all failure case are handled. The problem is the code is painful to read and modify. Every function that can fail has its own variant type to represent success and error. Composing the functions is painful since every thing returns a different type. We have to create a type that can represent all of the failures the other functions returned. It would be nice if each function could return an error and we could use that value instead. It would also be nice if everything read as a series of steps, rather than pattern matching on a tuple which makes it hard to read.

ex3.ml introduces Core's Result.t type. The useful addition is that we only need to define a type for parse_person. Every other function only has one error condition so we can just encode the error in the Error variant. This is still hard to read, though. The helper functions aren't so bad but the main function is still painful.

While the previous solutions have solved the problem of ensuring that all errors are handled, they introduced the problem of being painful to develop with. The main problem is that nothing composes. The helpers have their own error types and for every call to them we have to check their return and then encompass their error in any function above it. What would be nice is if the compiler could automatically union all of the error codes we want to return from itself and any function it called. Enter polymorphic variants.

ex4.ml Shows the version with polymorphic variants. The nice bit of refactoring we were able to do is in parse_person. Rather than an ugly match, the calls to the helper functions can be sequenced:

let parse_person s =
  match String.split ~on:'\t' s with
    | [name; age; zip] ->
      let open Result.Monad_infix in
      parse_name name >>= fun name ->
      parse_age  age  >>= fun age  ->
      parse_zip  zip  >>= fun zip  ->
      Ok { name; age; zip }
    | _ ->
      Error (`Bad_line s)

Don't worry about the monad syntax, it's really just to avoid the nesting to make the sequencing easier on the eyes. Except for the >>=, this looks a lot like code using exceptions. There is a nice linear flow and only the success path is shown. But! The compiler will ensure that all failures are handled.

The final version of the code is ex5.ml. This takes ex4 and rewrites portions of it to be prettier. As a disclaimer, I'm sure someone else would consider writing this differently even with the same restrictions I put on it, I might even write it different on a different day, but this version of the code demonstrates the points I am making.

A few points of comparison between ex1 and ex5:

  • The body of parse_person is definitely simpler and easier to read in the exception code. It is short and concise.
  • The rest of the helper functions are a bit of a toss-up between the exception and return-value code. I think one could argue either direction.
  • The return-value code has fulfilled my requirements in terms of handling failures. The compiler will complain if any failure parse_person could return is not handled. If I add another error type the code will not compile. It also fulfilled the requirements without bloating the code. The return-value code and exception code are roughly the same number of lines. Their flows are roughly equal. But the return-value code is much safer.

Two Points

It's not all sunshine and lollipops. There are two issues to consider:

  • Performance - Exceptions in Ocaml are really, really, fast. Like any performance issue, I suggest altering code only when needed based on measurements and encapsulating those changes as well as possible. This also means if you want to provide a safe and an exception version of a function, you should probably implement the safe version in terms of the exception verson.
  • Discipline - I referred to discipline a few times above. This whole scheme is very easy to mess up with a single mistake: pattern matching on anything (_). The power of exhaustive pattern matching means you need to match on every error individually. This is effectively for the same reason catching the exception base class in other languages is such a bad idea, you lose a lot of information.

Conclusion

The example given demonstrates an important point: code can become much safer at compile time without detriment to its length or readability. The cost is low and the benefit is high. This is a strong reason to prefer a return-value based solution over exceptions in Ocaml.

Thursday, May 17, 2012

Phantom type examples in Ocaml

What are phantom types

Phantom types are a way for multiple types to have the same exact underlying representation but still be seen as a distinct type by the compiler. The common example is units of measurements. Feet and meters are both distances and are best represented as an int or float, but it makes no sense to add a foot to a meter. Phantom types allow you to solve this and still represent a foot and a meter exactly the same. One can think of this as the opposite of duck typing. In duck typing, if you only care if the current value you are working with has four legs, a cat a dog and a table are the effectively the same thing. In phantom types you care about what something actually represents and that means they are different, even though underneath they are represented with the same type.

Wednesday, April 27, 2011

[JC] Efficient Parallel Programming in Poly/ML and Isabelle/ML

Authors: David C.J. Matthews and Makarius Wenzel
URL: http://www4.in.tum.de/~wenzelm/papers/parallel-ml.pdf
Year: 2010

I had not heard of Poly/ML or Isabelle/ML prior to reading this paper. I tried to do a bit of background research to get an idea for it, but I may have gotten some details wrong. If I made any mistakes below I will be happy to correct them.

The Paper


Poly/ML is a full implementation of Standard ML originally developed by David Matthews. Larry Paulson was an early adopter and implemented the Isabelle theorem prover. Isabelle/ML is the implementation of Isabelle on Poly/ML. Poly/ML was originally implemented with a single threaded run time system (RTS). With the ubiquity of multicore machines the RTS was modified to support threading, the garbage collector was modified and threading APIs were introduced. Finally, the modifications were tested in Isabelle. This paper is relevant to the frequent debates that occur on the Ocaml mailing list. Ocaml currently has no support for parallelism and this deficiency is frequently brought up as a negative.

Tuesday, October 5, 2010

Summary of CUFP 2010

This year was my first attending CUFP and I had a great time. I was pleasantly surprised at how strong of a showing the OCaml community had. I knew Jane Street would be there but I ran into several other people working in OCaml. The star of the show was definitely F# in my opinion. The weakest part of the conference was the lack of outlets. My laptop battery ran out by the second session of the first day and it was really quite difficult to find an outlet to charge it.

Day 1


The first day was broken into two session, each in a tutorial style. For the first session I was in the Building Robust Servers Using Erlang presented by Martin Logan from Orbitz. This stumbled a bit at the beginning, I think Martin was hoping people would be more familiar with Erlang as a language so he could delve into how to build a robust server. It picked up in the end though and I think he successfully drove his message home. The people I talked to after the session expected it to be a basic description on how to write Erlang but were impressed by the power of OTP, especially the supervisor model. A few people remarked that Erlang seemed great for anything that needed to be long running, so I think Martin was successful.

I jumped between all of the presentations in the second session.

  • F# - This was interesting, I hadn't seen F# much before. The presenter was teaching it through an ant simulation and had a contest with prizes.

  • Camlp4 and Template Haskell - I was a bit let down by what I saw of this one. It didn't seem like the presenters really gave a good introduction to templating languages. They presented a problem and let everyone work on it and would go around answering any questions. I wish my laptop battery was working so I could have taken a shot at playing with Camlp4. To their credit they were very helpful when asked but the initial presentation seemed lacking to me. Perhaps it was just too far over my head at this time.

  • Scala and Lift - This was the presentation that I had the least interest in but I think was the most well done. David's presentation was interactive and had no slides. He simply wrote code with you and explained what it did and I think that worked well. Everyone I talked to after seemed impressed by what Lift was capable of accomplishing so easily.



Day 2


Day 2 was all talks done in serial. I enjoyed most of the talks quite a bit. Yaron Minksy from Jane Street started out by saying something I think was important and easy to forget if you are heavily in the FP community. Despite the clear progress FP seems to be making (F# in Visual Studio, Real World Haskell, FP's in several big companies), we really aren't growing like we'd like to think. For most people management either says no to a functional language or it has to be snuck in through the back door. That is why they chose the keynote to be about F#. Microsoft including it in Visual Studio is a big leap and probably the biggest news in terms of FP going mainstream. But is it enough? We'll find out in the coming years.


  • F# - This was the keynote presented by Luke Hoban from Microsoft and he painted a really great picture of F#. His talk spanned how they introduce F# to non-functional programmers, a demo of F#, and some experiences in productizing it. The integration with Visual Studio was topnotch. Luke showed off how easy it is to create a GUI, handle events, and run asynchronous code. It almost made me wish I was running Windows, it looked so nice. The power of F#, to me, was making GUIs. The language looked like it had to be weakened a bit in order to successfully exist in the .Net ecosystem but if I ever find myself working on Windows I will gladly use F#. How much will F# be adopted by mainstream programmers? Who knows, I'm hoping quite a bit though.

  • Scaling Scala at Twitter - I knew Twitter used Scala but I did not realize they were such a large Scala shop. Scala was another language that seemed to have good representation at CUFP. I am still not sold on it but people seem to be doing great things with it. This talk was mostly about experiences in building the geolocation in Twitter. It was impressive that geolocation was built very quickly by two engineers who had no Scala or Java experience. There were two takeaways from this talk. The first is that the data center is the new computer. When you are designing a distributed application you really need to think differently about it than you would a non distributed application. This should not be a surprise if you really think about it but the emphasis seemed to be that in many cases people don't realize there is a difference. The second was that we should be honest about GC and realize it is a leaky abstraction. It would be nice if the application could get information back from the GC. The application really knows best how to handle working under heavy load and it would be nice if it could query the GC to figure out what kind of load it is under. I am not quite sure how much I buy the second one, couldn't the application monitor itself based on some metric relevant to its operations and modify its behavior based on that?

  • Cryptol, a DSL for Cryptographic Algorithms - This was from the people at Galois. I don't know much about Galois other than dons works there and they do Haskell, but it looks like they get nice government contracts too. I had no idea how complex the world of cryptology is. I knew the algorithms were sophisticated but not the rest of it. Cryptol seems powerful but much of the talk was over my head.

  • Naïveté vs. Experience - or, How We Thought We Could Use Scala and Clojure, and How We Actually Did - This talk was by Michael Fogus and my favorite. MIchael was entertaining and insightful. Most of this talk was about Scala and it included why they moved to Scala from Java, what they expected to use in Scala, what they actually did use in Scala, and the problems with Scala. Michael talked a lot about how he convinced his team to move to Scala as well. The experiences were positive but it did take a lot of convincing. The slides to his talk can be found here.

  • Reactive Extensions (Rx): Curing Your Asynchronous Programming Blues - Sadly Erik Meijer was unable to present this. I forgot to write down the name of who did present it, Wes something, but he did a great job. Rx looks really cool. I don't know how it scales up in writing an application but Wes was able to throw together some interesting programs very quickly using Rx. Rx is a Reactive Programming library for .Net. In short, it treats events like a collection and you simply iterate over the collection to get events (you can even use LINQ). This makes writing even driven software easier to think about and easier to compose events together. All of his examples were in C# but, because Rx is on .Net, it can be used seamlessly with F# (is the impression that I got).

  • Eden: An F#/WPF framework for building GUI tools - Eden is built by the Credit Suisse guys so they were unable to actually show Eden, however a subset of its functionality was built for the talk. This showed off more of how pretty GUIs can be created with F#. WPF has really great graphics and looked easy to produce. The portion of Eden shown was using a graph-based layout to calculate output on demand. It is difficult to explain succinctly but this talk showed off GUIs in F# as well as how easy it is to create asynchronous code. F#'s two strongest points seem to be OCaml's two weakest points.

  • Functional Language Compiler Experiences at Intel - The speaker couldn't talk too much about what they were working on (apparently Intel is making a functional language designed to be used for their processors with many many cores) they they did have some interesting meta-things to say. The first was, even in the FP world, sometimes you just want impurity. The second was, if your FP language is going to allow you to write code imperatively, don't make the syntax terrible. In this case they were writing SML. Finally, it is harder to teach someone FP if they have programming experience than something completely fresh. In their case they were looking at 8 - 12 months before really getting a return from the people they were training.

  • Riak Core: Building Distributed Applications Without Shared State - This talk was great. Rusty from Basho gave a great look at the important functionality in Riak. Riak is broken into three components: Riak Core - a core library for building robust distributed applications in Erlang, Riak KV - A key-value store using Riak Core, and Riak Search - a full text search engine using Riak Core. The message here, again, was the data center is the computer. I thought Riak's usage of virtual nodes was interesting too, and it seemed obvious in hindsight. Rather than break your distributed application up by physical nodes, create a ton of virtual nodes (more than you'll ever have of physical nodes) and then map those to physical nodes. Take sharding, for example, if you map to physical nodes, once you add a new physical node you'll have to repartition your shards all over again. But if you have a few hundred virtual nodes, adding a physical node just means you have to remap some data to it and point the new virtual nodes at it, but your upstream code doesn't need to change at all. Riak Core helps take care of the virtual node mapping for you as well as how to push data around when you add or take away physical nodes.

  • Functional Programming at Freebase - I was excited for this talk but sadly let down. This involved rewriting Freebase's query language parser and executor from Python to OCaml. It looked more like mental masturbation to me though. Several times I found myself simply wonder why some choices were made. Many of the choices came off as wishing he were writing Haskell. In the end the speaker got a 10x speed up, which was pointed out to not be very good, and it looked like they had to go through a lot of headaches a long the way.

  • ACL2: Eating One's Own Dogfood - I was unable to attend this talk.


I enjoyed CUFP quite a bit. It was great to meet the people I read papers from or see on videos about my favorite languages. In terms of being mainstream, Scala seemed to be making the fastest gains, most likely because it is so close to Java, it is an easy switch. In many ways I felt like we are all slowly catching up to Haskell. Many of the technical ideas presented here have already existed in Haskell for quite awhile and I could almost see the frustration on faces of the Haskell people wondering why the rest of us haven't figured out that we should be writing it. I'm hoping that next year the number of companies adopting functional languages continues to grow so we can see more examples of FP in industry at the next CUFP.

Sunday, September 6, 2009

Impressed with Haskell's concurrency

I have been playing with both Ocaml and Haskell* lately. In Ocaml, I have been rewriting a lot of simple Python scripts I use at work to see how they compare. They tend to be faster and more trustworthy. Ocaml, though, has pretty bad concurrency support. They have some thread library that wraps the OS threads, no real good message passing interface. Even the guys at Jane St have listed that as a complaint**.

So I decided to check out Haskell again. With Haskell I have always thought it was a great language, but could never grok it. That sounds a little weird, but reading Haskell code is simply great. When you figure out what it does, it tends to be very expressive and flexible. After looking at what Haskell offers for concurrency, I think that in theory it could give Erlang a serious run for its money. Here's why:

- Haskell, in general and in my opinion, is a safer language to write code in than Erlang. One can do a lot of work with Dialyzer to verify their code, but they are still somewhat limited. Haskells type system is very expressive and powerful. Haskell also has ADT's, which as far as I know Erlang still does not. For an idea of why ADT's are so powerful when it comes to writing safe code, see the Caml Trading video. And in this case, by 'safe' I mean writing correct code.

- Haskell produces generally fast code. GHC does some impressive optimizations, and supercompilation*** is most likely getting going to be part of GHC in the near future. It should noted that while Haskell can produce fast results, its lazyness can also be unpredictable in the optimizations (both speed and memory) that it performs. This is believed, by many, to be a big drawback to Haskell. I haven't done enough work in Haskell to really say how bad this is but Real World Haskell does give a complete chapter to diagnosing performance problems and optimizing them.

- Haskell's threading implementation uses green threads with a many-to-one mapping to OS threads. This means you can take advantage of multiple cores without modifying your Haskell code. The Erlang VM does this too, with SMP support. The greenthread implementation also appears to be blazing fast. Haskell is number one in the threadring solution on the language shootout. Erlang is about 4x slower. Take from that what you will.

- You can implement Erlang-like best-case programming in Haskell, from what I can tell. Haskell supports Exceptions, and you can throw exceptions to other threads using asynchronous exceptions. This gives you a way to 'link' threads like you can link Erlang processes. It is still programmer driven, so you can make a mistake, point for Erlang.

- STM, while I haven't read up on this, it seems like a pretty great way to handle synchronization between threads.

- Monads. When reading up on concurrency in Haskell, monads seemed to often come up as valuable in ensuring correctness. For example, in an STM transaction, one wants to restrict the transaction from doing things that cannot be rolled back, such as IO. This is done by the 'atomically' function taking an STM monad as input and wrapping the output in an IO monad. What this all means is one can't do IO in the atomically block unless it's unsafe. The ability to restrict what the user can do, when one wants to, with the type system is quite powerful.

That being said, Haskell does have some clear losses next to Erlang. The biggest drawback is the lack of a distributed model. There is distributed Haskell, I have not researched it much but I'm under the impression it is not 'there' yet. Erlang is easy to learn, very easy. Haskell is not. I have found that, in order to write really good Haskell code, one has to keep a lot of stuff in their head at once. Perhaps this is just because I am new but I have found Haskell better to read than to write. Erlang is not like this, while the syntax has some peculiarities to it, it is not hard to pick up and start writing good Erlang. I think Ocaml shares more in common to Erlang in this regard. The hump one needs to get over in order to write solid Haskell code is a real and legitimate reason to not choose Haskell.


All that being said, I admittedly am fairly new to Haskell so these opinions will change over time, I'm planning on putting more effort into writing real projects in Haskell to see how it goes. Needless to say, I am impressed by what Haskell has to offer for concurrency. If I'm factually wrong on anything here, please correct me, this is all based on some reading research I've been doing on Haskell, not my actual experiences.

* When I say Haskell, I really mean GHC here

** Yaron Minsky's Caml Trading lecture, very good! Makes a great, practical argument, for Ocaml - http://ocaml.janestreet.com/?q=node/61

*** Supercompilation http://community.haskell.org/~ndm/downloads/slides-supercompilation_for_haskell-03_mar_2009.pdf