More Brainf*ck
Friday, May 16, 2025
Almost 16 years ago, I wrote about implementing the Brainfuck programming language in Factor. It is a curious programming language, sometimes considered one of the most famous esoteric programming languages.
In any event – and encouraged by a question I was asked recently – I spent some time thinking about the current process of “compiling” the Brainfuck into quotations versus how an interpreter might work instead.
As a quick reminder, our current implementation expands a program written in Brainfuck into an equivalent form in Factor, and then allows it to be run:
IN: scratchpad USE: brainfuck
IN: scratchpad "
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++
.>.+++.------.--------.>+.>.
" run-brainfuck
Hello World!
IN: scratchpad [
"
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++
.>.+++.------.--------.>+.>.
" run-brainfuck
] expand-macros .
[
<brainfuck> 10 (+)
[ get-memory zero? ] [
1 (>) 7 (+) 1 (>) 10 (+) 1 (>) 3 (+) 1 (>) 1 (+) 4 (<)
1 (-)
] until 1 (>) 2 (+) (.) 1 (>) 1 (+) (.) 7 (+) (.) (.) 3 (+)
(.) 1 (>) 2 (+) (.) 2 (<) 15 (+) (.) 1 (>) (.) 3 (+)
(.) 6 (-) (.) 8 (-) (.) 1 (>) 1 (+) (.) 1 (>) (.) drop flush
]
Notice the coalescing that it performs to collapse multiple identical operators into a single action.
But, this got me curious about a couple of things:
- How could we cleanly write a Factor word that is implemented in Brainfuck?
- How could we write a Factor interpreter for Brainfuck, and what benefits would it have?
Building a syntax word
Thankfully, the answer to the first question is simple using parsing words.
SYNTAX: BRAINFUCK:
scan-new-word ";" parse-tokens concat
'[ _ run-brainfuck ] ( -- ) define-declared ;
Now, we can define a Hello, World, complete with inline comments:
BRAINFUCK: hello
+++++ +++ ! Set Cell #0 to 8
[
>++++ ! Add 4 to Cell #1; this will always set Cell #1 to 4
[ ! as the cell will be cleared by the loop
>++ ! Add 4*2 to Cell #2
>+++ ! Add 4*3 to Cell #3
>+++ ! Add 4*3 to Cell #4
>+ ! Add 4 to Cell #5
<<<<- ! Decrement the loop counter in Cell #1
] ! Loop till Cell #1 is zero
>+ ! Add 1 to Cell #2
>+ ! Add 1 to Cell #3
>- ! Subtract 1 from Cell #4
>>+ ! Add 1 to Cell #6
[<] ! Move back to the first zero cell you find; this will
! be Cell #1 which was cleared by the previous loop
<- ! Decrement the loop Counter in Cell #0
] ! Loop till Cell #0 is zero
! The result of this is:
! Cell No : 0 1 2 3 4 5 6
! Contents: 0 0 72 104 88 32 8
! Pointer : ^
>>. ! Cell #2 has value 72 which is 'H'
>---. ! Subtract 3 from Cell #3 to get 101 which is 'e'
+++++ ++..+++. ! Likewise for 'llo' from Cell #3
>>. ! Cell #5 is 32 for the space
<-. ! Subtract 1 from Cell #4 for 87 to give a 'W'
<. ! Cell #3 was set to 'o' from the end of 'Hello'
+++.----- -.----- ---. ! Cell #3 for 'rl' and 'd'
>>+. ! Add 1 to Cell #5 gives us an exclamation point
>++. ! And finally a newline from Cell #6
;
And, it works!
IN: scratchpad hello
Hello World!
Note: we are using ! as a comment character which is the convention in
Factor. Some Brainfuck implementations use that character to indicate embedded
program inputs.
That’s pretty cool, and a neat example of using the lexer, the parser, and macros.
Building an interpreter
The answer to the second question might be more complex and nuanced, but thankfully we can re-use some of the current implementation to make a quick-and-dirty interpreter:
: end-loop ( str i -- str j/f )
CHAR: ] swap pick index-from dup [ 1 + ] when ;
: start-loop ( str i -- str j/f )
1 - CHAR: [ swap pick last-index-from dup [ 1 + ] when ;
: interpret-brainfuck-from ( str i brainfuck -- str next/f brainfuck )
2over swap ?nth [ 1 + ] 2dip {
{ CHAR: > [ 1 (>) ] }
{ CHAR: < [ 1 (<) ] }
{ CHAR: + [ 1 (+) ] }
{ CHAR: - [ 1 (-) ] }
{ CHAR: . [ (.) ] }
{ CHAR: , [ (,) ] }
{ CHAR: # [ (#) ] }
{ CHAR: [ [ get-memory zero? [ [ end-loop ] dip ] when ] }
{ CHAR: ] [ get-memory zero? [ [ start-loop ] dip ] unless ] }
{ f [ [ drop f ] dip ] }
[ blank? [ "Invalid input" throw ] unless ]
} case ;
: interpret-brainfuck ( str -- )
0 <brainfuck> [ interpret-brainfuck-from over ] loop 3drop ;
And give it a try:
IN: scratchpad "
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++
.>.+++.------.--------.>+.>.
" interpret-brainfuck
Hello, World!
It works! But now I’m curious about relative performance. Let’s build a silly benchmark equivalent to cat to redirect the contents of an input-stream to an output-stream. We can compare our compiled run-brainfuck macro to a version that uses the interpreter we made above and then to a native version implemented using stream-copy.
: cat1 ( -- ) ",[.,]" run-brainfuck ;
: cat2 ( -- ) ",[.,]" interpret-brainfuck ;
: cat3 ( -- ) input-stream get output-stream get stream-copy* ;
First, we should make sure they both work:
IN: scratchpad "Compiled" [ cat1 ] with-string-reader
Compiled
IN: scratchpad "Interpreted" [ cat2 ] with-string-reader
Interpreted
IN: scratchpad "Factor" [ cat3 ] with-string-reader
Factor
Okay, so it seems to work!
For quick performance testing, lets compare them outputting to a null stream:
IN: scratchpad [
1,000,000 CHAR: a <string> [
[ cat1 ] with-null-writer
] with-string-reader
] time
Running time: 0.059820291 seconds
IN: scratchpad [
1,000,000 CHAR: a <string> [
[ cat2 ] with-null-writer
] with-string-reader
] time
Running time: 0.13840325 seconds
IN: scratchpad [
1,000,000 CHAR: a <string> [
[ cat3 ] with-null-writer
] with-string-reader
] time
Running time: 0.015008417 seconds
The compiled one is a bit more than 2x faster than the interpreted
version, but both are slower than the native version.
Let’s try comparing our “Hello, World” example – where the operator coalescing that the compiled version does might help:
: hello1 ( -- )
"
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++
.>.+++.------.--------.>+.>.
" run-brainfuck ;
: hello2 ( -- )
"
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++
.>.+++.------.--------.>+.>.
" interpret-brainfuck ;
We can see that the compiled one is now more like 7x faster:
IN: scratchpad [ [ 10,000 [ hello1 ] times ] with-null-writer ] time
Running time: 0.018075292 seconds
IN: scratchpad [ [ 10,000 [ hello2 ] times ] with-null-writer ] time
Running time: 0.133718416 seconds
Obviously, this is somewhat comparing apples and oranges because it’s ignoring compilation time in the comparison, and I didn’t spend any time on optimizing the interpreted version – for example, stripping blanks or validating inputs before doing the interpreter loop – but it’s a useful starting point for understanding tradeoffs.
How long does it currently take to compile?
IN: scratchpad [
[
gensym [
"
++++++++++[>+++++++>++++++++++>+++>+<<<<-]
>++.>+.+++++++..+++.>++.<<+++++++++++++++
.>.+++.------.--------.>+.>.
" run-brainfuck
] ( -- ) define-declared
] with-compilation-unit
] time
Running time: 0.02294075 seconds
…a bit more time than it takes to call it 10,000 times. Interesting.