Brainfsck in Haskell
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.