• The LLVM backend to GHC
• the Accelerate, a Haskell EDSL for regular array computations, using various backends (CUDA, OpenCL, LLVM etc.)
• Hubris, the Haskell-Ruby binding
• Leksah, the Haskell IDE written in Haskell
• MPI bindings

then please put your name down on the sign up page.

This should be a great opportunity for Aussie (and non aussie!) haskell hackers to come and meet all those people you know from Planet Haskell and #haskell, and give something back to the community, while having a great time.

Hope to see you there, – Alex Mason

Hi, thanks for writing this stuff. I think it could be pretty cool, but it could benefit from more precise reading and implementation of the spec.

For example, bencoded integers can be negative.

Also, my alarms go off whenever I see ‘read’. In ‘getBString’, you pass ‘read count’ to ‘getByteString’, which expects Int. But check, e.g., ‘read (show $ 2^64-1) :: Int’ in ghci. So if the torrent data is malformed, you could end up passing a negative length to ‘getByteString’. Maybe it knows how to deal with that, but it’s not something you should rely on.

You also have to decide what to do about dictionaries you read whose keys aren’t in order, etc.

Basically, please be more precise, especially if you put this on Hackage. This stuff is supposed to be industrial strength. Thanks.

The first problem, not handling negative integers was pretty trivial to fix, all I needed to do was check to see if there was a ‘-’ char out the front, and if not, just get all the digits, and then read them:

-- | Parses a BInt
getBInt :: Get BCode
getBInt = BInt . read <$> getWrapped 'i' 'e' intP
    where intP = ((:) <$> char '-' <*> getDigits) <|> getDigits

Brian also pointed out something I also wasn’t particularly happy with, the use of read to read in an Int64. This should under normal circumstances be more than large enough to read any bytestring that should be in any bencoded data (.torrent files are usually less than 1-200KB), so we should never have run into a problem here, but it’s still good to make sure we can be ‘industrial strength’:

