## Posts Tagged ‘interpreter’

### Programming Praxis – Fractran

July 6, 2012

In today’s Programming Praxis exercise, our goal is to write an interpreter for the esotreric programming language Fractran and use it to execute a program that generates prime numbers. Let’s get started, shall we?

A quick import:

`import Data.List`

The fractran interpreter itself is pretty simple. We use tuples to represent the fractions rather than Ratios since this made for slightly more elegant code. Unfortunately the Prelude doesn’t have a function to swap the values of a tuple, or I could’ve use divMod rather than having to repeat the multiplication.

```fractran :: [(Integer, Integer)] -> Integer -> [Integer]
fractran xs = unfoldr (\m -> fmap ((,) m) . lookup 0 \$
map (\(n,d) -> (mod (m*n) d, div (m*n) d)) xs)```

Since we’re using tuples, we represent the primegame program as a zip.

```primegame :: [(Integer, Integer)]
primegame = zip [17,78,19,23,29,77,95,77, 1,11,13,15,15,55]
[91,85,51,38,33,29,23,19,17,13,11,14, 2, 1]```

Finding the primes is a matter of finding the terms in the output of fractran primegame 2 that are powers of two.

```primes :: [(Integer, Integer)]
primes = [(i,e) | (i,n) <- zip [1..] \$ fractran primegame 2
, let e = round \$ log (fromIntegral n) / log 2, 2^e == n]```

A test to see if everything is working properly:

```main :: IO ()
main = mapM_ print \$ take 26 primes```

### Programming Praxis – Brainfuck

October 4, 2011

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

### Programming Praxis – Brainfuck interpreter

May 14, 2010

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.