Brainfuck is an esoteric programming language. It is known for two things:
1) It is very hard to understand and write brainfuck programs (hence the name).
2) It has a very small instruction set, which means that compilers for it can be very small. In fact, this was the design goal for the language.
A brainfuck program consists of only 8 different characters, each of which is a command:
+ and – increase and decrease the value of the current data cell by one, respectively.
< and > move to the previous/next data cell.
. prints the value of the current data cell.
, accepts a byte of input and stores it in the current cell.
[ and ] handle looping: if a [ is encountered and the value of the current cell is zero, it will skip to the matching ], otherwise it will execute the loop body. Similarly, ] moves execution to the start of the loop if the value of the current data cell is non-zero, otherwise it moves on to the next command, effectively exiting the loop.
The main practical use for brainfuck lies in the fact that it is a Turing-complete language. Hence, any language in which a brainfuck interpreter can be written is necessarily Turing-complete itself. Your task in today’s exercise is to write an interpreter that can run brainfuck programs. When you are finished, you are welcome to read a suggested solution below, or to post your own solution or discuss the exercise in the comments below (to post code, put it between [code][/code] tags).
The first decision we need to make is what data structure we’re going to use. While a plain list would work just fine, there’s a better fit. A zipper perfectly matches our needs: it’s a list with a cursor that we can move left or right one cell at a time – just what we need for the < and > commands. We can also use it for the program itself, since [ and ] require skipping back and forth.
Handling [ and ] is going to be nearly identical, since they both need to find the matching bracket, so we make a function to avoid duplication.
skip :: Eq a => (Zipper a -> Zipper a) -> a -> a -> Zipper a -> Zipper a skip f o c = (\z -> if cursor z == o then skip f o c $ skip f o c z else if cursor z == c then z else skip f o c z) . f
Running a brainfuck program is a simple matter of going through it one command at a time and taking the appropriate action.
run :: String -> IO () run program = f (fromList program) (fromList ) where f p z = if endp p then return () else case cursor p of '>' -> go $ (\x -> if endp x then insert 0 x else x) $ right z '<' -> go $ if beginp z then push 0 z else left z '+' -> go $ replace (succ $ cursor z) z '-' -> go $ replace (pred $ cursor z) z '.' -> putChar (toEnum $ cursor z) >> go z ',' -> go . (`replace` z) . fromEnum =<< getChar '[' -> jump (skip right '[' ']' p) p ']' -> jump p (skip left ']' '[' p) _ -> go z where jump a b = f (right $ if cursor z == 0 then a else b) z go = f (right p)
To test our interpreter, we’ll try to run the brainfuck version of Hello World (I refer you to the Wikipedia article for a description of how it works).
main :: IO () main = run $ "++++++++++[>+++++++>++++++++++>+++>+<<<<-]>+\ \+.>+.+++++++..+++.>++.<<+++++++++++++++.>.++\ \+.------.--------.>+.>.<"
As you can see, at a mere 15 lines a brainfuck interpreter is pretty small. Also, now we know (as if we didn’t already) that Haskell is a Turing-complete language.