Hello, Brainfuck

Question

It has been bugging me for a while that while I understand how the basics of Brainfuck works, I can't get a firm grasp on the advanced features of the language. So I started to re-evaluate what I know about the language from the ground up.

Brainfuck's memory consists of a tape of cells. Every cell can be modified by pointing the pointer at it and incrementing or decrementing it's value.

The most basic operators are +, - and .. These operators will respectively increment, decrement and print the data at the current cell. The print operator will take the current value and put the corresponding ASCII character on screen.

To print a basic sentence:

Hello, World!

I've written the following:

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.  Increment to 'H' and print
+++++++++++++++++++++++++++++.                                             Increment to 'e' and print
+++++++.                                                                   Increment to 'l' and print
.                                                                          Value is already at 'l' so just print
+++.                                                                       Increment to 'o' and print
-------------------------------------------------------------------.       Decrement to comma and print
------------.                                                              Decrement to ' ' and print
+++++++++++++++++++++++++++++++++++++++++++++++++++++++.                   Increment to 'W' and print
++++++++++++++++++++++++.                                                  Increment to 'o' and print
+++.                                                                       Increment to 'r' and print
------.                                                                    Decrement to 'l' and print
--------.                                                                  Decrement to 'd' and print
-------------------------------------------------------------------.       Decrement to '!' and print

Writing Brainfuck in this style to print a sentence is pretty straightforward. Iterate over the sentence and do the following per character:

• Calculate the difference between the current character and the previous
• Write either as many + or - as the difference between characters. + if current character is higher than previous character, - if lower than previous character
• Write . to print current character

The result as seen above isn't as bad as it looks. It's very memory efficient since all operations are made on the same cell. But speed is also important. Unfortunately I do not know how to properly time Brainfuck executions (yet).

I'm fairly sure this is not the 'best'/'idiomatic' way of writing this. I know Brainfuck supports a while construction which seems like a good idea here, but I haven't found the most obvious implementation yet. I've seen Simon's method, but I'm not at that level yet.

As usual I don't care about the length of the code (Brainfuck isn't JavaScript after all), but I'm definitely repeating myself an awful lot.

How bad is my current implementation? Pointers as to how to gradually improve this to the more standard style of Brainfuck (using loops instead of repetition) are welcome.

Answer 1

Brainfuck Multiplication

Elaborating a bit more about 200_success' multiplication, and the "shorter, less readable version, using similar ideas, but with more cell reuse":

The ASCII values of what you want to write is, as 200_success mentioned:

72 101 108 108 111 44 32 87 111 114 108 100 33

So these are the numbers we want to generate. Let's start by sorting them:

32 33 44 72 87 100 101 108 108 108 111 111 114

Grouping

Here we notice that we can separate the numbers into different groups. How to do that is a bit opinion-based, but I would chose a 30-50 group, a 70-90 group and a 100+ group, which leaves us with these groups:

32 33 44
72 87
100 101 108 108 108 111 111 114

The idea now is to use multiplication to get three numbers, it is important to remember what number in each group we want to write first. Looking back at our list of ASCII values sorted by the order they appear, we see that we want 72, 101, and 44.

Using a bit of mathematics, we know that \$72 = 7 * 10 + 2\$, \$44 = 4 * 10 + 4\$ and \$101 = 10 * 10 + 1\$.

Generating the numbers

To generate these numbers in BF we will do the typical BF construct:

a++++[-b++++a]

a and b means "go to cell a/b". The number of + signs to use varies with what number you want to generate. As we want to generate three different numbers, we can do this all at once with something like this:

a++++[-b+c++d+++a]

The [...] construct in BF means "while the current cell is not zero", this is the only conditional and looping construct that BF supports, and in reality it is the only thing you actually need. You just need to know how to use it.

As we already start on cell a, we can write our construct like this:

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

This will generate 4 * 1, 4 * 2 and 4 * 3, respectively. Adjusting the number of + signs leave us with:

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

That is, 10 * 4, 10 * 7 and 10 * 10.

So now we can use these values to write our string. The values we have are 40, 70 and 100, so we will go to the different cells and change their values slightly up and down to get and print the numbers we want.

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

Comments and formatting

Now we clean up the formatting and add a bit of comments:

+++++ +++++ [-          10 times
  >++++                 10 * 4 = 40
  >+++++ ++             10 * 7 = 70
  >+++++ +++++          10 * 10 = 100
  <<<] 40 70 100
>>++.                     40 72 100 print 'H'
>+.+++++ ++..+++.         40 72 111 print 'ello'
<<++++.----- ----- --.    32 72 111 print comma and space
>+++++ +++++ +++++.       32 87 111 print 'W'
>.+++.----- -.----- ---.  32 87 100 print 'orld'
<<+.                      33 87 100 print '!'

Brainfuck doesn't have any guidelines (that I know of) about indentation, formatting and comments, so how you do those parts is entirely up to you.

