Friday, January 4, 2013

Deconstructing Zed's K&R2 Deconstruction

I recently stumbled upon Zed Shaw's deconstruction of K&R2. The post is well intended but, in my opinion, flawed. I believe Zed fails to make a valid argument and also fails to provide a valid solution to the issue he raises.

The chapter is clearly not finished, so this rebuttal might not be valid at the time of reading.

The Argument

The primary argument is that K&R2 is not an appropriate tool for learning C in our modern age. The example given is a function called copy which is effectively strcpy. Zed points out that if the function is not given a valid string, as C defines it, the behaviour of the function is undefined.

This provides a formal proof that the function is defective because there are possible inputs that causes the while-loop to run forever or overflow the target.

When presented with the rebuttal that the cases where it fails are not valid C strings, the response is that it doesn't matter:

... but I'm saying the function is defective because most of the possible inputs cause it to crash the software.

The problem with this mindset is there's no way to confirm that a C string is valid.

Also:

Another argument in favor of this copy() function is when the proponents of K&RC state that you are "just supposed to not use bad strings". Despite the mountains of empirical evidence that this is impossible in C code...

To reiterate, the problem with copy is that:

  1. It depends on valid C strings to operate correctly
  2. C strings are impossible to validate at run-time
  3. The behaviour of copy is undefined for most values that are possible to be put into a char*

Proposed Solution

The solution is a function called safercopy which takes the lengths of the storages as input, allegedly guaranteeing the termination of safercopy:

In every case the for-loop variant with string length given as arguments will terminate no matter what.

What's Wrong With This

We can write what is wrong with safercopy using the exact same criteria Zed used for copy:

  1. It depends on valid lengths to operate correctly
  2. The lengths are impossible to validate at run-time
  3. The behaviour of safercopy is undefined for most values that are possible to be put into a size_t (I am presuming that the lengths would be a size_t)

Additionally, Zed instills a false confidence in his safercopy. The function is no more guaranteed to terminate than copy when given bad input. Specifically, if the lengths are wrong causing the copy loop to go out of bounds of its storage it could easily overwrite the value of anything, including the lengths and pointer values in the loop its in. It could blow up, it could loop forever, who knows. It's undefined.

Finally, if it is hard to properly handle C strings, why should we think it is any easier to track the length of a string separately? Remember, in C the length of a string is encoded in the string itself by the location of the '\0'. The solution provided by Zed takes the length of the strings as separate input. But he provides no reason to believe developers will get this correct. If the solution proposed had been implementing a safe string library, I might be able to agree.

And that is the crux of the problem. It's not if K&R2 is any good or not, it's that the solution given isn't any better. It doesn't address the faults of C strings. There are known way safely handle C strings, the problem tends to be that its tedious so people get it wrong. Many C strings issues have to do with lack of proper allocation rather than forgetting the '\0'-terminator. In what way does the solution solve this problem?

If the solution given is no better than the problem it's solving, then it isn't a very good solution.

K&R2

Is K&R2 not suitable for teaching people C in this day? It has plenty of faults in it but I don't think this particular article, as it exists now, makes a compelling argument. Nor does it provide anything better than what it's critiquing.

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.