Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Implementing Control Structures in Brainfuck

For the uninitiated, Brainfuck is a Turing-complete language with only 8 commands, all of which have literal equivalents in C:

bf    c
----------------------
>     ++ptr;
<     --ptr;
+     ++*ptr;
-     --*ptr;
.     putchar(*ptr);
,     *ptr=getchar();
[     while (*ptr) {
]     }

On any linux distro that has a package manager, you ought to be able to find and install the package beef, a Brainfuck interpreter so you can play along at home.

As you can see above, Brainfuck has but one control structure, […] which translates to C as:

while (*ptr) { … }

Which gives you all the control of IF VAR = 0 THEN GOTO 10 from BASIC. The following will call getchar() until it returns 0:

,    # *ptr = getchar();
[    # while (*ptr) {
  >,    # *(++ptr) = getchar();
]    # }

But what if I only want to read to a newline char \n? After having some difficulty wrapping my brain around how this could be adapted to work as a simple if I came up with the following:

,            # *ptr = getchar();      /* store input                               */
----------   # *ptr -= 10;            /* test for \n by subtracting 10 before loop */
[            # while (*ptr) {         /* if *ptr == 0, last char read was \n       */
  ++++++++++   # *ptr += 10;          /*   wasn't \n, add 10 back to val under ptr */
  >,           # *(++ptr) = getchar();
  ----------   # *ptr -= 10;
]            # }

(If anyone has a better way of doing this, please let me know)

Now lets say I want to test break out of that loop on \r in addition to \n. How can I test for either, given that I only have one opportunity to break out of the loop? My goal is to be able to emulate switch, nested ifs or if/else ifs.

like image 247
Ryan Tenney Avatar asked Aug 06 '10 06:08

Ryan Tenney


3 Answers

Here are algorithms to perform basic LOGICAL but complex operation for Brain F*ck :)

like image 87
jmj Avatar answered Nov 08 '22 12:11

jmj


I didn't take a look at the link yet, but I imagine that AShelly's answer is probably more universally useful...however, having not dared to let my fingers type out some Brainfuck before, I decided that now was as good of a time as any and was able to get the following, which I think works.

The second half is just for printing out what was captured by the first part. Also, I won't lie, my brain does indeed feel thoroughly "fucked" after having tried to work this out...A very aptly-named language, heh.

+
[
    >,
    ----------
    [
        ---
        [
            +++++++++++++
            >>
        ]
    ]

    <
    [
      >>
    ]
    <
]

++++++++++++
[
    <
]

>
[
    .>
]
like image 3
Tim Stone Avatar answered Nov 08 '22 13:11

Tim Stone


See this page for a description of how to start with the single BF control structure and define a series of increasingly complex sequences representing more sophisticated operations.

like image 3
AShelly Avatar answered Nov 08 '22 13:11

AShelly