Sunday, June 7, 2009

Brainf*ck

The Brainfuck programming language is a curious invention. Seemingly useful only for proving oneself as a True Geek at a party, it could also be useful for educational purposes.

The first programming example in any language is typically "Hello, world!". In Brainfuck, this could be written as:

++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++
.>.+++.------.--------.>+.>.

For fun, I thought I would build a Brainfuck compiler for Factor.

( scratchpad ) USE: brainfuck

( scratchpad ) "
               ++++++++++[>+++++++>++++++++++>+++>+<<<<-]
               >++.>+.+++++++..+++.>++.<<+++++++++++++++
               .>.+++.------.--------.>+.>.
               " run-brainfuck
Hello World!

Behind the scene, the Brainfuck code is being compiled into proper Factor using a macro that parses the Brainfuck code string. When translated into Factor, the "Hello, world!" example becomes:

<brainfuck>
10 (+) [ (?) ] [
    1 (>) 7 (+) 1 (>) 10 (+) 1 (>) 3 (+)
    1 (>) 1 (+) 4 (<) 1 (-)
] while
1 (>) 2 (+) (.) 1 (>) 1 (+) (.)
7 (+) (.) (.) 3 (+) (.) 1 (>) 2 (+) (.)
2 (<) 15 (+) (.) 1 (>) (.) 3 (+)
(.) 6 (-) (.) 8 (-) (.) 1 (>) 1 (+) (.) 
1 (>) (.) drop flush

I made only a slight optimization, which you might notice above, to collapse a series of identical operators together into a single call to the operator word, while staying true to the original set of Brainfuck operators.

Some fun examples of Brainfuck in the brainfuck-tests.factor unit tests include addition, multiplication, division, uppercase, and a cat utility.

It is available on my Github, and hopefully will be pulled into the main repository soon.

No comments: