Programming Praxis – Brainfuck interpreter

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.

import Data.List.Zipper

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 [0]) 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.

About these ads

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