On Peer Processes

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.

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.

Data.ByteString.Lazy

HCodecs

Erlang code

Haskell code

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.

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.

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.

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.

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.

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!