Brainfuck

from Wikipedia, the free encyclopedia

Brainfuck (German: "Hirnfick") is an esoteric programming language that the Swiss Urban Müller designed in 1993. The language is also known as Brainf * ck, Brainf *** or BF.

Brainfuck is far too cumbersome and inefficient for productive use, but it is suitable for training the methodology of software development. In particular, Brainfuck is characterized by an extremely simple language concept and highly compact implementation of the compiler, but at the same time the universal applicability (in the computability-theoretical sense) was not restricted.

General

Müller's goal was to design a simple Turing-complete language that could be translated with the smallest possible compiler - he was inspired by False , another esoteric programming language whose compiler was only 1024  bytes . He finally managed to write the second version of his compiler for the Commodore Amiga in just 240 bytes. Brian Raiter was able to undercut this by writing a Brainfuck compiler for x86 Linux using only 171 bytes . For MS-DOS there is a brainfuck interpreter from Bertram Felgenhauer with a size of only 98 bytes.

Language design

A brainfuck program is very similar to the formal definition of a Turing machine . Instead of a read / write head on a tape, states, and a freely definable alphabet, however, a pointer to a data field , loop constructs and a rudimentary ALU are used in the sense of an iterative programming language .

Instruction set

Brainfuck has eight commands, each consisting of a single character:

character C equivalent semantics
> ++ptr; increments the pointer
< --ptr; decrements the pointer
+ ++*ptr; increments the current cell value
- --*ptr; decrements the current cell value
. putchar(*ptr); Outputs the current cell value as ASCII characters on the standard output
, *ptr = getchar(); Reads a character from standard input and stores its ASCII value in the current cell
[ while (*ptr) { Jumps to the front, after the appropriate ]command, if the current cell value is 0
] } Jumps back after the appropriate [command if the current cell value is not 0

Note: There are several semantically equivalent variants of the last two commands, but the ones given here are the most efficient to implement.

Other characters that appear in the source text (e.g. letters, numbers, spaces, line breaks) are usually ignored and can thus be used as source text comments.

Turing completeness

Turing completeness was proven for different brainfuck environments :

  • For an infinitely large field of cells of finite size and for a finite field of cells of infinite size by Daniel B. Cristofani .
  • For an infinitely large field of cells of infinite size by Frans Faase .

A Brainfuck variant with finite cell size and finite field size (e.g. BFmin) is - like every real computer - a finite automaton .

Sample programs in Brainfuck

Hello World!

The following program gives “ Hello World! “And a line break .

 ++++++++++
 [
  >+++++++>++++++++++>+++>+<<<<-
 ]                       Schleife zur Vorbereitung der Textausgabe
 >++.                    Ausgabe von 'H'
 >+.                     Ausgabe von 'e'
 +++++++.                'l'
 .                       'l'
 +++.                    'o'
 >++.                    Leerzeichen
 <<+++++++++++++++.      'W'
 >.                      'o'
 +++.                    'r'
 ------.                 'l'
 --------.               'd'
 >+.                     '!'
 >.                      Zeilenvorschub
 +++.                    Wagenrücklauf

For better readability, this brainfuck code has been distributed over several lines and commented on. Brainfuck ignores all characters that are not brainfuck commands. All characters with the exception of +-<>[],.can therefore be used to comment on the source code.

First, the first (the "zeroth") cell of the data field is set to the value 10 ( a[0] = 10). The loop at the beginning of the program then uses this cell to calculate further values ​​for the second, third, fourth and fifth cells. The value 70 is calculated for the second cell, which is close to the ASCII value of the letter 'H' (ASCII value 72). The third cell receives the value 100, near the letter 'e' (ASCII value 101), the fourth the value 30 near the value for spaces (ASCII value 32), the fifth the value 10, which corresponds to the ASCII character " Line Feed "and is interpreted as a line break (or should be, see the section" Implementations ").

The loop calculates the values ​​by simply adding 10 times 7, 10, 3 and 1 to the cells initially initialized with 0. After each loop pass, a [0] is decreased by one until it has the value 0 and the loop is thereby ended.

At the end of the loop has the data field then the following values: a[0] = 0; a[1] = 70; a[2] = 100; a[3] = 30; a[4] = 10;

Next, the pointer is positioned on the second cell of the data field ( a[1]) and the value of the cell is increased by two. It has the value 72, which corresponds to the ASCII value of the character 'H'. This is then output. The other letters to be output are calculated according to the same scheme with the help of the values ​​initialized by the loop and the values ​​already used.

Basics of programming in Brainfuck

Note : All characters outside of the Brainfuck command set are ignored by the interpreter. They are thus interpreted as a comment. For example, since plus signs are not understood as a comment, but are evaluated as an increment command, in the example given below, the comment is n plus 1 for this reason .

grind

Loops begin with the character '[' and end with the associated ']'. The loop is executed until the value of the current cell is zero. The simplest meaningful form is the zero loop, which decrements the value of the current cell until it is zero:

  [-]

Simple loop

  ,[.,]

Simple echo program. Characters are read from standard input and returned to standard output.

Nested loops

The definition of the two loop commands also includes the option of programming nested loops. Corresponding examples can be found in the source code of several arithmetic operations (see below).

conditions

  • x not equal to y (obtained by subtracting the two numbers)

It is important that cell 0 is set to 0, otherwise the condition block can be called several times.

  >+++++           addiere 5 zu Zelle 1
  >++++            addiere 4 zu Zelle 2
  [<->-]           subtrahiere Zelle 2 von Zelle 1
  <                gehe zu Zelle 1

  [                wird aufgerufen wenn Zelle 1 ungleich 0 ist
  <                gehe zu Zelle 0 (somit wird die Schleife nur einmal durchlaufen)
  ]

Arithmetic operations

Shifting the value of one cell to the next (first zeroing the next cell, then incrementing the next cell in a loop , simultaneously decrementing the current one):

  >[-]<[>+<-]

A value is copied by moving it to two subsequent cells and then moving it back:

 >[-]>[-]<<          nur notwendig wenn die beiden Variablen nicht leer sind
 [>+>+<<-]           verschiebe Inhalt von Zelle n nach Zellen n plus 1 und n plus 2
 >>[<<+>>-]          verschiebe Inhalt von Zelle n plus 2 nach Zelle n
 <<                  gehe wieder auf Zelle n

Addition : p [1] = p [1] + p [0]; Side effect: p [0] = 0

  [>+<-]

Subtraction : p [1] = p [1] - p [0]; Side effect: p [0] = 0

  [>-<-]

Multiplication with a constant p[1] = p[0] * 5:; Side effect: p [0] = 0 A normal shift is carried out, whereby the target cell is not increased by one but by the corresponding factor.

  [>+++++<-]

Multiplication with a cell value: Here, the second factor is added to the product by means of the above copy function repeatedly: p[2] = p[0] * p[1]; Side effect:p[0] = p[3] = 0

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

Exponentiation : Writing a number with +++ in a cell becomes more than time-consuming at the latest from two-digit numbers. Therefore, one makes do with powers: p [2] = 5 ^ 3 = 125; Side effect: p [0] = p [1] = 0

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

Division works easiest as complete division, everything else in this case results in an infinite loop. The idea is otherwise the same as with multiplication: p [1] = p [0] / 5; Side effect: p [0] = 0

  [>+<-----]

The remaining division in Brainfuck is a bit more complicated.

The C code for the following Brainfuck program:

while(p[0]--) {
  p[1]--;
  p[2]++;
  if(p[1] == 0) {
   p[3]++;
   p[1] = p[2];
   p[2] = 0;
  }
 }
 p[2] = p[0] % p[1];
 p[3] = p[0] / p[1];

Side effect: p [0] = 0; p [4] = 0; p [5] = 0; p [1] = p [1] - p [0]% p [1]

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

Conversion

The following code outputs a number in decimal form

 ++++++++[>++++++++<-]>[-<++>]<-----     schreibt die Zahl 123 in die erste Zelle
 >[-]++++++++[>[-]<[->+<]>-]<<<<<<<<<    Löschen der nächsten Zellen
 [->+<]>[>+<-<+>]>[>>>>>[->+<]>+<<<<<    der eigentliche Code
 ++++++++++<[->>+<-[>>>]>[[<+>-]>+>>]
 <<<<<]>[-]>[-<<+>>]>[-<<+>>]<<]>>>>>
 [<<<<+++++++[-<+++++++>]<-[<+>-]<.[-
 ]>>>>>>[-<+>]<-]<<<<<<<

Implementations

Since Brainfuck is not a standardized programming language , incompatibilities can arise. These mostly concern the different line break formats of the Windows and Unix operating systems , as well as their different character codes for the Enter key. Most brainfuck programs, including Urban Müller's, are designed for Unix environments and therefore cannot be translated correctly with implementations that start from Windows character codes.

Similar languages

There is also the Brainfuck 2D programming language , which ports the Brainfuck concept into a two-dimensional drawing space. A string is formed with text characters, the direction of which indicates the corresponding brainfuck command, whereby the length is insignificant for the number of calls. An instruction is repeated according to the sum of all digits on its segment. So + ********* is the same command as +; However, +93 *** executes the command twelve times (9 + 3 = 12). The command +0 **** is not interpreted because it is not executed at all. In this way you can create space for your line if it is not enough. If the course of the string is not clearly recognizable for the interpreter or if the string ends, the program is terminated.

Another variant of Brainfuck that is not meant to be very serious is Ook! .

Another 2D variant is Path, which enables / and \ to be used as a mirror. The program flow then represents a kind of light beam. In Flow , which is quite similar to Path , the program flow runs like water, that is, when it branches, it splits and thus enables (pseudo) threads.

literature

  • Oliver Lau: Hexenwerk - A plea for esoteric programming languages . In: c't 22/2007, pp. 192-199.

Web links

  • Esolang : overview, examples and classification of the programming language
  • Brainfuck on-line interpreter in JavaScript with an extensive library of programs.
  • awib - Brainfuck compiler written in Brainfuck

Individual evidence

  1. hugi.scene.org
  2. hevanet.com
  3. hevanet.com
  4. ^ BF is Turing complete . iwriteiam.nl
  5. Brainfuck 2D reference
  6. Flowbf project page on GitHub