-- | Parses a BString
getBString :: Get BCode
getBString = do
    count <- getDigits
    BString <$> ( char ':' *> getStr (read count :: Integer))
    where maxInt = fromIntegral (maxBound :: Int) :: Integer
          getStr n | n >= 0 = B.concat <$> (sequence $ getStr' n)
                   | otherwise = fail $ "read a negative length string, length: " ++ show n
          getStr' n | n > maxInt = getByteString maxBound : getStr' (n-maxInt)
                    | otherwise = [getByteString . fromIntegral $ n]

Here you can see we’re now using an Integer as the read value, and taking chunks of maxBound :: Int bytes, until there are less than that many bytes left to fetch.

I’ve decided to ignore the problem with dictionaries with out of order elements, I can see this being something others may have overlooked in their implementations, and it’s entirely possible that other implementations do not put the keys in the right order. Our implementation does, but can easily handle malformed implementations. I see this is a bonus, and I hope others do too (I feel the code is more robust, and that’s always good).

I hope this has made some difference to the code, and what people think of it.

Until next time,

– Axman

I’ve been playing around with cereal lately in jlouis’ haskell-torrent project, rewriting the various binary parsing and producing parts of the program (the torrent file parser, and the wire protocol parser). I though it would be nice to share some of the code used for these, to demonstrate how easy cereal makes it to do such things.

To begin with, I’ll show you the part that decodes and encodes torrent files (if needed in the future). Torrent files are encoded using a very simple encoding, known as bencoding, which consists of four major primitives: Integral numbers, Strings of bytes, Arrays of bencoded objects, and Dictionaries of String, bencoded object pairs. This is very nicely represented using this datatype:

-- | BCode represents the structure of a bencoded file
data BCode = BInt Integer                       -- ^ An integer
           | BString B.ByteString               -- ^ A string of bytes
           | BArray [BCode]                     -- ^ An array
           | BDict (M.Map B.ByteString BCode)   -- ^ A key, value map
  deriving Show

Integers are encoded as the ASCII character for ‘i’ as a byte, followed by the digits of the integral value, terminated by the ASCII byte for ‘e’.

Eg: the number ‘42’ would be encoded as “i42e”

Strings are encoded as the digits of their length, followed by a colon (‘:’), then the bytes of the string. these strings are really just byte sequences, and probably shouldn’t be treated as having an encoding (as jlouis and I found out when I tried to test the current code on GHC 6.12.1, with the BString type using Strings, instead of ByteStrings, and finding out that the simple test contained byte sequences that could not be represented as Strings).

Eg: the string “hello” would become “5:hello”, “hello world” would become “11:hello world”

Arrays are encoded as ASCII ‘l’ (for list I believe), followed by any number of bencoded objects, terminated by an ASCII ‘e’. (This is where using binary became difficult, as you had to explicitly check whether you had reached the terminating ‘e’ using lookAhead when parsing before attempting to parse another bencoded object, du the the lack of actual failure handling)

Eg: ["Hello", 123] would become “l5:helloi123ee”. Notice how we’ve used the previous definitions for integral numbers, and strings.

Dictionaries are encoded as an ASCII ‘d’, followed by the String, object pairs, followed by an ASCII ‘e’.

Eg: fromList [("test",123),("arr",[1,2,"hello"])] would become “d4:testi123e3:arrli1ei2e5:helloee”.

It looks a bit of a mess, but it is quite efficient.

Encoding

When writing my Serialize instance (Cereal’s version of the Binary class) for the BCode type, I decided it would be much easier to write the put methods first. This turned out to be rather straight forward, once I’d written a few helper functions.

toW8 :: Char -> Word8
toW8 = fromIntegral . ord


fromW8 :: Word8 -> Char
fromW8 = chr . fromIntegral

toBS :: String -> B.ByteString
toBS = B.pack . map toW8

fromBS :: B.ByteString -> String
fromBS = map fromW8 . B.unpack

-- | Put an element, wrapped by two characters
wrap :: Char -> Char -> Put -> Put
wrap a b m = do
    putWord8 (toW8 a)
    m
    putWord8 (toW8 b)

-- | Put something as it is shown using @show@
putShow :: Show a => a -> Put
putShow x = mapM_ put (show x)

instance Serialize BCode where
     put (BInt i)     = wrap 'i' 'e' $ putShow i
     put (BArray arr) = wrap 'l' 'e' . mapM_ put $ arr

    put (BDict mp)   = wrap 'd' 'e' dict
                      where dict = mapM_ encPair . M.toList $ mp
                            encPair (k, v) = put (BString k) >> put v
     put (BString s)  = do
                          putShow (B.length s)
                          putWord8 (toW8 ':')
                          putByteString s

Decoding

Parsing the data was the next step. this proved a little more difficult, but with my recent (shallow) experience with Parsec, I knew what was needed.

I decided to start by writing some useful combinators (this is a lie, I wrote them when needed, but lying makes the post flow better >_>). These included the following:

-- | Get a Char. Only works with single byte characters
 getCharG :: Get Char
 getCharG = fromW8 <$> getWord8


-- | Parse a given character
 char :: Char -> Get ()
 char c = do
     x <- getCharG
     if x == c
         then return ()
         else fail $ "Expected char: '" ++ c:"' got: '" ++ [fromW8 x,'\'']

-- | Get something wrapped in two Chars
 getWrapped :: Char -> Char -> Get a -> Get a
 getWrapped a b p = char a > p < char b
                  -- The same as char a >> p >>= \x -> char b >> return x

-- | Parse zero or items using a given parser
 many :: Get a -> Get [a]
 many p = many1 p mplus return []

-- | Parse one or more items using a given parser
 many1 :: Get a -> Get [a]
 many1 p = (:) <$> p <*> many p

-- | Returns a character if it is a digit, fails otherwise. uses isDigit.
 digit :: Get Char
 digit = do
     x <- getCharG
     if isDigit x
         then return x
         else fail $ "Expected digit, got: " ++ show x

-- | Get one or more digit characters
 getDigits :: Get String
 getDigits = many1 digit

With these in hand, I could now go ahead and write the actual parsers for various BCode types. Parsing BInts and BArrays is dead simple now:

-- | Parses a BInt
 getBInt :: Get BCode
 getBInt = BInt . read <$> getWrapped 'i' 'e' getDigits


-- | Parses a BArray
 getBArray :: Get BCode
 getBArray = BArray <$> getWrapped 'l' 'e' (many get)

BStrings were a little more difficult, but not hard, given what I’ve just written:

-- | Parses a BString
 getBString :: Get BCode
 getBString = do
     count <- getDigits
     BString <$> ( char ':' *> getByteString (read count))

-- | Parses a BDict
 getBDict :: Get BCode
 getBDict = BDict . M.fromList <$> getWrapped 'd' 'e' (many getPairs)
     where getPairs = do
             (BString s) <- getBString
             x <- get
             return (s,x)

    get = getBInt <|> getBArray <|> getBDict <|> getBString

Please, I implore you, do let me know what you think of this all, I’m always interested in seeing what others think of my code, and ways to improve it.

Until next time,

— Axman

After trying to compile the code using GHC 6.12.1, I noticed that a rather strange dependency: HCodecs. Investigating further, I realised that all that was being used was its fairly nice binary builder and parser, and was being used in the parsing and construction of bencoded files. This seemed to me to be the domain of one of my favourite packages, binary. I also noticed that when trying to parse the sample torrent file jlouis had provided, there was binary data that could not be represented in a String type, because there were byte sequences that could not be parses into Char’s.

So I went off to try and implement the BCode module using Data.Binary. The encoding was really simple and straight forward, but parsing was another matter. Binary has no real error handeling, which meant that decoding things like lists where you keep adding elements to the list until you reach an ‘e’, was made quite verbose due to this fact. After implementing a (semi) working module, I went in search of a more parsec like interface to binary parsing. This is when someone on #Haskell informed me of cereal, a package based on binary, which added an Alternative instance, and an Either String a return type for better error reporting.

I fell in love. This was exactly what I was after, I could create my own combinators like many and many1, with the same ease I could with parsec. Using cereal, I was able to make a really clear, concise parser, which should also be quite efficient.

I will post some of this code at a later time, when i’m not writing on my iPhone, and show you just what I mean. I’m also considering releasing the BCode module as a package of it’s own, if anyone else feels it might me useful to them. Either that, or I might write up a module of useful combinators for use with cereal.

Until next time, happy new year and I hope this year treats you all better than the last one did.

– Al

The HTML type is now

data HTML a = Doctype String String String (HTML a)
            | Content a
            | Text String
            | Node Tag Attrs [HTML a]
            | NoContent Tag Attrs
            | Comment String
            deriving Show

instead of

data HTML a = Doctype String String String [HTML a]
            | Content a
            | Text String
            | Node Tag Attrs [HTML a]
            | NoContent Tag Attrs
            | Comment String
            deriving Show

I’ve also added some more helper functions:

addAttrs :: Attrs -> HTML a -> HTML a
addAttrs attrs (Node tag attrs' rest) = Node tag (attrs' ++ attrs) rest
addAttrs attrs (NoContent tag attrs') = NoContent tag (attrs'++attrs)
addAttrs _ x = x


toTable :: [[String]] -> HTML a
toTable xss = table . map (tr . map (\x -> td [text x])) $ xss

toTable' :: Show a => [[a]] -> HTML b
toTable' = toTable . map (map show)

And updated my example:

example :: HTML ()
example =
    doctype "html PUBLIC"
            "-//W3C//DTD XHTML 1.0 Transitional//EN"
            "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd" $
        xhtml [
            header [
                title "My random page",
                meta "name" "Alex"
            ],
            body [
                comment "This is a comment",
                para [
                    text "The hr tag defines a horizontal rule:"
                ],
                hr,
                para [
                    text "This is a paragraph"
                ],
                hr,
                para [
                    text "This is a paragraph"
                ],
                addAttrs [("border","1px")] . toTable' $ [[0..n] | n <- [0..3]]
            ]
        ]

Which produces this html:

    <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN"
       "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
    <html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
        <head >
            <title >
                My random page
            </title>
            <meta name="name" content="Alex"/>
        </head>
        <body >
            <!-- This is a comment -->
            <p >
                The hr tag defines a horizontal rule:
            </p>
            <hr />
            <p >
                This is a paragraph
            </p>
            <hr />
            <p >
                This is a paragraph
            </p>
            <table border="1px">
                <tr >
                    <td >
                        0
                    </td>
                </tr>
                <tr >
                    <td >
                        0
                    </td>
                    <td >
                        1
                    </td>
                </tr>
                <tr >
                    <td >
                        0
                    </td>
                    <td >
                        1
                    </td>
                    <td >
                        2
                    </td>
                </tr>
                <tr >
                    <td >
                        0
                    </td>
                    <td >
                        1
                    </td>
                    <td >
                        2
                    </td>
                    <td >
                        3
                    </td>
                </tr>
            </table>
        </body>
    </html>

The main type behind the package is:

data HTML a = Doctype String String String [HTML a]
            | Content a
            | Text String
            | Node Tag Attrs [HTML a]
            | NoContent Tag Attrs
            | Comment String
            deriving Show

where

type Attr = (String, String)
type Attrs = [Attr]
data Tag = Html
         | ARef
         | BlockQuote
         | Body
         ...
         | Title
         | TR
         | UL

I’ve also provided helper functions to make this an actual DSL (I guess?):

example :: HTML ()
example = 
    doctype "html PUBLIC" "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd" [
        xhtml [
            header [
                title "My random page",
                meta "name" "Alex"
            ],
            body [
                comment "This is a comment",
                para [
                    text "The hr tag defines a horizontal rule:"
                ],
                hr,
                para [
                    text "This is a paragraph"
                ],
                hr,
                para [
                    text "This is a paragraph"
                ],
                table [
                    tr [
                        td [
                            text "data"
                        ],
                        td [
                            text "more data"
                        ]
                    ],
                    tr [
                        td [
                            text "more data"
                        ]
                    ]
                ]
            ]
        ]
    ]

produces:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en" lang="en">
    <head >
        <title >
            My random page
        </title>
        <meta name="name" content="Alex"/>
    </head>
    <body >
        <!-- This is a comment -->
        <p >
            The hr tag defines a horizontal rule:
        </p>
        <hr />
        <p >
            This is a paragraph
        </p>
        <hr />
        <p >
            This is a paragraph
        </p>
        <table >
            <tr >
                <td >
                    data
                </td>
                <td >
                    more data
                </td>
            </tr>
            <tr >
                <td >
                    more data
                </td>
            </tr>
        </table>
    </body>
</html>

I don’t claim that anyone should use this (there’s a good chance I won’t be releasing it, unless someone really wants me to), but I’m still quite proud of it.