brainfuck.md

   1 # Brainfuck
   2
   3 Brainfuck is an extremely simple, [minimalist](minimalism.md) untyped [esoteric programming language](esolang.md); simple by its specification (consisting only of 8 commands) but very hard to program in (it is so called [Turing tarpit](turing_tarpit.md)). It works similarly to a pure [Turing machine](turing_machine.md). In a way it is kind of [beautiful](beauty.md) by its [simplicity](minimalism.md), it is very easy to write your own brainfuck [interpreter](interpreter.md) (or [compiler](compiler.md)) -- in fact the Brainfuck author's goal was to make a language for which the smallest compiler could be made.
   4
   5 There exist **[self-hosted](self_hosting.md) Brainfuck interpreters and compilers** (i.e. themselves written in Brainfuck) which is pretty fucked up. The smallest one is probably the one called [dbfi](dbfi.md) which has only slightly above 400 characters, that's incredible!!! (Esolang wiki states that it's one of the smallest self interpreters among imperative languages). Of course, **Brainfuck [quines](quine.md)** (programs printing their own source code) also exist, but it's not easy to make them -- one example found on the web was a little over 2100 characters long.
   6
   7 The language is based on a 1964 language P´´ which was published in a mathematical paper; it is very similar to Brainfuck except for having no [I/O](io.md). Brainfuck itself was made in 1993 by Urban Muller, he wrote a compiler for it for Amiga, which he eventually managed to get under 200 bytes.
   8
   9 Since then Brainfuck has seen tremendous success in the [esolang](esolang.md) community as the **lowest common denominator language**: just as mathematicians use [Turing machines](turing_machine.md) in proofs, esolang programmers use brainfuck in similar ways -- many esolangs just compile to brainfuck or use brainfuck in proofs of [Turing completeness](turing_complete.md) etc. This is thanks to Brainfuck being an actual, implemented and working language with I/O and working on real computers, not just some abstract mathematical model. For example if one wants to encode a program as an integer number, we can simply take the [binary](binary.md) representation of the program's Brainfuck implementation. Brainfuck also has many derivatives and modifications (esolang wiki currently lists over 600 such languages), e.g. [Brainfork](brainfork.md) (Brainfuck with [multithreading](multithreading.md)), Boolfuck (has only binary cells), Brainfuck++ (adds more features like [networking](network.md)),  Pi (encodes Brainfuck program in error agains [pi](pi.md) digits), Unary (encodes Brainfuck with a single symbol) etcetc.
  10
  11 In [LRS](lrs.md) programs brainfuck may be seriously used as a super simple [scripting language](script.md).
  12
  13 Brainfuck can be trivially translated to [comun](comun.md) like this: remove all comments from brainfuck program, then replace `+`, `-`, `>`, `<`, `.`, `,`, `[` and `]` with `++ ` , `-- `, `$>0 `, `$<0 `, `->' `, `$<0 <- `, `@' ` and `. `, respectively, and prepend `$>0 `.
  14
  15 ## Specification
  16
  17 The "vanilla" brainfuck operates as follows:
  18
  19 We have a linear memory of **cells** and a **data pointer** which initially points to the 0th cell. The size and count of the cells is implementation-defined, but usually a cell is 8 bits wide and there is at least 30000 cells.
  20
  21 A program consists of these possible commands:
  22
  23 - `+`: increment the data cell under data pointer
  24 - `-`: decrement the data cell under data pointer
  25 - `>`: move the data pointer to the right
  26 - `<`: move the data pointer to the left
  27 - `[`: jump after corresponding `]` if value under data pointer is zero
  28 - `]`: jump after corresponding `[` if value under data pointer is not zero
  29 - `.`: output value under data pointer as an ASCII character
  30 - `,`: read value and store it to the cell under data pointer
  31
  32 Characters in the source code that don't correspond to any command are normally ignored, so they can conveniently be used for comments.
  33
  34 Brainfuck source code files usually have *.bf* or *.b* extension.
  35
  36 ## Implementation
  37
  38 This is a very simple [C](c.md) implementation of brainfuck:
  39
  40 ```
  41 #include <stdio.h>
  42
  43 #define CELLS 30000
  44
  45 const char program[] = ",[.-]"; // your program here
  46
  47 int main(void)
  48 {
  49   char tape[CELLS];
  50   unsigned int cell = 0;
  51   const char *i = program;
  52   int bDir, bCount;
  53
  54   while (*i != 0)
  55   {
  56     switch (*i)
  57     {
  58       case '>': cell++; break;
  59       case '<': cell--; break;
  60       case '+': tape[cell]++; break;
  61       case '-': tape[cell]--; break;
  62       case '.': putchar(tape[cell]); fflush(stdout); break;
  63       case ',': scanf("%c",tape + cell); break;
  64       case '[':
  65       case ']':
  66         if ((tape[cell] == 0) == (*i == ']'))
  67           break;
  68
  69         bDir = (*i == '[') ? 1 : -1;
  70         bCount = 0;
  71
  72         while (1)
  73         {
  74           if (*i == '[')
  75             bCount += bDir;
  76           else if (*i == ']')
  77             bCount -= bDir;
  78
  79           if (bCount == 0)
  80             break;
  81
  82           i += bDir;
  83         }
  84
  85         break;
  86
  87       default: break;
  88     }
  89
  90     i++;
  91   }
  92 }
  93
  94 ```
  95
  96 TODO: comun implementation
  97
  98 ## Programs
  99
 100 Here are some simple programs in brainfuck.
 101
 102 Print `HI`:
 103
 104 ```
 105 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ . + .
 106 ```
 107
 108 Read two 0-9 numbers (as ASCII digits) and add them:
 109
 110 ```
 111 ,>,[<+>-]<------------------------------------------------.
 112 ```
 113
 114 TODO: more
 115
 116 ## Variants
 117
 118 TODO
 119
 120 ## See Also
 121
 122 - [False](false.md) (a very similar esolang)
 123 - [comun](comun.md)