Code Golf: Brainfuck Interpreter

Brainfuck Interpreter in two tweets.

Previous article Code Golf: Game of Life raised some interest, and I decided to proceed. Today's problem is a Brainfuck Interpreter.

Brainfuck is an esoteric programming language, famous because of its small command set. It is based on array of cells (Turing Tape) and pointer to this array. There are only 8 commands:

That's all. Brainfuck is Turing Complete language, that means it capable to implement any program. If you crazy, of course.

Tweet

Final version took 280 characters in Clojure:

(fn[a p k c](let[h #(nth %1@%2)e #(h a p)s #(swap! %1%2 1)t
#(aset a@p(%(e)1))l #(do(s k %)(case(h c k)\]()\[()(recur %)
))](while(>(count c)@k)(do(case(h c k)\>(s p +)\<(s p -)\+
(t +)\-(t -)\.(print(char(e)))\,(aset a@p(.read *in*))\[(if
(=(e)0)(l +))\](if(>(e)0)(l -)))(s k +)))))

Exactly 2 tweets.

"Sugared" version

Translating to more readable code:

(defn parse-internal [a pt pc cs]
  (letfn [(act []
            (case (nth cs @pc)
              \> (swap! pt inc)
              \< (swap! pt dec)
              \+ (aset a @pt (inc (nth a @pt))) 
              \- (aset a @pt (dec (nth a @pt)))
              \. (print (char (nth a @pt)))
              \, (aset a @pt (.read *in*))
              \[ (if (zero? (nth a @pt)) (loop- inc))
              \] (if-not (zero? (nth a @pt)) (loop- dec))))
          (loop- [f]
            (do (swap! pc f)
                (case (nth cs @pc)
                  \[ ()
                  \] () 
                  (recur f))))]
    (while (not= (count cs) @pc)
      (do
        (act)
        (swap! pc inc)))))

So, what's happening there?

Function arguments are parameters of our tape and brainfuck program.

Function act decides which action to perform depending on current command, loop allows us to move command pointer inside a loop, and main while-do loop executes commands until they exhausted. Simple enough.

To make our interpreter more friendly we create function parse that accepts string - program, written in brainfuck.

(defn parse [s]
  (let [a (int-array 100)  ;; Turing Tape
        p (atom 0)         ;; Pointer to Tape
        k (atom 0)         ;; Pointer to Command
        c (vec (seq s))]   ;; Vector of Commands
    (parse-internal a p k c)))

Testing

Print "Hello, world"

(parse "++++++++++[>+++++++>++++++++++>+++>+<<<<-]
        >++.>+.+++++++..+++.>++.<<+++++++++++++++.>
        .+++.------.--------.>+.>.") =>
Hello World!

Input 5 characters and reverse print them

(parse ",>,>,>,>,.<.<.<.<.") => <wait input "hello">
olleh

More complex program need nested loops, which is not supported by this version (for the sake of small size!)

History of implementation, nested loops and more available here

P.S. This version is not "fully-featured" brainfuck interpreter.

But, you are welcome to improve it!

mishadoff 09 August 2013
blog comments powered by Disqus