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 ()

About these ads

Tags: bonsai, brainfuck, code, Haskell, interpreter, kata, praxis, programming