Personally, when writing Brainfuck, I find it extremely important to keep track of the values of the memory tape, which is why I prefer adding comments about what the values of the memory tape are. Then if you want to edit anything you can more easily change what you want to change by reading your comments about the values of the memory tape.

Performance

It's very memory efficient since all operations are made on the same cell. But speed is also important. Unfortunately I do not know how to properly time Brainfuck executions (yet).

The most reasonable way to time Brainfuck executions is to count the number of instructions being performed at runtime.

I added a feature to my Brainfuck Interpreter to allow me to easily count this.

I also used a certain Brainfuck Developer IDE that includes a "Text generator" tool to generate BF code for your string, this tool produced the following code:

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

Here is an overview of the number of instructions being performed at run-time in the different versions:

$$ \newcommand{smallm}[0]{\overset{n\ \gg\ m}{\longrightarrow}} \begin{array}{|l|c|c|} \hline \\ & \textrm{Your code} & \textrm{200_success A} & \textrm{200_success B} & \textrm{My code} & \textrm{bfdev tool} \\ \hline \\ \textrm{Next} & 0 & 99 & 69 & 35 & 39 \\ \hline \\ \textrm{Previous} & 0 & 90 & 64 & 34 & 39 \\ \hline \\ \textrm{Print} & 13 & 13 & 13 & 13 & 13 \\ \hline \\ \textrm{Add} & 193 & 709 & 466 & 256 & 226 \\ \hline \\ \textrm{Subtract} & 160 & 21 & 22 & 36 & 193 \\ \hline \\ \textrm{Start While} & 0 & 1 & 1 & 1 & 6 \\ \hline \\ \textrm{End While} & 0 & 10 & 10 & 10 & 33 \\ \hline \\ \textrm{Total} & 366 & 943 & 645 & 385 & 549 \\ \hline \end{array}$$

And here is an overview of the source code length of the different versions:

Your code      : 366
200_success A  : 151
200_success B  : 123
My code        : 124
bfdev generated: 185

As you can see, using loops doesn't normally improve performance. The reason for this is that instead of using only one cell, loops uses more. There is no faster way to go from 0 to 100 than to write + 100 times. Using loops does however reduce code length.

I suggest that you try to aim for a combination of less code and few instructions at runtime. If you are concerned with performance, you shouldn't use Brainfuck in the first place ;)

Another small improvement

The order of the tape values does matter a little bit. I realized that the order you wanted to go to the cells was 70 100 40 70 100 40, but my BF program kept the cells in the order 40 70 100. So by reordering the cells slightly, I saved 2 run-time instructions and reduced source code length by 2! (Yay!)

My updated code: (383 run-time instructions, source code length 122)

+++++ +++++ [-          10 times
  >+++++ ++             10 * 7 = 70
  >+++++ +++++          10 * 10 = 100
  >++++                 10 * 4 = 40
  <<<] 70 100 40
>++.                      40 72 100 print 'H'
>+.+++++ ++..+++.         40 72 111 print 'ello'
>++++.----- ----- --.     32 72 111 print comma and space
<<+++++ +++++ +++++.      32 87 111 print 'W'
>.+++.----- -.----- ---.  32 87 100 print 'orld'
>+.                       33 87 100 print '!'

Answer 2

No, that's unreadable code and therefore not idiomatic. The typical way to generate large numbers is to use multiplication.

"Hello, World!" translates to ASCII values

< 72, 101, 108, 108, 111, 44, 32, 87, 111, 114, 108, 100, 33 >

… which can be thought of as

10 * < 7, 10, 11, 11, 11,  4,  3,  9, 11, 11, 11, 10, 3 >
   + < 2,  1, -2, -2,  1,  4,  2, -3,  1,  4, -2,  0, 3 >

The code should therefore be written that way. The consecutive elevens can lead to a compression optimization.

+++++ +++++ [- >
 +++++ ++ >
 +++++ +++++ >
 +++++ +++++ + >
 ++++ >
 +++ >
 +++++ ++++ >
 +++++ +++++ + >
 +++++ +++++ >
 +++ <<<<< <<<<
]                        Print:
> ++ .                   "H"
> + .                    "e"
> -- .. +++ .            "llo"
> ++++ .                 comma
> ++ .                   space
> --- .                  "W"
> + . +++ . ----- - .    "orl"
> .                      "d"
> +++ .                  "!"

For readability, you should also group the increment and decrement operators in fives. I also find your comments unnecessarily verbose.

This solution uses more memory cells than the original code. It's well worth it for the readability, in my opinion.

---

Here's a shorter, less readable version, using similar ideas, but with more cell reuse.

+++++ +++++ [- >
 +++++ ++ >
 +++++ +++++ >
 +++++ +++++ + >
 ++++ >
 +++ >
 +++++ ++++ <<<<< <
]                        Print:
> ++ .                   "H"
> + .                    "e"
> -- .. +++ .            "llo"
> ++++ .                 comma
> ++ .                   space
> --- .                  "W"
<<< . +++ . ----- - .    "orl"
< - .                    "d"
>>> + .                  "!"