Brainfsck in Haskell

Wed, 27 Jan 2010 - 3:18pm — Corsix

Recently, I had to sit an exam which involved questions on/about the functional language Haskell (it was an Oxford start of term exam, also known as a collection, if you're interested). To revise the feel and syntax of Haskell, I decided to write a minimal interpreter for my favourite esoteric language, Brainfsck, in Haskell.

Writing such an interpreter in C/C++ is fairly trivial, with the only slight difficulty being providing an array which is infinitely long in both directions. As Haskell is a functional language (function in the mathematical sense, rather than the sub-procedure sense), providing an infinitely long array is extremely simple, and it is everything else which is non-trivial. The code ends up making heavy use of monadic I/O (ironically, monadic I/O isn't really covered in the course syllabus beyond "you can construct a string and then pass it to putStr to write stuff"), and looks very different to how you'd implement it in C/C++:

code = "++++++++++[>+++++++>+++++++++++>+++>++++++++++<<<<-]>+.>+.>++.<<++++.>.+++.>>+.<+.<<<."

data Token = C Char | L [Token]

join a (b, c) = (a:b, c)

parse ('[':xs) = join (L inner) (parse etc) where (inner, etc) = parse xs

parse (']':xs) = ([], xs)

parse (x:xs) = if elem x "<>+-.," then join (C x) (parse xs) else parse xs

parse [] = ([], [])

evalWith l c r = eval (return (l, c, r))

evalRaw (C '<') (l:ls) c r = evalWith ls l (c:r)

evalRaw (C '>') l c (r:rs) = evalWith (c:l) r rs

evalRaw (C '+') l c r = evalWith l (if c == 255 then 0 else (c + 1)) r

evalRaw (C '-') l c r = evalWith l (if c == 0 then 255 else (c - 1)) r

getCharNoR = getChar >>= \c -> if c == '\r' then getCharNoR else (return c)

eval s ((L  cs):xs) = s >>= (\(l, c, r) -> if c == 0 then (eval s xs) else (eval (eval s cs) ((L cs):xs)))

eval s ((C '.'):xs) = s >>= (\(l, c, r) -> (putStr [toEnum c]) >> (eval s xs))

eval s ((C ','):xs) = s >>= (\(l, _, r) -> getCharNoR >>= \c -> evalWith l (fromEnum c) r xs)

eval s (x:xs) = s >>= (\(l, c, r) -> evalRaw x l c r xs)

eval s [] = s

result = evalWith (repeat 0) 0 (repeat 0) (fst (parse code)) >>= (\_ -> return ())

The parse function (along with its helper, join) is used to perform a first-pass over the Brainfsck code. This removes non-code characters, and performs bracket matching to simplify the evaluation stage. The output of the parse function is a list of tokens, where each token is either a code character, or a loop (which is just another list of tokens). To simplify the implementation of parse, it also returns the tail of the code which it could not understand as a second return value.

The eval function (along with helpers evalWith, evalRaw, and getCharNoR) handles the transformation of the tokenised Brainfsck code into a monadic I/O object representing the evaluation of the Brainfsck code.

Finally, the result function ties everything together. Note the incredibly simple creation of the infinite array - it is just (repeat 0) 0 (repeat 0), which also describes the infinite array fairly well.

Corsix's blog

Comments

Tue, 2 Mar 2010 - 9:20pm — Anonymous (not verified)

awesome :)

thats really clever code you have there

Wed, 27 Jan 2010 - 6:53pm — Jack (not verified)

Haskell is fun

I really like Haskell, except I think Monadic I/O is not great. Another problem is I wish that [A] (for a type 'A') was also considered a type in itself (and so match against B rather than just [B]), at least at an option. Do you know of a technical reason why this is?

I think it'd be brilliant if there was a decent .Net version of Haskell so it could be used with C#. F# just isn't quite as good.

Also, collections are rubbish, we didn't have them at Cambridge and I am so thankful of that =D

Wed, 27 Jan 2010 - 6:31pm — AtlasRedux (not verified)

Corsix.org