Brainfuck

From Bauman National Library
This page was last modified on 1 June 2016, at 17:17.
Brainfuck
Paradigm esoteric
Designed by Urban Müller
First appeared 1993
OS crossplatform
Filename extensions .b, .bf
Website None
Influenced by
FALSE

Brainfuck is a one of the most famous esoteric programming language invented by Urban Mueller for fun. The language has eight commands, each of which is recorded by one symbol.

History

Urban Muller invented Brainfuck language in 1993. Müller designed Brainfuck with the goal of implementing with the smallest possible compiler, inspired by the 1024-byte compiler for the FALSE programming language. Several brainfuck compilers have been made smaller than 200 bytes[1]. Brainfuck programms is difficult to write. That is why brainfuck called masohists' language. Importantly Brainfuck is a Turing-complete and simple language and can be used in the definition of computability.

Brainfuck machine consists of an ordered set of cells and the index of the current cell, reminding the tape and the head of the Turing machine. In addition, the device is meant to communicate with the user (see. command . and ,) through the input and output streams.

Commands

Brainfuck Commands can be described with c equivalents:

Brainfuck command C equivalent Command description
Begin int i = 0;
char arr[30000];
memset(arr, 0, sizeof(arr));
allocate 30 000 cells
> i++; go to next cell
< i--; go to previous cell
+ arr[i]++; increase cell value by 1
- arr[i]--; decrease cell value by 1
. putchar(arr[i]); print cell value
, arr[i]&nbsp;=&nbsp;getchar(); input cell value
[ while(arr[i]){ if the byte at the data pointer is zero, then instead of moving the instruction pointer forward to the next command, jump it forward to the command after the matching ]command (considering nesting).
] } if the byte at the data pointer is nonzero, then instead of moving the instruction pointer forward to the next command, jump it back to the command after the matching ]command (considering nesting).

Despite the apparent primitiveness, Brainfuck with an infinite set of cells is Turing-complete, and therefore on the potential is not inferior to a general purpose language.

Classic Brainfuck has 30 000 one-byte cells. In the initial state pointer is in the leftmost position, and all the cells are filled with zeros. Increase / decrease arithmetic is modular with modulo 256. Input-output work with bytes using ASCII (as result of input cymbol 1 writes 0x31 (49) in cell, output operation prints А for cell with value 0x41 (65)). In other implementations of the size and number of cells may be different. Some versions have float-point values.

Programm sample

The following program prints "Hello World!"
 ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++
 .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.
 ------.--------.>+.>.

Analysis of the program:

Memory preparation (from cell 1) for values close to ASCII for output symbols(70, 100, 30, 10), repeating 10 times the increment of the cells at 7, 10, 3 and 1.
++++++++++ set cell 0 (counter) value 10
[ repeat until the value of the current cell (0) is greater than zero
>+++++++ increase cell 1 value by 7
>++++++++++ increase cell 2 value by 10
>+++ increase cell 3 value by 3
>+ increase cell4 value by 1
<<<<- Returns to the cell 0 (counter), and a decrease counter by 1
] return to cycle begin
Get the code letters and their output
>++. Print «Н». Code «H» (72) from 70 in cell 1
>+. Print «e». Code «e» (101) from 100 in cell 2
+++++++.. Print «ll». Code «l» (108) from 101 in cell 2 and double print
+++. Print «o» Code «o» (111) from 108 in cell 2
>++. Print space. Code « » (32) from 30 in cell 3
<<+++++++++++++++. Print «W» Code «W» (87) from 72 in cell 1
>. Print «o» o already in cell
+++. Print «r» Code «r» (114) from 111 in cell 2
------. Print «l» Code «l» (108) from 114 in cell 2
--------. Print «d». Code «d» (100) from 108 in cell 2
>+. Print «!». Code «!» (33) from 32 in cell 3
>. Print «\n» Code «\n» (10) in cell 4

«Hello World!» programm can be implemented easer, but it makes code three times larger:

 +++++++++++++++++++++++++++++++++++++++++++++
 +++++++++++++++++++++++++++.+++++++++++++++++
 ++++++++++++.+++++++..+++.-------------------
 ---------------------------------------------
 ---------------.+++++++++++++++++++++++++++++
 ++++++++++++++++++++++++++.++++++++++++++++++
 ++++++.+++.------.--------.------------------
 ---------------------------------------------
 ----.-----------------------.

