44
\$\begingroup\$

Just joking guys, Brainfuck is an awesome, challenging language.

I've tested the following code with bf-x86 compiler and rather big JSON file. I believe code is fully functional on a valid (!) JSON input.

That's my second JSON formatter and my first code in Brainfuck. I know nothing about best practices and code style, though I've tried to do my best in both parts.

Points of interest:

  • code style and formatting
  • value of comments
  • value of used algorithms and preferable alternatives

The heart of a program is a reading loop with a switch statement:

#!/usr/bin/brainduck

This program is a JSON formatter
It takes a valid(!) JSON input and outputs formatted JSON


Memory layout used:
0   input
1   input copy
2   switch flag
3   input copy for switch
4   indent
5   indent copy
6   indent copy
Zero separated strings
7   zero
8   placeholder
?   zero
?   JSON specific chars
?   zero
?   "while inside string" memory


Zero separated strings

Filling placeholder "  " (two spaces)
>>>>>>>
>  >++[-<++++++++++++++++>]<
>  >++[-<++++++++++++++++>]<
>zero

Filling JSON specific chars after placeholder
>  0a  \n              ++++++++++
>  20  space           >[-]++[-<++++++++++++++++>]<
>zero

Back to cell 0
<[<]<[<]<<<<<<<


Initial input
,

while input [

    Input in cell 0 already

    Zeroing memory in cells 1 2 3
    >[-]>[-]>[-]<<<

    Copying input to cells 1 3
    [-
        >+<
        >>>+<<<
    ]

    switch flag = on
    >>+

    >


    The Switch

    switch cell 3
    \t  ---------[
    \n           -[
    \r            ---[
    space            -------------------[
    "                                   --[
    comma                                 ----------[
    :                                               --------------[
    ( square bracket                                              ---------------------------------[
    ) square bracket                                                                               --[
    {                                                                                                ------------------------------[
    }                                                                                                                              --

    default [[-]<-
        in each switch case <.> outputs current char
    >]

    case '}' <[-

        Newline              >>>>>>[>]>.
        Back to cell 2       [<]<[<]<<<<<
        Decrementing indent  >>-
        Copying indent       [->+>+<<]
        Placeholders         >>[->>[.>]<[<]<]
        Copying indent back  <[-<+>]
        Back to cell 2       <<<
        Closing brace        <.>
    ]>]

    case '{' <[-

        Opening brace        <.>
        Newline              >>>>>>[>]>.
        Back to cell 2       [<]<[<]<<<<<
        Incrementing indent  >>+
        Copying indent       [->+>+<<]
        Placeholders         >>[->>[.>]<[<]<]
        Copying indent back  <[-<+>]
        Back to cell 2       <<<
    ]>]

    case closing square bracket <[-

        Newline              >>>>>>[>]>.
        Back to cell 2       [<]<[<]<<<<<
        Decrementing indent  >>-
        Copying indent       [->+>+<<]
        Placeholder          >>[->>[.>]<[<]<]
        Copying indent back  <[-<+>]
        Back to cell 2       <<<
        Closing bracket      <.>
    ]>]

    case opening square bracket <[-

        Opening bracket      <.>
        Newline              >>>>>>[>]>.
        Back to cell 2       [<]<[<]<<<<<
        Incrementing indent  >>+
        Copying indent       [->+>+<<]
        Placeholders         >>[->>[.>]<[<]<]
        Copying indent back  <[-<+>]
        Back to cell 2       <<<
    ]>]

    case ':' <[-

        Colon                <.>
        Space                >>>>>>[>]>>.
        Back to cell 2       [<]<[<]<<<<<
    ]>]

    case comma <[-

        Comma                <.>
        Newline              >>>>>>[>]>.
        Back to cell 2       [<]<[<]<<<<<
        Copying indent       >>[->+>+<<]
        Placeholder          >>[->>[.>]<[<]<]
        Copying indent back  <[-<+>]
        Back to cell 2       <<<
    ]>]

    case '"' <[-

        Quotation mark       <.>
        Going to string memory after JSON chars
                             >>>>>>[>]>[>]>

        Memory layout:
        0   string loop flag
        1   switch flag
        2   string input
        3   escape flag
        4   temp

        Zeroing memory
        [-]>[-]>[-]>[-]>[-]<<<<

        string loop flag = on
        +

        while string loop flag [

            Echo string char >>,.

            if escape flag >>[-]+<[

                escape flag = off
                [-]

                >-<
            ]
            else >[-

                switch cell 2 <<<+>
                "  ----------------------------------[
                \                                    ----------------------------------------------------------

                default [<->[-]]

                case '\' <[-

                    escape flag = on
                    >>+<<
                ]>]

                case '"' <[-

                    Unescaped quote ends string
                    string loop flag = off
                    <->
                ]>
                >>

            ]<<<<
        ]

        Back to switch cell
        <<[<]<[<]<<<<<
    ]>]

    Skipping original formatting
    case space <[-]>]
    case '\r'  <[-]>]
    case '\n'  <[-]>]
    case '\t'  <[-]>

    Back to cell 0
    <<<

    Next char
    ,
]

