JLOUIS Ramblings

On Abstraction in Erlang

2011-12-30T10:00:00.001-08:00

Programs of a certain size are complex. As long as the program is written by a single programmer and is fairly small, say under 1000 lines of code, then everything is easy. The programmer can keep the whole program in the head and it is easy to do stuff with that program. If on the other hand the program grows in size or we add more programmers, then we can't rely on the singular knowledge of a programmer.

The only way to solve this problem is to build in abstractions in your programs. We will review two such methods in Erlang. The idea of abstraction, informally, is that we will hide certain details and only provide a clean interface through which to manipulate stuff. Erlang is a "Mutually Consenting Adult Language" (read: dynamically typed with full term introspection - or more violently - unityped crap with everything in one big union type). So this abstraction is not possible in reality. On the other hand, the dialyzer can provide us with much of the necessary tooling for abstraction.

As an example of so-called modular abstraction, let us consider a small toy module:

 -module(myq).

 -export([push/2,
          empty/0,
          pop/1]).
 -type t() :: {fifo, [integer()], [integer()]}.
 -export_type([t/0]).

 -spec empty() -> t().
 -spec push(integer(), t()) -> t().
 -spec pop(t())     -> 'empty' | {'value', integer(), t()}.

These are the definitions and specs of the module we are implementing. We are writing a simple queue module for a FIFO queue, based on two lists that are kept back-to-back. I am using a Standard ML / Ocaml trick here by calling the canonical type it operates on for 't'. The operations push/2 and pop/1 are used to push and pop elements to and from the queue respectively. Note we are prefixing queues by the atom 'fifo' to discriminate them from other tuples. The implementation of the queue is equally simple:

 empty() -> {fifo, [], []}.

 push(E, {fifo, Front, Back}) -> {fifo, Front, [E | Back]}.

 pop({fifo, [E | N], Back}) -> {value, E, {fifo, N, Back}};
 pop({fifo, [], []})        -> empty;
 pop({fifo, [], Back})      -> pop({fifo, lists:reverse(Back), []}).

We always push to the back list and always pop from the front list. If the front list ever becomes empty, we reverse the back list to the front. Not used persistently, this queue has amortized O(1) run-time and is as such pretty fast.

The neat thing is that all operations are local to the myq module when you want to operate on queues. This abstracts away details about queues when you are using them via this module. There can much code inside such a module which is never exposed to the outside and thus we have an easier time managing the program.

There is a problem with this though, which is that the implementation of the queue is transparent. A user of the myq module can, when handed a queue, Q, of type myq:t() we can discriminate on it like this user:

 -module(u).

 -compile(export_all).

 -spec f(myq:t()) -> myq:t().
 f(Q) ->
     case Q of
         {fifo, [], []} ->
             myq:push(7, Q);
         _Otherwise ->
             Q
     end.

Note how we match on the queue and manipulate it. This is bad practice! If the myq module defined the representation of the queue it ought to be the only module that manipulate the internal representation of a queue. Otherwise we might lose the modularity since the representation has bled all over the place. Now, since Erlang is for mutually consenting adults, you need to make sure this data structural representation leak doesn't happen yourself. It is especially important with records. If you want modular code, avoid putting records in included header files if possible unless you are dead sure the representation won't change all of a sudden. Otherwise the record will bleed all over your code and make it harder to change stuff later on. Also changes are not module-local but in several modules. This hurts the reusability of code.

However, the dialyzer has a neat trick! If we instead of

 -type t() :: {fifo, [integer()], [integer()]}.

had defined the type as opaque

 -opaque t() :: {fifo, [integer()], [integer()]}.

Then the dialyzer will report the following when run on the code:

 u.erl:9: The call myq:push(7,Q::{'fifo',[],[]}) does not have an
      opaque term of type myq:t() as 2nd argument

which is a warning that we are breaking the opaqueness abstraction of the myq:t() type.

The Other kind of abstraction in Erlang
Languages like Haskell or ML has these kind of tricks up their sleeve in the type system. You can enforce a type to be opaque and get type errors if a user tries to dig into the structure of the representation. Since the dialyzer came later in Erlang one might wonder why one could write programs larger than a million lines of code in Erlang and get away with it when there was no enforcement of opaqueness. The answer is subtle and peculiar. Part of the answer is naturally the functional heritage of Erlang. Functional languages tend to have excellent reusability properties because the task of handling state is diminished. Also, functional code tend to be easier to maintain since it is much more data-flow oriented than control-flow oriented. But Erlang has another kind of abstraction which is pretty unique to it, namely that of a process:

If I create a process, then its internal state is not observable from the outside. The only thing I can do is to communicate with the process by protocol: I can send it a message and I can await messages from it. This makes the process abstract when viewed from the outside. The internal representation is not visible and you could completely substitute the proces for another one without the caller knowing. In Erlang this principle of process isolation is key to the abstractional facilities.

What does this mean really?
Erlang has not one, but two kinds of ways to handle large applications: You can use modules, exports of types and opaqueness constraints to hide representations. While you can break the abstraction, the dialyzer will warn you when you are doing so. This is a compile-time and program-code abstractional facility. Orthogonally to this, a process is a runtime isolation abstraction. It enforces a given protocol at run time which you must abide. It can hide the internal representation of a process. It provides an abstractional facility as well. It is also the base of fault tolerance. If a process dies, only its internal state can be directly affected. Other processes not logically bound to it can still run. It is my hunch that these two tools together is invaluable when it comes to building large Erlang programs, several hundred thousand lines of code - and get away with it!

So in conclusion: To create modular code-level functional abstractions, rely on the dialyzer to create them for you like in the queue example from above. To create a modular runtime, split your program into processes, where each process handles a concurrent task.

An example of Property Based Testing in Erlang

2011-12-18T11:39:00.001-08:00

Introduction

The unit test is the lowest common denominator. We can use them, but they are cumbersome and they only peek once into the fabric of our work. A better solution for many tasks, namely Property Based Testing exists for Erlang. This post is an example of how to use the statem type of test, mainly because there are so few of these out there. The outset is this: We will randomly generate operations on a priority queue and then validate that these operations are correct according to a simpler model.

The setup was that Michael Truog had a nice library of (min) priority queues which he had written (see okeuday/pqueue) He was mostly interested in how they benchmarked, but before benchmarking, you need to have some kind of knowledge that your PrioQ is correct indeed. Otherwise, you may just return the value 42 on each output and claim that this is the "right" thing to do. So the system under test (the SUT) is the various priority queue implementations by Michael. In order to test them, we need a model of a priority queue though.

The model of a SUT is some code we write which can reflect the observations of the SUT. In the case of a priority queue, there is a very simple model we can choose. We can simply base it upon a naive priority queue. The idea is then, that our PrioQ is easy to write but it may not be particularly fast. If an error shows up, it means that the SUT and our model will disagree (hopefully) and we can figure out if the problem is with our Model or the SUT.

We are going to use PropEr. The choice could equally well have been Erlang QuickCheck though, with minor changes. Both tools reflect the same interface for this kind of work, even though their real working might be slightly different in practice.

Note: All code is in Michaels repository linked above. If you want to digest the code yourself, go read it there - after having read this blog post. I've pulled out the important parts, but eh real repo has a bit more code in it.

Building the model

The model in this case is fairly simple. When constructing the model you need to have an idea of what you are going to test for. The goal is to get the model as small as possible while still being able to handle everything you may need. On the other end of the spectrum, you build up a model that is a complete specification - which can in some cases actually mean your model will be larger than the SUT. But in this case the model is way smaller and simpler than the queue it tests.

For this particular example though, we are very lucky. Essentially our example is a complex implementation (implementations) of a simple idea. So our model goes for reflecting the simple idea instead.

Let us write a priority queue to serve as the model. Our representation is [{priority(), [element()]}] that is a list of tuple-pairs where the firstelement is a priority and the second element is the list of values we are storing under that priority. We require that the list is sorted by the priorities. This makes lookup a bit faster.

Insertion is awfully simple. Just skip until we hit the right spot and inject the value:

%% A listq is a sorted list of priorities
listq_insert({P, V}, []) -> [{P, [V]}];
listq_insert({P, V}, [{P1, _} | _] = LQ) when P < P1 ->
    [{P, [V]} | LQ];
listq_insert({P, V}, [{P1, Vs} | Next]) when P == P1 ->
    [{P, Vs ++ [V]} | Next];
listq_insert({P, V}, [{P1, Vs} | Next]) when P > P1 ->
     [{P1, Vs} | listq_insert({P, V}, Next)].

Note that if we get a hit on the priority, we just add the next value in the back. This is slow, but we don't care since we only need the model to carry out tests. Now, converting a prioq to a list is easy. So is taking the length of a priority queue in the model:

listq_to_list(L) ->
    lists:concat(
      [ Vals || {_Prio, Vals} <- L]).

listq_length(L) ->
    lists:sum(
      [ length(Vs) || {_Prio, Vs} <- L]).

There! Michael have two ways to remove elements from a priority queue. The first is the common solution where you remove the next element. Note that if the queue is empty then the result is an empty queue. Also note, we don't return the removed element. This semantics seem a little odd to me, but on the other hand, it is better to make the model reflect the expected behavior here:

listq_rem([]) -> [];
listq_rem([{_P, [_V]} | Next]) -> Next;
listq_rem([{P, [_V1 | Vs]} | Next]) -> [{P, Vs} | Next].

Michael also have a variant where we remove an element of a given priority. We can simply dig through the list until we find the desired priority and then remove an element from that one. If there are no more elements left of that priority, we kill the pair:

listq_rem([], _P) -> [];
listq_rem([{P, [_]} | Next], P) -> Next;
listq_rem([{P, [_ | Vs]} | Next], P) -> [{P, Vs} | Next];
listq_rem([{P1, Vs} | Next], P) -> [{P1, Vs} | listq_rem(Next, P)].

Finally, we need to be able to peek into the queue. There are three variants. We can peek for the minimal element. We can peek for the element with a given priority, or we can peek for an element but also obtain its priority in question:

listq_peek([]) -> empty;
listq_peek([{_P, [V | _]} | _]) -> {value, V}.

listq_prio_peek([{P, [V | _]} | _], P) -> {value, V};
listq_prio_peek([{_P1, _} | Next], P) -> listq_prio_peek(Next, P);
listq_prio_peek([], _P) -> empty.

listq_ppeek([]) -> empty;
listq_ppeek([{P, [V | _]} | _]) -> {value, V, P}.

Making a gen_server to drive the SUT.

Strictly speaking, this example does not need a properstatem test. You could just build up the priority queue by using valid operations and then make tests. But to illustrate the use of statem we have built a simple driver for a priority queue. This code is in okeuday/pqueue/src/queuesrv.erl and it is not that interesting. We just have a separate process which keeps track of the internal state of the priority queue for us. This means, that we can only observe the queue_srv by means of what we prod it to do and what it answers with.

You can have a look at the code, but it is not that interesting. It merely reflects what operations are allowed on a priority queue.

Introducing the StateM behaviour

We need a bit of work in order to support the proper_statem behaviour:

-module(pqueue_proper).
-include_lib("proper/include/proper.hrl").
-behaviour(proper_statem).

-export([command/1, initial_state/0, next_state/3, postcondition/3,
    precondition/2]).

The next part is somewhat wrong, from a type perspective. I should probably change it. The state is tracked far too broadly here, but the code will still function properly.

-type value() :: integer().
-record(state, { in_queue :: [{value(), term()}] }).
-define(SERVER, queue_srv).

Now we are at the point where we need to handle the given callbacks from proper_statem. The first one we will be attacking is the command/1 which states what commands are eligible for firing. But before doing that, we need some helpers:

priority() -> integer(-20, 20).
value() -> integer().

This is a generator of priorities and one of values. Michael decided that priorities should be in the range -20 to 20, so we reflect that in our generator. The values are always integers, but they have no bound on the other hand.

priority(InQ) -> elements([P || {P, _} <- InQ]).

Given a queue, we extract all the priorities from that queue. And then we use elements to select one at random. This is a generator of existing priorites that are already in the queue. Then there is the initial state of the system, which is the empty priority queue:

initial_state() -> #state { in_queue = [] }.

Commands

Now we are ready to define the command function. It is keyed by the current state, so we can take that into consideration as well. It may be that the current state limits what commands are eligible for firing.

