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: , , , , , , , ,

2 Responses to “Programming Praxis – Brainfuck interpreter”

  1. Graham Says:

    Where do you get some of the imports? For instance, my GHCi doesn’t include Data.List.Zipper, and a lot of your older posts include imports my interpreter doesn’t have.

  2. Remco Niemeijer Says:

    You can find all packages for Haskell on http://hackage.haskell.org/packages/archive/pkg-list.html. For easy installation, use cabal.

    Data.List.Zipper can be found in the ListZipper package (http://hackage.haskell.org/package/ListZipper). To find out which package contains a certain import, you can use Hayoo or Hoogle.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: