## Programming Praxis – Brainfuck

In today’s Programming Praxis exercise, our goal is to implement a Brainfuck interpreter. Let’s get started, shall we?

Since we’ll be doing a lot of moving left and right in the program and cells a zipper is an obvious data structure to use.

`import Data.List.Zipper`

Running a program is a simple matter of executing all the steps until we arrive at the end, starting with a zeroed-out list.

```run :: String -> IO String
run = fmap toList . flip step (fromList \$ replicate 30000 '\NUL') . fromList

step :: Zipper Char -> Zipper Char -> IO (Zipper Char)
step prog s = if endp prog then return s else
uncurry step =<< instruction (cursor prog) prog s```

Using the zipper, most of the instructions are fairly trivial. The brackets are the only ones that require a bit of extra work.

```instruction :: Char -> Zipper Char -> Zipper Char -> IO (Zipper Char, Zipper Char)
instruction '<' prog s = return (right prog, left s)
instruction '>' prog s = return (right prog, right s)
instruction '+' prog s = return (right prog, replace (succ \$ cursor s) s)
instruction '-' prog s = return (right prog, replace (pred \$ cursor s) s)
instruction '.' prog s = putStr [cursor s] >> return (right prog, s)
instruction ',' prog s = fmap ((,) (right prog) . flip replace s) getChar
instruction '[' prog s = return \$ (if cursor s == '\NUL' then
right \$ move right '[' ']' prog else right prog, s)
instruction ']' prog s = return (move left ']' '[' prog, s)
instruction _   prog s = return (right prog, s)```

Moving the cursor to the corresponding bracket requires stepping over any nested sets of brackets.

```move :: (Zipper Char -> Zipper Char) -> Char -> Char -> Zipper Char -> Zipper Char
move dir open close = f 0 . dir where
f 0 z | cursor z == close = z
f n z = f (if cursor z == open  then n + 1 else
if cursor z == close then n - 1 else n) \$ dir z```

All that’s left to do is to run the program, which prints the expected Hello World message.

```main :: IO ()
main = run "++++++++++[>+++++++>++++++++++>+++>+<\
\<<<-]>++.>+.+++++++..+++.>++.<<++++++\
\+++++++++.>.+++.------.--------.>+.>." >> return ()```