- Do you plan to release the
5 days 10 hours ago - Joining/helping with CorsixTH
1 week 44 min ago - Pipeline
1 week 2 days ago - I don't suppose you could
2 weeks 1 day ago - As I wanted to override the
3 weeks 4 days ago - Why inherit from the generic
3 weeks 4 days ago - Code Signing for Individuals - GlobalSign
4 weeks 4 days ago - Quite interesting. I'm also
4 weeks 4 days ago - Code not works: "test.lua:41:
9 weeks 2 days ago - Support adding wxComboBox
12 weeks 2 days ago
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 ())
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.
Comments
awesome :)
thats really clever code you have there
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
Gotta love Brainfsck xD
Gotta love Brainfsck xD
Post new comment