command(#state { in_queue = InQ }) ->
    oneof([{call, ?SERVER, in, [value()]},
           {call, ?SERVER, in, [value(), priority()]},
           {call, ?SERVER, is_empty, []},
           {call, ?SERVER, is_queue, []},
           {call, ?SERVER, len, []},
           {call, ?SERVER, out, []}] ++
          [{call, ?SERVER, out, [priority(InQ)]} || InQ =/= []] ++
          [{call, ?SERVER, pout, []},
          {call, ?SERVER, to_list, []}]).

We generate calls to ?SERVER which is our queuesrv genserver construction. We use the already given generators to generate random values and priorities where applicable. Note the trick [priority(InQ) || InQ =/= []] which is a degenerate list comprehension. The list is [] if InQ is empty. Otherwise it uses the priority/1 function from above to pick a random priority to remove among those already in the queue.

Updating our model

Now, assume we have run an operation on the SUT with the command/1 callback. Then our model needs to be updated with the same value as well. Otherwise we could not check for correctness. The function next_state(State, Ret, Call) reflects this change. The three parameters taken are the current State of the model, the return value of the operation we invoked, and Call describes the command we executed.

Note: There is one very important thing with the next_state/3 function. It is used twice internally in PropEr/QuickCheck. First it is used in an abstract mode where all values are symbolic in nature. That is you can not rely on a return value being a "real" value. Rather you must only transfer values around without discriminating on them. Secondly, the function is used concretely when you are running the test cases. The notion used is symbolic and dynamic respectively. Just keep this in mind when you write your own tests. Since you may be executing this with symbolic values, it is limited how you can discriminate values as they may be symbolic in nature.

Here is the first clause:

next_state(#state { in_queue = InQ } = S, _V, {call, _, out, []}) ->
    S#state { in_queue = listq_rem(InQ) };

This means we had a call to out/0 on the queue and we should remove an element from the queue. We can then call our own listq_rem/1 function to track this operation in our own model state. Note also that some of the clauses are not going to update the state since the calls generated does not alter the state. Also note that we sometimes look inside the call to figure out what values were generated as input so we can transition our model state accordingly:

next_state(#state { in_queue = InQ } = S, _V, {call, _, out, [Prio]}) ->
    S#state { in_queue = listq_rem(InQ, Prio) };
next_state(#state { in_queue = InQ } = S, _V, {call, _, pout, _}) ->
    S#state { in_queue = listq_rem(InQ) };
next_state(S, _V, {call, _, to_list, _}) -> S;
next_state(S, _V, {call, _, is_queue, _}) -> S;
next_state(S, _V, {call, _, is_empty, _}) -> S;
next_state(S, _V, {call, _, len, _}) -> S;
next_state(#state { in_queue = InQ } = S, _V,
               {call, _, in, [Value, Prio]}) ->
    S#state { in_queue = listq_insert({Prio, Value}, InQ) };
next_state(#state { in_queue = InQ } = S, _V,
              {call, _, in, [Value]}) ->
    S#state { in_queue = listq_insert({0, Value}, InQ) }.

Preconditions

This example does not use preconditions:

precondition(_S, _Call) -> true

Normally you use preconditions to limit what calls can be done in what state. That is, if the precondition fails, then the given transition is not allowed. One can use this as a constraining measure in some tests. But for this example, everything can always fire, so there is no reason to limit the calls in any way.

Postconditions

The postcondition is where we check that the model and SUT agrees on the observations. This is not executed symbolically, but is entirely dynamic execution. Here is the first clause:

postcondition(#state { in_queue = InQ }, {call, _, out, [Prio]}, R) ->
    R == listq_prio_peek(InQ, Prio);

it states: If we have a current state, InQ and a call to out with a specific priority, Prio and the SUT returned the value R. Then peeking in InQ for the first element at that given priority should be the same element. After this test, the state transition with next_state/3 will happen. Equally:

postcondition(#state { in_queue = InQ }, {call, _, pout, _}, R) ->
    R == listq_ppeek(InQ);
postcondition(#state { in_queue = InQ }, {call, _, out, _}, R) ->
    R == listq_peek(InQ);

handles the remaining checks for removing elements from the priority queue. Converting to a list or taking the length can also be done by calling our model variants and looking for equality:

postcondition(S, {call, _, to_list, _}, R) ->
    R == listq_to_list(S#state.in_queue);
postcondition(S, {call, _, len, _}, L) ->
    L == listq_length(S#state.in_queue);

Finally, one can ask if we have a queue, which should always be true - and we could ask if the queue is currently empty, which we can determine by discriminating on our model state. In this case they should also agree. Inserting elements into a queue always succeeds in addition:

postcondition(_S, {call, _, is_queue, _}, true) -> true;
postcondition(S, {call, _, is_empty, _}, Res) ->
    Res == (S#state.in_queue == []);
postcondition(_S, {call, _, in, _}, _) ->
    true;

All other outcomes are errors:

postcondition(_, _, _) ->
    false.

Running the test

Now, running this property test is the following property:

correct(M) ->
   ?FORALL(Cmds, commands(?MODULE),
      ?TRAPEXIT(
        begin
           ?SERVER:start_link(M),
               {History,State,Result} = run_commands(?MODULE, Cmds),
               ?SERVER:stop(),
               ?WHENFAIL(
                 io:format("History: ~w\nState: ~w\nResult: ~w\n",
                               [History,State,Result]),
                               aggregate(
                                command_names(Cmds),
                                Result =:= ok))
                end)).

Where M describes the module we wish to test. Michael wrote several and we can test them all with the same code! Then we start a queue_srv with M as the module and then we run a series of commands. The server is then stopped. Then, upon failure, we output necessary stuff to figure out what went wrong. Also, we aggregate how often the commands are hti so we are sure we have a decent coverage.

The test uncovered some errors straight away. Here is one such which was much much bigger but got minimized down by PropEr:

[{set,{var,1},{call,queue_srv,in,[-18]}},
 {set,{var,5},{call,queue_srv,in,[9]}},
 {set,{var,6},{call,queue_srv,in,[-10,-4]}},
 {set,{var,18},{call,queue_srv,in,[-29]}},
 {set,{var,22},{call,queue_srv,in,[11]}},
 {set,{var,26},{call,queue_srv,len,[]}}]

So, if you insert [-18, 9, -4 at priority -10, -29, 11] and then ask for the length of the priority queue, something failed (the pqueue code crashed).

The point here is that normal unit tests won't usually come up with examples this complex. But by starting out asking: "What can be done here?" by means of generators and then carrying out random operations uncovers nasty errors quickly. Michaels code now routinely survives 1500 PropEr test runs on all his priority queue modules. Given that it took 1-2 hours writing the test, it seems like it was worth it.

Using the Event Tracer tool set in Erlang

2011-10-23T09:00:00.000-07:00

A common problem in concurrent systems is the following: events fire from all places all the time and you have no direct control over when and why events fire. Thus, to figure out problems one can often make use of a sequence diagram like this one (thanks Wikipedia):

The purpose of such a diagram is to show the interactions between different concurrent parties. In this case, Fred, Bob, Hank and Renee - in a restaurant. One can easily draw such diagrams on paper. But the problem with such a drawing is that it is disconnected from the machine. What the drawing shows may or may not be what the program actually does.

Wouldn't it be neat if you could make such diagrams by tracing what the code does and then build up the diagram in a programmatic way? Well, with Erlang, you can. I'll use some code I wrote as an example for how to do it.

Step 1: Build a tracer function
The first step is to construct a tracer function. Mine look like the following and resides in a module called "utp".

report_event(DetailLevel, FromTo, Label, Contents) ->
    %% N.B External call
    ?MODULE:report_event(DetailLevel, FromTo, FromTo, Label, Contents).

report_event(_DetailLevel, _From, _To, _Label, _Contents) ->
    hopefully_traced.

The basic idea is found in the latter of these two definitions. It defines a dummy-function taking 5 arguments which are thrown away promptly. The return value "hopefully_traced" is arbitrary, but it signifies what we want out of this function. The first variant, is used when it is the same party that does both things.

The arguments are as follows:

DetailLevel: A number between 0 and 100. It signifies the level of detail for this event. We can use it to give major events low level and more detailed event at a finer grained scale higher levels. The event tracer can cut off events based on this value so we get the desired graininess.
From: The party from which the event originates.
To: The party to which the event is sent.
Label: The notational label to put on the message.
Contents: If you click on the event, we will show this term to the user. It can be used to pack up more detailed information to present, while avoiding cluttering up the diagram.

Step 2: Trace the events in the program
Whenever something important in the program happens, you add a call to "utp:report_event/5" or whatever the designation for your tracing function is. This will be default do nothing, but it allows us to hook that function later with Erlangs tracing facilities. As an example, here is the interaction from above:

trace_test() ->
    Events = [{fred, bob, order_food},
              {bob, hank, order_food},
              {bob, fred, serve_wine},
              {hank, bob, pickup},
              {bob, fred, serve_feed},
              {fred, renee, pay}],
    [utp:report_event(50, F, T, L, [])
     || {F,T,L} <- Events].

But note that anything can be reported really, by spreading the event reporting function out over your code base. Rather than run scores of debug statements, you can add a reporter at the point in the code. Also note I have condensed it a bit in the above example with a list comprehension because I don't care for the detail level and the contents.

Step 3: Introduce code to invoke the et application
Next, we need to invoke Erlangs et application in the right way. I have a module, called "utp_filter" which does it, even though it still doesn't contain any filter function. Here is the code of interest:

start(ExtraOptions) ->
    Options =
        [{event_order, event_ts},
         {scale, 2},
         {max_actors, 10},
         {detail_level, 90},
         {actors, [fred, bob, hank, renee]},
         {trace_pattern, {utp, max}},
         {trace_global, true},
         {title, "uTP tracer"} | ExtraOptions],
    et_viewer:start(Options).

What this code does is to initalize the et_viewer in a way such that it can be used with our example. The event order is event_ts which means we are timestamping events at when they fire and not when they are received. The actors define the order in which the actors appear. The trace_pattern is pretty important. It is what makes us hook to the "utp:report_event/5" call. You can give a lot of options to this or event produce such patterns yourself. But just name the module in which your trace function is placed will work.

Step 4: Test
If we invoke "utp_filter:start([])" which starts up the et viewer by executing the code in step 3, we can then invoke the trace test code from step 2 to obtain:

Which should reflect the example from Wikipedia, but now obtained by executing a program in Erlang. This idea has been used by me to capture and find bugs in TCP-stack variants, in particular uTP:

(Even if these diagrams are small, the basic idea should be in there - it is not about the diagrams, but about the steps to obtain the glory yourself :). For a TCP stack-like protocol it is very powerful: You have a tcpdump(1) output, an strace(1) output, as well as the internal protocol state in the same diagram. I found quite some bugs with these tools in my code, simply by inspecting the interaction of the programs.

And thats it. With the above code in your application, you can enable a graphical trace viewer on your code at any time. If you don't enable it, the overhead of the trace functions are negligible - unless you have a very hot critical path indeed. If you do enable it, you can see exactly what your code does in the given situation.

Musings on Dart

2011-10-10T07:03:00.000-07:00

Now the Dart language is out at http://dartlang.org, we can begin looking at the language and see what we think of it. Everything here are musings from reading the spec of the Dart language. Note that my points here are quite subjective at times. Don't expect this to be an objective run down of the language. Rather, I wanted to write down what I thought about the language just by looking at the specification alone.

Starting out, we generally won't focus on the syntax of the language. The syntax is boring, tedious and just there. It is Java/Javascript-like, mostly to interest the right kinds of people on the language. We note that the syntax is considerably shorter and leaner than the equivalent Java code and that there are notational
stuff going on to make certain things easier to write down in the programs.

The major goal of Dart is to clean up Javascript and make design choices in the language which does not hamper raw execution speed. Javascript is not built for compilation into fast programs. There are simply too many nasty warts and design choices in the language which makes it very hard to compile. V8 is astoundingly good at it, but by altering the source language a little bit, you can squeeze out much more power with very little effort.

I think that this is a goal of Dart which is central. Don't design yourself into a corner by language features.

Dart is Single Threaded but support concurrency through an Actor-like concept of isolates. The choice of making the runtime single threaded is understandable. It is vastly simpler to write a compiler for a single threaded runtime than it is for a multi-threaded one. Also, the focus is perhaps on writing programs for web browsers and the amount of extra processing power to be had there from multiple processors is perhaps limited. Note that while the language specification says it is single threaded, the Isolate concept in the library talks about heavy isolates which are separate threads. One could imagine that the execution inside an isolated region is always single-threaded (Like in, Erlang for instance), but the system as a whole might have several isolates working simultaneously.

On the other hand, even your modern mobile device goes multi-core. Thus, the choice is as much as a gamble as opting for a multi-core solution from day one. This choice is the conservative one.

Dart makes it explicit that it has several kinds of errors and that these may come "lazily" on demand. The idea is to facilitate JIT-compilation, so an implementation is not required to report all errors up front. An understandable and interesting choice. For a programmer with the proactive view (Haskell, Java, Ocaml) on error reporting, this sounds rather bad, but for a programmer with an reactive view (Erlang), it sounds quite familiar.

Naturally, the language makes the almost ubiquitous billion dollar mistake of C.A.R Hoare: the language includes null as a default. Almost all non-functional languages do.

An interesting choice is to enforce simplicity on static/final values. This is to ensure fast startup times, so a program can't hide a large computation in a global variable at startup.

Amusingly, the language must make sure that every function returns 'null' in the case where the function has no return statement. This is funny because in functional languages, this kind of problem doesn't exist. a 'void' function can't be used in expression context in an imperative language, but since Dart type system is not enforcing, there are no guarantees. Hence a kludge is introduced.

Functions are first class values with a simple notation for the equivalent of a lambda construction.

The language has operator overloading, but as is common in imperative languages, you cannot define your own operator. Rather, you must use the operators that come with the language.

Stealing ideas from other languages, there are convenience notation for getters and setters. On the other hand, there is no mention of lenses. The language is pretty much a standard OO-language with no mention of prototypical OO as in Javascript. This choice is probably smart since prototypical OO is irritating to compile.

There is a built-in notion of factory construction, much like the notation of getters and setters. The idea is to allow a constructor to act as a factory under the hood so the callers don't need to get exposed to the fact that there is a factory. One could imagine this concept extended to other classic design patterns over time.

The language is single-inheritance+interface+generics. Unlike Go, this language does support generics with upper bounds on the class hierarchy. In other words, the language has bounded quantification. And it even support F-bounded quantification on generics (also called recursively bounded quantification - you allow the class parameter T to occur in the bound as well: "T extends I(T)", see wikipedia on bounded quantification).

The language is pure. Everything is an object. You see that choice since null is the sole instance of class Null for example.

Dart has true integers of unbounded size. There is no cramming everything into double values. There are no pesky size bounds to battle. In other words, Dart picked the innovative choice.

I wonder... if a bool is an object, can I have a null bool?

Strings are unicode. We got lists and maps in the language. We have a functional expression notation for fast notation of small simple function evaluation thingies. It is perhaps the easiest way to get some functional ideas into a language without making it not seem like Java.

Note that a simple expression like '2 + 1' is internally compiled into a method invocation of the 2 objects + method with a parameter of 1.

In a very controversial move the type system is unsound. Having an unsound type system means that the type system may allow for certain bugs to happen in production code. Time will show if this is a problem in practice. It may be you almost never hit the problem in practice and then this choice might end up being pretty sane. But if you can hit the unsoundness easily, this choice will end up being pretty bad.

As in Java, constructing new types is had by making classes. To construct compound types, you need to use generics and parametrize the types as holes in the generic.

The most interesting part of the language, which is pretty conservative, is the choice of baking in both dynamic and static types into the same language. While the static type system is unsound, time will show if this unsoundness is troubling. C is also pretty bad type-wise, but that has not withheld people from writing software in it and using the type system to weed out bugs.

The other interesting part is hidden in the library as a library extension and are called Isolates. An Isolate is, technically, an actor which processes by itself. There is a concept of message passing ports between actors so one can send and receive information. Naturally, futures also form part of this definition.

My primary critique of the language is that Dart provides nothing new to the table. It looks like a Java-for-the-web clone without providing something new. Granted, it may sway some Java programmers to move toward the Web in the long run. Granted, this is in the interest of Google because the reliance on Java is dangerous when Oracle controls it. As a language, Dart is considerably less innovative than Google Go. Rather it buys into existing ideas, and adds a gradual type system as the most innovative feature. I am not too worried about the unsoundness currently, but it is an inherent danger lurking until the static checker will warn about it.

The secondary critique is the Isolate construction. First, there is a difference between a heavy and a light isolate. One provides a new thread of execution while the other provides an light-weight process in the current thread. There is no concept of migration so the programmer has to know beforehand how the program will run and execute to use isolates. It does provide pure isolation though, something not present in Go.

There are problems with this though. Can I create 100000 heavy isolates? Can I create 100000 light isolates? Suppose one of the light isolates ties up the CPU for a long time. Will isolates then be preemptively scheduled out so others gets a chance, or will the system keep running the single isolate while all others wait in queue? I am asking because it hurts latency.

Second, the notation is not built-in but provided as a library. This usually leads to code with heavier weight.

Third, there is no way to scrutinize the mailbox. You get a callback whenever a message is delivered, but it is up to you to build the search infrastructure for the mailbox. This is in strong contrast with Erlang and it usually leads to more complex actors in the long run.

Fourth, there is no concept of robustness. I can't link together Isolates so I can be told when other Isolates die and take care of it. Without links and monitors, it is cumbersome to build anything resembling OTP for Dart.

Fifth, where is my selective receive? We can easily imagine a single isolate having access to multiple ReceivePorts.

In conclusion, the current Isolate-implementation leaves much to be desired. I'd much rather want to hack Google Go in the browser than Dart to be honest. Go is a neater language, is more innovative, is farther ahead and has built-in-concurrency primitives. You just need to add a jQuery-like interface to Go and then it can substitute Dart as an imperative language.

What Dart DOES provide however is the ability to run faster than Javascript. It is clear that some of the choices enables the language to be compiled to much faster executing code. Also, if all you know is Javascript, the language is probably pretty neat. To the Java programmer, proper closures will be a warm welcome.

But for a guy who has seen things you wouldn't believe. Haskell ships off the shoulder of MultiCore CPUs. Watched OCaml glitter in the dark near TAPL. All those moments will be lost in time, like tears in rain. Time to die.

Finally, a disclaimer: I may be wrong on several occasions. I've had some 1-2 hours to study the language, and you can't really grasp a programming language in less than 1-2 months. So I may be wrong. Wrong on all points. Like fine wine, languages need a bit of time to mature and bloom into what they are. Dart is pretty young and drafty in its nature. A lot of things can happen.

One major difference - ZeroMQ and Erlang.

2011-10-02T08:10:00.000-07:00

When a dog owner wants to train his dog, the procedure is well-known and quite simple. The owner runs two loops: one of positive feedback and one of negative ditto. Whenever the dog does something right, the positive feedback loop is invoked and the dog is treated with a snack. Whenever the dog does something wrong, the dog is scolded and the negative feedback loop is used.

The result is positive and negative reinforcement of the dogs behavior. The dog will over time automatically behave as the owner wants and never even think of misbehaving.

When a programming language trains its leashed programmer, it likewise uses positive and negative feedback. Whenever a problem is easily solvable in the constructs and features of said language, it reinforces the use of those features and constructs. And also in the same vein, if something is hard to do in the language, the programmer will shy away from thinking the idea, since it may be too hard to do in the language. Another negative feedback loop is when resource usage of a program is bad. Either it will use too much memory of too many CPU resources to carry out its work. This discourages the programmer from using that solution again.

The important point is that while all practical general purpose languages are Turing complete, the way they train programmers to behave as they want is quite different. In an Object Oriented language for instance, the programmer is trained to reframe most - if not all - questions as objects of bundled fields and methods. A functional programmer is trained to envision programs as transformations of data from the form X into the form Y through the application of a function. And so on.

Which brings us to how ZeroMQ and Erlang will train its programmers into doing vastly different things:

In ZeroMQ, the programmer will configure a messaging network. That network will probably be fairly static. It is not the case that there is one configuration, invoked in the beginning of the system, which stays there for all of the systems execution, but chances are that the configuration is still fairly rigid and not subject to much change.

Around this messaging network, we now add processes which operate on the network. We send and receive messages on the network, processing them in various different programming languages. A process is also fairly static in the sense that the process is started, and then tend to use the messaging network as a queue: It will pick off some work, look at the data, process the data and push it back into the messaging network again. Taken to the extreme, ZeroMQ applications are often queue processors like this.

Incoming requests are transformed to a message and then sent into the messaging network of ZeroMQ. Then it will be processed by some vacant process in the other end and it will be moved from queue to queue until it finally completes. Note ZeroMQ is more complex than a simple point-to-point messaging framework, but the gist of the idea here is that many applications will have the above mentioned system design.

In Erlang, the programmer will take the request and turn the request into a process. Erlang programmers are trained by the language to like having a large amount of small processes like this, because the language encourages that behaviour. ZeroMQ-solutions on the other hand will be discouraged to dequeue a message and create a process out of it - if the processing language uses a traditional heavyweight thread for a process.

Now, given that the request is a process, an Erlang programmer will do the dual to the ZeroMQ programmer. Since the process is now the request, whenever the request needs to do some processing, it will do so itself. If it needs some external information, the request/process will ask for it. The preemptive scheduler will ensure that no request can stall the pipeline. Also, since the scheduler in Erlang is parallel, it is relatively easy to get all cores to work, but by having enough requests/processes in the run-queue.

Note, also, how the messaging network in this solution is fairly dynamic. Point-to-point exchanges are formed on demand when a request need some information.

To the Erlang programmer, the representation of the request is the process. There is no "message" living in a queue which is the representation of the request at any point. There are less need to tune fan-in/fan-out at the end of queues to make parallel work go through, since the schedulers will automatically parallelize.

Both styles have their advantages and disadvantages. But that is not the interesting point. The interesting point is how the ZeroMQ idea encourages one system design, whereas the Erlang solution encourages another. In Erlang a process is cheap, so it is totally feasible to turn each request into one. Furthermore, since there is no concept of a message channel, sending a message to a target is all about knowing or finding the name of the target (see for instance Ulf Wiger/Erlang Solutions gproc framework for an efficient name registry). On the contrary, since ZeroMQ has the concept of a generalized socket as a channel endpoint and assuming the programming language we use for processing does not have cheap processes. Then the only feasible solution is to build a static channel network with processors.

Another interesting point is that most languages with static type systems have latched onto the channel solution. It is easy because a channel can be annotated with the type traversing the channel. But it also trains programmers to think in that model. It would be fun to see a language where process Id's - that is names of processes - have a type of what that process receives.

The concluding remark: ZeroMQ/Erlang above is just an example. You can find this kind of reinforcement with basically any language design choice. It is rarely that a feature is ubiquitously good or bad. Rather, most choices are a trade-off. Haskells lazy evaluation enables some optimizations but disallow some other optimizations. Ocaml, being eager, can do the optimization that Haskell can't and can't do the ones that Haskell can. Similarly, for a programmer, getting easier access to some feature often means less control of something else, or that something else become much harder to pull off. The next time you enter in a discussion on the merits of a given language feature, make sure there is not a programming language holding your leash and telling you what is right or wrong!

Erlangs parallelism is not parallelism!

2011-07-04T07:40:00.000-07:00

This post is all about parallel computation from a very high level view. I claim Erlang is not a parallel language in particular. It is not created with the primary goal of speeding up computation and harnessing multiple cores, your GPU and so on. If that is your goal, there are other languages which will probably fare much better for your needs (Haskell, for instance).

Note however, while Erlang is not a parallel language, its runtime is rather excellent at forcing out parallelism of existing concurrent programs. So when we say Erlang is parallel, we say that Erlang is parallel in a specific way! The recent years have seen much work in Erlang/OTP on making the runtime concurrently parallel and we are reaping the benefits. The reason can be found in the simple observation that a Erlang program has thousands of processes which gives thousands of executable threads of control. Since you have more than one thread of control, and communication between them is largely asynchronous, you have all the opportunity for a parallel speedup.

Parallelism vs Concurrency
A fine point indeed, is that parallel computation and concurrency are different entities when considering computation. Simon Marlow has a blog post in which he describes the details.

The gist of it, however, is rather simple: computing parallel is to hunt for a program speedup when adding more execution cores to the system running the program. This is a property of the machine. Computing concurrent is to write a program with multiple threads of control such that it will non-deterministically execute each thread. It is a property of the language.

If you come with a view from the hardware and upwards toward to computing logic, then surely you may fall into the trap of equating the two terms. The reason is that to implement parallel computation in current hardware and software, you use a concurrent semantics. The pthread library for instance is writing a concurrent program which then takes advantage of multiple processors if they are available. To
program for the shared memory architecture, you use mutex'es and locks. Most other methods build on top of these primitives. Deep down at the hardware level, it is the presence of a Compare-and-swap
operation that is at the heart of the idea.

One may then surmise: are we always going to use these primitives deep down when we implement parallel programs. Are we always going to go parallel from the concurrency primitives? If your opinion is largely yes, then you may hold the view from below, from hardware and up.

The view up from the logic and down, is that the language has certain constructs available to it, of which some are parallel. How we are going to implement those features is postponed until later. That is, we squint our eyes in a way such that we cannot see the deeper down details - but can concentrate on the general ideas. One could imagine different hardware on which another implementation would be more beneficial, for instance by running on special purpose hardware for the task, an FPGA or a GPU.

The main point is that parallelism is a declarative notion in the logic. If you want an array processed in parallel, you are not going to explain how the underlying implementation should squeeze in more computational work on multiple cores. You are just stating that the semantics of your program is such that it is allowed to do so. Most importantly, in parallel array processing you must be very specific about the order in which elements are being processed. For some computations it doesn't matter. For other computations, there is a notion of order and you can't screw it up. The difference in semantics here w.r.t. order is among what concerns a language designer with the view from logic.

So there are essentially two views: from hardware or from logic. From the perspective of logic, if you have toyed with formal semantics, is that we define concurrency-primitives in a different way than parallelism-primitives formally. That is, they are different entities. The perspective of hardware on the other hand, conflates the ideas because the only way to achieve parallelism is to use
concurrency - especially in UNIX.

Erlang is not a parallel programming language!
Erlang is not a concurrent functional programming language. It is not concurrent in the sense that Erlang was built for robustness and fault tolerance. To implement robustness and fault tolerance, it was decided that concurrency was a good vehicle. Likewise for the decision to make the language functional. These choices were merely done in other to achieve the greater goal and had to be chosen along the way.

Erlang is not a parallel language either! The goal is to provide robustness and fault tolerance. Going parallel does not directly facilitate this goal, and hence from a perspective of language logic there are very few primitives that has to do with the concept of parallelism. Contrast with concurrency of which there are several central primitives built into the language.

From the view of the hardware and the actual implementation of Erlang/OTP, much attention has been paid the recent years to make the Erlang VM be able to execute processes in parallel. This has mainly been done because you can then increase hardware utilization and hope to gain a speedup in your programs. In other words, it is not a necessity, but a nice-to-have feature.

The main point to take away from this observation is that in Erlang, parallel computation is implicit. If you write your program in an idiomatic way, you will often find that there are automatic speedup gains from going to multiple cores. But you have little direct control of how things are going to be parallel. Rather, you design your program such that it can implicitly take advantage of multiple cores.

There is an inherent want for many newfangled Erlang programmers to harness the full potential of their new K-core machine (with K > 1). The idea is simply that by using Erlang, the program will run faster because you will stand a chance at getting the utilization of the cores up.

But this is and has not been the primary focus of Erlang! And hence it is not a given that your program will run faster. To make it go fast, the program has to be written in a style that makes it possible for multiple cores to work on the program at the same time, implicitly.

That said, Erlang was designed in a way that makes automatic use of multiple cores much simpler than some other languages out there. In fact, a common case is that you should be able to speed up an unaltered program in many cases just by adding more cores. Given the focus on robustness and faul tolerance this sounds decision logical. If you have a system that works and is relatively void of bugs, then you should not have to go out and change the internals of the program to make it run faster. The Danger is that your new altered program is incorrect and then it does not matter at all if it runs faster or not.

One might take the goal of Erlangs parallel endeavours as: we hope to achieve a relatively good amount of speedup when adding multiple cores without you having to change the program. That is, if you add more cores, we expect some speedup, but not necessarily a speedup which is the best possible. It is an attempt at a best-effort solution rather than a perfect one. Herein lies the gist of why Erlang is not a parallel programming language. It is not about maximizing the throughput and usage of the many cores, but to use them to automatically enhance an already written program.

Finally, if one looks at the Erlang history, parallelism only came to the language fairly late. While some believe that the language is excellent in a multi-core era because it is (relatively) easy to make the runtime parallel this was not the goal initially. By sheer luck, some of the design decisions made for Erlang makes the language brilliant for running on multiple cores.

Finally, a word has to be said on granularity of processes. What is the smallest piece of computation that can be made to work on multiple cores. In Erlang, the grain is finer than most other languages concepts of "threads". And processes are so cheap that it is easy to spawn a new one to do separate computation. But it is important to note that the grain is coarser than the Haskell concept of a "spark" (see
Runtime support for multicore Haskell (PDF) for instance). And the spark concept is spot-on for squeezing out parallelism at a much finer grain than what Erlang has. The essential trick for sparks in Haskell is that they share the Thread-State-Object (context). So you don't have to go start new threads to service sparks, making them much cheaper to execute even if there are millions of them. As an explicit method of gaining parallelism, sparks is a very interesting concept.

In conclusion: Erlang can do parallelism in the view of adding it on top of concurrency. This means that parallelism is implicit rather than explicit in the program and hence you want to program in a certain style to make sure your program goes fast. The rest of this post here are ideas for doing that.

Utilization vs Speedup
It is very easy to get full utilization of a 128 core machine: Let 1 core do the actual work, and let the remaining 127 cores run an infinite loop.

All cores will now show that they utilize 100%, yet the program is not running any faster than before. We would love to have the program run 128 times faster, now we had 128 times the computational power available. The actual *speedup* is what we are after.

As a programmer, you have two goals. The first goal is to get the utilization up. You can't hope for speedup if cores are sitting there, idling. *The utilization is an upper bound for speedup*. Next, the goal is to make the additional cores do something better than the endless loop above. That is, decrease the execution time of the program.

It is worth to look at Amdahl's law in the parallel variant. The central aspect of the law is *"serial parts in program will slow your program down"*. That part can only be run on a single core, and hence it will limit the other cores into idling if they have to wait. And when we consider a parallel part, there is a critical path, called the span of the computation (see Work & Span for instance). Making the span smaller will also yield a faster program - but when optimizing for the span, the critical path may jump to another part of the computation.

Also of importance is Gustafson's law. Amdahl assumes a fixed workload size. If we can complete that workload in half the time, we have a speedup of two. But as the number of cores increases, so does the overhead of orchestrating their communication. Gustafson (et. al) proposed that we instead make workload size the scaling variable. That is, suppose the solve a workload of size 1 in 1 minute on 1 core. Now, if we have 8 cores, perfect speedup would be that we were able to solve a workload of size 8 in 1 minute on 8 cores. Contrast with Amdahl: workload 1, 1/8 minute and 8 cores.

Erlang and speedup
While Erlang is not an explicit parallel language, it does not hurt to write your Erlang programs in a style which invites multiple cores to do work. In this section, we will try to give some general advice on how to do exactly that. To make Erlang able to execute programs in parallel, you must obviously structure your program as such.

First, your process run-queue must have enough work that it can be divided among several cores. If there is only ever a single process that can run, that will limit the parallelism of your program.

Second, be aware of serializing bottlenecks. A process executing is the granularity. So if a large number of workers all go to the same single process for their data, that single process is now the contention point which is serial and for that part of the code there will not be any speedup. If the query to the single process is dominating in your program you are in a bad shape. The extension of this is rather simple: if you have 4 workers processing a queue, then your maximal speedup is 4. This may not be enough on a 16-core machine.

Third, synchronous calls blocks more than asynchronous casts. If possible, prefer asynchronously communicating processes over synchronous ones. Long chains of synchronous calls following each other are serialization in disguise. They block out other callers when they are processing. They are also prone to creating deadlocks in programs. Asynchronous calls will in addition tend to fill up mailboxes with work. It is much more efficient to handle 8 messages in a context switch time slot than it is handling 1 message and then switch right away on an empty queue. In some cases you can go pseudo-async by making 1 out of 100 calls synchronous for instance. This is an effective way to ensure that you don't overflow a slow receiver as it forces in some amount of flow control.

In Erlang a process is very cheap. It is far cheaper than a `pthread` thread in C. This leads to a programming methodology where you are not afraid of creating processes. Much like you would be creating objects in OOP. A million processes is not a limiting factor. A good design choice in Erlang is simply to create a process per incoming request or event. Take an HTTP server for instance. Each GET-request will spawn a new process to handle that GET. Had processes been heavy in weight, this approach would not have been viable at all. The idea is that the data you are going to be operating on is morphed into a thread-of-control so the data itself can go ask other parties for information, process on itself and so on. There is a strong similarity to OOP here as each process plays the role of an living object (they are "dead" in OOP only to be temporarily revived from their zombie state when the current executioner of control comes by).

The design effectively ensures our run-queue is always filled up well with work to do. Had we opted for a queue-pipeline approach as is common in many other languages, the amount of workers working on each queue would have to be tuned to the number of cores. Furthermore, you have to watch out for overloading a specific queue. In our morph-data-into-process design it is the run-queue we have to watch
out for, but that is simpler and there are tools for doing it (see for instance Erlang Solutions esl/jobs application).

Note, however, that if these many small processes all request data from the same server-like process, then performance will dwindle and suffer. The server-like process is a serializer which we warned about earlier.

One idiom I commonly use is to have a protected ETS table with the option {read_concurrency, true} set. When all the spawned processes want to read data, they go directly into the ETS table and fetch what they need. Writes are serialized through a central process. Of course this scheme can be altered if you need a large amount of writes, or general reader-writer access.

In the newer Erlang/OTP releases (R14 and upwards, I believe) the access to the ETS table is highly parallel in the runtime. Hence, your million processes will not have to wait on each other to read data out of the table.

Another common trick is to increase the independence of computations. Whenever you can eliminate some sharing, perhaps by recalculating it or caching it somewhere, then you increase the independence of the computation. In Erlang semantics, processes have exclusive access to their own data. Hence, the independence of data is already really good. What you want to avoid is having to partner with other processes to solve a task -- if the partner is heavily contended.

The central point is to be aware where serialization might occur in your code and then eliminate it. Otherwise, you may see a bad utilization, and no speedup. There is a nice tool, Percept, which can profile the runnability of a process; when a process or port can be run on a core.

Also, you should be aware of the following interesting gotchas:

I disabled SMP and now my code runs faster!
Yes. This is a common thing. First, when you benchmark your code, a very grave but all too common mistake is to use your code optimized for parallel execution on the single core. Parallel code often has some overhead due to communication and often, it also impedes the execution speed if you run it on a single core only.

You must benchmark the fastest possible non-parallel version of your program and count the speedup against that. The other solution is simply not fair. It is one way you can make your benchmark look better by cheating.

The overhead is also present when you take your program, written in Erlang, and run it on the non-SMP variant of the Erlang VM. It can often go faster for some work loads. The reason is that your program may not exploit parallelism that well and thus the overhead of going truly parallel is dominating the actual speedup gain. I have seen this with some of my Haskell programs as well.

There is a fairly high price for suddenly having multiple cores inside the VM doing things. You will have to synchronize in the runtime and even though your synchronization primitives are heavily optimized, they have overhead. Now, if the problem you are looking at is not even saturating a single core, then surely, it would have been better to run in a single-threaded manner. It is only when you could benefit from a second core that it will help you.

If, on the other hand, your problem maxes out the core, then adding a new core to the mix has some overhead, but it will make the computation scale further and you may experience a better throughput in the end.

So if you are well below a single core in utilization, this is often a way to lower the amount of work your system has to do. And make the code run faster.

My code has faster than perfect speedup!
Another common thing that can happen is super-linear speedup. That is, you may have 8 cores and expect a speedup close to 8 -- but all of a sudden you have a speedup of 12. This happens. The reason it happens is usually that when you add cores to your computer, you also alter other resources. Most notably, you often increase the amount of available cache. If you distribute the computation over multiple physical machines, you may also increase the amount of available RAM.

These factors can improve your computational speed by quite a lot if you can manage computations such that they become independent of each other. It directly reaps the benefit of the added caches as there will be no migration of data from one cache to another. If the computation can suddenly fit into the caches, then the speed can be much increased. Likewise, the same pattern can emerge if you add more RAM to your cluster. Suddenly the central data can be kept mostly in memory and you don't have to load data off the disk anymore.

Hiding latency - the secret weapon for fast parallel computation

If there is a single trick resulting in fast parallel speedups, it has to be latency hiding. Note problems come in three varieties: The simple, the impossible and the interesting.

The simple problems are called the Embarrassingly parallel problems. They are simple to solve: split them into equal sized chunks and solve each part. Then reintegrate the individual solutions into a final result. The idea of Map-Reduce leans itself to a solution method. It is obvious if your problem is simple, then Map-Reduce solves it. The impossible problems are the class of problems for which you have little to no hope of speeding up the computation by having more cores. A compiler, for instance, can compile multiple modules at once. But the steps of lexing-parsing-code-gen-optimization-and-so-on has to happen in that order and has to happen in a serial fashion - a large span is dominating. Some numerical iterative computations require a finished computed step N before they can tackle step N+1. These problems are so data dependent that you have no hope of making those parts parallel. Essentially the span of each iteration is chained together in a way that makes it impossible to speed up.

This leaves us with the interesting class of problems. In order to compute these, you need to have some amount of sharing/dependence in between the processes. And this is where the latency hiding trick comes into play.

When one process sends data to another process, there is latency involved. We must copy data into another mailbox, or perhaps copy to another computer. The bandwidth of the network and the size of the data we have to copy puts us into a situation where there is a minimum latency we can expect when we copy. Now, the naive solution is to repeat a two step process: Compute this iteration. Then Exchange this iteration with other processes. But every time we exchange data the processes are waiting and are idle. If communication time dominates, then our speedup will suffer.

The latency hiding idea almost doesn't even warrant a name: "do something else while the data transfers". That's it. Like an operating system is doing something else while a process waits for disk IO to complete, a process can do something else while waiting for data to transfer.

To Erlang programmers this means that the order in which you send and receive matter. If you reorder the receives such that the communication overhead is hidden, then your program will be able to find the relevant message in its mailbox already there when it is needed. The rule is send early and receive late. As soon as you have data another process will need, you must make it available to them. And when you need data make sure you get it as late in the process as possible, just before you need it. That way, it may already be there in the mailbox, ready for you to use.

The conclusion is that one must take into consideration the impact of latencies. In high performance computing it is of primary importance. A worthy bet is that on modern computers, moving data around is often the bottleneck. Not the raw speed of the CPU core. If we have a distributed system, then the latencies may be much higher due to network copying - with a much higher impact on speed. The CPU cache also plays a crucial role in limiting the speed by which your computations will run.

Conclusion
We have given a brief overview of some of the parallel computation basics. We have argued that concurrency and parallelism are different beasts. We have argued that Erlang is not particularly parallel. We have surmised on what one should do to increase parallelism in Erlang programs. We have also hit on a small number of interesting gotchas when computing parallel. And we have discussed about the concepts of latency hiding.

There is much more to be said about Erlang and parallel computation. I particularly like that Erlang does not assume a cache-coherent architecture for instance. But that will be a post for another time since I am all out of blog space and this is already too large.

Google+ - so what is different, technically?

2011-07-01T05:10:00.000-07:00

Google released Google+. Everyone has now blogged about whether it will "rank or tank", but nobody has really looked into the concept of circles from a more technical viewpoint to my knowledge. Let us remedy that.

Online communication services can all be classified according to different aspects. A chat IM message is, as an example, usually a one-to-one realtime communication. There is an assumption that I will answer a chat message rather quickly - even when I don't have to. IRC - Internet relay chat - is different: communication is topical as I join a channel discussing a certain topic. Communication is many-to-many and there is no assumption I answer the message right away. Likewise for emails - but there exchange of messages happen at a slower pace with larger bodies of text. The reason you use more than one service is essentially that different communication services cater to different kinds of communication. The collaborative benefits you gain when developing source code over IRC is not paralleled in any place currently for instance - not as a free open project at least.

What kind of communication services disrupts your flow of thought by alerting you and requiring you to answer (phones, I am looking at you!)? How realtime/instant is a message? Can you post additional content like photos, images, urls? Can you split communication into topics of interest? Are topics invite-only or free-to-join by default? How is moderation done on topics? Is it easy to form groups of privacy to discuss something? Is the communication one-to-one-focused, or is it one-to-many or even perhaps many-to-many? Can you build robots to automate tasks for the service? And so, in the light of Google+:

Google+ major point is to work like Facebook does in the core. This means that I am not the primary customer - as I don't use Facebook much. Hence, I am probably the wrong guy to judge if it will work out or not. By the core of Facebook, I mean that the primary goals of G+ and FB overlap very much. In the long run, the goal is to form a relation-graph between people and get access to it for Google.

The major, essential, difference between Google+ and Facebook is the formation of connections. In Facebook, A adds B and then B confirms the relationship. The opposite of this is Twitter: you just follow people you are interested in. Facebook runs a 2-way handshake whereas Twitters is one-way. Since connections in Facebook is 2-way, then we trivially have: if A is connected to B, then B is also connected to A. In other words: the connection graph is undirected in Facebook. Contrast with Twitter: graphs in twitter are directed. There are numerous one-way connections in Twitter. Most notable are celebrity-figures with an extremely high amount of followers. The communication from such an account is essentially 1-to-many and public.

So what does Google+ do? It chooses a variant of Twitter. In G+, the graph is directed like in Twitter, but you also label the edges with a name -- your circle designation for the connection. You can have multiple edges to the same person/account, so in reality the graph is a multigraph where edges are discriminated by their circle-labels. Another representation is to deem that a graph edge is labeled with a set of circle-labels.

When A adds B to the circles, A is adding an edge in the graph from A to B for each circle. So A builds a one-way path to the other end. If later B decides to add A to his circles, then there will be edges in the opposite direction. They may not be labeled the same at all. This means that A can have B in the circle of close friends while B has A in the circle ObnoxiousCatPhotoSubmitters. This is an interesting skew of connections which come into play. When you post something to a circle, the recipients can not see the message as if it is originating from that circle - in fact circles are exclusive to an account and can't be seen by others. This in effect makes a message a low-level value which is exchanged from a sharer to a list of people the sharer decides via circles. Upon receipt, the message is then cast into the light of the recipients circles.

So forming connections is like in Twitter, only that edges are labeled by Circles given by the source. This is a rather genius move. When A shares, he chooses the circles he want to share the message with. The system then searches all edges labeled with those circles, and posts on those edges only. If A wants to post Tech-related stuff, A can do so in the Tech-circle so only people that might care is hit by the sharing.

The sender, A, has complete control of who sees the message. This is what Google refers to as the ability of G+ to accommodate different kinds of privacy levels on messages. Also, it is the sender, A, that defines his or her own levels of privacy with Circles as they are local to an account. It also blurs the definition of "follower", "friend", "connection", "add" and so on. Some edges are labeled as "close friends" and are thus strong edges from a privacy perspective. Other edges are weak in the sense that you have a connection, but there are limits to what you want to share with the other person.
When data arrives at B, messages from A gets sorted according to the circles of B. So when B looks at streams from circles in which A is in, he sees the shared information from A.
Consequence: A needs to moderate what he sends along the Tech-circle to B. If A begins sending Cat photos to his tech-friends, he will end up in the ObnoxiousCatPosters circle at B - and only that circle. B is free to replace him at any time if he wants. The assumption currently is that relations between people are formed one primary ground. "He is family". "She and I are always discussing cool graphics design". This may largely be true.

One thing I have not figured out yet: Suppose I want to follow B for more than one interest. Cats and Dogs. I have a circle of Cats and one of Dogs. But when B posts in his public circle for all to see, his posts will end up at my place in both Cats and Dogs. To the best of my knowledge there is no way I can currently split this. My guess is that Google will have to solve it in the longer run. They have several options among of which is to use statistical analysis on the posts through machine learning. Or allow #tags as in Twitter.
Another thing I have not figured out completely yet: I don't think G+ can substitute for the other communication tools I am already using. Since I am not much of a Facebook user I am not the right demographic, but I don't see G+ replacing Email, IRC or Twitter. Twitter is the thing it will have the best options at replacing in my opinion. Email and IRC needs a more wave'esque approach to the problem I am afraid. I would really like to see an "IRC for the masses" and I am not convinced that Huddle is it. Further, the locality of circles to an account makes them distinctively different from IRC channels. On the other hand, if you have a topical connection graph, you can use machine learning to suggest IRC-like topics later on - and it is not that hard to add proper IRC-like group chat features to Google Chat which is already integrated.

I find the technical difference mentioned here quite interesting. It is definitely a generalization of the existing models of connection-forming, and it will be interesting to see if it takes off, and what people will get out of using it.

So in conclusion: G+ is a funny hybrid between the style of Facebook and Twitter. The circle concept is central to how the connection-graph is formed. And thus, central to how G+ works. It will be interesting to see if Facebook will have a counter-solution. Currently, FB can create groups of friends and handle these in many ways like G+ can handle circles. We can only hope that this competition from Google will force Facebook to improve their system as well. But they probably can't get rid of the two-way connections easily.

Web Server Benchmarking, a rant.

2011-06-01T04:02:00.000-07:00

When people carry out benchmarks of web servers, their reporting of data is often inadequate. Apart from the trouble of http://www.mnot.net/blog/2011/05/18/http_benchmark_rules and getting that right, I want to focus on the reported data. The main point is this: Don't maim the raw data by taking the mean - give us a link to the raw information so we can draw our own conclusions. And don't use benchmarking tools which destroy the raw data after test.

Overload:
The interesting situation is not the standard situation. What you want to know is not that server X is 30% faster than server Y - but rather what happens when the server gets a spike of incoming traffic. That is, the Poisson teams up against you and you hit serious load. In that case, you want the server able to sustain the load instead of the server which will degrade in performance.

It is far better to dismiss some operations as errors quickly but do serve the requests you accepted, and serve them fast. The raw speed matters less as 30 or even 70% is just a constant factor deciding when you need to scale - either a faster machine or a new one next the the computer you already got. Of course, with 150% it begins to matter a lot which is faster, but for most servers, the speed is so good it doesn't matter. Stability and the overload situation is more important to optimize for.

Errors and latency:
In a benchmark, there is a bar which describes what is an error. In some benchmarks, the error will be a request which never completed. In other tests, it will be that a given request took too long. There is little reason to accept a request of 10 seconds as the poor user will almost always have reloaded or clicked again. Moderns users are impatient to the point of being painfully so.

This leads to the idea we should regard requests which are too slow as errors as well. If a request doesn't complete under 5 seconds, it is an error as well. But for a lot less, users may become bored on your site and not use it. Even a 100ms bump can mean a lot.

This leads to the virtue of the benchmarker numero uno: Record latencies for the measurements

You should, ideally, be recording each of your 250000 requests and their individual latency. But this is usually too much for the benchmark tool to handle. Rather, you want the tool to do random sampling and record, say, 2500 samples and store them in a file. The cool thing about this is that you can hand the data out when you present your information. It is like cake to a statistician, who will be able to use the raw data.

Beware the heretic: Average
Unfortunately, many benchmark tools report statistics rather than raw data. They will give you the minimum, maximum, average, median, stddev and so on. The very first thing you should do when you get raw data is to plot them. You want to see what the data looks like. Just a simple histogram plot can often tell you a lot about the data at hand:

This looks fairly okay as a normal distribution of data with a mean of 7 and a standard deviation of 2. In fact it is, because it was randomly generated as such. Here is another one:

And that one is very interesting. It has an odd latency spike around 25 as well! Again, the example is generated from two normal distributions whose observations we have plotted here as a histogram. For the first one it may be ok to use the stddev and average value because they make sense in that case. But for the second it is most definitely not acceptable. We ask R for the summary of the first:

> summary(a)
Min. 1st Qu. Median Mean 3rd Qu. Max.
0.1309 5.6200 6.7750 6.8090 7.9960 13.3500

For a web server the Min value would tell us something about the lower limit. If the server is 30ms away travelling at the speed of light, that is the minimum value we can ever hope for. The Maximum observation is interesting as well. If it is too high, the user will not hoover and is gone. The mean is the average value of the observations. We'll get back to the dreaded mean. The 1st quartile, Median and 3rd quartile is achieved by lining up all the observations in a sorted manner to get the distribution function:

And then you pick the guy 25% in from the left of the X-axis as the 1st quartile. The guy at 50% as the median and finally the guy at 75% as the 3rd quartile. If there is no middle value (in the case of an even number of observations) you pick the mean between the two middle observations. For the first example plotted here, the median and mean is basically the same value. But what about example 2?

> summary(example_2)

Min. 1st Qu. Median Mean 3rd Qu. Max.

0.1309 5.8300 7.1380 9.4180 8.9150 26.1900

This looks bad. The Median and Mean doesn't line up and this should normally be a warning sign you should plot the histogram. In fact, if you look at the above histogram plot you will find that the observations around 25 skew the mean too much to the right. In fact 9.4 is not a very likely value. It is more likely to get either a 7 (in around 85% of the time) or a 25 (around 15% of the time). The median tells us that the most likely value is around 7. The distribution plot should tell us something as well:

A value of 17 is highly unlikely. Yet, if I had constructed more observations in the 25 area, then the mean would have been 17. That is why the mean is a bad indicator for a data set. And it is why we want the raw data. If you report something, make it be the median. Or make whiskers on your values so we can see the development as you increase your load on the server:

Notice how Mark Nottingham adds small vertical bars to each measurement so he can report the range in which most of the repsonses fall? That is a neat idea!

Even better is to use boxplots on each observation so you can see how it relates to the mean value:

My hunch:

I think there is a gem to be found but currently hidden from our scrutiny. I hypothesize some web servers are far better than others when it comes to harnessing the latency and keeping it stable, whereas other servers are more likely to skew the results a lot. It tells you a lot about the robustness of the server and it is another key factor on which to measure. I don't care that much about requests per second as I care about this number. It is like claiming your network is better because it has more bandwidth, blindly ignoring the question of latency (a rant for another time).

Face it, if you measured two web servers correctly, you could do the statistics to figure out if one were significantly (in the statistical sense) better than the other. In Ostinellis work, http://www.ostinelli.net/a-comparison-between-misultin-mochiweb-cowboy-nodejs-and-tornadoweb/ for instance, we see that mochiweb is only 66% faster than Node.js, which isn't going to make a dent in practice. The 25% difference between Misultin and Cowboy reported is even less so. But the response time for Node.js is 6.6 times as large compared to Mochiweb. (Around 600ms compared to around 90ms at 10000 in load). That is difference you should be worried about. And that is the reason for my plea:

Give us latency samples when you benchmark web servers!

(Edit: Smaller changes to sentences in the beginning to get the narrative to flow better)

Node.js vs Erlang is the wrong battle.

2011-05-06T03:26:00.000-07:00

Every once in a while, we see the same discussion popping up again: "Should I concentrate on Node.js or Erlang for my needs?" Let me be clear: I think it is the wrong discussion. Fact is, if you have chosen a language which support a large number of concurrent tasks at the same time, you are probably going to be ready for the future.

Divination is hard, but I am not sure we are going to see a fast multi-core revolution with thousands of processes. As per Moore's law, if transistor count increased as we would like, we would have had 2 cores in 2006 (Intel Core 2 Duo), 4 (physical) cores in 2008 (Core i7, Intel also) and 8 physical cores in 2010. Where is my 8 core laptop today? Even Sandy Bridge is not up there. I have a hunch a couple of things are happening: the market has seen a shift to low-power devices, which is more important to the consumer, notably by the ARM incursion. And people can't utilize a multi-core machine with 8 cores since their programs are not written to take advantage of several cores. Finally, it is cheaper to buy infrastructure on-demand at places like Heroku, Google, Amazon, Microsoft, Rackspace and so on.

But if parallelism is not coming, distribution and concurrency is! Modern programs have to live on several devices at the same time. You check your mail on the mobile phone, on the tablet device, on your laptop and on the workstation, if you still use one. Likewise, a modern program will probably live on multiple devices at once and to harness that game, you need efficient distribution. Enter new languages with support.

And this is why the battle must stop. Like a game of Chess the point of the languages are to be different. Haskell, Google Go, Erlang and Node.js all come with a given set of features for controlling the multi-core problem. But like in Chess the pieces are different and built for different purposes. And here we are only looking at current implementations. Theoretically, the ML family, with Standard ML, Ocaml and F# are really well suited for the concurrency and distribution revolution as well, even though the implementations lack in robustness.

The enemy of the state, is a large set of old ways of programming. It is not so much the language chosen as it is the ideology. You can't rely on shared information when the RAM is physically split between two devices (and you have no fast reliable link in between). You can't rely on OOP in the Java sense to save you. And you can't usually get consistency across the distribution parts due to unreliability.

Rather, see the different languages as stakes in the future of computing. They are different for a reason and they gamble by being different. Personally, I like Erlang because it has what I see as a good view of the problem and hand, and a novel way at solving it. Yes, it can be made better in so many ways, but I think Erlang is at the right point on the "Worse is Better" scale. It actually solves a lot of my real-world gripes.

Node.js plays different cards in the game. I really like the mix of continuations, lack of blocking, V8 and Javascript on the server side. Go plays it yet differently, taking a much more low-level approach to the problem at hand. Go feels like an updated C with channels, and it got substructural subtyping to boot. Haskell is just awesome because the language needed very little change to support concurrency. The semantics of Haskell are on a different level than most other, and with Haskell, it is the fabric of computation you are mangling to your desire.

In the endgame of Chess, pieces like the knight become less efficient since its cunning ability to pass through other pieces is not as powerful. Time will tell what piece was the knight. But if you did not bet on every approach, you wouldn't know if you just hit a local optimum.

2011-04-06T08:37:00.000-07:00

4 Functions and one view

Let us define an Agda module:

>    module Partition where
> 
>    open import Data.Bool
>    open import Data.Nat
>    open import Data.Product

In Agda, we can define the option-type as the following hybrid between Haskell and ML:

>    data Option (A : Set) : Set where
>      Nothing : Option A
>      Just : (o : A) -> Option A

That is, option types are formed by either being Nothing or by being Just A for some element type A. Likewise, we can define Lists as:

>    data List (A : Set) : Set where
>      [] : List A
>      _∷_ : (x : A) -> (xs : List A) -> List A

That is, lists are either the empty list [] or they are formed as a cons operator, where we have an element x of type A, the head, and a tail-list. Together this forms a list.

We now define a really simple function on lists. We will ask if there is an element of the list that satisfies a predicate p. That is, we ask “Exists an element satisfying the predicate?”

>    exists : {A : Set} -> (A -> Bool) -> List A -> Bool
>    exists p [] = false
>    exists p (x ∷ xs) with p x
>    ... | true = true
>    ... | false = exists p xs

The function makes use of a with statement of Agda. with p x can in this case be seen as a case p x of where the two possible variants are then handled to the left of the pipe bar |. The three dots, ... signifies that nothing else change in the parameters. Generally, the match in Agda is dependent, so the output of p x could have constrained the other parameters (that is the other parameters depend on the output of the match).

This function is very simple, but it does not yield us a lot of information, should we want to know which element that actually existed. Essentially, we have become blind to some information. On the other hand, if we are only interested in the question of existence, then the function will not produce additional information, we later need to throw away.

Let us add a remedy to our alchemical formulae: We present the find function:

>    find : {A : Set} -> (A -> Bool) -> List A -> Option A
>    find f [] = Nothing
>    find f (x ∷ xs) with f x
>    ... | true = Just x
>    ... | false = find f xs

This guy is exists-one-step-up. Here, when our scrutineer finds a matching element, we return the element itself. Thus, if we need the element for further work, we have it at our disposal. In practice, it may seem more expensive than exists, but it is not: first, x we return is a reference, so it has a fixed size. Furthermore, if we don’t use x, then the compiler is free to declare all code involving producing x as dead and remove it from the code. Essentially, a compiler like Haskell’s GHC will probably re-obtain the exists version automatically by optimization.

But the sexiness of this function is still pretty low. We don’t know if there is only a single element matching, or if there are more elements matching. We add another ingredient, and present to you the filter function:

>    filter : {A : Set} -> (A -> Bool) -> List A -> List A
>    filter f [] = []
>    filter f (x ∷ xs) with f x
>    ... | true = x ∷ filter f xs
>    ... | false = filter f xs

Now, when the function return, we get back a list of all the guys matching the predicate. Thus, we can just pick up the head and in a lazy language, we would probably not make more work on the rest of the list if we chose to do so. It is yet a generalization in our stack. It provides a view with a lot more information than from before. We can for instance easily detect the case where there are 3 elements satisfying the predicate by pattern matching, and then handle that case specially, should we want to do so.

But we are not done yet. Everything was merely foreplay. Add the next level of abstraction and generality:

>    partition : {A : Set} -> (A -> Bool) -> List A
>              -> List A × List A
>    partition d xs = part d xs [] []
>      where
>        part : ∀ {A : Set} -> (A -> Bool)
>              -> List A -> List A -> List A
>              -> List A × List A
>        part d [] yes no = yes , no
>        part d (x ∷ xs') yes no with d x
>        ... | true  = part d xs' (x ∷ yes) no
>        ... | false = part d xs' yes (x ∷ no)

Partition use a discriminator function, d, which splits the list into the yes’s — those matching the predicate — and the no’s; those that do not. It is interesting we can walk down back the chain easily:

>    filter₁ : {A : Set} -> (A -> Bool) -> List A -> List A
>    filter₁ p xs = proj₁ (partition p xs)
> 
>    find₁ : {A : Set} -> (A -> Bool) -> List A -> Option A
>    find₁ p xs with filter₁ p xs
>    ... | [] = Nothing
>    ... | x ∷ xs' = Just x
> 
>    exists₁ : {A : Set} -> (A -> Bool) -> List A -> Bool
>    exists₁ p xs with find₁ p xs
>    ... | Nothing = false
>    ... | Just _  = true

Which shows how partition is an aggressive generalization of exists.

Essentially, this is a question of information you have when using the different functions. With partition, you have the most information: you know exactly which elements matched, and which did not. Again, with enough optimization, it should be possible for a compiler to derive the faster versions if possible. The view this function provides happen to be better than the views the other functions provide. It is, in some sense, the correct implementation.

In Agda, views mean something more specific. A view there is a datatype, with the sole purpose of being evidence of some observation. If we compute some outcome, we shove the resulting information into a data type, the view and then we can later ask the question “Why?” by matching on that type. The Agda tutorials has more details, but the general idea of using a data structure to carry information is what motivated this blog post initially. I also find the relationship between the four functions interesting by itself.

You may wonder: Why do we even bother to have the other definitions around? Mostly, it has to do with optimization hints to the compiler. An implementation like find tell the compiler we are only interested in a single element, first match and it can throw away other parts of the computation. In other words, it can be seen as a guide to the compiler about our current intent. It is also an intent-hint to the human reader. We make it explicit we don’t need certain parts of the computation, so the reader is free to ignore those.

In some languages, the only discriminator is the boolean test. So you are essentially forced into a model where either you only have exists or you are to write a specialized version of the above whenever you need access to them. If your language miss Algebraic Data Types or has no construct which can stand in for it easily, then you are doomed to reimplement lots of stuff all the time. Your modularity suffer deeply as a result.

Agda musings on huttons razor

2011-01-24T15:32:00.000-08:00

Agda musings on Huttons razor

So Ralf Lämmel, also known as “Professor Fish”, defined a small language of which he took full copyright. The language was used as an assignment for students hacking Haskell and they were to carry out two alterations on the language in question. First, they were to give it a CPS style semantics and next, they were to define an analysis determining when expressions in the language were pure.

So far so good, but I am kind of tongue-in-cheek when I see tasks like these. And I wanted to play a bit with the idea. The first decision was to throw out Haskell as a tool. No, if we will have types, then let us get some real types. Dependent types. And let us require that all our programs terminate while we are at it. In other words, employ Agda2 to solve the task.

We begin by aptly naming the module as fish

module fish where

in honor of the grand professor who devised this magnificent language we are to present shortly. To define the language, we will need to pull in some Agda libraries for our use. If there is anything I’ve missed in my Twelf-hacking, it is the ability to use libraries defined by others when I am writing code.

open import Function hiding (const)
open import Data.Bool
open import Data.Nat
open import Data.Product
open import Data.Sum
open import Relation.Binary.PropositionalEquality

At this point, we get to define the language in question. We begin with a simple definition of a local module in which to define the language:

module HRazor where
  data Exp : Set where
    Const : ℕ -> Exp
    Plus  : Exp -> Exp -> Exp

What is this? This language is in a HRazor module. While it seems Professor Fish took copyright on the language, we know that Graham Hutton already took a patent on this language and dubbed it Hutton’s razor. We will shortly see that the language is different from the one which Ralf had in mind eventually - but the Razor is at the heart of it.

In Hutton’s Razor, we have expressions defined by Exp and these have exactly two constructors. The first constructor, Const takes a natural number and returns an expression. Note how Agda is a Unicode-aware language. This is an idea that will slowly creep upon you until you begin liking it. It signifies constants in the language. The other constructor, Plus adds together two expressions. This is the full language.

Is the language silly? Most decidedly not! Suppose you are researching some new idea in language theory. The Razor described above is about the smallest language you can define that does something meaningful. So your idea better work for the razor. Otherwise, you can as well ignore getting the idea working for harder problems.

Here is the function for (denotational) evaluation of the language:

  eval : Exp -> ℕ
  eval (Const y) = y
  eval (Plus y y') = (eval y) + (eval y')

which for most programmers of functional languages should be pretty straightforward. Essentially, we turn the expression tree into an evaluation in Agda.

Ralf adds a construct

Ralf’s assignment does not revolve around Huttons Razor. After all, Hutton has a patent (which he graciously grants every language researcher free use of). Rather, Ralf augments the razor with a Exit construction:

data Exp : Set where
  Const : ℕ -> Exp
  Plus  : Exp -> Exp -> Exp
  Exit  : Exp -> Exp

The informal meaning of Exit is this: Exit e will evaluate the computation e and then abort the rest of the program, returning e as its value. To reflect the idea that the program may be in two possible states now, either computing, or exiting, we need a way to tag what state we are in. Haskell people have the Either a b type, but in Agda, this is a disjoint sum:

R = ℕ ⊎ ℕ

Ralf generously provided some helper functions defining an algebra for how to compute with the disjoint sum so we translate these to Agda. Constant expressions are injected to the left in the sum:

const : ℕ -> R
const i = inj₁ i

Addition compares the two sides. It propagates right injections up, but computes on left injections. This is as Ralf does in his post.

add : R -> R -> R
add (inj₁ x) (inj₁ x') = inj₁ (x + x')
add (inj₁ x) (inj₂ y) = inj₂ y
add (inj₂ y) y' = inj₂ y

Finally, if we want to exit, we convert a left injection to a right one, and just pass on the right injection.

exit : R -> R
exit (inj₁ x) = inj₂ x
exit (inj₂ y) = inj₂ y

The neat thing about defining an algebra like this for R-computations is that now the evaluation function is almost as simple as in the Razor:

eval : Exp -> R
eval (Const y) = const y
eval (Plus y y') = add (eval y) (eval y')
eval (Exit e) = exit (eval e)

The only new thing is the Exit case which formalizes our informal definition above: compute eval e and exit with it.

So what is the point?

Well, this is Agda, so we can analyze the language we have defined for some very simple properties easily. Remember that I said that Agda programs are required to terminate. This comes in very handy when we want to prove that our language does, because we have a definition of it in Agda.

If Agda’s termination checker says that the Agda-program terminates, so does our Ralf augmented-Razor. In other words, we immediately have the property. Neat. In the same vein, our language must be deterministic. These properties can be formalized in Agda and proven as well, but they are immediate.

Task 1, continuations

Next, we CPS-transform our semantics. We could naively transform the language, above into CPS and then provide that, but that is a boring solution. Nay, the cool thing about CPS is that it makes the control flow of the program explicit. We can exploit this explicit control-flow to optimize the case of Exit expressions in the program.

module NotNaive where

Ok, so we throw everything into a submodule, NotNaive, to limit what is in our scope at any point in time so naming is not going to trip us up later.

  constK : ℕ -> (ℕ -> ℕ) -> ℕ
  constK i k = k i

This is part of our algebra as before. If we have a constant, how do we handle it? We add another parameter, the k above which is the kontinuation. In the case of the Razor-extension, we can regard k as “the rest of the program”. It has type (ℕ -> ℕ) which sort-of makes it a transformer on natural numbers. So if we are to deliver the natural number i to the kontinuation, we apply k i.

Additions take two values and delivers the addition to the kontinuation (which still is, intuitively, the rest of the program):

  addK : ℕ -> ℕ -> (ℕ -> ℕ) -> ℕ
  addK v1 v2 k = k (v1 + v2)

In the Exit case comes the trick. We do the following

  exitK : ℕ -> (ℕ -> ℕ) -> ℕ
  exitK i k = i

which is to not deliver the value to k but just return it straight away. This means that we will abort the evaluation of “the rest of the program” and just return the exit value straight away.

We now turn our attention in this language towards the evaluation function in the language. Constants are handled in the obvious way by using the algebra directly, but the two other cases are handled differently:

  evalK : Exp -> (ℕ -> ℕ) -> ℕ
  evalK (Const y) k = constK y k
  evalK (Plus y y') k = evalK y (\v1 -> evalK y' (\v2 -> addK v1 v2 k))
  evalK (Exit y) k = evalK y (\v1 -> exitK v1 k)

Take the Exit-case first. We evaluate the y like in the direct case. But then, we need to supply a continuation which says what the rest of the program does. Our continuation assumes it gets passed a value v1 which is the result of the y computation. It then exits with this value. The Plus case is similar, but there are two continuations to juggle. We evaluate y and deliver it to a continuation that first evaluates y' and then delivers to the final continuation, using our addK function from above.

To run the program:

run2 : Exp -> ℕ
run2 e = NotNaive.evalK e id

note we pass in the id identity function to “start up” the evaluation. This is in balance with what Ralf did. Again, Agda’s termination checker immediately provides termination guarantees for program.

Task 2: A Taste of dependent types

The main reason I set out to do this however, was to utilize the dependent types Agda has built-in. There are something eternally pleasing in defining programs which do not need to compute to answer questions, and here we will see an example of it.

The task is to create a function pure taking an expression and returning true if the expression is pure and false otherwise. Purity is defined as absence of an Exit expression. New module:

module DepAnalysis where

Now, dependent types are more than what the following claims it to be, I am aware. But as a first foray, it is quite mind-boggling in itself and serves as a great simple introduction. If we define

  data Exp' : Bool -> Set where

we have declared a dependent datatype Exp' which has a Bool value attached to it. This means we have two types of expressions: Exp' true and Exp' false. These are different types from the view of the type checker. You can read Bool -> Set as “if we supply a boolean value to an Exp', then it will yield a Set - Set being the elements of the Agda”world" we are working in. So we can just assume in our world, that if an expression is pure, it is Exp' true and otherwise, it is Exp' false.

    Const : ℕ -> Exp' true

This constructor tells Agda that if we supply the Const constructor with a natural number, it will hand us a pure expression. Seems in order, sir! Next constructor:

    Exit  : ∀ {c} -> Exp' c -> Exp' false

This can be read as “if you give my any expression, pure or not - I don’t care - then I will give you a non-pure expresssion”. This makes sense. There is an Exit in the expression, so it better not be pure. It doesn’t matter what the internal expression is.

    Plus  : ∀ {c1 c2} -> Exp' c1 -> Exp' c2 -> Exp' (c1 ∧ c2)

In the final case, Plus we get to supply two expressions. These two expressions have c1 and c2 as their purity-values. Agda will hand us back an expression which is pure if and only if both subexpressions are - due to the conjunction (logical and) in the returned expression.

What have we done here? We have created a dependent data type which will itself track if an expression is pure or not. As we build up the abstract syntax tree, the system will make the calculations necessary. Notice, that if the whole AST is known at compile time, then so is the purity of the expression - right away.

For completeness, we supply the required function pure. Here is the type:

  pure : {b : Bool} -> Exp' b -> Bool

It introduces a new concept, namely implicit parameters. The type {b : Bool} names a parameter which is implicit. We can normally omit implicit parameters when writing functions because it can be extracted from another type in the specification (in this case from Exp' b which contains the b). However, if we need access to the implicit parameter, we can positionally match it by wrapping it in brackets like this:

  pure {x} e = x

So the purity of the expression is already there, we just need to return it! I personally think this is awfully neat.

I want to play more

The Agda wiki contains tutorials, the Agda implementation, and all the other cool information on how to play with Agda. The development here is in a gist on github should you want to play with. Note that the development I made hardly qualifies to show off the really cool features of Agda but only scratches (barely) the surface of what is possible. My intuition is, however, that we will see much more dependently typed programming in the future, when everyone is programming functionally :)

Commentary is as always welcome.

Errlxperimentation: Clustering of Erlang Error Reports.

2011-01-07T15:43:00.000-08:00

Errlxperimentation: Clustering of Erlang Error Reports.

If anyone wonders what I hacked over the holidays, this is it :)

In the Erlang/OTP system, there is a registered process with the name of error_logger. Whenever an error happens in the Erlang system by a correctly configured OTP process, it will send reports to the error_logger. The logger is then responsible for taking the report and in a pub-sub manner send it to any error handler currently configured.

One of these error handlers, log_mf_h, is a multi file log handler. It writes reports in binary term format to a set of files. Whenever a file reaches a certain size, it is rotated and a new file is written. The result is that we essentially have ring-buffer of all errors that occur in a running Erlang system.

A tool named rb the “Report Browser” allows us to read in the binary logs and process them. We can list certain errors, “grep” among them, apply filters to the reports and so on. It gives us a system for looking into a running Erlang system for errors — and handling them if we deem them to be problematic. This tool is very neat when you have a running system to inspect. You can basically leave it on for some time and then go look into the log-mf files for errors and crashes. Since the file is rotated on size the only worry is that important errors get rotated out of the log. But if you have enough log space, this won’t happen. In a modern world, you can easily leave 100 Megabytes of error logs. I have taken the leisure of having a modified log_mf_h which can compress term that goes to disk on the fly. This of course improves the size of error report sizes even more.

The experiment

An experiment that has been on my mind for some time was can I possibly do automatic clustering of similar error reports so like reports are clustered together? If this is possible, I could then just pick a representative for each error cluster and use that as a basis for handling like errors. Even if you have thousands of reports, it may be that there are only a few of them which are really different and a lot of them which are redundant.

I know nothing about clustering. But a question later on StackOverflow and after a kind soul on the #erlang IRC channel hinted me in the direction of the paper Ephemeral Document Clustering for Web Applications (2000) DOI: 10.1.1.59.131 I was set for an experiment with this. The algorithm implemented here is a variant though, mostly due to getting something fast. So it does not implement the full paper. We implement the ideas from there and the paper can be consulted if anything below is unclear (or comment, I'll try to explain).

I altered rb to rerb, short for the riak_err report browser. The Basho guys have this excellent alternative to the sasl application built into OTP, see riak_err and I used that as a starting point. I am not even sure riak_err is the right place for this, but at least this is what I did for now.

Processing

The first part is now to convert an error report. They usually look something along the lines of [{badarg, MFA1}, MFa2, ..., MFaN] where each MFA is a tuple {Module, Function, [Arg1, ..., ArgN]} — and each MFa is a tuple {Module, Function, Arity} (arity being the number of parameters of the function). Note that Erlang errors are Erlang terms, so they are easily manipulated by our code. It does make them harder to read for newcomers however.

First, we linearize and canonicalize the input. We change the tuple to [badarg, {Module, Function, length([Arg1, ..., ArgN])}, MFa2, ..., MFaN]. In other words we flatten the error term and we change the occurrence of MFA to MFa. As an example we may have an MFA [{badarg, {ets, insert, [table_foo, {123, something}]}}] and this is changed into [badarg, {ets, insert, 2}]. This ensures that we don’t care about the difference of arguments, but only care about the arity of the function and the call stack.

Next, suppose an error report has the structure [A, B, C] for arbitrary terms A, B and C. We now form bigrams ['#', A], [A, B], [B, C] and [C, '#']. The '#' is just an atom we use as padding for the boundary terms. For each of these we now run the erlang:phash2/2 function to obtain a hash of each bigram: [{phash2(Bg), 1} || Bg <- Bigrams]. Note we also smacked the hash into a tuple with a value of 1. This list of {Bigram, 1} pairs forms a vector in an (euclidian) vector space where the bigram part names a dimension in the space. If we form bigrams like this for all error reports, and take the union over all bigrams we have a set of bigrams defining the basis of the space.

Now we define a metric called similarity on two vectors, A and B, of the space by (A . B) / (||A|| * ||B||) = cos(t) where . is the dot-product and ||x|| is the norm of the vector x. This is equivalent to the cosine of the angle t (theta) between the two vectors A and B. Now, if two vectors point in the exact same direction, the angle is 0 and the cosine is 1, i.e., perfect similarity. If the two vectors are orthogonal to each other, the similarity will be 0.

The similarity of a set of vectors is had by taking the minimum of any two vectors from the set. It to a certain extent measures how “different” the cluster is because the minimum suggest the most dissimilar result is chosen.

Clustering

We form a forest of singleton clusters, and place each vector/error-report in its own cluster. Then we consider similarity of each pair of clusters. The two clusters with the highest similarity are joined. The joining also forms a binary-tree, a dendogram, of the two clusters. Whenever we join two clusters, the original clusters are removed. So whenever a join is executed, we are left with one less clusters. Recursively repeat this until we have a binary tree. This forms the cluster dendogram.

Listing the clusters is done by choosing a similarity, 0.5 say and then walking the tree until a similarity of 0.5 is reached. The subtree is then flattened into a cluster of like error reports.

Looking forward

The code is in an experimental branch of my github repo, jlouis/riak_err/n-gram-analyzer. Note I currently make no guarantees of its stability currently. I may rebase it still, so poke me if you want to base something on it. Currently you can only configure the riak_err config tree like:

{riak_err,
 [{log_mf, true},
  {error_logger_mf_dir, "log/mf"},
  {error_logger_mf_maxbytes, 10240000},
  {error_logger_mf_maxfiles, 10}
 ]},

and then run rerb:start(). followed by rerb:analyze() to analyze the reports. Listing the clusters are done by rerb:list({clusters, Similarity}) where the similarity is between 0.0 and 1.0.
The code not seen many wars yet, so it is probably quite unstable.

Another important point is that the algorithm used is a simplification of what the above linked paper does. In particular the algorithm is at least O(n^3) though I think one can pretty easily lower that to O(n^2 lg n). Also, there are some constants that can be shaved down to improve the clustering speed (It is not that fast at the moment since it walks lists all the way). Finally, it is not parallel though some parts of it lends itself to a fork/join style speedup.

I’d also want to provide the clustering tree in a raw way, so you can run arbitrary functions over it. I’ll probably implement a variant that for each cluster tells the size of it and picks three random representatives for it.

Final words

The clustering used here seems to work wonderfully well for the error reports I tried it on. It happily clusters up like error reports and different clusters contain different error reports. The Bigrams ensure that we grab the call-path rather than just a presence in a function. We only operate on the stack trace, but we could be operating on more of the error-report.

Also, I am not too sure riak_err is the right place for this. I did some alterations to log_mf_h and rb which

Enables error reports above 16Kb in size. No limit-function is employed yet, though it would be preferable. I could imagine a report with the state of a large heap being pushed.
Use compression on terms. Disk IO is slow compared to in-memory compression.
Fixes some redundancy in the rb grep code by making the code into a match compiler. This patch can probably flow into OTP after some more testing.
Use binary notation. The rb and log_mf_h code is probably so old Erlang did not have binaries at that time.

Some of the ideas here are inspired by analysis of stack traces in other languages, Java in particular. But perhaps some of these ideas are applicable to log files in general.

Finally, any comments, positive/negative are welcome. Suggestions for improving the ideas here are also much appreciated.

A response to "Erlang - overhyped or underestimated"

2010-12-25T08:31:00.000-08:00

A response to “Erlang - overhyped or underestimated”

There is a blog post about Erlang which recently cropped up. It is well written and puts forth some critique of the Erlang/OTP language. Naturally, I have a bias. I write a lot of Erlang and I like the language - and anything less then a blog post myself would not be fair: There is much to discuss and a fleeting Twitter comment or a comment below the original post can’t convey the information needed.

Erlang is like an exotic beautiful woman with no dressing sense.

I Love this comment from the article. There is truth in it: underneath the clothes of Erlang, beauty is hiding. Yet, I feel that one might have misunderstood the dress code in the exotic world, which is why I sat down, C-x C-f’ed a new buffer and began writing.

1. Today’s mainstream developers who are used to C or Java like syntax wont find its Prolog-like syntax too friendly.

This point, the syntax point, comes up all the time. The claim is that Erlangs syntax is too far away from “mainstream” languages, whatever that means. I don’t think the critique is warranted, but since we have alternative languages like Efene and Reia there are a least some people who think Erlang has a syntax problem, so it warrants discussion.

Perhaps, one should be nuanced and hammer through the difference between syntax and semantics. Syntax is, roughly, the rules for forming valid sentences in the programming languages. Whereas semantics roughly is the meaning of the language, what it denotes. In other words, syntax are rules for transforming a valid input text into an internal parse tree — semantics the rules for executing that parse tree, running the program.

There is a tendency to focus more on Erlangs syntax than its semantics. I think this is partially wrong: the semantics shape the syntax and vice versa. I also have a hunch that people may claim a problem with the syntax of Erlang, where the point is really a misunderstanding of its semantics.

Is Erlangs Prolog-like syntax unfriendly? I don’t think so! Erlang has extremely few syntax rules and they are quite consistent. The grammar is less than 500 lines. Contrast with the Ocaml parser 3 times as large. The Go programming language has a parser which is well above in size as well - I cannot imagine the parser for Java nor C be any smaller.

The main objection is familiarity: “It doesn’t look like Java!” I think the point is somewhat moot. Python doesn’t look like Java. Neither does Ruby or Perl. Still programmers have no trouble picking up those languages. Before the C-style languages became dominant, programmers wrote Pascal, COBOL and Algol whose syntax is far from what we expect.

I expect far more people have trouble with the unfamiliarity of the semantics. If you come from an imperative setting, you need time to wrap your head around functional programming styles and idioms. Yet, unfamiliar semantics should pose no problem either: Python, Javascript, PHP and Java all execute very differently if you look at them modulo imperative execution.

2. While the core language itself is small and easy to learn, the libraries within the language are inconsistent, incomplete and poorly documented.

The Erlang/OTP libraries suffer from inconsistency having been built over time whenever there was a need for a new function. This is indeed unfortunate, but note this: apart from a few libraries which implement their functionality directly in the Erlang VM kernel, most libraries are written in pure Erlang and can be replaced easily. If you hate the list module, you can write your own lst.

Some libraries are de-facto deprecated as it is known they have certain limitations. The way Erlang tend to work however is that older modules known to have trouble are removed fairly slowly from the language - there may be a user out there, however poor that module is.

I cannot agree with the bad documentation. Erlang has excellent documentation. There a man-pages for every module, accessible with erl -man lists for instance (provided your distribution of Erlang is correctly built) and we have several online places where you can look up function definitions. In addition many modules have users guides which you can use to get started quickly. There even is an efficiency guide so you know how to write efficient code and there is a set of programming conventions with good advice on how to structure your programs.

Usually the documentation of functions are rather good I think. If you find something which you think is poorly documented, I’d advice you to make a patch against the documentation and discuss the change with others. Improving documentation is more important than ranting on its inadequacy.

3. Only a few people have written production level codes and you rarely get to hear from them.

I have written production level code in Erlang, namely a BitTorrent client good enough for everyday use. Our performance is currently as good as most other BitTorrent clients, CPU and memory-wise, despite we are writing the client in a “slow” language. I have also written programs professionally in Erlang - for the Web, but I am getting ahead of myself.

I try to write about my experiences - in part to tell stories, in part to educate and encourage others to pick up the language. No programming language is a silver-bullet. But when your task is to write highly concurrent programs Erlang shines. And if you look at the usual protocols for distributed computing on the web, http-servers, xmpp-servers, ad-serving frameworks, payment processing systems, BitTorrent-clients, video-servers, and so on — you find that many of them are highly concurrent.

Successful systems that just work will not catch headlines. A system that is shock-full of errors will. Many Erlang programs are running in companies with no open-source policy as well - don’t expect the programmers of those systems to even be able to talk about what they do. It is a competitive advantage to keep the mouth shut.

4. I can’t imagine how you can organize large code-bases in Erlang or even work as team, and this doesn’t feel right to any OO programmer.

Large Erlang programs are structured around the concepts of applications and releases. You write several isolated functional units, applications. Then you bundle these into a release which you can ship to the production environment. A typical application will provide an abstraction for something, be it running an HTTP server, talking to a database, controlling an external CPU-centered numerical program and so on.

The organization of large programs hinges on API-design. You want to design your program such that each application has a small API used by the other parts of the program. There may thousands of code lines behind the wall of the API, yet the interface to the rest of the world is small.

The trick of OO-languages is “abstraction is had by introducing another object”. If you take a look at the OO-design patterns, you will find that often a new object is introduced to mediate and solve an abstraction problem. This because the only way to abstract in those languages are to construct new objects (or classes, depending on lanuage).

In Erlang, the mantra is “abstraction is had by introducing another process”. In other words, you can usually solve abstraction-problems by introducing a middle-man mediating process, store state in a separate process, split a computation between several processes and so on. The OO-property of isolation, much important to structuring large programs, is present in the isolation of processes: you can’t go rummaging around inside the memory heap space of another process, you must ask it gently and nicely.
Naturally, this model has a design-pattern language as well and I know of several such. Remember this: “In OO-languages state is kept in objects; in Erlang, state is kept in processes”.

5. Most of the performance matrices are one-sided, and are performed by people who have an interest in Erlang. I would love to see some independent analysis.

In general, you should be wary of performance measurements where one does not fully understand the platforms they are working with. It is hard to make a program perform better but it is extremely easy to make a program perform worse. To improve a program you must understand the rules of the game you are playing. The rules used to speed up, e.g. node.js are much different from the rules used in Erlang. And that is different again from Ocaml, Scala, Java, Python, …

Also, workarounds for problems tend to be vastly different. A recent blog post of mine lays bare a curious property of node.js but the seasoned Node programmer understands how to work around it. He or she may deploy the multi-node for instance and it fixes a lot of the problems by using a single accept() queue for several workers. This is a nice way to break the rules of the game to avoid a problem.

Rather than thinking in terms of performance, I would argue you should think in terms of what your problem is. Erlang shines when a fully-preemptive, heavily concurrent process model is a good solution to your problem. It is powerful in that respect and it has the advantage it is a very mature system.

6. Its support for web-development is very primitive. With web frameworks like rails and grails, there is a lot of serious work for Erlang if it ever intends to go to that market.

I don’t think this is true. Web frameworks like Rails or Grails only talk about half of the web world. Clients in modern systems tend to be Javascript-heavy and only go to the server for their RPC Ajax-like requests. In this world, you need a lot less tooling at the side of the server. There are many web framworks popping up for Erlang currently, but let me plug the nitrogen project.

Yet, I think we will see much less need for web-frameworks as they were. We will need a new kind of framework which is much easier to work with server-side. And I think node.js shows the server doesn’t need a lot of stuff to be effective.

You should also think about the emerging alternatives to RDBMs data storage. There are systems such as couchdb and riak, which can cleverly bypass some of the usual Model-View-Controller pattern. I think we are in for a change in the way we do web development for the better and that Grails and Rails are a thing of the past if they don’t adapt to the new world (I am sure Rails will - but have to little experience with Grails to know if they stagnate or not).

7. Did I talk about Strings in Erlang? IO speed?

This single item is a blog post worthy in itself. First the strings.

A string in most languages is a sequence of bytes, pointed to by reference. In some languages the string is the central data you pass around and in some, it is the only kind of data you could pass around. Haskell and Erlang most notably defines a string to be a list of characters and integers respectively. There is much good and bad to be said about this choice - but it hurts people who don’t understand the difference.

Most web systems manipulate strings. The string is the ubiquitous data format: it stores integers, it stores floats, it stores XML documents, JSON, and such. The string is easy to transfer over a TCP/IP stream. It is no surprise that many languages center around string manipulation and are very effective at it. Perl is perhaps the ultimate string processor (apart from crm114, naturally).

The ubiquity of strings are also their Achilles-heel. The type information they carry is weak — nonexistent to be precise. To manipulate a string in any statically typed language, Java, Ocaml, Haskell, etc., you need to transform it into an internal format. You process the string to an Object-hierarchy or an algebraic data type — and then you throw the string away! The new representation has all the advantages: it is typed, it can carry additional information in object state, and it can make illegal states unrepresentable.

You should never ever work directly with strings if performance matter. Even simple things like string comparisons may be fairly expensive (if the pointer comparison says different), whereas an atom comparison is not. The world of programming is more complex than just shoving every piece of data into a string.

Another weakness of the string is that the representation only answers to query by regular expression, recursive descent or LALR(1)-parsing. Some languages are very good at the former, regex query, but Erlang is not one of them since regular expressions are not built into the syntax and semantics.

So the first virtue of the Erlang programmer: Convert a string as fast as possible into an erlang-term() and then manipulate the term. Only work with crappy weakly-typed strings at the border of your application. An Erlang application should not constrain itself to work with only a single data type, namely strings!

The second virtue follow fast: If your string is large, use a binary() for effective storage and sharing. The binary representation, like the ByteString in Haskell, is as space efficient as C and it can be pattern matched if needed.

The third virtue is: Know thine iolists. When you construct strings in Erlang, you are not to build a sequence of characters! You should be building a tree of small string-like fragments, binaries, other trees, lists and so on. The output functions know how to effectively walk the tree and stream it to the output device.

The IO performance of Erlang is pretty good. I easily had some early tests in Etorrent moving 700 megabit on a single 1.2Ghz Pentium M CPU. Without any optimization at all.

Yet, it is important to notice that IO in Erlang is abstracted by default and this makes it a tad slower than what it can to be. The abstraction is rather nice and has to do with distribution. You can access a socket or file on another machine as if it is locally accessed. But this neat abstraction naturally has an overhead. Of course it is easy to build a primitive which throws away that abstraction if needed. And that will definitely run as fast as any other language.

Differences between Node.js and Erlang

2010-12-14T08:45:00.001-08:00

Differences between Node.js and Erlang

Suppose we have a canonical ping/pong server written in Node,

var sys = require("sys");
var http = require("http");
http.createServer(function (req, res) {
  res.writeHead(200, {"Content-Type": "text/plain"});
  res.end("Hello, World\n");
}).listen(8124, "127.0.0.1");
sys.puts("Server running at http://localhost:8124");

We can run this server easily and test it from the command line:

jlouis@illithid:~$ curl http://localhost:8124
Hello, World

And it does what we expect. Now suppose we do something silly. We make a tiny change to the Javascript code:

var sys = require("sys");
var http = require("http");
http.createServer(function (req, res) {
  res.writeHead(200, {"Content-Type": "text/plain"});
  res.end("Hello, World\n");
  while(true) { // Do nothing
  }
}).listen(8124, "127.0.0.1");
sys.puts("Server running at http://localhost:8124");

Now, the first invocation of our test works, but the second hangs:

jlouis@illithid:~$ curl -m 10 http://localhost:8124
Hello, World
jlouis@illithid:~$ curl -m 10 http://localhost:8124
curl: (28) Operation timed out after 10001 milliseconds with 0 bytes received

This should not surprise anybody. What we have here illustrated should be a common knowledge. Namely that Node is not preemptively multitasking but is asking each event to cooperate by yielding to the next one in turn.
The example was silly. Now, suppose we have a more realistic example where we do work, but it completes:

var sys = require("sys");
var http = require("http");
http.createServer(function (req, res) {
res.writeHead(200, {"Content-Type": "text/plain"});
  x = 0;
  while(x < 100000000) { // Do nothing
    x++;
  }
res.end("Hello, World " + x + "\n");
}).listen(8124, "127.0.0.1");
sys.puts("Server running at http://localhost:8124");

We introduce a loop which does some real work. And then we arrange for it to be non-dead by requiring it in the output. Our server will now still return, but it will take some time before it does so.
Let us siege the server:

jlouis@illithid:~$ siege -l -t3M http://localhost:8124 
** SIEGE 2.69
** Preparing 15 concurrent users for battle.
The server is now under siege...
[..]

For three minutes, we hammer the server and get a CSV file, which we can then load into R and process.

Erlang enters…

For comparison, we take Mochiweb, an Erlang webserver. We do not choose it specifically for its speed or its behaviour. We choose it simply because it is written in Erlang and it will context switch preemptively.
The relevant part of the Mochiweb internals are this:

count(X, 0) -> X;
count(X, N) -> count(X+1, N-1).

loop(Req, _DocRoot) ->
  "/" ++ Path = Req:get(path),
  try
    case Req:get(method) of
      Method when Method =:= 'GET' ->
    X = count(0, 100000000),
    Req:respond({200, [], ["Hello, World ", integer_to_list(X), "\n"]});
      [..]

It should be pretty straightforward. We implement the counter as a tail-recursive loop and we force its calculation by requesting it to be part of the output.

erl -pa deps/mochiweb/ebin -pa ebin
Erlang R14B02 (erts-5.8.3) [source] [64-bit] [smp:2:2]
[rq:2] [async-threads:0] [hipe] [kernel-poll:false]
1> application:start(erlang_test).
{error,{not_started,crypto}}
2> application:start(crypto).     
ok
3> application:start(erlang_test).
** Found 0 name clashes in code paths 
ok
4>

Notice that we get both my CPUs to work here automatically. But performance is not the point I want to make.
Again, we lay siege to this system:

jlouis@illithid:~$ siege -l -t3M http://localhost:8080 | tee erlang.log

Enter R

We can take these data and load them into R for visualization:

> a <- read.csv("erlang.log", header=FALSE);
> b <- read.csv("node.js.log", header=FALSE);
> png(file="density.png")
> plot(density(b$V3), col="blue", xlim=c(0,40), ylim=c(0, 0.35));
lines(density(a$V3), col="green")
> dev.off()
> png("boxplot.png")
> boxplot(cbind(a$V3, b$V3))
> dev.off()

Discussion

What have we seen here? We have a situation where Node.js has a much more erratic response time than Erlang. We see that while some Node.js responses complete very fast (a little more than one second) there are also responses which take 29.5 seconds to complete. The summary of the data is here for Node.js:

> summary(b$V3)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
  1.040   6.328  13.580  13.940  20.940  29.590

And for Erlang:

> summary(a$V3)
   Min. 1st Qu.  Median    Mean 3rd Qu.    Max. 
   9.87   11.21   12.24   12.21   13.16   15.32

The densities are (green is Erlang, blue is Node.js)

And for completion, a boxplot:

This is a result of Erlang preemptively multitasking the different processes so its responses all come around the same time. You can’t really use the mean for anything: Erlang ran 2 CPUs whereas Node.js only ran one. But the kernel density plot clearly shows how Erlang stably responds while the response times of Node.js is erratic.
Does this mean Node.js is bad? No! Most node.js programs will not blindly loop like this. They will call into a database, make another web request or the like. When they do this, they will allow other requests to be processed in the event loop and the thing we have seen here is nonexistent. It does however show that if a Node.js request is expensive in the processing, it will block other requests from getting served. Contrast this with Erlang, where cheap requests will get through instantly as soon we switch context preemptively.
It also hints you need to carry out histogram plots for your services (kernel density plots are especially nice for showing how the observations spread out). You may be serving all requests, but how long time does it take to serve the slowest one? A user might not want to wait 30 seconds on a result, but he may accept 10 seconds.

Conclusion

My main goal was to set out and exemplify a major difference in how a system like Node.js handles requests compared to Erlang. I think I have succeeded. It underpins the idea that you need to solve problems depending on platform. In Node.js, you will need to break up long-running jobs manually to give others a chance at the CPU (this is essentially cooperative multitasking). In Erlang, this is not a problem — and a single bad process can’t hose the system as a whole. On the other hand, I am sure there are problems for which Node.js shines and it will have to be worked around in Erlang.

EDIT: Minor spelling correction.

2010-11-20T14:33:00.000-08:00

Tracing Erlang programs for fun and profit

One of the neat things about Erlang is its instrumentation capability. You can instrument programs to tell you interesting things about what is happening in the program. This blog post is about a tool by Mats Cronqvist, redbug.

Redbug can be downloaded from github and is part of Mats’ eper suite of tools. Installing the tool is easy. I recommend to set the $ERL_LIBS environment to something. Mine is set at:

   jlouis@illithid:~$ env | grep ERL_LIBS
  ERL_LIBS=:/home/jlouis/lib/erlang/lib

so I can just drop Erlang libraries I use on-and-off into that directory and they will be picked up by any Erlang I run. It is not a good solution when you are building software with dependencies, but for smaller tools used by you, like eper or Erlang QuickCheck, this mechanism is really good.

Installing eper should be fairly simple.

Redbug invocation

Redbug can either be called from the command line. There is a redbug shell script you can call or you can call it from the Erlang shell. The main invocation is like this,

   redbug:start(TimeOut, MessageCount, MS)

where TimeOut is a timeout in milliseconds at which redbug ceases to operate, MessageCount sets a limit to how many reports redbug is going to make, and MS is a match-spec matching trace points in the program. There are several possible ways to write MS and I am only going to give some simple examples to get you started. The tool is self-documenting and you can call

   redbug:help().

from a shell and get the whole story.

The timeout and messagecount limitation is very useful. Erlang has a built-in tracer on which redbug is built. But contrary to the built-in tracer, redbug protects the running system by the limitations. You can’t hose the system by accidentally set a specification which hoards all of the resources on the Erlang node.

A typical MS is written like {erlang,now,[return,stack]}. This states we are tracing for the erlang:now call of any arity. When we match, we want the current stack printed and we want the return value of the call:

  22> redbug:start(100000, 2, {erlang,now,[return,stack]}).
 ok
 23> erlang:now().

 22:40:12 <{erlang,apply,2}> {erlang,now,[]}
 {1290,289212,474520}
  shell:eval_loop/3
  shell:eval_exprs/7
  shell:exprs/7

 22:40:12 <{erlang,apply,2}> {erlang,now,0} -> {1290,289212,474520}
 quitting: msg_count
 24> erlang:now().
 {1290,289219,57040}

Notice the quitting: msg_count which states after two messages from redbug, it will cease to do any further tracing. In general, the MS can also be written like, e.g., {module,function,[return,{'_', 42}]} stating that we accept any call matching module:function(_, 42) and gets its return stack.

A real-world bug hunt

Redbug means you don’t in general have to add a lot of debug-printing to your Erlang code. Rather, it is easier to probe systematically with redbug on a running system. I was wondering why a recent patch in etorrent seemed to work incorrectly, so we go hunting:

(etorrent@127.0.0.1)26> redbug:start(10000, 2, {etorrent_choker, split_preferred, [return]}).
ok
22:47:32  {etorrent_choker,split_preferred,[[]]}
22:47:32  {etorrent_choker,split_preferred,1} -> {[],[]}
quitting: msg_count

This choker call should not be passed the empty list, so we look into the code and find that the rechoke_info builder right before it is odd:

(etorrent@127.0.0.1)29> redbug:start(10000, 30, {etorrent_choker, build_rechoke_info, [return]}).
[..]
22:49:22  {etorrent_choker,build_rechoke_info,2} -> []
22:49:22  {etorrent_choker,build_rechoke_info,1} -> []

So - both build_rechoke_info/1 and build_rechoke_info/2 return the empty list. Something is wrong inside that function. Since the function is looking up data in other modules, we trace each of the module lookups:

(etorrent@127.0.0.1)29> redbug:start(10000, 10, {etorrent_table, get_peer_info, [return]}).
[..]
22:51:42  {etorrent_table,get_peer_info,[<0.5759.0>]}
22:51:42  {etorrent_table,get_peer_info,1} -> {peer_info,
                                                              leeching,17}

Nope, that looks right, on to the next:

(etorrent@127.0.0.1)30> redbug:start(10000, 15, {etorrent_rate_mgr, fetch_send_rate, [return]}).
ok
22:53:12  {etorrent_rate_mgr,fetch_send_rate,[4,<0.3919.0>]}
22:53:12  {etorrent_rate_mgr,fetch_send_rate,2} -> none

Oh, a return of none is wrong here! Why does it return none? The call looks fine, but we are looking up data in an ETS table…

At this point, we can use another nice little Erlang tool, tv or the Table Viewer. We run:

tv:start().

find the problematic table and inspect an element, which turned out to contain the wrong information. Thus, the hunt is all about figuring out why the wrong information is entered into the table in the first place.

(etorrent@127.0.0.1)35> redbug:start(10000, 5, {ets,insert,[stack,{etorrent_send_state, {rate_mgr, {'_', undefined}, '_', '_'}}]}).

Basically, we have now constricted the output to exactly the wrong types of calls. And the culprit function is easily found in the callers stack.

Further digging shows the problem to be a race at the gproc process table which can be fixed by asking gproc to await the appearance of a given key.

On Erlang, State and Crashes

2010-11-13T13:49:00.000-08:00

On Erlang, State and Crashes

There are two things which are ubiquitous in Erlang:

A Process has an internal state.
When the process crashes, that internal state is gone.

These two facts pose some problems for new Erlang programmers. If my state is gone, then what should I then do? The short answer to the question is that some other process must have the state and provide the backup, but this is hardly a fulfilling answer: It is turtles all the way down. Now, that other process might die, and then another beast of a process must have the state. And this observation continues ad infinitum. So what is the Erlang programmer to do? This is my attempt at answering the question.

State Classification

The internal state of an Erlang process can naturally be classified. First, state has different value. State related to the current computation residing on the stack may not be important at all after a process crash. It crashed for a reason and chance are that the exact same state will bring down the process again with the same error. The same observation might apply to some internal state: It is like a scratchpad or a blackboard: when the next lecture starts, it can be erased because it has served its purpose.

Next is static state. If a process is governing a TCP/IP connection that process should probably connect to the same TCP/IP Address/Port pair if it crashes and is restarted. We call that kind of data configuration or static data. It is there, but it is not meant to change over the course of the application, or only change rarely.

Finally our crude classification of state has dynamic data. This class is the data we generate over the course of the running program, get from user input, create because other programs communicate with us and so on. The class can be split into two major components: State we can compute from other data and state we cannot compute. The computable state is somewhat less of a problem. We can basically just recompute it after a crash, so the real problem is the other kind of user/program-supplied information.

In other words, we have three major kinds of state: scratchpad, static and dynamic.

The Error Kernel

Erlang programs have a concept called the error kernel. The kernel is the part of the program which must be correct for its correct operation. Good Erlang design begins with identifying the error kernel of the system: What part must not fail or it will bring down the whole system? Once you have the kernel identified, you seek to make it minimal. Whenever the kernel is about to do an operation which is dangerous and might crash, you "outsource" that computation to another process, a dumb slave worker. If he crashes and is killed, nothing really bad has happened - since the kernel keeps going.

Identifying the kernel plugs the "turtles all the way down" hole. As soon as the kernel is hit, we assume correctness. But since the kernel is small, the trusted computing base of our program is likewise. We only need to trust a small part of the program, and that part is also fairly simple.

A visualization is this: A program is a patchwork of small squares. Some of the squares are red, and these are the "error kernel". Most (naively implemented) imperative programs are mostly red, save for a few squares. These are the squares where exceptions are handled explicitly and the error is correctly mitigated. The kernel is thus fairly large. In contrast, robustness-aware Erlang programs have few red squares - most of the patchwork is white. It is a design-goal to get as few red squares as possible. It is achieved by delegating dangerous work to the white areas so a crash does not affect the kernel.

Handling the state classes

Each class must be handled differently. First there is the scratchpad/blackboard class. If a process crashes, the class is interesting because it contains the stack trace and usually the data which tells a story - namely how and why the process crashed. We usually export this data via SASLs error logger, so we can look at a crash report and understand what went wrong. After all, the internal state is gone after the crash report is done and logged.

Next, there is the static class. The simplest thing is to have another process feed in the static data. This can be done by, among others, the supervisor, by asking an ETS table, by asking GProc (if you use gproc in your system), by asking another process or by discovery through the call application:get_env/2. It is important to note just how static the data is - you have few options with differing advantages and disadvantages. Which one to choose depends on how much the data is going to change.

Finally, the fully dynamic data is the nasty culprit. If you can recompute the data, you are lucky. As an example from my etorrent application, each peer has a dynamic table of what parts of a torrent file the given peer has. So the controlling process has an internal table of this information. But if we crash and reconnect to the peer, the virtue of the bittorrent protocol will send us this information again. So that information is hardly worth keeping around. Other times, you can simply recalculate the information when your process restarts, and that is almost never a problem either.

So what about the user supplied data? This is where the error kernel comes in. You need to protect data which you can not reconstruct. You protect it by shoving it into the error kernel and keep some simple state maintenance processes there to handle the state. A word of warning though: If your state is corrupted, it means that processes basing their work on the state will do something wrong. To mitigate this, it is important to make some general sanity checking of your data. Make it a priority to check your data for invariants if you find them. And don't blindly trust non-error-kernel parts of the system.

If a process crashes, you should definitely think how much of its internal state you want to recycle. If you recycle everything you risk hitting the exact same bug again and crash. Rather, there may be a benefit to only recycling parts of the internal state.

The next step: Onion-layered Error kernels

The next logical step up, is to recognize that the error kernel is not discrete. You want to regard the error kernel as an onion. Whenever you peel off a layer, you get a step closer to the trusted computing base of the application. Then your system design is to push down state maintenance to the outermost layer in the onion where it still makes sense. This in effect protects one part of the application from others. In Etorrent, we can download multiple torrent files at the same time. If one such torrent download fails, there is no reason it should affect the other torrent downloads. We can add a layer to the onion: Some state which is local to the torrent is kept in a separate supervisor tree - to mitigate the error if that part fails.

The net effect is program robustness: A bug in the program will suddenly need perseverance. It has to penetrate several layers in the onion before it can take the full program down. And if the Erlang system is well designed, even the most grave bugs can only penetrate so far before the stopping power of the onion layers brings it to a halt.

Furthermore, it underpins a mantra of Erlang programs: Small bugs have small impact. They won't even penetrate the first layer. And they will hardly be a scratch in the fabric of computing.

(Aside: Good computer security engineering use the same onion-layered model. There are strong similarities between protecting a computer system against a well-armed intruder and protecting a program against an aggressive, persistent, dangerous and maiming bug. End of Aside)

EDIT: smaller language changes where my first post was a bit drafty.

On being obsessed with concurrency

2010-10-10T12:08:00.000-07:00

Grace Hopper on multiple occasions explained the length of a nanosecond with a piece of wire. The length of the wire was exactly the distance light would travel in a nanosecond. See [1] for one such occasion.

While Grace was using the method to describe the delay in satellite communication and why computers need to get smaller, it turns out it is more relevant than ever today. We are officially over the era of computing where people glued together libraries to form programs. Today, virtually every new application built is distributed.

The problem is that if you think latency due to disk seeks are slow, then imagine reaching a machine at the other end of the world - the delay is high. From here, my delay to yahoo.com is around 200ms, much more than the average seek time on an old harddisk. There is a common trick in the high-performance computing world to battle latency: latency hiding. While waiting for a message to pass through the slow network, you do something else. And then when data from the message is in grave need to continue the program, you gamble that it already arrived. The same trick has been used in operating systems for years while waiting on the disk to return data: run another program in the meantime.

And this is why any modern programming language must tackle concurrent operations. From now on, most programs will be distributed. The client program will be because they live on mobile phone-sized systems and they have to pull in data from multiple sources. The server program will be because distribution is key to scaling and redundancy. In short, any program will have a situation where getting data amounts to asking another system for them -- and then handling the inherent latency present in the communication. The limit of a computer from here on out will not be in the amount of instructions it can retire successfully on its cores. Rather, it will be the amount of communication it can perform and how well it deals with it. On the memory bus. On the network. To the satellite.

I am making a bet: Distribution will be huge and will be solved by message passing concurrency. That is, I claim we already have the necessary tools in the toolbox to tackle the problem. There is not going to be the concurrent doomsday where the world curls up in a corner and deadlocks. There is not going to be a parallel doomsday revolution either. If the internet has told us anything it should be that we can handle the problems which will come forth to rear their ugly heads (and breath fire). The reason I am betting on message passing concurrency is that it is easy to program and fast enough for a 200ms round trip in most cases. The amount of nanosecond wires utterly dwarfs the price we pay to pass a message.

I am making another bet as well: parallellism is not going to be as huge as we think it is. We have relied for years on our computing technology to be faster every other year -- and this low hanging fruit is not there anymore. But it disguised another trend with even greater consequences: computers keep getting smaller and smaller. My mobile phone has the computing power of a State-of-the-art computer in 2001-2002. Imagine that in 8 years! It is not about splitting the computation up so it can run on a single machine with many cores anymore. It is about splitting the computation so it can run on many machines with many cores.

Today is the 10/10/10 but the day is only special in the calendar. The change did not happen overnight. There has been a slow crawl towards a more distributed world for some years. But undoubtedly, the mobile devices will propel us with full force into the new world order.

-- All Hail! Think concurrently!

[1] http://www.youtube.com/watch?v=57bfxsiVTd4

Adding support for more than 1024 files to etorrent.

2010-05-23T05:55:00.000-07:00

Some torrent files contain a humongous amount of files. Thousands. This is one of the problems you have to cope with as a client-writer and I plan to take care of both etorrent and combinatorrent. However, the solution I've adopted for etorrent is sinisterly beautiful, so I decided to write it down.

The Problem

Open files are limited on UNIX systems. This is to protect different applications against each other and to circumvent an eventual resource exhaustion on the system. A typical limit is 1024 files, or fewer in some cases. In etorrent, a file is governed by a process which plays the role of that file. Whenever you want to do a file operation on that file, you get hold of the process Pid and send it a message. Simple.

Resources are limited by a timeout in these file processes. When a file has not been in use in 60 seconds, the process governing it terminates and frees up the resources on that file. It works reasonably well. The problem, however, is that some torrents have more files than the file descriptor limit. When we check the file upon starting up, we unfortunately open more than 1024 and then hit the limit.

The Solution

The solution is deceptively simple. We add a janitor process to the game. Whenever a new file is opened the janitor gets informed and the file process enters itself into an ETS table. Whenever we do an operation on the file a timestamp is bumped in the ETS table. This goes on and on; if a process dies, a monitor in the janitor cleans out the entry from the ETS table.

Now, whenever a new file is opened we check the size of the table against a high watermark, 128 by default. If more processes are opened, we extract the full table and order it by last bump. Thus, the first elements in the resulting list are the processes which have been used the farthest back in time. We then ask enough of these to terminate to bring ourselves back under a low watermark - ensuring we won't be hitting the resource collection all the time we add a new file system process to the game.

Updating the ETS table is expected to be rather cheap. The table is public, so each file governing process maintains its own entry. I don't think they will spend much time waiting for each other on the table. And if they do, there is always {write_concurrency, true} we can set on the table.

Haskell vs. Erlang for bittorent clients

2010-04-26T15:01:00.000-07:00

Haskell vs. Erlang

Since I wrote a bittorrent client in both Erlang and Haskell, etorrent and combinatorrent respectively, I decided to put up some bait. This might erupt in a language war and “My language is better than yours”, but I feel I am obligated to write something subjective. Here is to woes of programming in Haskell and Erlang.

Neither Haskell, nor Erlang was a first language for me. I have programmed serious programs in C, Standard ML, Ocaml, Python, Java and Perl; tasted the cake of Go, Javascript, Scheme and Ruby; and has written substantial stuff in Coq and Twelf. I love static type systems, a bias that will rear its ugly head and breathe fire.

I have written Haskell code seriously since 2005 and Erlang code seriously since 2007. I have programmed functionally since 1997 or so. My toilet reading currently is “Categories for the working mathematician” by Mac Lane. Ten years ago it was “ML for the working programmer” by Paulson.

Enough about me.

Caveats:

With any language war material follows a disclaimer and a healthy dose of caveats. This is subjective. You have to live with it being subjective. My writing can’t be objective and colorful at the same time. And I like colors in my life. Also, it is no fun reading a table listing the comparison. Rather, I will try to make it into a good foil duel with attacks, parries, guards, pierces, bananas, and barbed wire.

I built etorrent in Erlang first and combinatorrent in Haskell second. Hence, the 2nd time around, with the sole goal of redoing the functionality of etorrent was much easier and could proceed much faster. The Erlang code is slightly fattier at 4.2K lines versus 3.6K lines of Haskell (SLOCs). The performance of the two clients is roughly equal, but more time was spent at optimizing the Haskell code.

My hypothesis is this: The Erlang VM is much more optimized at the IO layer than the current IO layer I use in GHC (specifically, the way incoming data is handled allocates more memory. This might change in the future do to a new IO layer). GHC kills the Erlang VM for everything else though, perhaps including message passing.

Also, the quality of the Erlang code could be better, relatively compared to the Haskell code.

Enough!

Enough with the caveats!

Haskell cons:

What weighs against using Haskell for the project? First is laziness. Sometimes you want your code to be strict and sometimes lazy. In combinatorrent, we do some statistics which we don’t really need to calculate unless we want to present them. Stuff like bytes uploaded and downloaded for instance. Since you do not necessarily ask for these statistics, the compiler is free to build up thunks of the calculation and you have a neat little space leak. This is a recurring problem until you learn how to harness the strictness annotations of Haskell. Then the problem disappears.

IO in Haskell is somewhat weak if you naively assume a String is fast. But there is help from Bytestrings, attoparsec and low-level Socket networking. Combinatorrent could use more help with getting the speed up here. I have substituted the IO layers lowest level some 2–3 times in combinatorrent. Contrast this with Erlang, where the original protocol parser and IO is the one still standing. If you want fast network IO in Haskell, you should be using bytestrings and network-bytestring. It is not worth the simplicity going over String in my experience.

The GHC compiler has, comparatively, more performance regressions compared to the Erlang VM. It should come as no surprise: GHC is acting as both a research vehicle and a compiler implementation. I want to stress however, that this has not worried me a lot. When asking the GHC developers for help, the response has been fast and helpful, and in every case it was easy to fix or work around. Also, change is a necessary thing if you want to improve.

Haskell pros:

Haskell has one very cool thing: Static typing (remember the bias!). The type system of Haskell is the most advanced type system for a general purpose language in existence. The only systems which can beat it are theorem provers like Coq, and they are not general purpose programming languages (Morriset and the YNot team might disagree though!). Static typing has some really cool merits. Bugs are caught fast and early; types ensure few corner cases in the programs (why check for null when it can’t be represented). The types is my program skeleton and the program inhabiting the type is the flesh. Getting the skeleton right yields small and succinct programs. The abstraction possibilities from this is unparalleled in any language I have seen (and I’ve seen a few).

The GHC compiler provides programs which have excellent execution speed. You don’t need to worry a lot about speed when the compiler simply fixes most of the problems for you. This in turn means that you can write abstract code without worrying too much about the result. This yields vastly more general and simpler programs.

One very big difference in the implementations is that of STM channels versus Erlangs message passing. In Erlang, each process has a mailbox of unbounded size. You send messages to the mailbox, identified by the process ID of the mailbox owner. In Haskell, we use STM Channels for most communication. Thus, you send messages not to the PID of a process, but to a specific channel. This effectively changes some rules in channel network configuration. In Erlang you must either globally register a process or propagate PIDs. In Haskell, channels are created and then propagated to communicating parties. I find the Haskell approach considerably easier - but also note that in a statically typed language, channels is the way to go. The sum type for a PID mailbox would be cumbersome in comparison.

Haskell has excellent library and data structure support. For instance you have access to priority search queues via Hackage. PSQueues are useful for implementing the piece histogram in a bittorrent client: knowing how rare a given piece is so you can seek to fetch the rarest first.

Haskell can create (im-)mutable (un-)boxed arrays. These are useful in a bittorrent client in several places. Immutable arrays for storing knowledge about pieces is an example. Or bit-arrays for storing knowledge about the pieces a given peer has. Erlang has no easy access to these and no guarantee of the data representation.

Bryan O’Sullivans attoparsec library allows for incremental parsing. When you get a new chunk of data from the network, you feed it to attoparsec. It will either give you a parsed message and the remaining bytes, or it will hand you back a continuation. This continuation, if invoked with more food, will continue the parsing. For network sockets the incrementality is pure win.

The GHC compiler has some awesome profiling tools, including a powerful heap profiler. Using this, the run-time and memory usage of combinatorrent was brought down.

Finally, testing in Haskell is easy. QuickCheck and Test.Framework provides a —tests target built into the combinatorrent binary itself. Self tests are easy.

Haskell mistakes:

I made some mistakes when writing the Haskell client. For one I relied on the CML library until I realized STM would do an equal or better job. The amount of Haskell developers with STM experience compared to the CML head-count made the decision to change easy.

Furthermore, I should have focused on laziness earlier in the process. The first combinatorrent releases leak memory because of lazy thunk buildup. The latter versions, after I understood it intuitively, does not leak.

Erlang cons:

In Erlang, dynamic typing is the norm. Rather than enforce typing, you can get warnings by a type analyzer tool, the dialyzer, if need be. Running this on the code is a good idea to weed out some problems quickly. When building etorrent I had much use of the dialyzer and used a at that time experimental extension: spec() specifications. Yet, I think that 19/20 errors in my erlang programs were errors which a type system would have caught easily. This means you spend more time actually running the program and observing its behavior. Also note that dynamic typing hurts less in Erlang compared to other languages. A process is comprehensible in its own right and that reduces the interface to the process communication - a much simpler task.

Etorrent has less stability than combinatorrent and has erred more. Yet, this is no problem for a bittorrent client since the supervisor-tree in Erlang/OTP will automatically restart broken parts of the system. For a bittorrent client we can live with a death once a week or once a day without any troubles.

You have no mutability in Erlang and you have far less options for data representation. This in turn make certain algorithms rather hard to express or you have to opt for variant with a larger space usage. There were no Cabal-equivalent at the time I wrote the code and thus fewer libraries to choose from.

For the built-in libraries, the HTTP library was more strict with respect to correctness. In turn, many trackers would not communicate with it and I had to provide a wrapper around the library. Today, this might have changed though. Haskells HTTP library worked out of the box with no changes.

Erlangs syntax, compared to Haskell, is ugly, clunky and cumbersome. Make no mistake though: Tanks are ugly, clunky and cumbersome. It does not make tanks less menacing.

Erlang pros:

One application SASL. SASL is a system logger which will record in a ring-buffer any kind of process death and process restart. I used this a lot when developing. I would load a couple of torrents in the client and go to bed. Next morning I would check the SASL log for any error that might have occurred and fix those bugs. This way of developing is good for a bittorrent client: utmost stability is not needed. We just to get the number of errors below a certain threshold. Rather than waste time fixing a bug which only occurs once every year, we can concentrate on the things that matter.

The IO layer in Erlangs VM is FAST! It is written in C, and it is optimized heavily because this is what Erlang does best. For file IO it uses asynchronous threads to circumvent having to wait on the kernel. For the network, it plugs into epoll() getting good performance in turn.

The Beam VM of Erlang is a beast of stability. Basically, it doesn’t quit unless you nuke it from orbit. One of the smaller things I learned some weeks ago was the rudimentary flow control trick. Erlang schedules by counting reductions in an Erlang process and then switching process context when it has no more reductions in its time share. Sending a message never fails but it costs reductions proportional to the queue size of the receiving process. Hence, many senders have a harder time overloading a single receiver. The trick is simple, easily implementable and provides some simple flow control. While not fail-safe, it ups the ante for when communication overload happens.

Erlang has OTP, the Open Telecom Platform, which is a callback-framework for processes. You implement a set of callbacks and hand over control to the OTP-portion of your process. OTP then handles a lot of the ugly, gritty details leaving your part simple. OTP also provides the supervision of processes, restarting them if they err. Supervisor-processes form trees so they are in turn supervised. It isn’t turtles all the way down in an Erlang VM…

Erlang executes fast enough for most things. Haskell gives you faster execution, but Erlang was more than adequate for a bittorrent client in the speed department. As an example of how this plays together with the IO layer, an early version of etorrent could sustain 700 megabit network load on a local network of 1 gigabit when seeding. The current version of etorrent can do the same as a seeder I suspect. Also, message passing in Erlang is blazing fast. It feels like a function call - a key to good Erlang I think.

The Erlang shell can easily be used as a poor mans user interface. Etorrent simply responds to some functions in the shell, showing status of the running system. I suspect GHCi can do the same, but I never got around to doing it and it doesn’t seem as easy to pull off.

I love the Erlang way of programming. You assume your code does the right thing and let it crash otherwise. If it crashes too often you handle that case. Code is not lingered with error handling for things that never happen and should it happen occasionally, the supervisor tree saves the day.

Erlang mistakes:

Unfortunately, I made a number of mistakes in Etorrent. Most of these has to do with being the first version. Fred P. Brooks hinted that you want to throw away things when building the first version. And I did. I used ETS tables in places where they are not good. ETS is a table in which you can store any erlang term and later retrieve it. They give you a way to circumvent the representation limitation in Erlang. But they are no silver bullet: When you pull out a term, you copy it to the process pulling it. When your terms are 4–8 megabyte in size, that hurts a lot.

I relied far too much on mnesia, the database in Erlang. Mnesia is basically using software-transactional-memory so locking is optimistic. When you have something like 80 writers wanting access to the same row in a table, then the system starves. Also, there is no need for a bittorrent application to require a mnesia store. A simple serialization of key data to a file based on a timer is more than adequate.

I made several mistakes in the process model. I thought that choking was local to a torrent while in reality it is a global thing for all torrents currently being downloaded. These reorganizations require quite some refactoring - and missing in the static typing department these are somewhat more expensive compared to Haskell refactorings.

I thought autotools were a good idea. It is not. Autotools is the Maven of C programming.

Finally, I shedded unit-tests. In a dynamically typed environment you need lots and lots of these. But I decided against them early on. In hindsight this was probably a mistake. While unit-testing Erlang code is hard, it is by no means impossible.

Future:

The future brings exciting things with it. I will continue Combinatorrent development. I am almost finished with the Fast-extension (BEP 0006) for combinatorrent and have some more optimization branches ready as well. I still follow Erlang in general because it is an interesting language with a lot of cool uses. I do check that etorrent compiles on new releases of Erlang. If anyone shows interest in any of the client implementations, feel free to contact me. I will happily answer questions.

There is no clear winner in the duel. I prefer Haskell, but I am biased and believe in static typing. Yet I like programming in Erlang - both languages are good from different perspectives.

Want to hack Haskell? Bittorrent?

2010-03-15T08:03:00.000-07:00

Helping with HaskellTorrent

I have a ideology in which an Open Source project must be easy to hack for other people than the original author. Thus, I am trying to make this possible with HaskellTorrent. In particular, I keep several things in unsolved so others might join the fray, should they want to. This is a list, in no particular order, in which I put forth some things there are left to be done.

Do note that I tend to keep bugs off this list. Many projects use the bug tracker as a way to track what needs doing. I have a TODO.md file in the top-level dir which contains things. Some of these things are taken from this list.

HAVE message pruning

Torrent files work by splitting a file into pieces and then breaking pieces into blocks. The blocks are then exchanged between peers until every block in a piece is downloaded. At that point, the SHA1 checksum of the piece can be used to verify the piece got downloaded correctly. If this is the case, a HAVE message is broadcasted to all peers we are connected to. This notifies other peers of the newly available piece so they can begin requesting it.

However, there is an optimization oppurtunity. If the peer already has told us (usually by a HAVE message) that it got the piece already, there is no reason to tell it about the availability. Thus, we can prune the sending of the HAVE for those clients. There is already an IntSet with the necessary information inside the PeerP process with the information, so the change is fairly simple.

Optimize Peer/PieceMgr communication

Profiling shows we spend a considerable amount of time in the communication between the Peer and the Piece Manager. The Peer will, when downloading, try to keep a pipeline of block REQUEST messages going towards the other end. It mitigates the delay on the internet doing so. Hence, it periodically asks the PieceManager for new blocks to request. It does so by sending a number of blocks it wants together with an IntSet of what pieces the peer at the other end has.

The Piece Manager is responsible for giving exclusive access to blocks to peers. There is no reason to download the same blocks at multiple peers, so it keeps track of what blocks where requested. Also, it must only serve blocks that the given peer can download. Another goal is that we would like to complete a piece as early as possible so we will try to complete from pieces that are in progress first.

Currently, the system works by looking at the pieces in progress and then try to serve from these. If all blocks have been taken on pieces in progress, we find one that is pending (randomly) and available at the peer. This one is then promoted to being in progress and the algorithm runs again.

There are a couple of nice optimizations possible. First, if the peer is a seeder, it effectively has every piece. Thus, there are no reason to keep the IntSet around for those, nor is there any reason to carry out expensive IntSet intersections. Second, if the peer is not a seeder, it would be better to keep a bit array around rather than an IntSet. It does count for a good amount of live memory in the Peer processes, and we expect there to be quite many of those. Third, we could benefit from keeping a cache of the last piece the peer requested blocks from. Trying this cache element blindly in the Piece Manager is advantageous to us: we spend less time in the Piece Manager code. It is also nice for the peer: if a piece is cached at the other end, we might help by requesting as many blocks as possible from that piece. Disk IO is a point of contention in modern bittorrent client implementations.

Always pick the rarest piece first

We currently pick pending pieces at random. A better scheme is to know about their availability and then pick them rarest first. The rarest piece is the easiest for us to spread, so it maximizes our ability to give back, which in turn maximizes our ability to download fast. The right Haskell cabal library for this is Data.PSQueue in the package PSQueue. If there are more pieces eligible at the same rarity, we will pick one at random. This gives an excellent use of View Types in Haskell, should one be interested.

To do this, there is a milestone you need to reach beforehand. When we receive knowledge of piece availability, either through a BITFIELD or a HAVE message, we should propagate that information to the Piece Manager. In the beginning, we can just do nothing with it, and throw it away. It will pave the way for a PSQueue implementation however.

Increase code quality

Run hlint on the code. There is a target in the Makefile, which has recently been fixed. Find a GHC warning which is not yet enabled in the .cabal file and enable it, fixing the bugs that turn up. I guess some of these are more evil to fix than others, so start with the easier ones.

Another area are tests. Running HaskellTorrent —tests will run the embedded test suite. This one fails on 64bit architectures at the moment (I think, this is the narrowing-down I’ve done). If you spot any area which you can figure out how to test, I would really like to discuss it with you. The code can do with a lot more testing than it use right now.

Discuss use of attoparsec, attoparsec-iteratee and the event library

I am seriously contemplating impaling all network performance bottlenecks once and for all by using this triple. If you are interested in hacking these, I’ll be happy to talk to you about it. It would push the bottleneck to the Disk layer once and for all, I think. The cool thing is that there are code to gain inspiration from.

Another nail to the coffin is to support the FAST-extension in the new parser right away. It would pave the way for the rest of the client to understand this extension, so we would be able to get better and faster communication. It also plugs a bug in the original bittorrent specification.

Use mmap() for Disk IO

The right way to do disk IO is by use of mmap() on the files. Reading and writing files are not going to be hard, but we also need to get the hopenssl library to talk to the mmap()’ed backend so we get fast checksum calculations.

On Computer games and Tufte

2010-03-08T04:02:00.001-08:00

Tufte applied to games

I played a small bit of the old Infocom game “Wishbringer” the other day. And somehting struck me. This game is small. It has something like 50 locations, with miniscule text at each location. Of course this is because of the limitations of the hardware from the day the game was released, but it also made me think. There is so much game crammed into those 50 locations. Clever location reuse makes the game seem larger than it is. In fact, the majority of locations change considerably over the course of the game.

Now contrast this with newer sandbox games of enormous size: Morrowind, Oblivion, Fallout 3, all by Bethesda. These games are absolutely huge, but in contrast, the world is a mostly static one with very few changes over the course of the game. Tufte, who just got appointed by the US government to visualize government spending, had this notion of “ink carrying meaning” and “ink”. The ratio between these gives you a number of how much ink is wasted and how tightly information is packed on a piece of paper.

Applying Tuftes observation to game worlds is interesting and fun. Games like Morrowind and Oblivion has a very low ratio of value, whereas an old game like Wishbringer has a very high value. Surprisingly, the game Arx Fatalis from 2002 will have a rather high ratio. In Arx Fatalis, the game world is pretty small. But the game uses several tricks to circumvent this. The game world is reusing locations for more than one thing. Also, the game world is opened up to you gradually along with the game unfolding. The same idea is applied in the game “The Witcher” where the majority of the game is going on inside a city. New major areas of the city opens up in later acts, but the old areas are kept and changes.

Today, building huge worlds is not hard. You procedurally generate most of the content in the game through different technologies like SpeedTree for instance. Oblivion has hand-crafted dungeons it would seem, but usually they are just there for being there and not for moving the story ahead. Contrast that with random dungeon in Diablo 2. Usually, there is a chest at the end of those with good levelled loot. Being a loot-game, Diablo 2 encourages you to walk the dungeon.

I sincerely hope that in the future, more games will be like “Wishbringer”. Mass Effect 1 (Have not played the 2nd game) shows some of the way, but it also adds a lot of randomly generated open spaces driven by a car. These are boring. Kill.

Luck has it, that small flash-games and similar platforms will make the game logic be central again. I expect there to be some really interesting games with good “Tufte ratios” in the coming years. But the platform will be Web, mobile phone, Javascript or Flash.

HaskellTorrent v0.0 and further developments

2010-02-25T10:57:00.000-08:00

HaskellTorrent v0.0 released!

Last weekend I released version 0.0 of the HaskellTorrent project. However, as modern development will have it, the interesting things happen on the main integration branch, master, on github: haskell-torrent. From the point where the 0.0 release was done and till today, three main things happened in the client.

CPU optimizations

A little bit of work with the profiler has shaved the use of the CPU down by a fairly large amount. I optimized the assertions on the piece database by using Data.IntSet rather than plain old lists. Right now the cost centres are the piece database assertions (still) and deciding which blocks to download. The former of these is simple to get rid of. We don’t need to assert the database at each message, but can do so with a rarer frequency. As for the latter, I have a couple of ideas to shave off CPU cycles on that one as well.

Listen sockets

HaskellTorrent now accepts incoming connections! It does this on port 1579 that has no special connotation apart from being one of the fairly low prime numbers. The etorrent project uses 1729 which has a more interesting history associated with it. Of course, one has to open the eventual NAT/PAT or Firewall to get connections flowing in, should you want to test it.

test-framework

Finally, we now use the excellent test-framework by Max Bolingbroke. The test inclusion was inspired a lot by Eric Koweys blog post on the subject, and it also used bits and pieces from Real World Haskell.

The bottom line is that now you can execute tests directly:

jlouis@illithid:~/Projects/haskell-torrent$ make test
runghc Setup.lhs build
Preprocessing executables for HaskellTorrent-0.0...
Building HaskellTorrent-0.0...
runghc Setup.lhs test
Test test-framework:
reverse-reverse/id: [OK, passed 100 tests]
Protocol/BCode:
QC encode-decode/id: [OK, passed 100 tests]
HUnit encode-decode/id: [OK]
Protocol/Wire:
Piece (-1) 1 ""
QC encode-decode/id: [Failed]
Falsifiable with seed 2776559770653812966, after 1 tests. Reason: Falsifiable

       Properties  Test Cases  Total
Passed  2           1           3
Failed  1           0           1
Total   3           1           4

though it does seem we need to do some work in order to correct the software :)

2010-02-03T16:10:00.000-08:00

How logging is performed in Haskell-Torrent

First an update: Haskell-torrent has downloaded its first torrent file “from the wild”. Unfortunately, this behaviour is not deterministic yet, and sometimes the download fails in spectacular ways.

For a bittorrent client, which is heavily concurrent, we have a few obvious tools at our disposal to ensure correctness. We can use QuickCheck to generate test cases and test properties. This is best done with the parts of the code relating to encoding and decoding of data in the client. Second, and I think this is important, we can pose invariants on the various processes and check that these invariants hold periodically. Third, we can trace the execution.

In order to trace the execution, we need a logging framework. Several exist for Haskell, but none of these really suits our purpose.

Logging

The first thing we have done is to create a process with a channel. This process is the logger and the only task is to drain the channel and send out log messages on stdout. All other processes log by synchronization on an event where a log message is sent to this process.

Log messages have three components: A /name/ of the logging process, a /message/ to log, and a priority:

> data LogPriority = Debug -- ^ Fine grained debug info
>          | Warn  -- ^ Potentially harmful situations
>          | Info  -- ^ Informational messages, progress reports
>          | Error -- ^ Errors that are continuable
>          | Fatal -- ^ Severe errors. Will probably make the application abort
>          | None  -- ^ No logging at all
>              deriving (Show, Eq, Ord)

Since the log channel is part of so many process configurations, it is beneficial to create a type class of those configurations which can log:

> class Logging a where
>    getLogger :: a -> (String, LogChannel)

For example, the Piece Manager has a configuration

> data PieceMgrCfg = PieceMgrCfg
>     { logCh :: LogChannel
>     , pieceMgrCh :: PieceMgrChannel
>     , fspCh :: FSPChannel
>     , chokeCh :: ChokeInfoChannel
>     , statusCh :: StatusChan
>     }

so to make it possible to log, we instance this

> instance Logging PieceMgrCfg where
>   getLogger cf = ("PieceMgrP", logCh cf)

And to formalize what a log message and channel are:

> data LogMsg = Mes LogPriority String String
> type LogChannel = Channel LogMsg

> instance Show LogMsg where
>     show (Mes pri name str) = show name ++ "(" ++ show pri ++ "):\t" ++ str

The logging itself is done by a logger function. Here is its type:

> log :: Logging a => LogPriority -> String -> Process a b ()

It designates that it takes a Priority and a Message to log (the String). It then logs in a Process monad where the configuration is of type a and the state is of type b. Note that the configuration must be an instance of the Logging class.

The code itself is rather straightforward, save for the call to the logLevel function:

> log prio msg = do
>   (name, logC) <- asks getLogger
>   when (prio >= logLevel name)
>       (liftIO $ logMsg' logC name prio msg)
>   where logMsg' c name pri = sync . transmit c . Mes pri name

For the sake of convenience, we want it simpler for most uses, so without much further ado:

> logInfo, logDebug, logFatal, logWarn, logError :: Logging a => String -> Process a b ()
> logInfo  = log Info
> logDebug = log Debug
> logFatal = log Fatal
> logWarn  = log Warn
> logError = log Error

Filtering

The missing piece of the puzzle is now the “logLevel” function. In the function above, we only log messages which has a priority higher than the current log-level. The log-level is discriminated by the process name in question that tries to log.

Basically, what we want is a simple way to filter log messages. Rather than log all messages, we want to selectively log only part of these, depending on what we are currently debugging or tracing. A log filter is:

> type LogFilter = String -> LogPriority

That is, given a process name, they return a minimum priority for that name. The log function then filters the message if it is not above this priority. Here are a couple of simple combinators:

> matchP :: String -> LogPriority -> LogFilter
> matchP process prio = \s -> if s == process then prio else None
> 
> matchAny :: LogPriority -> LogFilter
> matchAny prio = const prio

The first of those matches a process by name. If there is a match it sets a specific priority. Otherwise it punts by returning the highest priority possible. The second is a simple wrapper for always matching at a given level.

With this down, we get to action. Log priorities are Monoids in the sense that None is the neutral element and composition ignores None by “eating” it:

> instance Monoid LogPriority where
>     mempty = None
>     mappend None g = g
>     mappend f g    = f

Since there is already an instance:

> instance Monoid b => Monoid (a -> b) where ...

Log filters are now monoids. So we can write:

> logLevel :: LogFilter
> #ifdef DEBUG
> logLevel = mconcat [matchP "SendQueueP" Fatal,
>             matchP "ReceiverP" Fatal,
>             matchAny Debug]
> #else
> logLevel = matchAny Info
> #endif

Which means that we do not care much for log messages from the processes “SendQueueP” and “ReceiverP” unless they are fatal. Otherwise we want Debug messages or above. The only restriction is that the first match in the monoid chain is the one that steers the level.

Haskell Torrent is nearing a preview release

2010-01-27T12:01:00.000-08:00

Since the last blog post, a number of new things have been developed for Haskell Torrent. Here is a list of the highlights:

John Gunderman documented a queue interface and helped me with haddock.
The code doing SHA1 Digests have been abstracted into its own module.
We now handle interest as intended in the bittorrent protocol. We update interest based on what peers tells us they have available.
We now pick pieces in Random order rather than linearly.
We correctly inform peers when we have retrieved a full message by sending them HAVE messages.
We can now track how many bytes are left on a torrent. This is needed for the tracker.
We have some preliminary rate calculation code, based on a 20 second window and running averages. It ensures a somewhat fair treatment of the rates of different peers.
The Choke Manager now uses the rate calculation code to choke peers based on their current speed.
The Readme file has been updated with what extensions and protocol-parts we support.

The current goal:

We currently aim for two things: BEP-003 support and a preview release (version 0.1). The BEP-003 is the support for the basic bittorrent protocol with no extensions at all present. This is the bare minimum needed to be able to call ourselves a bittorrent client. The list of missing items for BEP-003 is as follows:

When the torrent file is initializing it needs to calculate how many bytes there are left to download before completion. This number is reported to the tracker.
We need to make sure that the tracker is informed of Torrent completion in the right way.
The client will have to handle multi-file torrents. That is, torrents where there are more than one file. We can punt this to after the preview release if needed, because it is not that important for a preview of the client.
We must correctly change to a seeder mode when the torrent file in question completes. This is currently not happening.
We use a Pure Haskell SHA1 checksum code. Rather than doing this, we should outsource our digest calculation to OpenSSL through the hsopenssl package. The abstraction should make this easier. This is not strictly needed for BEP-003, but it is nice to have.

The client will currently not handle the endgame in any special way. This means that a torrent will take considerably more time to complete. On one hand this would be nice to have before the preview release. On the other hand, I think it is better to bump it.

On the Preview:

The preview is not a working client. The purpose is to get the client tested in different environments by different people so we can find some bugs and get them sacked. I would like to have a client which has shown itself able to download files in non-lab environments, but perhaps with many bugs still left. This is also to get a test of the release engineering involved in the process. The release will also mark a milestone in the development: we can use it as a stepping stone and a breathing space while we decide what to work on next.

The plan is to use hackage for the release. I am using the Haskell Platform here - but that means GHC6.10.4. We could use a couple of compilation tests on what will become the next Haskell Platform. I am afraid we use some stuff which changed. A quick heads up would be nice.

Also, before the release, I would like some janitorial code work done. I have not enabled -Wall while developing, but around now might be the time that someone enables it and begins cleaning up dead code, limit module exports and similar janitor-work.

Watch this blog. The moment the client has downloaded its first non-lab torrent will be worthy of an announce. I can't predict the future, but my gut feeling says it is going to be soon.

(Note: The layout of this post is miserable. This is what you get in return for using blogspots built-in editor :)

The state of Haskell-Torrent

2010-01-16T10:25:00.000-08:00

Implementing processes

The Haskell Bittorrent project is evolving at a steady state these days. In the last couple of days, we have implemented most of the code relevant for carrying out choking of peers. Choking is the process by which you only communicate to a few peers at a time. Thus TCP/IP congestion can be avoided which drives up the download and upload rates. This post is not on this part however, which must wait a bit.

A fellow dane, Thomas Christensen, heeded my call and did some hlint runs over the code. Hopefully, we’ll see more work from him (github). Alex Mason has added even more parsing stuff through Cereal to the code, fixed a number of bugs in the parser and improved its general state. His venture is described on his blog (here).

Processes

I will be talking about processes in this post. When haskell-torrent started, our processes were simply “things spawned in the IO monad”. The approach works, but it quickly becomes inadequate for several reasons. In Haskell and FP in general, a lot of power stems from the idea that we can write a large set of small building blocks and then compose them together to form increasingly larger and larger blocks as we go. When composing, we use a fairly small number of helpers — readily present in the standard libraries.

When running in IO, we quickly end up with a lot of state. This can of course be passed around by “hand” and tail-calls. Unfortunately, this means we will end up using a lot of our precious coding time doing just exactly that. To optimize, we need a way to reflect away configuration and state when we don’t need it, and reify the information at certain points in the program where it is necessary to know the state.

The ubiquitious tool in Haskell for this are Monads. Not a single monad like IO, but a for-the-case relevant monad built from monad transformers. A couple of days ago, I installed XMonad by Spencer Janssen, Don Stewart, Jason Creighton and many more. This is a window manager — but surprisingly, it needs to solve some problems similar to the one in haskell-torrent. By inspiration from XMonad, we define

> newtype Process a b c = Process (ReaderT a (StateT b IO) c)
>    deriving (Functor, Monad, MonadIO, MonadState b, MonadReader a, Typeable)

That is, a Process is a type. It contains some configuration data a, an internal state b and is in the process of evaluating to a value of type c. We use a Reader transformer so we can ask for configuration data when we need it. We do not expect this configuration data to be altered when the process runs. A State Transformer takes care of the internal state of the process. Finally, we let the underlying monad be IO. This gives us access to CML and the outside world.

We let GHC derive a large set of things automatically (using several extensions in the process). This gives an easier way to manipulate the state when the process is running.

Running a Process is easy:

> runP :: a -> b -> Process a b c -> IO (c, b)
> runP c st (Process p) = runStateT (runReaderT p c) st

which is exactly like in XMonad. Spawning a new process is also fairly easy:

> spawnP :: a -> b -> Process a b () -> IO ThreadId
> spawnP c st p = spawn proc
>   where proc = do runP c st p
>                   return ()

In general different processes will have different configurations a. These will usually contain the channels on which the process can communicate. We then define a type class

> class Logging a where
>   getLogger :: a -> LogChannel
> 
> instance Logging LogChannel where
>   getLogger = id

of types that contain a logger channel. This means we can define a generic log function like this:

> log :: Logging a => String -> Process a b ()
> log msg = do
>     logC <- asks getLogger
>     liftIO $ logMsg logC msg

Type classes are a magnificent tool when we want to coerce a general function on top of different types. Many of our configurations in the client will instance the Logging class and then the log function knows how to access the logger in the Reader.

What does this buy us

The advantage of doing this change on the code is twofold: First, the amount of parameter passing is considerably reduced. Reflection into the monad solves this problem. We are now able to compose easier. Function composition is considerably harder when there are many parameters abound. With the change, preliminary restructuring of the Peer process shows a much simpler flow. Also, there are now ample refactoring opportunities available with the change.

Second, the monad means we can use locality much more to our advantage. A common idiom is to modify the state of the process or to retrieve the current state for query. This now happens locally at the point where it is needed. Before, we might have needed to pass a parameter through several functions and then use it.

What next?

There are a small number of things that needs to be addressed before we can claim that the client is a full bittorrent client:

The client needs to correctly handle the concept of interest. It must tell other clients if it is interested in the pieces they have at their disposal for transmission. I have some preliminary code for doing this.
The client needs to correctly tell the tracker how many bytes it uploaded and downloaded. This measure is needed on many private trackers as they require people to upload data back.
The client needs to be better at choosing the next eligible piece. Choosing one randomly is good enough.
The client needs to handle multi-file torrents. It is not as hard as it may sound — the only part of the system that needs to know about files is the code handling the file system. All other parts can just keep on transferring pieces.
For choking to work correctly, we must know how fast we are currently transferring to a peer. This is an interesting little problem if somebody feels their curiosity tickled :)
We currently take space proportional to torrent size due to our SHA1 calculation being slow and not use a file descriptor. Research into a faster SHA1 library would be really beneficial.
We need to accept incoming connections. The system only connects outward at the moment.

And of course, it needs some testing in a non-lab setting. Currently it can seed and leech, but my setup is very simple: Opentracker and rtorrent on another computer.

The main github repository for haskell-torrent is here.

Thoughts on process hierarchies in Haskell.

2010-01-05T12:40:00.000-08:00

On Process Hierachies

I have been in thinking mode the last couple of days. It all started when I decided to look at the problem of wrong in haskell-torrent. What will happen when something fails? Joe Armstrong has part of the answer by arguing that we must proactively expect a process to fail and then let some other process clean it up (paraphrased a lot by me, these are not his exact words).

Take a look at this image,

It is a hypergraph where each vertex corresponds to a process and each edge corresponds to an channel. The graph is undirected because in principle each process can both send and receive on the channel in question. In practice however, one can limit the communication as some processes will only transmit on a channel, and others will only receive (and some will do both).

To simplify the graph, I omit local RPC channels. It is customary to implement RPC by creating a local channel and transmitting that channel over one of the hypergraph edges. Response can then work directly on the local channel, simplifying the problem of giving identity to processes in many cases.

Termination

A somewhat scary part of such a network is what happens when we want to terminate it or if something goes wrong in one of the processes. In particular, we have the problem that while Haskell is a pure, nice, protected Nirvana — the real world inside IO is a dank, dark place of twisted little passages (all alike). Thus it might very well be that we get to experience an exception first-hand in one of the above processes.

I have toyed with the idea of copying the excellent CHP library by Neil Brown. Neil defines a concept of poison for channels. A channel that has been poisoned will always transmit poison. Poison thus propagates through the hypergraph and slowly but surely kills off each process. Neil has a description of the process on his blog. I like the idea because it uses the existing infrastructure of the hypergraph. It would be fairly easy to add support for writing poison handlers at each node.

Process Hierarchies

I have pondered on a different scheme for the last couple of days however. We can impose a location graph on the hypergraph above:

This graph, a tree, describes the location or hierarchy of the processes in question. The processes named S0, S1, … and so forth are supervisors. Their responsibility is only one: Keep their children running according to a policy. Erlang programmers fluent in the OTP high level libraries present in the Erlang distribution will recognize the supervisor term.

A normal (worker) process has two rules:

If the process terminates, it must inform its supervisor.
If the process gets an asynchronous KillThread exception, it must die.

A supervisor process needs to obey the following scheme:

If a process under its supervision dies it must take affair according to its policy. This may mean that it kills off all other children and reports back to its supervisor for instance. Or it may mean that it simply restarts the process that got killed. What happens is dependent on the policy we configured the supervisor with.
If a supervisor is asked to shutdown by a KillThread exception, it must first kill all of its children.

Note that with these rules, termination is almost free: Terminate the tree. Because everything is linked to the tree, termination will happen. We will terminate by asynchronous exceptions aggressively.

An interesting difference from Erlang is that of communication, which is a certain sense is Dual in Haskell+CML: In Erlang, the process id is what you need to hold in order to transmit an (async.) message to the process. In our CML-based system the channel is the name you must hold in order to communicate. In other words, this lets us, in some circumstances, replace the process with a new one but keeping the channel. Note, though, that the interface is not completely clean: if the Haskell runtime figures out a thread is indefinitely blocked, it will in general throw an exception — but I have not yet read the CML code in detail so I do not know if this will happen. It depends on what MVar references a channel hold.

Another view

The hypergraph and location graph constitutes what is sometimes called a Bigraph. This is not to be confused with the term Bipartite graph which is a completely different term but sometimes also called a bigraph unfortunately. I somewhat resist the idea to use the same term for different concepts, but work done in this twi-graph concept presented in this post on bigraphs suggests that the term is quite used in this respect.

The research seems different from what I need however. ITU has done extensive research in bigraphical programming languages, letting them describe various known calculi (Lambda, Pi, etc.). I just want to use the descriptive power of the bigraphs to discriminate location from communication.

So to conclude: Does that give anybody out there a brilliant idea or does my design have an inherent flaw I should be aware of? If not, I'll probably try to sketch some code in Haskell for the Supervisor tree and processes.

On the idioms in haskell-torrent

2009-12-29T11:30:00.000-08:00

This post serves several purposes. First, we bring an update on the code state: The client is now able to leech, that is download, in a lab setting. The lab consist of a test tracker, an rtorrent client two computers. The tesfile is file of 5000000 bytes containing a specific phrase over and over. This gives good compression ratio in git and thus it is not that irritating to move over the wire if needed.

Alex Mason did a good job improving several things in the project. He added prioritization to logging, got compilation working on GHC 6.12.x and is now looking at improving every aspect of data parsing. The BCode work, able to handle the bittorrent bencoded data using applicative functors (Data.Applicative) look really good.

The latter part serves two purposes in parallel: It describes the used idioms and it describes the piece manager code used for leeching torrents. This is a work in progress and there are some things we don’t handle yet.

Also, I am trying to use John MacFarlane’s excellent pandoc package for typesetting this in blogger.

The Piecemanager

The Piece Manager is defined in the module PieceMgrP. It is responsible for keeping track of the torrents internal Piece State. That is, what do we need to download, and what have we already downloaded and can serve to other peers. Remember that in our terminology, a Block is a subset of a piece, given by an offset and a length. You could call it a slice of a piece.

The basic idiom of the piecemanager is that of an owning process. In traditional semaphore-oriented programming we protect a data structure by a mutex. We could also protect it software transactions, but since we partially derived haskell-torrent from etorrent, we’ll go with the message passing method. We simple invent a process to manage the data structure. Operations on the structure is then serialized by passing them to the process and gettings answers back, RPC-style. It might not be parallel, but it certainly is easy.

The data structure we want to protect is the piece database:

> data PieceDB = PieceDB
>    { pendingPieces :: [PieceNum]
>    , donePiece     :: [PieceNum]
>    , inProgress    :: M.Map PieceNum InProgressPiece
>    , infoMap       :: PieceMap
>    }

The database contains a list of pieces which are pending for download. This list should, in a perfect world, be maintained with a histogram such that we know the rarity of each piece. A good client prefers rare pieces to young pieces and selects randomly among pieces of the same rarity. A weaker client picks randomly without taking their rarity into consideration. A dumb client, like haskell-torrent currently, just picks them off from a single end. This is bad for the torrent cloud to do, but it is a start. If someone comes up with a data structure which is (practically) efficient for storing histograms, I would be happy to hear about it.

The donePiece record field is the list of pieces that are done. We keep this around because when a new peer is connected to the client then we need to tell this peer about what pieces we have fully downloaded.

Then we have Data.Map Map which tells us something about Pieces that are in progress. The InProgress data type has the following structure:

> data InProgressPiece = InProgressPiece
>    { ipDone  :: Int
>    , ipSize  :: Int
>    , ipHaveBlocks :: S.Set Block
>    , ipPendingBlocks :: [Block]
>    } deriving Show

These fields are (in order) how many blocks in the piece we have downloaded, the complete size of the piece, a set of the blocks we have downloaded and a list of blocks pending download. The size of the piece is almost always the same, but the last piece is different if the complete file is not a multiple of the block size.

Returning to the PieceDB, the last entry describes the complete torrent. The PieceMap tells, for each piece, its offset in the file, its length and its SHA1 digest. Note we do not support multi-file torrents yet, although this code would probably be unaltered. The offset is in the multi-file-case the offset in the concatenation of the files in the torrent.

Starting the process

The PieceManager process is started with the start call:

> start :: LogChannel -> PieceMgrChannel -> FSPChannel -> PieceDB -> IO ()
> start logC mgrC fspC db = (spawn $ lp db) >> return ()
>   where lp db = do
>           msg <- sync $ receive mgrC (const True)
>           case msg of

We supply a number of CML-channels to the process from the outside and then we spawn off the main loop before returning (). This is probably not good in the long run, where we will need to handle errors in the process. But for now we accept that the code is supposedly error-free and never have any problems.

The loop code itself synchronizes on messages here named msg. These messages have the form

> data PieceMgrMsg = GrabBlocks Int [PieceNum] (Channel [(PieceNum, [Block])])
>                  | StoreBlock PieceNum Block B.ByteString
>                  | PutbackBlocks [(PieceNum, Block)]
>                  | GetDone (Channel [PieceNum])

and each of these are going to be explained in the following. A general note is that if the message contains a channel, it is usually a form of RPC-message, where the channel is the return channel on which to send back an answer. One could probably factor this out into a generic RPC-construction with a bit of cleverness, but I have not given it much thought yet.

In the following, we present some examples of processing these messages.

Grabbing blocks

Here is the fragment for grabbing blocks. It is one of the paths in the diagram above.

> GrabBlocks n eligible c ->
>    do logMsg logC $ "Grabbing blocks"
>       let (blocks, db') = grabBlocks' n eligible db
>       logMsg logC $ "Grabbed..."
>       sync $ transmit c blocks
>       lp db'

Basically, this call is a request by a peer process to get exclusive access to n blocks among all the available blocks for a while. This ensures that only this peer will download the blocks, eliminating block collisions. The eligible value is a list of pieces that the peer has already downloaded, and we should of course only choose blocks among those. Our block grabber may honor the request or return an empty list if no block can be satisfied.

The guts is hidden in the call to the helper grabBlocks’, which we will describe later.

Storing blocks

The other path in the diagram is maintained by this code fragment:

>  StoreBlock pn blk d ->
>      do FSP.storeBlock fspC pn blk d
>         let (done, db') = updateProgress db pn blk
>         if done
>            then do assertPieceComplete db pn logC
>                    pieceOk <- FSP.checkPiece fspC pn
>                    let db'' =
>                      case pieceOk of
>                        Nothing ->
>                          error "PieceMgrP: Piece Nonexisting!"
>                        Just True -> completePiece db' pn
>                        Just False -> putBackPiece db' pn
>                    lp db''
>             else lp db'

We get a request to store the block blk in piece pn where d is the data we want to store as a ByteString. We invoke the filesystem to actually store the block. In a real world, we would check that this is really what we wanted. If the piece is already complete and checked, we don’t want a stray block to errornously destroy the piece. In general we want more checks like these in the client.

Then we update the database with the progress on the piece. If the piece is done, we invoke a checking of that piece. Either it is complete and Ok, in which case we mark it as such in the database — or it is not Ok, in which case we put it back for downloading. This happens in the real world at times due to clients with bugs so it is always important not to trust the other client. If the piece completes, we should send out HAVE messages to all connected peers. I plan to make the Peer Manager do that, but the code has not yet been implemented for that.

The RPC idiom

When we initially connect to a peer, we will have to transfer the pieces we have. To do this, we construct a BITFIELD message and to construct this, we need the set of pieces which are complete. The GetDone message handles this:

> GetDone c -> do sync $ transmit c (donePiece db)
>                 lp db

and the peer which want this calls the function

> getPieceDone :: PieceMgrChannel -> IO [PieceNum]
> getPieceDone ch = do
>  c <- channel
>  sync $ transmit ch $ GetDone c
>  sync $ receive c (const True)

I think there is an idiom to be extracted from this code and as it is used quite a lot it would be very beneficial to have in the long run.

Grabbing blocks, the inner workings

The diagram above hints that grabbing blocks has a more complicated control flow. The idea of the code is that the control flow is modeled by a tail call into the next box. Let us break up the code:

> grabBlocks' :: Int -> [PieceNum] -> PieceDB
>             -> ([(PieceNum, [Block])], PieceDB)
> grabBlocks' k eligible db = tryGrabProgress k eligible db []
>   where

So we will try to grab k blocks from the eligible pieces from db. The empty list is the accumulator in which we add the blocks we found as we go.

>    tryGrabProgress 0 _  db captured = (captured, db) -- Enough, exit
>    tryGrabProgress n ps db captured =
>        case ps `intersect` (fmap fst $ M.toList (inProgress db)) of
>          []  -> tryGrabPending n ps db captured
>          (h:_) -> grabFromProgress n ps h db captured

Grabbing from the pieces already in progress minimizes the number of “open” pieces. We want to minimize this as a complete piece can be checked for correctness. Correct pieces can then be shared to others and since our download speed is dependent on our upload speed, complete pieces is key. Finding a piece is simply to carry out set intersection. If you’ve read to this point, there is a refactoring opportunity by using M.keys.

A smarter client, as hinted, would order the eligible pieces such that the rarest pieces were tried first. One could also toy with the idea of pruning: tell the peer what pieces we already have downloaded so it won’t include them in further requests. This would keep the ps parameter small in size.

There are three exit-points. Either there was a piece, h, we can grab from that one, or there were none among the pieces in progress: we will then seek the list of pending pieces. Finally, if we are requested to grab 0 blocks, we already have enough blocks and can return those we have together with the new database.

>   grabFromProgress n ps p db captured =
>       let ipp = fromJust $ M.lookup p (inProgress db)
>           (grabbed, rest) = splitAt n (ipPendingBlocks ipp)
>           nIpp = ipp { ipPendingBlocks = rest }
>           nDb  = db { inProgress = M.insert p nIpp (inProgress db) }
>       in
>           if grabbed == []
>            then tryGrabProgress n (ps \\ [p]) db captured
>            else tryGrabProgress (n - length grabbed) ps nDb ((p, grabbed) : captured)

Here, we have found the piece p as being in progress. So we find its InProgress structure, and use Data.List.splitAt to cut off as many blocks as possible. We may find that we can’t grab any blocks. This happens when we or other peers are already downloading all pieces. We then prune the piece p from the set of eligible pieces and try again. Otherwise, we update the database and the number of pieces to grab and go back to start. Another hint: We should probably prune p from ps here as well :)

>   tryGrabPending n ps db captured =
>       case ps `intersect` (pendingPieces db) of
>         []    -> (captured, db) -- No (more) pieces to download, return
>         (h:_) ->
>             let blockList = createBlock h db
>                 ipp = InProgressPiece 0 bSz S.empty blockList
>                 bSz = len $ fromJust $ M.lookup n (infoMap db)
>                 nDb = db { pendingPieces = (pendingPieces db) \\ [h],
>                            inProgress    = M.insert h ipp (inProgress db) }
>             in tryGrabProgress n ps nDb captured

Finally, this part grabs from the pending pieces. Either we can’t find a piece and then we can just exit. In the other case we have found a piece. We then create the blocks of the piece and insert it into the pieces in progress. The tail-call to tryGrabProgress will then find it.

I hope the similarity to the diagram is clear. When building these tail-call mazes I usually start with the diagram sketch. Then I hand-write them in Graphviz’s dot-notation and create them. Finally I write the code.

On Peer Processes

2009-12-27T16:37:00.000-08:00

On Peer Processes

The diagram above is the control-flow in the Peer Process as it stands right now. This process is responsible for communicating with another Peer in haskell-bittorrent. This post is not about the details of the inner workings. Rather it serves to document the legend of the diagram.

All the ellipses that are blue signifies other processes. The inbound process waits on the socket for incoming messages and sends them into the Peer process. The outbound process is a queue which dequeues messages as fast as possible to the peer in the other end. Peer Manager is the process which manages a set of peers -- we have one Peer process for each peer. Finally, Piece Manager is responsible for managing the state of the torrent: what subsets of pieces do we have and what is missing before we have the full file?

A little bit of terminology: a piece is the smallest array of bytes we can SHA1 check for correctness. A block is a subset of a piece which is transferred by the wire protocol. In practice these are always 16K although the protocol provisions for alternative sizes. The reason for this split is that the 16K blocks means we can interleave other messages in between. Further, we can get a hunch on how fast we transfer to a peer by looking at the amount of bytes we can dequeue and smaller blocks means a better granularity.

The diagram depicts the control flow of the client. Black arrows designate how control transfers from one function to the next (usually by tail-calling this is functional programming after all). The blue dotted arrows specifies synchronization points with external processes. If a blue dotted arrow enters a box it usually means that control can only transfer to this point if the corresponding event tied to the arrow fires. The Piece Mgr and "Grab up to ..." is the exception from the rule however: when arrows are back and forth, it is a rpc call.

If a blue dotted arrow leaves towards an external process it means we will wait for a synchronization towards that process before continuing out of the box.

The current state

Modulo some work in the debugging and QA department, the client should be able to leech in a laboratory setting. We cheat by having no Peer Manager yet and we can essentially not really support many Peers properly yet. When the client portion stabilizes it should be fairly easy to add proper Peer managent. I hope to support leeching in the coming days.

Wanna help?

If you want to help out, there is plenty to do. I am still, deliberately, leaving many things open so it should be fairly easy to pick up the code from github and then do some of the simpler stuff. I've not run the excellent hlint by Neil Mitchell - so there should be an opportunity there. There is also an amortized queue implementation which could do with some documentation. Finally, the TODO list is littered with what needs to be done.

On github: haskell-torrent.

Concurrency, Bittorrent clients, and Haskell

2009-12-19T15:16:00.000-08:00

I have been writing code lately on a BitTorrent client in Haskell. Here is the grand old history of that effort. Many years ago, I attempted to start a client, Conjure, written in Haskell. Sadly, it really did not make it to the point where it was really usable, for me at least. Then a couple of years passed, I became involved with programming in Erlang. Erlang has a really nice Actor-based concurrency model. Since BitTorrent is highly concurrent and event-driven it was easy to start another implementation effort in Erlang. Thus etorrent was born. Sadly, I lost interest in etorrent - partially because I am partial to statically typed languages of which Erlang is not one. Thus, we come to this december, where I decided to figure out the state of concurrency in Haskell. To really give GHC a whirl, we need to implement something which is fairly complex. Some people implement ray tracers when toying with programming languages, some solve projecteuler problems. I ... write BitTorrent clients.

BitTorrent is a good maturity check. First, you need decent Disk I/O, decent network I/O and a fairly complete HTTP client. Second, the protocols are easy, but still requires some nontrivial parsing to occur. Finally, the system is fairly concurrent, so it fits nicely into concurrency models if the language has one.

Initial Thougths:

Initally, there is the choice of a concurrency framework. In Haskell, there are several such. The built-in Control.Concurrent is fairly low level and fairly simple. At the CS department at Copenhagen University, DIKU, there is currently a course running in CSP and some students decided to use Control.Concurrent.CHP by Neil Brown. I think it will suit them well for the course, but it irritated me that it mapped so weakly to the etorrent model. So Control.Concurrent.CML became the basic library for concurrency. This concurrency model is not entirely unfamiliar to me: it is written by John Reppy for ML.

The CML model is somewhat reminiscent of the Pi-calculus. In particular, we can transmit channels on channels. This gives a neat method for doing RPC-style operations. Send off a message together with a responder channel and then wait for a response on that channel. This means we are easily able to emulate most of what the Actor model has if needed.

Haskell-torrent design:

Haskell-torrent uses a basic design, where a fairly large number of processes communicate with each other to solve the problem of uploading and downloading files. We have a limitation of one single torrent right now, but that should be fixable in time. The process diagram at the header describes the basic layout. Each box is a single process, apart from the "Peer" box, which is multiple processes. The diamond-shapes describes external communication over the network.

Console: A process responsible for User communication. The idea is to have a simple console-interface on which to log messages (it is heavily used for debugging). The Console can in time also be used for parsing user input and affecting the system. It only responds to a "quit" command at the moment. Logging is done with a LogChannel on which the Console process syncs and prints out information.

Main: Initial program entry point. Spawns everything else and is the last thing that closes again.

Status: Keeps track of various torrent-specific statuses. How much is left to download? How many seeders are there? How fast is the torrent currently? The intention is to keep this kind of information around in that process.

Tracker: Communicates with the tracker. Is a specialized HTTP client. It talks to the Timer so it won't continually request the tracker for information. In due time, it should also be able to do UDP tracking. It is using bencoded documents as per the tracker spec. These bcoded documents are handled as in Conjure with the monadic parser generator Parsec.

PeerMgr: Handles a set of peers. Gets lists of other peers via the Tracker process and spawns a pool of them. In due time, this process will handle choking/unchoking of peers so we don't clog the TCP/IP stack by trying to talk to everybody at once.

Listener: Listens on a TCP port and spawns off Peers when they try to connect. Not implemented at all yet, but is fairly easy to get to work.

OMBox: A very simple implementation on top of CML of what is present in Control.Concurrent.SampleVar. This will let the PeerMgr be able to place things for the Peer to read later and it avoids a deadlock between those two which otherwise would occur. OMBox is currently not cleaned up properly. We need some mechanism for poisoning the communication channel so it closes down again gracefully.

Peer: The system contains zero or more peers. Each peer is really four processes. One controls the state of the peer and reacts on the events from the peer. Two are responsible for sending messages to the peer: one as a queue, and one blocks on the socket. Finally, a process receives messages on the socket and then sends them to the controller, blocking in the process.

PieceMgr: Keeps track of the current piece-state. It knows what pieces we have, what we are missing and what to request next. Peers will be using it for asking what to download next.

FS: Abstracts away the file system for the rest of the client. Is implemented as a communication process which peers ask for blocks to send.

Current State:

Currently, the client is pretty flaky. It is able to seed in a controlled lab-setting, but needs much work to be able to leech data from other clients. The TODO-list is fairly long and some of the things on it are pretty hard. But there are also many things which are fairly simple to fix. Feel free to grab anything and help out if it sounds interesting. I am deliberately keeping things simple and leaving doors open. It is my hope that even aspiring Haskell programmers might stand a chance at solving some of the things on the TODO list. I'll happily take any help I can get as in the long run, this is fairly hard to carry out as a single person. The code is on github in my haskell-torrent repository if this should indulge you.

Parsing Binary data in Erlang and Haskell

2009-12-14T07:15:00.000-08:00

The Bittorrent Wire protocol is a protocol used for communication between peers in a bittorrent cloud. The protocol is explicitly defined to balance between conserving bandwidth and being easy to parse. Hence, it is a binary protocol, but it is fairly easy to parse.

When I wrote etorrent as an experiment, I was faced with the problem of parsing this protocol. In Erlang the task is not hard however, since the language can pattern match on bit-patterns. I began by defining a set of constant values, each corresponding to a message type:

%% Packet types
-define(CHOKE, 0:8).
-define(UNCHOKE, 1:8).
-define(INTERESTED, 2:8).
-define(NOT_INTERESTED, 3:8).
-define(HAVE, 4:8).
-define(BITFIELD, 5:8).
-define(REQUEST, 6:8).
-define(PIECE, 7:8).
-define(CANCEL, 8:8).
-define(PORT, 9:8).

The designation 1:8 means that we need to represent the integer value of 1 in 8 bits of information (i.e., in a byte). With these values down, defining a decoder in Erlang is pretty straightforward:


%%--------------------------------------------------------------------
%% Function: recv_message(Message) -> keep_alive | choke | unchoke |
%%   interested | not_interested | {have, integer()} | ...
%% Description: Receive a message from a peer and decode it
%%--------------------------------------------------------------------
recv_message(Rate, Message) ->
    MSize = size(Message),
    Decoded =
    case Message of
        <<>> ->
            keep_alive;
        <<?CHOKE>> ->
            choke;
        <<?UNCHOKE>> ->
            unchoke;
        <<?INTERESTED>> ->
            interested;
        <<?NOT_INTERESTED>> ->
            not_interested;
        <<?HAVE, PieceNum:32/big>> ->
            {have, PieceNum};
        <<?BITFIELD, BitField/binary>> ->
            {bitfield, BitField};
        <<?REQUEST, Index:32/big, Begin:32/big, Len:32/big>> ->
            {request, Index, Begin, Len};
        <<?PIECE, Index:32/big, Begin:32/big, Data/binary>> ->
            {piece, Index, Begin, Data};
        <<?CANCEL, Index:32/big, Begin:32/big, Len:32/big>> ->
            {cancel, Index, Begin, Len};
        <<?PORT, Port:16/big>> ->
            {port, Port};
    end,
{Decoded, etorrent_rate:update(Rate, MSize), MSize}.

This is pretty straightforward idiomatic Erlang as one would write

it. We convert the numbers into tuples or atoms. The idea is that the atom or the first element of the tuple identifies the type of the message that was sent. Note that in idiomatic Erlang code, the process will crash if the pattern match fails. In that case, we have to handle that problem in another janitorial process.

I toyed with the idea of doing the same parsing in Haskell. Initially, my thought was that it would be rather hard to beat the Erlang code in size. Looking at the above code, it is almost the specification of the protocol and we can't get rid of the specification.

In Haskell, I started with the default construction of an algebraic datatype. It simply reflects the tuple/atom construction of Erlang:

type BitField = B.ByteString
type PieceNum = Integer
type PieceOffset = Integer
type PieceLength = Integer
data Message = KeepAlive
        | Choke
        | Unchoke
        | Interested
        | NotInterested
        | Have PieceNum
        | BitField BitField
        | Request PieceNum PieceOffset PieceLength
        | Piece PieceNum PieceOffset B.ByteString
        | Cancel PieceNum PieceOffset PieceLength
        | Port Integer
deriving (Eq, Show)

If it seems more verbose than the initial Erlang counterpart, then it fools you. In the above, we also encode the types of the messages - but this is the only place where we would have to designate the types in the whole program. Type reconstruction by inference will figure out the details for us.

I expect my data to be presented to me via lazy bytestrings (see Data.ByteString.Lazy). It also turns out that George Giorgidze built the HCodecs package. This package provides decoders for MIDI, Wave and SoundFont2 files. But the real gem of the package is the development of binary parsers for ByteStrings. This turns out to be exactly what we would like to process.

The parser is a monad. So we can use do-notation to decode the messages. Here is an example of decoding the PIECE-message:

7 -> do pn <- fromIntegral <$> getWord32be
   os <- fromIntegral <$> getWord32be
   c <- getRemainingLazyByteString         return $ Piece pn p c

This looks nice, but the <$> from Control.Applicative hints somewhat at where this will go. Note that we are not using the full power of the monad. In particular, we don't use earlier results from the monad to decide what to do next. Since there is no dependency chain, it means we can just utilize that every monad is also an applicative functor. In particular we can define

7 -> Piece    <$> gw32 <*> gw32 <*> gw32 <*> getRemainingLazyByteString
...
where gw32 = fromIntegral <$> getWord32be

using the applicative functor to solve the game. With this down, the rest of the parser is easy:

decodeMsg :: Parser Message
decodeMsg =
do m <- getWord8        case m of          0 -> return Choke
    1 -> return Unchoke
    2 -> return Interested
    3 -> return NotInterested
    4 -> Have     <$> gw32
    5 -> BitField <$> getRemainingLazyByteString
    6 -> Request  <$> gw32 <*> gw32 <*> gw32
    7 -> Piece    <$> gw32 <*> gw32 <*> getRemainingLazyByteString
    8 -> Cancel   <$> gw32 <*> gw32 <*> gw32
    9 -> Port     <$> (fromIntegral <$> getWord16be)
    _ -> fail "Incorrect message parse"
where gw32 = fromIntegral <$> getWord32be

And there you have it: A Haskell version which is more succinct than the Erlang version while being type safe in the process. The reason it works is due to the clever type class hierachy in Haskell: The parser is a monad and all monads are applicative functors. This lets us combine parsers cleverly into an effective decoder for wire protocol messages.

I do hope it is fairly efficient. Protocol decoding is probably going to be a hot place in the program.

Behaviour Driven Development is...

2009-10-05T06:10:00.000-07:00

So I spent the time necessary to look into this Behavior-driven-development idea. Summing it up in one sentence: "BDD is computable specifications". That is, you write a specification which is a program. This program takes as input a component and produces as output one of success or failure. A driver program then tries all the behavior-programs in succession and produces a report to the user or programmer.

This is a natural extension of test-driven-development, where one writes a computable test for each component in the software system before the component itself is written. The insight is that these tests are specification behaviors in the system so one can name them as such rather than as "tests".

The idea of building a model of the specification which can be computed is not new. There are strong similarities with Design by Contract (Meyer, 1986) and I am sure you can find older examples in the Lisp community with strong similarities. The BDD term is not defined rigorously, in tradition with most software development terms, sadly. Thus it means different things to different people. Some will say that DbC is BDD and some will say that it is not.

Main insight: If you have a specification written in English prose, you have no way to automatically check if the program lives up to the specification. You can only test it manually, which is a tedious, cumbersome process prone to failures. If the process is computable, we can get the machines to work for us and work out the details.

Getting the machine to understand the specification means it needs to be precisely specified, like a computer program. Our hope is that while the program specified may be complex, the specification itself is not. Thus we can specify the behavior of the program and have some assurance that the specification is correct. If the specifications are as hard to write as the main program it turns out to be turtles all the way down.

There are several ways we could attempt to write down a formal specification. We could, for instance, use Hoare logic - meaning we specify the behavior of the program in an assertion language different from the implementation language. One then tests the specification by verifying that the rules of HL is fulfilled.

Another path is to make the type system strong enough to capture formal logic and specify the program in the type system. To achieve this, one must have a type system much more expressive and powerful than what most mainstream programming languages provide. Testing the specification then amounts to a type check. Aside: Expressive type systems like the one found in Haskell or ML provides an approximation to this complete correctness. When we say that "type systems eliminate bugs in the program", we mean that the approximation caught a bug which would otherwise have slept into the program. Note that (static) type systems are a knob you can turn. The more expressive the system, the better an approximation to the specification. Turned to 11, the type system is the specification, but most programmers abhor the idea of programming at this level of precision. End of aside.

The BDD path is to define the specification in the host-language as a program itself. Usually this can be done by a compiler from a domain-specific language (describing behaviors) into the language in which the tested component is written. The advantage of this approach is that you don't need a separate tool chain but can reuse the existing one for running your tests. Testing the specification is done by running the spec-program against the implemented components and observing their behavior.

Thus, BDD is a runtime-oriented path to verifying the program specification. We check the program correctness by executing the test. I would imagine that we also design the behaviors such that they cover all paths of the component. This is fairly easily achieved by a coverage checker.

Personally, I see the BDD-idea as a poor-mans formal specification -- it is what you end up with if you just use the available tools rather than define a spec-language. You end up with exactly the same problems as most formal specifications any way: Explaining and understanding what they mean is hard. The problem can somewhat be alleviated by clever tricks where the actual code is hidden in a textual presentation which normal people would have a chance at understanding. This part of BDD circles around the problem of defining a good User Interface for the specification in question. This is the part of BDD I find the most interesting.

Also, the fine merits of BDD might be the first casualty to any deadline. Deadlines kill. Anything which can be placed into the scheme of "short-term good, long-term bad" and incurs technical debt is turned on as soon as the deadline approaches. Everything falls to a fast cost-benefit analysis. The problem here is that there are no measurable way to evaluate different software development methodologies so an equally good and faster analysis is thrown dice.

Things I love using PostgreSQL

2009-10-01T05:20:00.000-07:00

Let there be no doubt, that I like to use PostgreSQL as my main database of choice. I like my databases to use SQL, a declarative language, for my operations and queries. I guess the reason for this is my strong knowledge and experience with functional languages in general. The path from functional programming to SQL is rather short.

This is a list, in no particular order, why I love PostgreSQL. Note that many of these things are far better explained in the excellent documentation of PgSQL, so you can look up things there.

First, PgSQL takes types seriously. Data is typed from the outset and you need to convert data to match the given type. This means we rule out dates like '2009-02-31' by default. MySQL fails this blatantly for instance. Also, it allows us to import data into a typed language fairly easily as soon as we have a type mapping defined.
PgSQL has TOAST-storage. This includes several techniques like compression and out-of-line storage. What this means is that you can process data faster since disk I/O is what tend to kill database performance as soon as your data get beyond 'fits-in-memory'.
PgSQL can do partial indexes. I keep partial indexes on unprocessed data. Hence, even if the table contains billions of rows, I can quickly grab the unprocessed records and process them. I also keep some partial indexes around for performance.
PgSQL does bitmap index scans. This can combine several indexes into a bitmap telling the system what rows or pages to retrieve. Again, it lowers the amount of disk I/O needed to access data. Wonderful for complex queries.
PgSQL uses Multi-version concurrency control (MVCC). This means you can do backups of your database without having to worry too much about what happens while you take the backup. It also means you can be sure that your ACID compliance is done correctly without affecting the performance of individual queries.
You can disable autocommit by default in the psql client. No more accidentially destroying data.
Data Definitions (the DDL) are transaction safe! You can undo an ALTER TABLE statement if it goes wrong. It makes data manipulation into a blissful operation: Alter the table, CREATE VIEW to get the old view of the data back. COMMIT the transaction. You can do this on a live system, which is wonderful.
Need to add millions of rows? Use the COPY command (or its psql client \copy cousin). It is a lot faster than INSERT INTO for large amounts of data. My work desktop machine with an old SATA disk imports millions of (rather large) rows in a matter of minutes. This including raising a couple of indexes on the data.
Need to export data? CREATE TEMPORARY TABLE export ( ... ), fill it with a SELECT statement, fire up COPY. Done. I've built many reports directly in the guts of the psql prompt with a couple of VIEWs and this technique.
PgSQL is fast, especially for complex queries. This is especially true for recent PostgreSQL releases, where performance was the optimization target. And it paid off. Combine it with a query cache or a dedicated key-value store and you have a very stable, robust and fast platform which can scale to thousands of simultaneous users.
Built-in full-text-search. I've used this to answer search queries from users on the data with ease.

And I get to combine PgSQL with Ocaml, awk and R. Don't underestimate the data manipulation power of awk, it is extremely fast.

The gatekeeper role

2009-09-02T06:40:00.000-07:00

The single most important role in a software project, be it Open or closed source is the role of the gatekeeper. This person, or group of persons oversees the general progression and development of code in the project. Their responsibility is to read through the code of all commits and review them for correctness before they are let into the source code baseline upon which further development happens. There are many advantages in having a gatekeeper role in a software project. First and foremost, all code gets some review. Second, the gatekeeper can usually direct people to reuse existing code rather than write their own (At one time, the pine mail reader had several places in which file I/O operations happened for instance). Third, the gatekeeper can make sure that coding guidelines and structure is adhered to. If you are serious about the development, the gatekeeper must have the power of vetoing everything. It doesn't matter if it is the final release theres at stake. If the GK says no, it ain't gonna happen. This is important to ensure the quality in the project. Also, the GK should not have roles beyond the role of reviewing software. The best thing you can do for a software project is to get a model where people are willing to share their code patches with a mailing list so other people can chime in on the code. While the GK has the role of getting people to talk to each other and steer the project in general, getting other developers to work together is very important. I've seen to many projects with cage-isolation in the sense that each developer has their area of responsibility. It works fine until someone quits. Also, the GK hat could walk around among the most experienced developers. As a software vendor, you win if you can continue to improve the quality of your product and the skill of your creative software people. Constructive critique is a tremendous way to get this done. I don't give much for the idea of "Agile" development in general, but wether you adopt it or not, the GK role is crucial anyway. In some kind of perverted way, leading Open Source projects can't be wrong -- and you will find that almost all of them employ a de-facto gatekeeper somewhere.

Using Twelf to lift code quality in ExSML

2009-07-20T10:12:00.000-07:00

The ExSML project is a fork of Moscow ML which aims to replace the current MosML runtime with one based on LLVM. In Moscow ML the following things happen when you compile a file of SML source code: First the file is lexed and parsed into an abstract syntax tree. Then elaboration happens. In the elaboration phase we resolve, through type inference, the types of all expressions. We also resolve overloading such that all types are explicit from then on. Second the program is compiler by the frontend compiler into an Intermediate Representation (IR) called Lambda. This is an extended lambda calculus which is far simpler then core ML. At this step we also compile pattern matches into simple decision DAGs via a pattern match compiler by Peter Sestoft. The backend compiler then transforms lambda into bytecode which the mosml runtime reads and executes. We want to cut at the IR and produce LLVM code instead. However, there is a slight problem: LLVM is essentially a typed assembler whereas Lambda is untyped lambda calculus. To get around this, we have decided to use a typed variant of Lambda. This means we need a type system and we want the type system to be safe. Enter Twelf. The plan is to formalize the safety properties of the type system in Twelf. We are a far way from the goal at the moment as our Twelf-representation lacks many important things: reference operations, exceptions, reference state, recursive types, sum types, product types and polymorphism. But we hope to be able to add these to the representation with a little work. Knowing our language is type safe will give us some obvious advantages later on when we begin doing code transformations.

Arr, we be killin' the newspapers, mate

2009-05-13T05:57:00.000-07:00

Lately, we saw the emerging trend that newspapers are beginning to die. Good riddance. I've never bought a newspaper, I will never buy a newspaper, and I am pretty sure people younger than my age won't as well. The market is gone, so how are newspapers going to survive? Currently, they have placed their hope in advertising. As Steve Ballmer has said, it is all about advertising, advertising, advertising! This to the point where newspaper sites are infested to the brink with ugly colored flash behemoths in odd colors with nasty animations. Don't even get me started on what I want to do to the marketdroid who imagined that sound is a good idea, but let me divulge it includes a meeting with Mr. Garotte at the very least. I don't buy that advertising will be helping them anytime soon. First, I love to block Ads. I utterly despise ads, so I block them with AdBlock+ in Firefox. I don't want some idiotic marketdroid to invade and misuse my precious desktop space. Goodbye. This also has the nice side-effect that it undermines the Ad-industry and every industry basing their income system on Ads. Luckily, the majority of people can't block it, because they are too uneducated to install ad blocking software. Consequence: I can have my free stuff without paying for it or seeing Ads. But the majority will learn eventually, and that will be the slow and effective demise of Newspapers as we know them. We already face the first part of the "crisis" in Denmark as a major danish newspaper will have us pay for their service. This is a really good thing! I would probably like to pay others who use their time producing interesting material I can read about topics in my sphere of interest. But I also do not lament the death if everything I can get is the "Extended nobility package" where I get Wine and Restaurant reviews, news distilled to 99% irrelevance off of Reuters, and "Feminist" crap. Either newspapers will get a new networked revival or they will die. To survive, newspapers must produce something with a greater pastime value than perusing the /b/ board off 4chan (Might I add that the /b/ board is the sewage spill of the internet) -- or else irrelevancy will hit them where it hurts the most.

Static/Dynamic typing discussions are uninteresting

2009-05-09T16:03:00.000-07:00

People are talking about the RailsConf keynote "What killed Smalltalk?" by Robert Martin. You can watch the keynote talk at blip.tv. Of course, the Smalltalk guys weren't slow to answer the argument, which revolves around the fact that code easily becomes cluttered in Smalltalk programs. The arch-angel that will save this problem with Ruby is, of course, unveiled to be "Test Driven Development" much to the rejoice of the Audience.

Martins presentation is flawless in the sense that he does a really good job at capturing the audience. Another interesting point is that he has no slides, just a stack of paper cards on which the key points of the talk is written. In Academia, this would not have worked for most talks I note. Sooner or later you'll at least need a blackboard to draw up and explain a formulae or similar.

A side argument however is that the dynamically typed languages won over the statically typed languages. It is driven by the observation that Java now has reflection, which must mean it is dynamically typed, right? Unfortunately, this viewpoint is misguided in the sense it lacks delicate detail about the situation at hand. This blog postseeks to remedy the omission.

Static vs. Dynamic typing is uninteresting

Taking the argument as being static versus dynamic typing alone is a moot point. Here is why: suppose we want to embed a Java program in Ruby. This can easily be done, if we choose to ignore the types and strip them out. In fact, any statically typed language can be embedded in the dynamic world by stripping the types away. After all, assembly language is untyped, so compilers will at some point have to eschew the typing information for good in their transformation.

But any dynamically typed language can also trivially be embedded in a language with static type discipline. We invent a new type, lets call it T and then proceed to give everything type T. This is what happens inside the Ruby interpreter written in C. Of course we must then have a way to discriminate the different values of T but this is exactly what low-level operations will do in a dynamically typed language anyway.

Thus we have a way to convert back and forth between the static and dynamic world, so why do we not regard them as equal? We know they are not equal, but in what kind of sense are they not equal? If we convert from Java to Ruby and then back to the static world, everything will have the magic type T. We have lost the Java type information in the process. But this merely states that the conversion is not isomorphic.

If one thinks about it, there is little to be gained by studying the trivial world of dynamic typing: everything would look the same once it has been converted into the dynamic world. If we look at the static world, we obtain a different picture.

Meta-theoretic properties, baby!

Since Ruby would be trivially typable in the statically typed world, the whole debate about static typing versus dynamic typing falls apart. It is uninteresting because the level at which we communicate is too low. What really matters are the properties of the type systems: what kind of guarantee do we have from the type system weighing in favor of complex type systems -- and the hassle of maintaining well-typed programs weighing in favor of trivial type systems.

In Ruby, or Smalltalk, the contents of a value (an object) can be changed without having to retype big parts of the program. This is not always true in Java. It holds when there is a certain subtyping relationship between the objects in question, but it can't be done in general, since there is no "duck typing" available. Reflection in Java adds the magic type T so to speak so we can embed any type in a T and we can project any type out of a T. The latter might incur a runtime-error when done however; this is no different from Ruby where everything might potentially incur runtime errors.

The static type system on the other hand tends to guarantee varying levels of type safety. If the program is well typed (read: passes the type checker), then there will be no type errors at runtime. Since there will be no errors at runtime, we can just strip away type discrimination at runtime as well -- yielding great speedup compared to dynamically typed languages.

The difference is that Java, even with the addition of reflection, still have better meta-theoretic properties than Ruby, though we have added a way to poison the type system safety. This is not at all new to most static type systems out there, which allows coercing types unsafely if you really know what you are doing.

Java is also a fairly simple language from a type-complexity perspective. ML is much further up the scale. And Haskell is even further up, with many more complex concepts in the type system. Most theorem provers rely on even more complex type systems to get their work done. In fact they have type system; so powerful they can, in principle, encode correctness specifications of the program. You do not really need unit tests at that level. But it becomes increasingly harder to write correct programs, so most proponents of static typing settles on something further down the scale.

Also, most advanced languages will infer (deduce) types automatically. For ML it is customary to just specify types at the API-level and omit typing details elsewhere. This brings some of the ease from dynamic typing back into static typing.

Wrapping up

One can't possibly say that "dynamic typing won" when the world is much more complex. In reality one must ask: "What static type system won?"; which is not trivially answerable and subject to individual level of expertise, viewpoint, ideology, religion and what not.

What is clear though should be that the type systems of Java with reflection and Ruby are far from equal. Neither are Java or Haskell for instance. Or Haskell and Coq. Or...

Based on that, I think the view Mr. Martin puts forth is a bit too quick and simplified. I also hope we can move beyond the simple dynamic/static debate which is hardly interesting.

And finally the snide remark: What is interesting is the viewpoint that type systems are chastity belts or impose Bondage & Discipline upon programmers when I have just shown, by trivial conversion, how to embed dynamic features into any statically typed language. You just got the skeleton key to the chastity belt, should you need it!

Moving bits in a pirated world for fun and profit

2009-04-01T05:47:00.000-07:00

The premise

As soon as a movie/episode is out in the wild on the internet it is going to be spread like a wildfire. To circumvent this, the movie/series industry have to change their stance towards copyright protection. The best they can hope for is to slow down the spreading, because it is technically impossible to stop.

The right stance is that of convenience. Currently it is more convenient to download from the internet than it is to buy the movie. The internet download is almost instantaneous, the buy can take days to finish. For a series on a channel the problem is that the episodes will air at specific days of the week, whereas the episode on the internet can be viewed at your discretion when you want.

Convenience is a powerful and important tool to harness if you want to battle piracy. Most people know there will be no next episode if they don't pay for it in the first place. Most people do want to pay a fair price for a series.

If the MPAA did harness the convenience, they would have an increased market quickly. I hypothesize that episodes pirated from the internet is done also by legitimate buyers who just was not home the day the episode happened to be aired.

The idea

Occams Razor applied to the problem. You have no need for a new wild intricate system. You just need some basic, conservative tricks. An episode will be distributed by bittorrent in encrypted form before the airing. This means that people on a measly 1 megabit line can download around 5-6 HD quality episodes per week. If the distribution happens one week in advance, there is ample time to get the data out.

Next, on the airing you distribute the key, unlock the encryption and proceed to view the episode. At the same time an unencrypted file is produced, so the DRM is thrown out with the bathwater. This step is important guys! If the data is laden with DRM it has less value compared to the pirated one.

A season for a series costs $5 at maximum. The customer pays these money for the ease of getting things delivered to his doorstep each week, and to pay in advance for the production. In fact, production starts when the donation box has been filled to a certain point where it is profitable to start a new season, rather than being a gamble.

Why nobody has done this

Hypothesis: MPAA and RIAA are not desparate, are not operating at a loss and will continue to bully around. In general, money is still being made or shops would have closed up long ago. Hence, they have no intention in building a smarter distribution scheme because their current scheme works. After all they have TV channels and Cinemas as their primary distribution form and it works fine.

So then, why go after the pirates? Greed? No, they fear somebody creates a distribution system like the one above and takes them out of business. In one year the smarter distribution system could mean the end for their current structure which they are milking for money as a cash cow. They don't want disruptive technology to enter the marketplace at this moment.

The solution is to create a simple equation "internet = piracy" and bang that into the heads of people. This is their only hope as it will build a barrier making them able to cash in for a longer time before their structure is eradicated.

An update on the Moscow ML for LLVM

2009-03-29T07:21:00.000-07:00

The Moscow ML LLVM project is having a blast these days. First, we got autotools into the project, so everything is now built from autotools. Then we eliminated a lot of magic in the code base. Importantly, you can now reorder C functions without fear of the run-time breaking down and getting out of sync with the compiler.

We killed the threaded code interpreter. It is presumably fast, but it also hampers our further development with LLVM, so it had to go. The code base ended up much cleaner.

Then we coded up a simple opcode tracer that can write out the sequence of opcodes as they are executing. If you can simplify an error to the point where a trace can be used, then it tends to be easy to identify the problem with the tracer. It did uncover a couple of bugs.

The final nail in the coffin is the regression framework. We imported the regression framework from mlton and proceeded to add the tests that makes sense for mosml. We have 2 failing tests out of 88 at the moment. The original mosml passes all 88 and our version fails in 2 of those. Both these are in I/O, so it is narrowed down to a few commits at the moment. It is wickedly cool to have a working regression framework again.

We also killed the C preprocessor on all Standard ML files. Autoconf gives us what we need, so it is fairly easy to generate the correct files.

Looking forward

In the future, we intend to clean up the run-time some more and systematically begin getting more test cases to pass correctly, and construct the correct install-targets. We also need to get the standard ml front-end code into the game. Then we add 2003 Basis support and begin simplifying the back-end such that we can add LLVM on top if it. Another nail is the eradication of all C-compiler warnings and a simplification of the opcodes.

Graphviz talk slides

2009-03-28T05:51:00.001-07:00

So I did a small talk (in danish) on what Graphviz can do for you in the local LUG. But I have been a slacker and did not put up the slides yet. This remedies it: Graphviz talk slides

LLVM Update

2009-03-04T15:00:00.000-08:00

People tracking along will know that I am in the process of writing an LLVM backend for Moscow ML. There are several ways in which one can do this, so one has to be decided upon and tried out. It is however clear we need a way to manipulate and output LLVMs IR, so I set upon writing an set of bindings.

These bindings are not using an FFI to call into the C++ LLVM code. Rather they produce the IR assembly from an internal SML-like data structure. This approach has the disadvantage that it is more work to maintain. On the other hand, the OCaml bindings passes around llvalues all over the place so very few bugs will be captured at compile time (we could do oh so much better had we had dependent types).

I have written LLVM as a datatype in SML and then written about 40 percent of a type checker for it. The process is very simple as soon as one has converted LLVM rules into SML datatypes. Here is a part of the Type module

datatype t =
    T_Integer of int
  | T_Real of float_ty
  | T_Fun of {return: t, params: t list}
  | T_Struct of {elements: t list, packed: bool}
  | T_Array of {ty: t, length: int}
  | T_Pointer of t
  | T_Vector of {ty: t, length: int}
  | T_Opaque
  | T_Void
  | T_Label
  | T_Top

which is a straightforward adaptation of the Language Reference of LLVM. I could simplify it more, but at the moment there is little need for that.

Type checking is carried out by a set of combinators. They probably form a monad (Haskell guys can relate this to a variant of the Either monad with a Writer on it as well. It should be straightforward to write it down as one or use a transformer stack to achieve the same. I have not given it much thought though).

The checking basis is the datatype

datatype t_check = Ok | Wrong of string list

Immediately, a helper is introduced

fun type_fail str = Wrong [str]

And a function for running a checker

fun run checker_fun ty =
 case checker_fun ty of
   Ok => ()
 | Wrong errors =>
     <<Print out type checking errors>>

Note that run will have type (ty -> t_check) -> ty -> unit. The question is then how to produce type checkers. This is done with combinators but of course:

(* Logical or for types, consider monadizing *)
fun or checker1 checker2 ty =
case checker1 ty of
 Ok => Ok
| Wrong err1 => case checker2 ty of
         Ok => Ok
       | Wrong err2 => Wrong (List.concat [err1, err2])

The 'or' checker tries the first checker and if it fail it tries the second, picking up any errors on the way. It is also easy to assert that a given type must be the base type of a vector type:

fun vectorized checker1 vty =
case vty of
 T_Vector {ty, ...} => checker1 ty
| _ => type_fail "Checked type is not a vector type"

Perhaps one could be giving a better error message here by capturing the eventual error output from checker1, but this has not been done yet.

Primitive checks are just doint what they are supposed to do. The assertion for an integer looks like the following:

fun assert_int ty =
case ty of
 T_Integer _ => Ok
| _ => type_fail "Type is not of integer type."

Usage

An addition in LLVM is either an integer, a float or a vector of these. Aha:

val assert_int_float = or assert_int assert_float
val assert_add = or assert_int_float (vectorized assert_int_float)

Hopefully this shows the succinctness of the approach.

EDIT: Layout was bad. Fixed

Combinator parsing, part 3

2009-02-06T10:02:00.000-08:00

In the 3rd installment of combinator parsing, we will write the actual parser and use it for parsing our original problem from part 1. Parsers have a specific type, namely

type ('a, 'b) parser = 'a -> 'b * 'a

so a parser takes some type, 'a, breaks off part of the stream returning 'b and the rest of the stream. Our parser will have type (token list, exp) parser, as it will process a token list and produce an exp. We begin by defining two exceptions

exception Punt
exception ParserError

These are used a bit differently. The Punt exception is used whenever the parser wants to backtrack and attempt another parse. ParserError is going to be used when the parser fails to parse the input stream. Wrapping up the parser system is a function we use for parsing stuff. It handles the task of checking there are no excess data when the parse finishes. It also handles the coercion of top-level punts into general parser errors.

fun parse_list parser stream =
(case parser stream of
  (result, []) => result
| _ => raise ParserError) handle Punt => raise ParserError

Let us now build a parser for symbols:

fun symbol x ph =
case ph of
  (Symb y :: rest) => if x = y then (x, rest) else raise Punt
| _ => raise Punt

given a symbol, x, and a phrase, ph, to attempt to parse, we test if the head of the stream is the desired symbol. If yes, we return the pair of the symbol and the rest of the phrase. If no, we punt; the parsing failed here so we backtrack to try something else. It is easy to build more simple parsers like the one above. Here are numbers and identifiers:

fun number ph =
case ph of
  (Number n :: rest) => (n, rest)
| _ => raise Punt

fun identifier ph =
case ph of
  (Id id :: rest) => (id, rest)
| _ => raise Punt

But what makes this kind of parser special are the parser combinators. A parser combinator is a function which takes several parsers (of the ('a, 'b) parser type) and combines them into new parsers. We declare a couple of new operators and fill in their definitions later

infix 0 |||
infix 3 ---
infix 5 >>>

Normally, I am not that keen on declaring new operators, but when there is a certain sense of closure among the operators and they work on a specific domain, it might be easier to read code with operators. An aside is that it not always helps to have operators infix. For instance, 3 + 4 + 7 + 13 in ML can be written more succinctly in Lisp-systems as (+ 3 4 7 13). Nor do I find the operator noise of most Haskell programs very appealing. So one must use great care before just blindly declaring another operator. It should be warranted and justified. One justification is when you have a set of operators with closure, operating on the same domain. Binary arithmetic modulo N for instance. Or combinators for parsers. Back to our combinators. The first one, ||| is the 'or'-combinator. ph1 ||| ph2 will first try to parse with ph1. Upon success of ph1, then that is the return of the whole parse. Upon fail, it tries ph2. Observant readers will recognize the short-circuiting nature. The code is using the backtracking to achieve the described informal semantics:

fun ph1 ||| ph2 =
(fn stream =>
ph1 stream handle Punt => ph2 stream)

Similarly, there is --- which is the equivalent of a logical 'and'. The parser ph1 --- ph2 first parses with ph1 and then with ph2 on the stream remaining from ph1. It returns the pair of the result. Perhaps the code explains this better than I do:

fun ph1 --- ph2 =
(fn stream =>
let
  val (a, stream') = ph1 stream
  val (b, stream'') = ph2 stream'
in
  ((a, b), stream'')
end)

Next up is >>> which is the application operator. If one writes ph >>> f, then ph is used to parse the stream into (x, rest) but the final result will be (f x, rest). The code is straightforward:

fun ph >>> f = (fn stream =>
    let val (x, rest) = ph stream
    in (f x, rest) end)

The >>> operator lets us shove any translating post-processor into the parser at any point, which will become handy. With these down, it is easy to define some derived parsers. Here is one that lets you surround any parse with parenthesis:

fun parens ph = ((symbol #"(") --- ph --- (symbol #")"))
   (* Cut the relevant part *)
   >>> (fn ((_, x), _) => x)

Or even better, generalize that one:

fun surround left right ph = ((symbol left) --- ph --- (symbol right))
         (* Cut the relevant part *)
         >>> (fn ((_, x), _) => x)

val parens = surround #"(" #")"

One might look at the function that cuts out the relevant part and deem that it is an ugly function. It is, indeed. But since we are writing a combinator-parser, we can do a lot better than that. We can simply define functions to get rid of it:

infix 3 --$
infix 3 $--
fun ph1 --$ ph2 = (ph1 --- ph2) >>> (fn (x, _) => x)
fun ph1 $-- ph2 = (ph1 --- ph2) >>> (fn (_, y) => y)

fun surround left right ph = (symbol left) $-- ph --$ (symbol right)

fun parens token = surround #"(" #")" token

The functions $-- and --$ can now be used to remove parts of the parse-result without having to use a pattern deconstruction all over the place. It has been confined to the functions $--,--$ once and for all. The next obvious step is to use our combinator parser for parsing the small expression language from part one. First, we handle the two primitive, or atomic, rules:

fun exp_number token = (number >>> (fn n => Const n)) token
fun exp_id token    = (identifier >>> (fn id => Var id)) token

These functions are straightforward: If we parse a number, we just have to add the right constructor onto the result. The same is true for identifiers. There are several ways to parse the rest of the expression language, but one of the more clever ways is to use a function I first saw Lawrence C. Paulson do. Here is the function, which may look a bit daunting at first:

fun infixes (ph, prec_of, apply) =
let
  fun over k toks = next k (ph toks)
  and next k (x, Symb a :: rest) =
  if prec_of a <>>> apply a x) rest)
    | next k (x, toks) = (x, toks)
in
  over 0
end

The function infixes takes a primitive expression parser, ph, a precedence discriminator function, prec_of and an applicator function apply. It then proceeds to produce a parser with the given precedence designations. Basically, there are two functions mutually defined, over and next. The over function parses expressions over a given precedence. The next function operates the next symbol token we see. So, suppose we got a symbol. Then we look up it precedence. If the precedence is lower than the current level we are operating on, we simply return it back to the lower level. If it is higher, we start a recursive run for the higher level via a call to over -- and we arrange it such that when it returns, it applies the 'a' symbol with the return value and 'x' (it is nice to see currying at work). Finally, we proceed towards to next token at current level via a recursive call to next. In our case, the precedence table is easily given:

fun precOf x =
case x of
  #"+" => 1
| #"-" => 1
| #"*" => 2
| _ => ~1

and same for the apply table:

fun apply a x y =
case a of
  #"+" => Add (x, y)
| #"-" => Sub (x, y)
| #"*" => Mul (x, y)
| _ => raise InternalError

To use our infixes function, we build a mutual definition of primitive expressions, parenthesis structure and a call to infixes:

fun prim_exp toks =
let fun p_exp toks = parens exp_parser toks
in
  (exp_number ||| exp_id ||| p_exp) toks
end
and exp_parser toks = infixes (prim_exp, precOf, apply) toks

and exp_parser is our desired expression parser. A simple test:

fun p stream =
let
  val lexed = lexer stream
in
  parse_list exp_parser lexed
end

val testlex_str = "x + 33 * (y - 5)" : string
val testparser = p testlex_str
val out = eval_exp test_env testparser

returns the expected value, so we have some indication that it may work as desired:

...
val p = fn : string -> exp
val testparser = Add (Var "x",Mul (Const #,Sub #)) : exp
val out = 68 : int

There are still several things we can do with the parser combinators however, and there are some things left to discuss. There is a big disadvantage to having a parser that backtracks by default. At each possible junction it must store all of its state since it might return to that point later on when backtracking. Of course, this can be used for finding all possible parses with some alteration of the parser, but mostly, it is a bad idea. The Haskell Parsec library takes a more clever route. It has no backtracking by default and the ||| operator only tries the second parser if the first one failed to consume any input. Thus it can avoid keeping state around for backtracking. Also, combinator-parsers have certain limitations. If your grammar has left recursion, you will find yourself at an infinite loop very quickly. For anything that needs speed and efficiency one is probably better off with a parser generator for the LR family. But for smaller problems where speed is not paramount, combinator parsers tend to be a fine choice.

Combinator parsing, part 2 (Lexing)

2009-01-31T09:18:00.000-08:00

In the first part, we set up the scene for combinator parsing. We introduced a small toy language and an interpreter for it. The thing we left out was the meat of the problem. Namely how to parse an expression string into a Standard ML datatype value. We will not be ready for this entirely yet, however. Most parsing endeavours begin with the concept of lexical analysis or lexing, in which we break up a stream of characters into a stream of tokens. It can best be described by grouping characters that belong together into a single token. There exist lexer generators able to produce quite fast lexers automatically. These usually work by identifying tokens via regular expressions and then compiling these regular expressions into a state machine (DFA). The best of them do not even interpret this DFA but compile the DFA into code which when executed is the DFA is question. For a particularly cool version of this, see Shriram Krishnamurthi [1] For our purpose here it will be overkill to use a lexer generator. So we will resort to the much simpler solution of just hand-write it. But we will be clever enough to write it in a way which is pretty fast. The main disadvantage compared to most of the lever generators is that they work on the input stream in chunks. In other words they keep a small amount of work in memory at all times. Our solution will just read everything in. Haskell fares better here, as the default is ts lazy-read streams. Anyway, we begin by defining the basics:

exception Internal_Error
datatype token = Symb of char | Id of string | Number of int
val symbols = String.explode "+-*()"

The exception is for catching internal errors in the lexer. I tend to have such an exception in each module and raise it whenever something is non-expected. This way I eliminate an unexhaustive pattern match and make it clear to the reader what the intention of the code was. The datatype defines what tokens we have in our language. There are symbols, identifiers and numbers. Finally, we declare a character list of symbols our language has.

fun numTok ss =
 case Int.fromString (Substring.string ss) of
   NONE => raise Internal_Error
 | SOME i => Number i

fun idTok ss = Id (Substring.string ss)

The numTok function handles a number. It expects a substring and then converts it to an integer. The pre-condition of this function is that there is something to convert at all, or we face an internal error. The idTok expects the substring to be an identifier and converting that to a string is trivial. Substrings warrants an explanation. In Standard ML, strings are immutable. Strings cannot be modified once they have been created. In fact, strings are vectors of chars. And vectors are immutable. A substring is then 3 values (s, i, n) where s is the underlying substring, i is the index into it and n is the length. So substrings are slices of strings. Our main lexer function uses substrings to maintain a window over the original string. While it processes the string, this window is then systematically moved forward and the token stream is generated. Here is the main lexer function:

fun scan (toks, ss) =
 case Substring.getc ss of
   NONE => List.rev toks
 | SOME (c, r) =>
   if List.exists (fn x => x = c) symbols
   then (* Symbol *)
     scan (Symb c::toks, r)
   else if Char.isAlpha c
   then (* Identifier *)
     let
       val (cs, rest) = Substring.splitl Char.isAlpha ss
       val tok = idTok cs
     in
       scan (tok :: toks, rest)
     end
   else if Char.isDigit c
   then (* Number *)
     let
       val (cs, rest) = Substring.splitl Char.isDigit ss
       val tok = numTok cs
     in
       scan (tok :: toks, rest)
     end
   else (* Skip whitespace, etc *)
     scan (toks, Substring.dropl (not o Char.isGraph) ss)

fun lexer str =
 scan ([], Substring.full str)

The beast is easily explained: If we call lexer on a string, the string is made into a substring, and scan is called with an empty token list. The scan function carries out the hard work. If there are no more substring chars, then the tokens are just reversed and we are done. It might look odd to build the token list in reverse but SML mandates that list can only be built from the front, so this is the typical way to handle the last part of a tail-calling function. If there is a character, then we discriminate the type of character. For each possible discrimination, we break off some of the string, create the right token type, and proceed with the rest of the string. Finally, we have a skip of white-space in case nothing else matches. As a rather crude test

val testlex_str = "x + 33 * (y - 5)"
val testlex_toks = lexer testlex_str

results in

exception Internal_Error
datatype token = Id of string | Number of int | Symb of char
val symbols = [#"+",#"-",#"*",#"(",#")"] : char list
val numTok = fn : substring -> token
val idTok = fn : substring -> token
val scan = fn : token list * substring -> token list
val lexer = fn : string -> token list
val testlex_str = "x + 33 * (y - 5)" : string
val testlex_toks =
[Id "x",Symb #"+",Number 33,Symb #"*",Symb #"(",Id "y",Symb #"-",Number 5,
Symb #")"] : token list

Which looks right. In the next part we will finish this up and write the combinator-parser for the token list into the abstract syntax tree we aim for. [1] Swine Before Perl

Ripping the backend from Moscow ML

2009-01-20T04:12:00.000-08:00

Suppose you have two functions:

(* Type: int * int -> int *)
fun f (x,y) = x + y

(* Type: int -> int -> int *)
fun g x y = x + y

These functions do the same thing, namely add two numbers 'x' and 'y'. They have different types however, and they are called in different ways. 'f' is the usual way in most languages. We take a pair, and return the result. 'g' is curried: it is a function that takes an 'x' and then produces a new function taking a 'y'. The produced function returns the result when given an 'y'. Interestingly, 'g' is more powerful than 'f'. If we write

(* Type: int -> int *)
g 3

we get a so called partial application of 'g'. This means we only supply the first parameter to the function. It allows us to optmize with respect to the first parameter and it is a good way to define very general functions and then specialize them into what we need later on. Here is an example:

(* Type: int -> int -> int *)
fun h x =
 let val z = expensive_operation x
 in (fn y => y + z)
 end

We have defined a function which carries out some expensive operation between getting its first and second parameter. An application, 'let val foo = h 37' say, will only compute the expensive operation once and each time we use 'foo' we reap the benefits. Moscow ML is a quasi-implementation of the Standard ML programming language. It does not follow the standard completely, but it follows it enough to be usable and to let simple code flow between SML implementations without too much problems. What does not flow that easily is the module system which is treated somewhat differently between Moscow ML and e.g. SML/NJ or MLton. Moscow ML works by taking SML source code through a lexer and a parser into an abstract syntax tree. Then the types of all expressions are inferred in an 'elaboration' phase. Next, modules are stripped and pattern matches are simplified via a pattern match compiler. Now, the code is translated into an internal languauge, Lambda. Lambda is a lambda calculus + stuff. Finally, Lambda is translated into bytecode of a virtual machine. The Moscow ML runtime is written in C and can interpret the bytecode output from the compiler. The engine is neat, but it suffers somewhat from age. Several speedups are readily possible on this machine with relative little effort. The naive implementation of the 'g' function from before follows the semantics directly. Take the 'x', produce the intermediate function as a closure and then invoke the closure on 'y'. It is inefficient to produce the closure however, and we don't always have to! in 'g x y' we know all the arguments, so we can avoid building the intermediate function. Moscow ML relies on a derivative of the ZINC abstract machine as its VM. ZINC was an experiment by Xavier Leroy for writing a virtual machine for the Caml language. It is interesting because curried arguments do not build intermediate closures unless they have to. In other words, using the curried, more powerful, variant of a function has no extra cost in this machine. I want to compile Moscow ML into LLVM bytecode. The idea is to compile from Lambda down to LLVM, which is not that different to what the Ocaml compiler is currently doing. In the process, I would like carry over the ZINC machines good handling of curried arguments. I am taking some preliminary steps to get this done, but don't expect anything wild the next couple of months. This takes a lot of time getting right since I am writing it as a hobby project for the time being. I might be posting some updates later when the project has progressed furhter. References -- if you know any reading which might be interesting, do not hesitate to write me: The ZINC Experiment How to make a fast curry (I love Simon Peyton Jones paper names) The Mosml-llvm code lives here

Combinator parsing, part 1 (Setup)

2009-01-09T07:23:00.000-08:00

In this series of posts, we want to parse expressions. In order to make it worthwhile and fun, we will begin by placing some constraints on this.

We will be using the language Standard ML for describing the approach. Though note that any functional language of a certain power can do this. Converting it to Ocaml, Haskell, Erlang or a lisp should be pretty straightforward once you get the hang of the idea. In some sense, Standard ML is the simplest of the (statically typed) functional languages in that it has almost no fancy tricks you can pull.
We will not be using regular expressions. Not that regular expressions are bad, but I want to show that this can be done easily without the use of RE's. The goal here is to show people that there are different approaches to parsing data than just throwing a regular expression at the problem.

The language we will study has the following simple syntax structure, given in BNF form:

  e ::= x | n | e1 + e2 | e1 - e2 | e1 * e2

The 'x' is a variable. Its value can range over integers (we won't be concerned with the actual range of these integers, altough it is interesting to muse over). The 'n' is some integer constant. The term 'e1 + e2' is an addition of two numbers. Likewise for subtraction and multiplication. Here is a typical expression:

  x + 3 * (y - 5)

Note that the parenthesis are not given in the syntax. We just assume their existence and they work as you would expect: grouping together terms to force evaluation order.

Writing down the syntax in Standard ML is straightforward:

datatype exp = Var of string | Const of int | Add of exp * exp
           | Sub of exp * exp | Mul of exp * exp

Hopefully it is clear what is going on here. We have translated the syntax into an ML datatype. To discriminate each construct, we have added constructors 'Var','Const','Add','Sub', and 'Mul'.

If we can somehow bring strings of the form 'x + 3 * (y - 5)' into this datatype (correctly!) -- and we know what 'x' and 'y' is, then we are able to evaluate the expression. Here is how:

fun eval_exp env exp =
  case exp of
    Var x        => env x
  | Const n      => n
  | Add (e1, e2) => (eval_exp env e1) + (eval_exp env e2)
  | Sub (e1, e2) => (eval_exp env e1) - (eval_exp env e2)
  | Mul (e1, e2) => (eval_exp env e1) * (eval_exp env e2)

So we destruct the form of 'exp'. If it is a 'Var', we look up the variable in the environment 'env', which we will define shortly. If it is a 'Const', we just return the integer value. Finally, if it is a binary operator, we proceed to evaluate the two sub-expressions and apply the right ML-operator to it.

We still need to give a meaning to the environment 'env'. We would like to represent it as a map from strings to integers (ie, a function of type 'string -> int'), as our variables are strings. This is straightforward in Standard ML fortunately. Suppose we want to represent the mapping 'x' maps to 2 and 'y' maps to 7:

exception env_notfound of string
fun test_env v =
  case v of
    "x" => 2
  | "y" => 7
  | _   => raise (env_notfound v)

We define an exception for the case where we don't know about the variable and raise it if the variable is unknown. In Standard ML '_' stands as a wild-card for "any other unnamed value."

Let us round up by playing with what we have. If we manually parse the term 'x + 3 * (y - 5)' it becomes:

val term = Add (Var "x", Mul (Const 3, Sub (Var "y", Const 5)))

So if we try to run the term with our environment from above, we expect the result to be '2 + 3 * (7 - 5) = 2 + 3 * 2 = 2 + 6 = 8'. Here is what our Standard ML system says:

- eval_exp test_env term;
val it = 8 : int

In the next part, we will write the parser that allows us to automate the parsing of the term into the datatype of 'val term'

Common Erlang misconceptions

2009-01-06T02:10:00.000-08:00

There is a common saying that Erlangs I/O layer is slow. Bullshit. The etorrent program can easily sustain 70 megabit with less than 5% of CPU usage on my old machines. The reason is that etorrent is shuffling 16k binary blocks around mostly. But that means you have a pointer to each 16k block and you are only a writev(2) call away from the disk. This means I/O is not itself a problem. The problem that people often hit is Erlangs string handling. In Erlang a string can either by represented as an immutable array of 8-bit characters, called a binary; or it can be represented as a list of integers (ie, a linked list of integers). The latter is mutable in the sense that you can generate new integers and update the linked list from the front only. Whenever you mutate the list of integers, garbage is generated. Allocation will happen and this directly translates to more garbage collection pressure later on. Had you had destructible arrays in Erlang it would have been very easy to circumvent the worst performance problems, but you will have to do with a limited zoo of types. In better languages, like Ocaml, Standard ML or Haskell, your type zoo is much richer here. You can choose between several immutable and mutable variants so the leverage is much greater. First trick: Erlang has the concept of an IO list. These are lists of binary/string chunks. They are fast because they lend themselves to a writev(2) in the bottom of the system. Thus you don't have to concatenate strings in the Erlang language but you can hand a quasi-concatenated list to the VM and let C do the heavy-lifting for you. Second trick: Mutating data as strings is slow. But if you have a abstract tree of tuples then it can be manipulated fast. If you think about the command [Bin | IOList] where we add a Binary to the front of an IOList, you'll know it happens in O(1) (constant) time. If we build a tuple {atom, D1, D2, ...}, we can build it in constant time. So the trick is to maintain your data in a non-string form for as long as possible and then only change it to a string at the very last point in time. Third trick: Correct data structure. Ropes. Finger Trees. M-way trees. Don't brute force yourself over a string. Process the structure by pattern matching in a clever way so you minimize the amount of change needed. A good tree will have around logarithmic change whereas a list will have linear change. This leads to the next point: allocation. Another crap problem in Erlang is that you have few (traditional) ways to minimize allocation. Any kind of operation will allocate data if you are not wary of it. Hence you should try to build programs that do not gloss over data and allocate all the time. Mapping of lists via list comprehensions is a good example. It is easy to understand but it will build a new list and garbage collection will cost you. If you can do multiple things in one list comprehension, you win traversals and allocations. Whenever I hear about "Slow string processing" in Erlang I immediately think: "Another Ruby programmer trying to cram his language into Erlang". If you hit slowness the trick in Erlang is to redefine the problem! Don't try to string process yourself into oblivion. If the sole thing your problem concerns is string-processing, go use perl. Please. Or be clever and use Ocaml. Pre-process the data in other languages and make them into erlang terms which can be read fast by erlang. Erlangs power is the concurrency at which it is really good. There were no reason for giving it fast string processing. Also, don't get bitten by the mnesia bug, please. It is almost always the case that mnesia and ETS are the wrong way to go. I got bitten by it multiple times in etorrent and now I am contemplating ripping all of it out again. Plain old data structures baby! There are some nasty caveats to mnesia and ETS and they are not related to the size limit of the database. For mnesia, be aware that a failed transaction will be re-run! Now take 100 transactions tripping over each other. They will never finish. Etorrent did that when peers should update their state. Instant snail-speed application. Mnesia is crap at doing joins. Just forget it. ETS is also problematic: Any store or get from ETS means a data copy. Don't do as etorrent and add large rows (128k+) to ETS. Your app will come to a grinding halt. Don't message big data structures around. Any message incurs a copy (in the default VM). If you need to work with a big data structure, shove it into a process and then send the Pid of that process around or register him globally. You can think of a Pid as "Passing a pointer around" in this case. And finally: Measure measure measure! Be scientific about your performance problems. You need to know exactly what causes it before jumping to conclusions. And don't worry too much about being parallel at the beginning. You can always split things up in finer granularity later.

A little set of tools

2009-01-05T14:48:00.001-08:00

This is a little set of tools that I like to use now and then. I name them by their Ubuntu/Debian package names although I think one can find them easily for any package system out there. apg - The "automated password generator". It generates automated pronounceable passwords. It takes a lot of options as to how the passwords should look and what they must contain etc. It is a handy tool for generating passwords which are hard to guess but still easy to memorize. mp3gain - Mastered music today has different loudness levels. You will search for your volume button all the time because some tracks are much louder than others. This tool can analyze mp3 files and hint about the loudness level so programs can adjust accordingly. Or it can adjust the volume of the mp3 file in a lossless way (using a nice property of the MDCT in mp3s). password-gorilla - A Password safe application written on top of "pwsafe" in TCL. Main advantage of using this is that there are Windows and OSX programs able to read the format as well. stow - Manager for the hell that is /usr/local. You create /usr/local/stow and proceed to compile programs with "--prefix=/usr/local" but run "make install prefix=/usr/local/stow/foo-1.2.3". Now you can cd into /usr/local/stow and call the "stow" command on "foo-1.2.3". This creates a symlink farm in /usr/local. Want to get rid of the program? "stow -D" it followed by deletion. This is nice for handling seamless upgrades/downgrades of non-packaged software as wel. vorbisgain - Like mp3gain, just for vorbis files. graphviz - Hate drawing diagrams? Now you can program diagrams instead! Graphviz takes a description of a graph (not a plot!) and proceeds to build the graph for you. It uses some really good layout algorithms so you often get extremely neat graphs if you know a bit about the tool. Most kinds of graphs can be drawn easily. There are also tools for doing post-processing of drawn graphs if you want to do things a bit different than what the tool thought - but you rarely need that. It got a Cairo rendering backend and can output to PDF, PS, PNG, SVG, etc. The real power of graphviz is when your graph changes a lot. You just add vertices and edges and the system figures out layout itself. It is way easier than editing the graph in tool most of the time.

Unison - A file sync application

2009-01-04T15:05:00.001-08:00

Most system admins know about rsync. It is a really good tool to synchronize between different machines because it only moves data that happen to be changed. It lacks some things however. One of the things it is lacking is interactivity. Unison is a tool written by Benjamin C. Pierce and a couple of other guys. Pierce is a type theory researcher and he likes writing ocaml programs. But you should not let that put you off Unison. It uses the rsync protocol down below ;) When it sync's 2 sites it will ask you which way to propagate changes. It is also much more clever when it comes to shortcutting work. It can, for instance, detect that a file was moved so it has a local copy of that file it can use in the sync process. My preferred usage is to sync. directory contents between machines I work on. It often happens that I have worked on the machines in a way such a 2-way sync is needed. And Unison can give you that right away while it will be pain in rsync. Pierce now works on the Boomerang language which is really interesting. But I'll save that for a later post.

Avoiding memory fragmentation for fun and profit

2009-01-02T11:25:00.000-08:00

One problem that might occur in long-running programs is that of memory fragmentation in the VM-heap. The problem is pretty simple: when you allocate and deallocate memory in the program you might end up with small "holes" all over your heap which are too small for the new data you need. In a page-allocated VM-heap world, this has a serious cost in memory usage. There are several ways to avoid the problem. The first one is to be aware of the problem and be smart when allocating memory. With the right amount of thought you can often get around the memory fragmentation, or at least minimize it. The second trick is to restart the application periodically. It is not as bad as it sounds in a UNIX system. You set up the application and fork() off a child to do the hard work. When the child has been running for some time, you kill it and fork() off another from the (non-fragmented) parent. Apache 1.x used this. The third trick is to allocate a big region of memory, keep a pointer to the first unallocated word and then reset the pointer when you are done with your request and don't need the memory anymore. Interestingly there has been considerable research in the area to attempt to automate this idea. It is known as "Region Inference" in the automated setting, but here it is used in a manual way in e.g. C to achieve the same thing. The Subversion project used a region handler some years ago when I looked at their code. I don't know if they still do however. Poul Henning Kamp uses the reset-trick in Varnish as well. The fourth trick is to use a good garbage collector. Garbage collectors have the advantage that they are allowed to move data around, so the good ones compact live data to one end of the heap periodically and clears up fragmentation in the process. Note that most garbage collectors used in "scripting languages" like Python or Ruby are pretty weak. They usually avoid doing "real" garbage collection and opts for some simple poor-mans solutions. It is unfortunate because this puts GC in a bad light. That and Java-enterprise-behemoths abusing the VM-heap :)

The magic of puppetry

2008-12-10T14:45:00.000-08:00

At work, we have several geographically separated machines. This is no problem for puppet, one just declares a variable for the location and then proceed to factor out differencies between the locations. I just naively went along and choose one machine from each geo-location as the defining one in that location for generic services. We use OpenNTPd for our NTP services. Use geo-location to pick out the right DNS-name/IP-address and then proceed to set it in /etc/openntpd/ntpd.conf. Ensure that the package is installed, and the service is running on the host. Do the very same for the logcheck tool, though the configuration is less specialized to geo-locations. Go to lunch. When I come back, three hosts has tripped in the spider web of logcheck. All because they are off on the clock. The magic is that the streamlining of hosts happens automatically. You don't have to hunt for the discrepancies, you just have to specify what the hosts should contain. I had no idea that some machines were without NTP. It is not because system administrators are lazy and have bad memories. It is because you need better tools to maintain your server farm, ie, puppet. The next thing I do is to get apt to run via cron (There are several tools for this, pick your poison), get it to update the database and to download new updates. Then the following little piece of magic from the Puppet website does wonders:

 file { "/etc/update_initiator":
  group => root,
  owner => root,
  mode  => 640,
  source => "puppet:///dist/config/update_initiator",
 }

 exec { "/usr/bin/apt-get -y dist-upgrade":
  refreshonly => true,
  subscribe => File["/etc/update_initiator"],
 }

When '/etc/update_initiator' is changed, then run the dist-upgrade. The update_initiator file also serves as the descriptive changelog of when an update was sent through to the machines. Update that file on the puppetmaster and then all machines happily install their updates.

Master of puppets.

2008-12-03T10:54:00.000-08:00

No, this is not a post about Guitar Hero 3. It is about system administration and puppetry! If you manage more than 5 hosts you will need configuration management automation. Either you write your own scripts (shudder), use CFEngine (more shudder) or you use Puppet from Reductive labs (There are .deb packages: puppet and puppetmaster). Choose a server that is going to be the puppetmaster. This guy should be fairly well protected as he will be the server handing out configuration to other machines. Give him a repository in /etc/puppet via either Subversion, Git, Hg, Bzr or your poison of preference. Make it such that a DNS lookup on puppet.[dnsdomainname] hits the puppetmaster. Enable the puppetmaster fileserver if not already done. Install puppet on the clients. Hand it the server address and it will try to communicate. It will fail miserably until you allow the clients Security CA's on the puppetmaster. Then you are ready for the fun: Assimilation! I started with something easy. Behold, sudo.pp:

class sudo {
       package { sudo: ensure => installed }

 file { "/etc/sudoers":
  owner => root,
  group => root,
  mode  => 440,
  source => "puppet://puppet/dist/apps/sudo/sudoers",
               require => Package[sudo]
 }
}

This incantation tells puppet that we need the 'sudo' package. Puppet is intelligent enough to use the right poison: portage, apt, aptitude, yum, pkg-install (Hi FreeBSD!), etc for installing the package. Next it will update /etc/sudoers with a file over the puppet protocol from the 'puppet' host (Remember the DNS setup? You'll love it in the long run ;) and take it from /dist/apps/sudo/sudoers. This path is prefixed with whatever is set in /etc/puppet/fileserver.conf and the file is copied, checksummed and configured. B00m! You now have centralized your sudo configuration. Next up: NTP!

class openntpd {
 package { openntpd: ensure => installed }

       file { "/etc/openntpd/ntpd.conf":
     source => "puppet://puppet/dist/apps/openntpd/ntpd.conf",
           require => Package[openntpd]
 }

 service { openntpd:
     ensure => running,
     enable => true,
     pattern => "ntpd",
     subscribe => [Package[openntpd], File["/etc/openntpd/ntpd.conf"]]
 }
}

Note we have a declaration 'require' that orders the dependencies among things. We'll be sure things trigger in the right order. Next we define that openntpd needs a service 'openntpd' which should be running and enabled. The 'pattern' part tells puppet that it should look for a program 'ntpd' to discern whether openntpd is running or not. Puppet is intelligent enough to force the enabling via 'update-rc.d' on my Ubuntu/Debian boxes. Final thing: Locales (shudder).

class locales {
 package { locales: ensure => installed }

 file {
 "/etc/environment":
  owner => root,
  group => root,
  mode => 644,
  source => "puppet://puppet/dist/config/environment",
  require => Package[locales];
 "/etc/locale.gen":
  owner => root,
  group => root,
  mode => 644,
  source => "puppet://puppet/dist/config/locale.gen",
  require => Package[locales],
  before => Exec["generate locales"];
 }

 exec { "locale_gen":
  command => "/usr/sbin/locale-gen",
  alias => "generate locales",
  subscribe => File["/etc/locale.gen"],
  refreshonly => true
 }
}

The new thing is the 'exec' declaration that will call '/usr/sbin/locale-gen' if our subscription '/etc/locale.gen' were updated (refreshed). Now you add the classes to the machines that need them through the 'node' facility of puppet. And then you have centralized control over ntpd and locales as well. Of course, puppet can also do things depending on host-types, fill in config-file templates, discriminate configuration in every conceivable way and so on. I can live with the fact it is written in Ruby. It happens to be brilliant. If you want to start using it, I recommend going straight to the root of a complete setup, and use that as a base for yours.

Erlang Talk slides

2008-11-27T12:39:00.000-08:00

Some days ago I gave a talk at the local LUG on Erlang. The basic idea was to spark the interest in the language while keeping it comprehensible to most people. Of course you need slides for such an occasion, and what tool but LaTeX is the solution? First, you'll need the BEAMER package. Ubuntu has a 'latex-beamer' package. Then you'll simply begin a LaTeX document with: Update: Changed 'fontend' to 'fontenc' which is the right thing to write here ;)


\documentclass[20pt]{beamer}
\usepackage[T1]{fontenc}

\begin{document}
...

Each slide page can then be added with the following construction


\frame{
\begin{center}
Concurrency\\
$+$\\
Parallelism
\end{center}
}

which creates a single slide frame on which text is placed. Calling 'pdflatex' on the document then produces a PDF you can show in 'evince' or similar program. Run the document in presentation mode and you are set to go. The next part is graphics. One would think this is hard, but oh no! Not so! You just add


\usepackage{graphicx}

before the document environment. And then you can include images like I did in this slide (note that you can often omit the file-type ending and let LaTeX figure out that part by itself)


\frame{
\begin{center}
  \includegraphics[scale=0.5]{400px-Skull_and_crossbones.pdf}\\
  \textbf{\large{``Doom doom doom''}}
\end{center}
}

Luckily, you are not limited to only PDF documents. I used PNGs, JPEGs and a couple of other things. The Beamer homepage Slides from the talk Guy Kawasaki: the 10-20-30 rule for Pitching on Youtube

Debugging Erlang programs 101

2008-10-12T12:54:00.000-07:00

The first step in debugging Erlang programs is simple: Acknowledge that debugging concurrent programs is hard. Extremely hard. When you have that acknowledgement, the trick is to get your bag of debugging tools up to date. The very first thing you should do is to enable SASL. This can be done with the command

application:start(sasl).

or by using the boot-script that includes the SASL application. SASL will enable different kinds of information in the shell, but it can also be configured to output to a file. SASL will send reports in different situations. Whenever something CRASH-es or something PROGRESS-es, SASL will send a report to you. The next part of debugging is to understand how to dissect Erlang back-traces. Erlang will not report line-numbers where the error occurred. Hence, you should use many small functions, as the function will occur in the back-trace. You must also remember that the back-trace may does not include tail-calling stack-frames. How do you read a back-trace from Erlang? The first thing is to know what the different error messages means. The exit reason of a function will tell us what is wrong at the point where the error was raised. The next part of the stack-trace looks like:

** exited: {function_clause,[{foo,fact,[0.00000e+0]},
                             {foo,fact,1},
                             {erl_eval,do_apply,5},
                             {shell,exprs,6},
                             {shell,eval_loop,3}]} **

So what does this tell us? It says that the exit reason was a "function_clause" error. These are because no pattern matches in the foo modules fact function. The next term is a call to "foo:fact/1" and that comes from a call "erl_eval:do_apply/5" and so on. More evil are local "fun (...) ..." declarations which will be put into the stack as well. Watch out for these.

Assertions

The single assignment form of Erlang let us write assertions in a neat way in the code. If we set


X = Y

where both [X] and [Y] have already been defined, we define an assertion. Note this is also true if X or Y are (partially) constant expressions. This asserts that X and Y are equal. Use this to your advantage! Spray with assertions all over your code. Write down what you expect the value to be. Write functions that tests assumptions about the code. If the assertion is violated, you get an error right away. Use function guards. If you expect an integer, write

foo(X) when is_integer(X) -> ...

rather than


foo(X) -> ...

Sometimes, guards can't be used as only certain BIFs are allowed as guards. Then you, write a longer function that tests your assumptions and assert on that function. When things get concurrent, it is assertions that will save you. You should not worry too much about adding assertions to the code. Unless you add them in the cost-centre, it won't affect you much. Rather, you should worry about the correctness of the program. You can always remove assertions from critical parts and surround the critical part with a check if needed.

Dialyzer

One last debugging tool to mention is the dialyzer. It is a static checker for Erlang code and it is able to find many discrepancies in the code if you let it run on it. You should heed its warnings, for often they can alleviate a problem before it even becomes one. This concludes the 101 in Erlang debugging.

Books equals code?

2008-10-01T11:41:00.000-07:00

Suppose you were an author writing books. A publisher wants to publish a novel on a particular subject; a sci-fi novel say. Now imagine that the author will be paid for each month he or she works on the book with a nice pay, but once the book has been written, then it belongs solely to the publisher. The publisher will sell the book for the next 20-30 years and make a bit of money off it each month. The author will not get anything of these money. A mediocre author would -- perhaps -- jump at this. A bestselling author, however, wouldn't. She would only accept writing the sci-fi novel should she get considerate percentage of the earnings. She would know that her value is built by accumulating it in the books she writes because they will throw off a small bit of money each month for 20-30 years. Now imagine you are a programmer at a company. Most programmers happily give over all rights on the code to the company. They happily get their pay each month, and when they get fired or move on, their accumulated value is lost entirely. The paradoxical thing is: most programmers accept this. Some of their worth is in the code they wrote, but since it is entombed in the repository of the company they have access to that worth in their next job. I command this to stop. Now. Here is a set of ideas: First, you could tie the success of the company with your earnings, but be sure that you get something other than salary. It is gone when you leave. Stock options is one way. Or you may be one of the owners. Second, you could ignore the company and write code "in stealth" on the side of the company. When you have a product you could try to shrink-wrap it into something salable. With luck, you can then either get something fun out of it, or a lot of money. Note that many companies disallow such activity. If you are at one such company, I suggest you move on and let them outsource your seat to India. They will be sorry for trying to outsource the system kernel (it always fails). Third, you could have the company release part of their code as open source. This leaves you with a way to take your work with you to another company and with luck you also generate "street credit" in the Open Source community. In other words, you are generating accumulating value you can take with you when you leave. The company can get a feedback loop going on such open sourced software, so it might end up being beneficial to them. Fourth, you can write software and release the software under an open source license. But you only do work on the system by contract. If a company wants tailoring, it is negotiable for a price. They get the best programmer for the job and you back-fit the changes into your code generating even more value in the project. Another path is to take money for support on the code base.

The Law of secret weapons

2008-07-20T18:00:00.001-07:00

So, one searches the a job index in denmark: ML: 0 Lisp: 0 Haskell: 0 Erlang: 0 Python: 1 - Manage a Java EE build system(!) Perl: 2-3 system admin jobs. The conclusion is clear: the Law of the Secret Weapons(tm) still holds true. You can pick anything from the list above and you will be able to enter almost any field with the best technical platform in 4-6 months time. I am sick of the Java and .NET jobs which let me code in a mediocre language with mediocre IDE-crap on some project I have absolutely no love for. I can understand the functional toolset and mindset of ML and Haskell puts off people. Lisp is harder since it has so much backing in the commercial world after all. Same goes with Erlang - given that it currently has some of the hype. But seeing that few Python jobs astounds me. It is fairly easy to learn and has some great backing in Google. It is not going to perish the next 10 years. And you can deliver great software in a short amount of time with it. Python also has the advantage that its dynamic typing makes it easier for the PHP crowd to pick up. Static types are awfully cool, but they require some training and routine to use effectively to your advantage. Most integration is also complete bliss to pull off in Python if you know what you are doing. So any company that wants to use anything of the above can have me. I would be delighted to rip some Java/C# programs apart with a real language.

fprof in few paragraphs

2008-07-18T17:40:00.000-07:00

First you find a pid. Then you run


fprof:trace([start, {file, "f"}, {procs, [pid(0,1292,0)]}]).

and let it cook for a while. "f" will contain the profile raw data. When it has cooked for some time, you can run


fprof:trace(stop).

to close the file and stop the trace. Then you read in the data with


fprof:profile(file, "f").

which builds a database in memory from the profile run. The analysis output is then generated in 150 columns with


fprof:analyse([{dest, "f.analysis"}, {cols, 150}]).

to the file "f.analysis". To understand the profile output, you can read the Tools Users Guide which has a chapter on fprof and describes the output format. Let the CPU-cycle hunt begin!

The Dialyzer tool, love at first sight

2008-07-17T06:21:00.000-07:00

So I am hacking a lot of erlang at the moment. The problem is that erlang is a dynamically typed language and bugs are sneaking into my code. This is where the dialyzer enters the game. It is a system which will take erlang code, infer types for the code and use it in a static analysis in order to find errors. For me, this is a very valuable tool. While you can just run the code, it may take some time before you cover all cases, so periodically running the dialyzer can sometimes find bugs before they show up in running code. You compile your code and then you run


dialyzer -r "path-to-ebin-beams"

and the dialyzer will process your code and report problems. You will have to produce a PLT first. The PLT is the initial table with type information from other applications that you have stored in it. Creating the PLT takes time. A lot of time. If you run the dialyzer without a PLT you get hints on how to produce the initial PLT. I most often use the dialyzer before comitting a larger set of code or after merging a branch upwards (From less stable to more stable code). Sometimes it finds messy stuff. And then I can go and fix it!

etorrent - a bit of some history.

2008-07-09T05:25:00.000-07:00

So, writing a torrent client goes through 3 phases: In the first phase, you implement what is in the spec. These are the obvious things you need and the things you use as building blocks for the later steps. In the second phase, you read the spec and figure out how things must fit together. Luckily, there is only one way to fit in most places, but there are some small nasty exceptions where you need to read code of other clients to figure out what should happen. In the third phase, you go from the spec to implementing all the features that are more or less undocumented, but crucial for speed. Here is an example:

It does reciprocation and number of uploads capping by unchoking the four peers which it has the best download rates from and are interested. Peers which have a better upload rate but aren't interested get unchoked and if they become interested the worst uploader gets choked.

So this is simple enough to implement. Sort the peers on download speed to the client and go through them one by one, choking and unchoking accordingly. But you need to recalculate this on state changes. And then there is optimistic unchoking which must also be handled. Seems easy enough. The etorrent client currently has numerous problems with the above scheme. First of all, the measurement of download in clients must be running average, dampened and fine grained. Second, the 'four peers' part is a lie, and no modern client does that. Rather they choose the number based on the sum of the download rates and a heuristic. Of course this can only be understood if you read the source code of other clients. This is the undocumented hairy part of the bittorrent protocol.

Erlang and bittorrent?

2008-05-04T12:33:00.000-07:00

I have been working on an erlang bittorrent client for too many years at the moment. The reason it takes so long to get the code up and running is that it is a hobby project and that I have plenty of time doing it right. So at the moment the code works, but it does not have the stability I would like it to have in the long run. But the code does work for downloading smaller things and I would like to have more hackers on the project. To document my setup, I better explain what is used from the perspective of development. The editor is emacs with the distel mode on top of it. See The Distel Googlecode site. The distel program allows me to dynamically upload recompiled code to a running erlang node so I can cut down the fix time to a minimum. For a dynamically typed language this is quite important as most bugs are related to wrong types. Of course I run the standard Erlang distribution, without HiPE. I have not found the reason to compile code for speed yet as the code eats less than 1% CPU power when running. All database table access in the current code is linear, so there are definitely room for improvement and it will be needed as you want to download more than a single torrent file. The code is kept in a GIT repository at repo.or.cz and the bug tracker is on the google code site. I tend to keep the master branch in a stable baseline state so if you want to hack you better base your work on that. Also, I tend to keep my own main working branch in the repository as well so you can track what I am doing which is not yet ready to go into the baseline. Do I like hacking Erlang? Yes and no. I really like the language, but the lack of a static type system is seriously pissing me off at the moment. But you can't have it all and Erlang does have a good production quality system which is rather hard to find with most other esoteric languages. The closest contenders being Haskell and Ocaml.

Bugs which are not bumble bees

2008-04-26T19:40:00.000-07:00

We have "bumble-bee-season" at the moment here. Every hour a queen is coming by my window and flies into my apartment. For some reason the queen must have a vain hope that my apartment will be a suitable place for her nest. Luckily it's not an aggressive type of bee, so you just gently guide it to the exit -- and on it flies. Now this will not be about bumble bees, as however interesting it might be, the fate was that I shouldn't be a biologist. This is a shame -- gene manipulation sounds fun. So we will write on the other kind of bugs, that most readers will probably be more familiar with. The computer bugs who were once real insect bugs, but took on a more imaginative meta-physical form. Any set can be partitioned in two. Let us partition bugs in the interesting and non-interesting ones. Of course this is for the pure reason of studying bugs. The set of interesting bugs are those, which make for a good story over a cup of coffee. They explain some fallacy in your thinking in help you understand the problem you are working with. To be specific: interesting bugs alters your perception of the problem you are trying to solve. The other group of bugs, non-interesting, does not have the virtue of making a good story. These are most common and your only goal is to fix them as quickly as possible to get the program up and running. They manifest themselves all the time. It may be a wrong type that gets passed, it may be a wrong tag, off-by-one, a non-exhaustive pattern match with an obviously implemented missing pattern, swapped arguments in a function call or something similar. They may be really pesky to find and fix, but they do not tell anything new to your brain. I don't like non-interesting bugs. I don't like to play with code to make it work either. I began hacking ML at a very early age, so my brain is wired to the thought of having static types on everything. To me, I rather want to skip the non-interesting bugs and write the code so I can attack the next problem. At some point, the ML type system becomes a tool for avoiding bugs of the non-interesting kind. We can't pass the wrong type as the type system will complain. We can still tag things incorrectly but not with a typo. The last problem I had in a dynamically typed language was that I had written non-fetched rather than the correct not-fetched. A proper sum-type eliminates this problem. Off-by-one tends to be eliminated by using a data structure such that indexes are abstracted away. Non-exhaustive pattern matches are caught by the compiler. And finally, swapped arguments are either caught by the type system, or you can pass a named record so each argument has a name rather than a position in the call parameter list. Unfortunately, you don't get complete elimination of non-interesting bugs. There are still some left, but they tend to be few and far in between. I save time and altering the program is simpler because the types have to match for any change, eliminating much work with finding all spots having to be changed. For the experienced type hacker, one can use tricks like universal embeddings and phantom types to squeeze out even more expressibility. And that is without adding more tools into the bag: dependent typing, substructural typing and existential types. And with this, I think I have explained why I don't like programming in dynamically typed languages that much. My claim will be:

Dynamically typed languages make you fight more non-interesting bugs than statically typed languages.

Why I don't use Haskell for Functional Programming

2008-03-08T05:34:00.001-08:00

When designing programming languages, the hard choice is not about what you put into the language -- it is what you leave out or what is mutually exclusive. Haskell did make the choice of being a purely functional programming language and they did the choice of being lazy. The positive things manifesting from this is: Lazy evaluation finds more normal forms than strict evaluation. In the simply typed lambda calculus it finds all of them but I am not sure this is the case in Haskell. Secondly, since the language is pure the compiler is free to reorder computations as it sees fit. Languages which are strict have an evaluation order limiting how we can reorder terms. Standard ML is extremely limiting in this respect due to the correct handling of IEEE floating point numbers and that arithmetic overflow must throw exceptions. It is possible to have a strict functional language with added references and exceptions. These effects can, without too much hassle, be added to the language in a way such that the implications are minimal. Ocaml and Standard ML are the main examples, I believe. We all know that Haskell took the monad route to add effects. A heavy inspiration from Category Theory gave them a tool to build in effects by encoding them as monads. It should be noted that there are other ways to add effects into a purely lazy functional language as is shown by Clean. I don't like monads for programming effects. Granted, they give me a way to formalize (in the type) what effectful computations a given function have and that can be a tremendous help. But on the other hand, it also forces me to lift computations into the monad as soon as I bring it into play. First of all, the lifting adds a lot of boilerplate code. If I need a monad transformer, this quickly gets out of hand: My code tends to be invocation of the correct lifts into the monads. Second, as effects can alter control flow, there is often the requirement of doing global changes to the program. The changes are not limited to the function using the effect only - the infection spreads to the callers and often further up the call chain. And SML is not perfect at all too: We have a lot of old cosmetic changes we ought to do. And we better get a grip on how to add linear typing and an effect system so we can reap the benefits that monads does give you without all of the hassle.