ASCII table in Brainfuck

Question

I made my first Brainfuck program today, which prints the numbers 0-255 and the corresponding character.

I was wondering if I could improve my program, as I'm repeating myself a lot (e.g. 3 x copy & paste "comparer" function):

max   == 255
LF    == 10
space == 32
'0'   == 48
'9'   == 57
':'   == 58
Memory: counter
        ':' space LF
        char max&1 cmp1 0 0
        num1 '9'&1 cmp2 0 0
        num2 '9'&1 cmp3 0 0
        num3 '9'&1 cmp4 0 0

+++++ +++
[
    > +++++ ++
    > ++++
    > +

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

    >>>>
    > +++++ +
    > +++++ ++
    >>>
    > +++++ +
    > +++++ ++
    >>>
    > +++++ +
    > +++++ ++

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

<<<<< <<<<< <<<<< <<<<<

Memory: 0
        58 32  10
        0  256 0 0 0
        48 57  0 0 0
        48 57  0 0 0
        48 57  0 0 0

>>>>> >
+
[
    -

    >>> .
    >>>>> .
    >>>>> .
    <<<<< <<<<< <<<<< <<<
    .
    > .
    >> .
    < .

    Number increasing logic
        >>>>> >>>>> >>>>> >
        +
            Comparer: num1 num2 out 0 0
            [
                -
                >-
                >>>+
                <<<<
            ]
            >>+ set equal flag
            <   if num1 != num2
            [
                >-  clear equal flag
            ]
            >  if num1 == num2
            [
                >
            ]
            >  go to last and put numbers back
            [
                <<<+
                <+
                >>>>-
            ]
            <<<<   reset pointer
        >>
        [
            << ----- -----
            <<<<< +
            >>>>> >> -
        ]
        <<

        <<<<<
            Comparer: num1 num2 out 0 0
            [
                -
                >-
                >>>+
                <<<<
            ]
            >>+ set equal flag
            <   if num1 != num2
            [
                >-  clear equal flag
            ]
            >  if num1 == num2
            [
                >
            ]
            >  go to last and put numbers back
            [
                <<<+
                <+
                >>>>-
            ]
            <<<<   reset pointer
        >>
        [
            << ----- -----
            <<<<< +
            >>>>> >> -
        ]
        <<

    <<<<< <<<<<
    +

        Comparer: num1 num2 out 0 0
        [
            -
            >-
            >>>+
            <<<<
        ]
        >>+ set equal flag
        <   if num1 != num2
        [
            >-  clear equal flag
        ]
        >  if num1 == num2
        [
            >
        ]
        >  go to last and put numbers back
        [
            <<<+
            <+
            >>>>-
        ]
        <<<<   reset pointer

    >>

        Inverter: in/out 0 0
        [
            > +
            < -
        ]
        +
        >
        [
            < -
            > -
        ]
        <
]

Answer 1

Congratulations. This was pretty readable code, by brainfuck standards. I was able to follow it.

By initializing your max cell to 256, you've made your code portable to work on non-wrapping brainfuck interpreters as well. If you just wanted it to work on a wrapping brainfuck interpreter (i.e., one that works modulo 256), you could have left the cell set to 0. I considered changing the program to just loop 256 times instead of comparing the character against the maximum value, but it turns out that 255 times is much easier than looping 256 times when the machine operates modulo 256. You already have a comparison routine, so it's easy to just use it again. (Though preferably not by copying and pasting the code — more on that below.)

While there may be simpler ways to print a number as a decimal string, you asked to optimize for readability, so I have opted to stay close to your original strategy.

The key to readability, I think, is to add strategic comments. In brainfuck, any characters other than the eight commands (><+-.,[]) are ignored. You can also add comments of the form [-][Any comment text goes here], with two caveats:

1. The pointer must be pointing to a cell containing 0 or a cell that you want to be zeroed.
2. Any character can appear inside, as long as square brackets occur in pairs.

The main goals of your comments should be to clarify:

1. What the intention of each chunk of code is.

   It is not so important, in my opinion, to be able to follow every single micro-operation as long as you can understand the big picture.

2. What the memory layout is, and why it is laid out that way.

   I've given "variable names" to all important cells. There is also a long explanatory comment in the code below about what I call "frames", or groups of consecutive cells.

3. Which cell is the current one at any point in the program.

   It's a relatively minor bug if a cell contains the wrong value. However, if the pointer is not where it is supposed to be, the program blows up in a spectacular way. Therefore, I have developed the notation to mark the current pointer location in parentheses at strategic points throughout the code.

---

You raise a valid concern about repeating the comparison routine three times in your code. The way to handle that in brainfuck is to let the routine crawl along the cells, frame by frame, like a construction crew working on a section of highway. Just put the appropriate signposts to let it know where to stop crawling.

---

[-][
    # See MEMORY_LAYOUT below for explanation of SETUP.
]
SETUP
    +++++ +++ [ -
        > +++++ ++      (Colon)
        > ++++          (Space)
        > +             (Newline)

        >>>>>>
        ++++ [ -
            > +++++ +++ (Loop_limit)
            <
        ]

        >>>>> >
        > +++++ ++      (C_limit)
        > +++++ +       (c_ascii)
        >>>>
        > +++++ ++      (X_limit)
        > +++++ +       (x_ascii)
        >>>>
        > +++++ ++      (I_limit)
        > +++++ +       (i_ascii)

        <<<<< <<<<< <<<<< <<<<< <<<<< <<<<
    ]
    > ++                (Colon)
    >> ++ >             (all_done)
    >> + >>>>           (Loop_limit)
    >> + >>>> ++        (C_limit)
    >> + >>>> ++        (X_limit)
    >> + >>>> ++        (I_limit)

    <<<<< <<<<< <<<<< <<<<< <<<<< <<<
END_SETUP

MEMORY_LAYOUT
[-][
    # Using Roman abbreviations i, x, and c for units, tens, and hundreds,
    # respectively.  Braces { } indicate a frame: a repeated consecutive group
    # of cells.  Cells named with Uppercase are constants.  At all times,
    # parentheses indicate the current cell; neighboring cells may be noted
    # as well in the code.

    # The main loop starts working from the last frame.  It compares the last
    # two cells in the frame, and performs a carry if applicable.  It then
    # proceeds to the preceding frame and repeats.  The first "frame" is
    # special, as noted by the first cell being 0.  The comparison routine
    # will not be performed on it.  However, when ascii reaches Loop_limit,
    # all_done will be incremented to 1, since it is located at the offset
    # within the frame where carrying would increment a value.

  { (0)  Colon=":"=58  Space=" "=32  Newline="\n"=10  not_all_done=0 all_done=0 }
  { Compare_frame_0=1  0 0 0  Loop_limit=256       ascii="\0"=0   }
  { Compare_frame_1=1  0 0 0  C_limit=":"=58       c_ascii="0"=48 }
  { Compare_frame_2=1  0 0 0  X_limit=":"          x_ascii="0"    }
  { Compare_frame_3=1  0 0 0  I_limit=":"          i_ascii="0"    }
]
END_MEMORY_LAYOUT

>>>>
+
WHILE (not_all_done) [ -
    # Print one line of output
    >>>>> >>>>> >>> .                   (c_ascii)
    >>>>> > .                           (x_ascii)
    >>>>> > .                           (i_ascii)
    <<<<< <<<<< <<<<< <<<<< <<<<< <<< . (Colon)
    > .                                 (Space)
    >>>>> >>>> .                        (ascii)
    INCR (ascii)
    +
    <<<<< <<< .                         (Newline)

    >>>>> >>>>> >>>>> >>>>> >>>>> >
    INCR (i_ascii)
    +

    <<<<<
    REPEAT (Compare_frame_?) [
        >>>>>
        IFEQ eq_flag=0 ascii_save=0 ?_limit (?_ascii)
            [ -
                < - < + >>
            ] ascii_save=ascii; diff=limit=limit MINUS ascii; ascii=0

            <<< + (eq_flag=1)
            >> [
                << - >> [ - > + < ]
            ]    ifneq { eq_flag=0 ; ascii=diff }; (diff=0)
            # Restore diff
            > [ - < + > ]
            # Restore limit and ascii
            << (ascii_save) [ - > + > + << ]
            < (eq_flag) [
            THEN
                [-][
                    # Perform carrying.  If ascii == Loop_limit, then
                    # "carrying" will set the all_done flag.
                ]
                <<< +
                >>>>> > ----- -----
                <<<
            ]
        END_IFEQ (eq_flag=0) ascii_save=0 ?_limit ?_ascii

        <<<<< <<<
        (Compare_frame_next)
    ]

    >>>>>
    BOOL_NEGATE_AND_CLEAR not_all_done=0 (all_done)
        < +
        > [ - < - > ]
        < (not_all_done)
    END_BOOL_NEGATE_AND_CLEAR
]

It is possible to reduce the frame size by one. However, you would probably have to reuse the same cell for not_all_done and all_done, which would hurt readability.

Answer 2

Analysis

I analyzed your code with my Brainduck and I found a couple of improvements. First up, let's see what Brainduck says. I will not post the full output here, just the parts that I found the most interesting.

First of all, at runtime your program performs approximately 1.47 MILLION commands. This is quite much.

While loop - 49 to 58

My analysis showed interesting patterns in the number of times that your while loops are being performed. I found that some of your while loops have a clear sequence of:

[49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, (repeat 49 - 58 a couple of times...), 49, 50, 51, 52, 53, 54]

This means that the first time it is started it is performed 49 times, then 50, then 51, and so on up until 58, then it goes down to 49 times again, then 50, then 51, etc... this while-loop is your comparison of if (a == b).

What you are doing is comparing if (a == b), this is however a very long operation in Brainfuck, as you need to move the memory back and forth, it has a runtime complexity of \$O(n)\$ where \$n\$ is the value of a.

Modulo 10

There is also this interesting while loop:

[1, 1, 1, 1, 1, 1, 1, 1, 1, 0, (1 x 9 times), 0, (1 x 9 times), 0, (1 x 9 times), 0, (1 x 6 times)]

This is you deciding whether or not to increase the next number in the tape, for example when the last digit changes from 9 to 0 it is time to increase the second to last digit from x to x + 1.

It is much more effective in Brainfuck to count down to zero rather than count up to \$x\$.

Instead of counting from 49 to 58 and comparing x to 58 all the time, initialize a memory cell nearby to 10 and count down to zero, when it has reached zero, it is time to reset it to 10 and increase the next number (going from 09 to 10).

The same principle can be applied to your ending condition, you initialize the value 256, and then you compare with 256 all the time. Instead initialize 256 and decrease it by 1 until it reaches zero, then it is time to end your loop.

Other small changes

Your code contains some sequences of >><< that leads to no change, which leads to it being possible to simplify. I would recommend that you simplify these and instead improve the comments about where the current tape position is located.

Resulting code

max   == 255
LF    == 10
space == 32
'0'   == 48
'9'   == 57
':'   == 58
Memory: counter
        ':' space LF
        char max&1 cmp1 0 0
        num1 '9'&1 cmp2 0 0
        num2 '9'&1 cmp3 0 0
        num3 '9'&1 cmp4 0 0

+++++ +++
[
    > +++++ ++
    > ++++
    > +

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

    >>>>
    > +++++ +
    > +
    >>>
    > +++++ +
    > +
    >>>
    > +++++ +
    > +

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

<<<<< <<<<< <<<<<

Memory: 0
        58 32  10
        0 (Current Ascii) 256 (Countdown) 0 0 0
        48 10  0 0 0
        48 10  0 0 0
        48 10  0 0 0
positioned at 256 countdown
[
    ->

    >>> .
    >>>>> .
    >>>>> .
    <<<<< <<<<< <<<<< <<<
    .
    > .
    >> .+
    < .

    Number increasing logic
        >>>>> >>>>> >>>>> >
        +
            >-
            >+ set equal flag
            <   if num1 != 0
            [
                >-  clear equal flag
            ]
            >  if num1 == 0
            [
                Reset this counter to 10 and decrease digit to 0 again
                <+++++ +++++
                <----- -----
                Increase the next number by one
                <<<<< +
                > -
                Reset the equal flag
                >>>> >> - >
            ]
            <<[<] positioned at the digit

        <<<< goto next

            >>+ set equal flag
            <   if num1 != 0
            [
                >-  clear equal flag
            ]
            >  if num1 == 0
            [
                Reset this counter to 10 and decrease digit to 0 again
                <+++++ +++++
                <----- -----
                Increase the next number by one
                <<<<< +
                > -
                Reset the equal flag
                >>>> >> - >
            ]
            <<[<] positioned at the digit

    <<<<< <<<
]

The only changes here are that I never do if (a == b) comparison and instead always decrease some value down to 0 instead. This applies to both your if (x == 58) checks and your if (x == 256) check.

For 8-bit Brainfuck interpreters

200_success mentioned that your code supported 8-bit Brainfuck interpreters as well, thanks to your if (x == 256) check. As I removed that check here, the above code doesn't work for 8-bit wrapping BF interpreters. However, that can be solved by instead of having one 256 value, you have 2 of value 128.

Replace in the memory initialization:

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

with

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

This will initialize 2 cells with value 128 instead of one cell with value 256. Luckily, the cell after the 256 value was unused by my code, so this is an easy change.

Loop check:

Replace the start of the 256 loop:

[
    ->

with

[[
    ->

and replace the ] on the last line with ]>[-<+>]<].

This will, once the innermost loop has been finished, check for a value on the next cell and if there is a non-zero value there it will move it to the cell before and then it will use that value for the loop and continue decreasing until it hits zero. This will make your loop be performed x + y times, where in this case both x and y is 128, making it a total of 256. Of course these values could be adjusted to be 255 + 1 so that the moving of y to the position of x is performed faster.

Resulting performance

Analysis says that this code, with the support for 8-bit interpreters applied, only performs 30 934 operations at runtime, which is about 2% of your 1.47 million. So this program will be 50 times faster than your original.

Answer 3

I think this would be a more efficient way of doing it (at least for the printable ASCII characters):

++++[->++++++++<]                        Use cell 0 for loop and cell 1 for ASCII codes
++++[->>++++++++<<]>>>                   Use cell 2 for the space
+++>++>                                  Use cells 3 and 4 for the number equivalent
++++++++<<<<<                            Use cell 5 for incrementing the number equivalent
++++++++++++++++++++++++++++++++++++++++
++++++++++++++++++++++++++++++++++++++++ Get 95 for the loop
+++++++++++++++
[>.+>.>.>.+>-[----------<<->>>]<++++++++++<<+ Output ASCII & space & equivalent ASCII code
<<<]                                      Go back to cell 0

Tell me how this works for you. I don't exactly see why you need that comparing function. Also, note that I do use cell 6, but only to escape loops (as it has a value of 0).

The fixed code

Here is some different code with the same original formatting as the one in your question:

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

Answer 4

This seems pretty complicated. The first thing i noticed in your code is many "<<<<>>" commands which could be shortened to "<<".

I just thought about this and made an ASCII viewer by myself. It is only runnable on wrapping 8-bit interpreters but it is much easier to understand.

Tape: [":"(58)] [" "(32)] [lf(10)] [count(0)] [temp] [0] [numPrint]

++++++++[->+++++++>++++>+<<<] set values 0 56 32 8
>++>>++                       set values 0 58 32 10
>+[                           do 255 times (starting at 1)
  [->+>>+<<<]                 copy count to temp and numPrint
  >[-<+>]                     move it back to count

  >>>+[[-]<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->+<[->[-]>>+>+<<<]]]]]]]]]<]>>[>]++++++[-<++++++++>]>>]<<<[.[-]<<<]
                              use number printing routine from Brainfuck Wiki

  <<<<.>.                     print ": "
  >>.                         print symbol
  <.                          print lf
  >+                          increment symbol
]