Brainfuck interpreter

Example Brainfuck'a interpreter, written using C ++

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

static char cpu[30000];

int main(int argc, char **argv)
{

    vector<char> acc;
    char ch;
    ifstream infile(argv[1]);
    while(infile)
    {
        infile.get(ch);
        acc.push_back(ch);
    }
    infile.close();
    unsigned int j = 0;
    int brc = 0;
    for(int i = 0; i < acc.size(); ++i)
    {
        if(acc[i] == '>') j++;
        if(acc[i] == '<') j--;
        if(acc[i] == '+') cpu[j]++;
        if(acc[i] == '-') cpu[j]--;
        if(acc[i] == '.') cout << cpu[j];
        if(acc[i] == ',') cin >> cpu[j];
        if(acc[i] == '[')
        {
            if(!cpu[j])
            {
                ++brc;
                while(brc)
                {
                    ++i;
                    if (acc[i] == '[') ++brc;
                    if (acc[i] == ']') --brc;
                }
            }else continue;
        }
        else if(acc[i] == ']')
        {
            if(!cpu[j])
            {
                continue;
            }
            else
            {
                if(acc[i] == ']') brc++;
                while(brc)
                {
                    --i;
                    if(acc[i] == '[') brc--;
                    if(acc[i] == ']') brc++;
                }
                --i;
            }
        }
    }
}

Programming brainfuck

Turing Completeness means that the language may implement habitual for other languages ​​actions:

  • value copying
  • Use intermediate (accumulating) storage
  • conditional statements
  • Arithmetic multiplication and division
 Let @(k)  right shift for k cells if k>0, else left shift
 It means, @(k) = >…k times…> or <…-k times…<  
 zero(): zero current cell:
   [-]
   =
   [+]
 add(k): adds curent cell value to cell shifted by k:
    [ — @(k)  + @(-k)  ]
 as result curent cell value becomes zero
 mov(k): move curent cell value to cell shifted by k:
   @(k) zero() @(-k) add(k)
   =
   @(k) [-] @(-k) [ — @(k)  + @(-k)  ] 
 copy(k,t): copy curent cell value to cell shifted by k using temporary cell
   @(k) zero() @(t) zero() @(-k-t) [ — @(k) + @(t) + @(-k-t) ] @(k+t) mov(-k-t)
   =
   @(k) [-] @(t) [-] @(-k-t) [ — @(k) + @(t) + @(-k-t) ] @(k+t) [ — @(-k-t) + @(k+t) ]
 ifelse(t): if current cell value >0, then perform true branch
            if current cell value =0, then perform false branch
            t-относительный номер вспомогательной ячейки:
   @(t)[-]+@(-t) set else flag to 1
   [
    true branch operations
    @(t)[-]@(-t) set else flag to 0
    [-] break cycle
]
   @(t)
   [@(-t)
     false branch operations
    @(t)[-] break cycle
]
   @(-t-1)

Main application of Brainfuck is puzzles and tasks for the competition.

Derivatives

Ook! COW Brainfuck Description
Ook. Ook. MoO + Increace current cell value by 1
Ook! Ook! MOo - Decreace current cell value by 1
Ook. Ook? moO > go to next cell
Ook? Ook. mOo < go to previous cell
Ook! Ook? moo [ cycle begin
Ook? Ook! MOO ] cycle end
Ook! Ook. OOM . print cell value
Ook. Ook! oom , input cell value
mOO none Execute value in current memory block as if it were an instruction. The command executed is based on the instruction code value (for example, if the current memory block contains a 2, then the moO command is executed). An invalid command exits the running program. Value 3 is invalid as it would cause an infinite loop.
Moo none If current memory block has a 0 in it, read a single ASCII character from STDIN and store it in the current memory block. If the current memory block is not 0, then print the ASCII character that corresponds to the value in the current memory block to STDOUT.
OOO [-] Set curren cell value to 0
MMM none If no current value in register, copy current memory block value. If there is a value in the register, then paste that value into the current memory block and clear the register.

References

Cite error: Invalid <references> tag; parameter "group" is allowed only.

Use <references />, or <references group="..." />

External links

  • 166 byte compiler