[Haskell-cafe] Bit streams programs in Haskell

[Per Gustafsson]

Haskell gurus,

We have made a proposal to extend the Erlang `binary' data type from
being a sequence of bytes (a byte stream) to being a sequence of bits (a
bitstream) with the ability to do pattern matching at the bit level.

This proposal has now been fully implemented all
these at the level of the BEAM virtual machine and in the HiPE
compiler. Most probably, they will be part of the next major
Erlang/OTP open source release. (We write "most probably" because we
do not really control what Ericsson desides to release as part of its
open source system.)

We wanted to evaluate the performance of our implementation and the
succintness of our syntax, particularly against other `similar'
languages. For this reason, we wrote five reasonably representative
benchmarks, showing the things that one could employ bit stream pattern
matching and bit-level comprehensions for.

The benchmarks (drop3, five11, huffman, uudecode, and uuendode) have
all been written in Erlang, O'Caml and Haskell. For some of them, C
and Java versions exist. They can be found in the following homepage:

       http://bitbenches.infogami.com/

As you will see there, the Haskell numbers are significantly slower
than those of Erlang and O'Caml. We are wondering why this is so.

For each language, we have spent a considerable effort in writing the
benchmarks in -- at least what we feel -- is the most natural and
efficient way one can write them.

The only constraint we impose is that for functional languages, data
structures without any explicit mutation have to be used in the part
of the program for which measurements are taken.

Our experience in writing efficient (and beautiful) Haskell programs is
close to (if not below) zero. Also, perhaps our mind might be suffering
from severe case of strictness and might be completely unable to `think
lazily'. So, we request your help in noticing obvious NO-NOs and stupid
mistakes that we might have made. We even welcome completely different
Haskell programs provided they adhere to the constraint mentioned
above -- no mutation.

Best regards,

Kostis Sagonas and Per Gustafsson