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.