Code minification produces 923 bytes long program.

With help of Brainfuck shebang or compiler it can be pretty usable console application:

$ cat example.json
{"foo":"bar","baz":["\"rogue\" {s}tring",1,2,3.2e1]],"t":true,"f":false,"n":null}
$
$ ./pretty-json < example.json
{
  "foo": "bar",
  "baz": [
    "\"rogue\" {s}tring",
    [
      1,
      2,
      3.2e1
    ]
  ],
  "t": true,
  "f": false,
  "n": null
}

Well, good luck, you guys!

\$\endgroup\$
1
  • 11
    \$\begingroup\$ Whaaaaaat! This is probably the most useful Brainfuck program I've seen so far. Surely beats my FizzBuzz. I'm putting this on my Brainfuck review TODO-list. \$\endgroup\$ May 16 '18 at 17:02
4
+50
\$\begingroup\$

Your code is impressingly well structured and easy to follow, thanks to its comprehensive documentation.

The first thing I noticed that I would do differently is when initializing the space character. Your code reads:

>  20  space           >[-]++[-<++++++++++++++++>]<

You can leave out the [-] since the memory is zeroed out when the process starts.

There are some instances where adjacent <> or >< can be eliminated, but that job should be left to the compiler, since these are well-known optimization techniques. Having code that expresses its intention clearly is more important than doing the compiler's job.

Back to cell 0
<[<]<[<]<<<<<<<

Since there are exactly 2 JSON-specific characters, I would have replaced the first [<] with the simpler <<. This applies to the other situations as well where the code skips over this zero-terminated string.

When I saw the placeholder string, I thought about storing the indentation string as a plain number instead. I don't know whether this would make the code simpler overall. Did you try that?

Representing the indentation string as a number would additionally prevent it from consisting of characters other than spaces and tabs. Having other characters could produce malformed JSON.

Instead of naming it "placeholder", a more accurate name would be "indentation string", but that could easily be confused with the "indent", which then would have to be named "indentation depth".

Memory cells 5 and 6 both contain the "indent copy". This could be documented a little more detailed, to prevent confusion. It would be nice to know at which points in time each of these cells contains valid data.

In the two switch blocks you rely on the VM allowing numeric underflow, which is not guaranteed. I would have preferred code that deals with this situation in the most portable manner, but that would have been much more complicated, I guess.

in each switch case <.> outputs current char

This line confused me since it embeds code into a string that otherwise looks like a comment. You didn't state in your description that you intended to participate in the Underhanded Brainfuck Contest, and the rest of your code doesn't look that way. Or does it? That's hard to tell.

Newline              >>>>>>[>]>.
Back to cell 2       [<]<[<]<<<<<

I would have combined these two lines into a single line to keep the data pointer on cell 2 consistently, thereby making the comment in the second line redundant. As I already mentioned above, I would replace the first [<] with a simple <, to make it symmetric with the single > in the line above.

I like the shortcut you took for skipping the string escapes, even if that means that the code does not mirror each syntactical rules of the JSON format on its own. The gain in code simplicity is worth more in this case.

Overall, it's a really good example of careful program design, memory management, algorithms, design patterns and efficiency.

\$\endgroup\$
2
  • \$\begingroup\$ Wow, that's a great review, thanks a lot! Regarding the use of [>]: I wanted to support several spaces as a placeholder, (say 2 or 4), thats the reason I've done zero terminated strings. \$\endgroup\$
    – sineemore
    Jan 16 '20 at 18:31
  • 1
    \$\begingroup\$ And, yeah, in each switch case <.> outputs current char actually was Underhanded Brainfuck Contest participation ^.^ I simply could not resist \$\endgroup\$
    – sineemore
    Jan 16 '20 at 18:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.