I just finished an initial release of an interpreter for the befunge programming language, based on the ‘93 spec. The project was quite fun! My goal was to produce a well-designed program with performance that didn’t suck too bad. Here are some highlights:

Design

I found that writing the core functionality of the interpreter took almost no time, once I settled on the approach I would take. I used a monad transformer for the first time, StateT:

1

type REPL a = StateT ProgramState IO a

This let me pass around the state of the computation in the State monad while doing IO actions. This made some potentially-awkward befunge commands really easy to implement.

Here is an excerpt from the function execute :: Char -> REPL () which reads the befunge character at our position and returns the code to execute:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

    -- Pop value and output as an integer. funge-98 spec calls for  
    -- integer to be followed by a space, so we'll do that too:  
    '.' -> do i <- pop
              liftIO $ putStr $ show i ++" "

    -- Pop value and output as ASCII character  
    ',' -> do i <- pop
              liftIO $ putChar $ chr i

    '\\' -> do (a,b) <- pop2
               push a
               push b

    ':' -> do a <- pop
              replicateM_ 2 (push a)

    -- program flow commands: --  
    ' ' -> return ()

    '>' -> setDirection right

    '<' -> setDirection left

    '^' -> setDirection up

    'v' -> setDirection down

    '?' -> getRandomDirection >>= setDirection
 ```


And here is the program state that gets passed in the monad:

haskell data ProgramState = ES { – state of the code and stack:

    code :: Code,
    stack :: Stack,
 -- state of program flow:  
    position :: Position,
    direction :: Direction,
    haltBit :: Bool,
 -- random generator:  
    randGen :: StdGen,
 -- errors or other messages we collect:  
    messages :: [String],
 -- should we announce messages and warnings?:  
    verbose :: Bool

}

1
2
3
4
5
6
7

I only use the accessor functions (as opposed to pattern matching) to reach
into the state in my code, so it was easy to add another state parameter if I
wanted to extend the functionality somewhere.

Finally here is the evaluation loop that ties the core of the interpreter
together:

haskell evalLoop :: REPL () evalLoop = do

-- extract the command at our position & execute it:  
getCmd >>= execute
-- print messages in the queue (unless quiet), and clear it:  
printMessages
-- halt if @ command issued, else move and recurse:  
halting <- gets haltBit
unless halting (move >> evalLoop)

“`

I found the most time-consuming parts of this project were in the design decisions and behaviour tweaks related to holes in the ‘93 spec, and tracking down a few silly bugs that came from wrong assumptions about the spec.

Vital in debugging were the CCBI interpreter as well as the pyfunge interpreter. It’s difficult to debug an interpreter when you don’t whether the befunge code you are testing on is buggy or whether your interpreter is!

One last detail that I am proud of is the test suite that I have integrated into my darcs repo. Darcs automatically runs the befunge-93 portion of the amazing mycology test suite by Matti Niemenmaa on each commit, as well as two smaller test befunge programs from phlamethrower, testing that the interpreter hasn’t changed behavior.

Play With It

You can check out the full source for the program here, or get my whole darcs repository with:

$ darcs get --tag=v0.2 http://coder.bsimmons.name/code/Befunge

try out some programs from vsync’s funge stuff here.

There is still a lot that could be done, but I think I’m done with it for now. Thanks for looking!