Brainfuck
Brainfuck (англ. brain+fuck) — езотерична мова програмування, вигадана Урбаном Мюллером з метою забави. Складається з восьми команд, кожна з яких записується одним символом. Вихідний код програми на Brainfuck є послідовність символів мови без жодного синтаксису.
| Brainfuck | |
|---|---|
 | |
| Парадигма | езотерична |
| Дата появи | 1993 |
| Розробник | Урбан Мюллерd |
| Система типізації | відсутня |
| Під впливом від | LSD |
| Звичайні розширення файлів |
.b, .bf |
Машина, якою керують команди Brainfuck, складається з упорядкованого набору комірок і покажчика поточної комірки, нагадуючи стрічку і голівку машини Тюринга. Крім того, в апараті наявний механізм взаємодії із зовнішнім світом (див. команди «.» ", ").
Команди мови
| 8 команд мови Brainfuck: | ||
| > | перейти до наступної комірки | |
| < | перейти до попередньої комірки | |
| + | збільшити значення в поточній комірці на 1 | |
| - | зменшити значення в поточній комірці на 1 | |
| . | надрукувати значення поточної комірки | |
| , | ввести ззовні значення і зберегти в поточну комірку | |
| [ | якщо значення поточної комірки - нуль, перейти вперед по тексту програми до ] з урахуванням вкладеності | |
| ] | якщо значення поточної комірки не нуль, перейти назад по тексту програми до [ з урахуванням вкладеності | |
Незважаючи на зовнішню примітивність, Brainfuck з нескінченним набором комірок є повною за Тюрингом, але це зовсім не значить що Brainfuck не поступається можливостями іншим сучасним мовам, подібним до C, Паскалю або Java, бо повнота за Тюрингом гарантує лише можливість зробити будь-яке зчислення, а є й ще інші аспекти, такі як багатонитковість, робота з пам'яттю тощо.
Brainfuck підходить для експериментів з генетичного програмування, що обумовлено простотою синтаксису, і, відповідно, генерації вихідного коду.
У «класичному» Brainfuck, що описаний Мюллером, розмір комірки — один байт, кількість комірок — 30000.
У початковому стані покажчик знаходиться в крайній лівій позиції, а всі комірки заповнені нулями. Збільшення/зменшення значень комірок відбувається за модулем 256. Введення та виведення також відбувається побайтно, з урахуванням кодування ASCII (тобто в результаті операції введення (,) символ 1 буде записаний у поточний комірці як число 0x31, а операція виведення (.), виконана над коміркою, що містить 0x41, надрукує латинську А). В інших варіантах мови розмір і кількість комірок можуть бути іншими (більшими). Існують версії, де значення комірок не є цілочисельним (із рухомою комою).
Відповідність команд Brainfuck до команд мови С
| Команди Brainfuck | C еквівалент |
|---|---|
| (Початок програми) | char array[30000]; |
> | ++ptr; |
< | --ptr; |
+ | ++*ptr; |
- | --*ptr; |
. | putchar(*ptr); |
, | *ptr=getchar(); |
[ | while (*ptr) { |
] | } |
Приклад програми
- Програма мовою Brainfuck, що виводить «Hello World!»:
++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++.>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.------.--------.>+.>.
Розбір програми:
| Підготовка у пам'яті (із комірки 1) масиву значень, близьких до ASCII-кодів символів, котрі необхідно вивести (70, 100, 30, 10) через повторення 10 разів збільшення комірок на 7, 10, 3 і 1 відповідно | ||
++++++++++ | присвоювання комірці 0 (лічильнику) значення 10 | |
[ | повторювати, доки значення поточної комірки (комірки 0) більше нуля | |
>+++++++ | збільшення комірки 1 на 7 | |
>++++++++++ | збільшення комірки 2 на 10 | |
>+++ | збільшення комірки 3 на 3 | |
>+ | збільшення комірки 4 на 1 | |
<<<<- | повернення до комірки 0 (лічильника), і його зменшення на 1 | |
] | повернутися до початку циклу | |
| Отримання кодів букв і їх вивід | ||
>++. | Вивід «Н». Отримання коду «H» (72) із 70 у комірці 1 і вивід | |
>+. | Вивід «e». Отримання коду «e» (101) із 100 у комірці 2 і вивід | |
+++++++.. | Вивід «ll». Отримання коду «l» (108) із 101 у комірці 2 і вивід двічі | |
+++. | Вивід «o». Отримання коду «o» (111) із 108 у комірці 2 і вивід | |
>++. | Вивід пробілу. Отримання коду пробілу (32) із 30 у комірці 3 і вивід | |
<<+++++++++++++++. | Вивід «W». Отримання коду «W» (87) із 72 у комірці 1 і вивід | |
>. | Вивід «o». Код «o» (111) вже знаходиться у комірці 2, просто його виводимо | |
+++. | Вивід «r». Отримання коду «r» (114) із 111 у комірці 2 і вивід | |
------. | Вивід «l». Отримання коду «l» (108) із 114 у комірці 2 і вивід | |
--------. | Вивід «d». Отримання коду «d» (100) із 108 у комірці 2 і вивід | |
>+. | Вивід «!». Отримання коду «!» (33) із 32 у комірці 3 і вивід | |
>. | Вивід коду переводу рядка (10) із комірки 4 | |
Приклади інтерпретаторів Brainfuck'а
Інтерпретатор на мові 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;
}
}
}
}
Інтерпретатор мовою Python
def block(code):
opened = []
blocks = {}
for i in range(len(code)):
if code[i] == '[':
opened.append(i)
elif code[i] == ']':
blocks[i] = opened[-1]
blocks[opened.pop()] = i
return blocks
# Let it oof!
def parse(code):
return ''.join(c for c in code if c in '><+-.,[]')
def run(code):
code = parse(code)
x = i = 0
bf = {0: 0}
blocks = block(code)
l = len(code)
while i < l:
sym = code[i]
if sym == '>':
x += 1
bf.setdefault(x, 0)
elif sym == '<':
x -= 1
elif sym == '+':
bf[x] += 1
elif sym == '-':
bf[x] -= 1
elif sym == '.':
print(chr(bf[x]), end='')
elif sym == ',':
bf[x] = int(input('Input: '))
elif sym == '[':
if not bf[x]: i = blocks[i]
elif sym == ']':
if bf[x]: i = blocks[i]
i += 1
code = input()
run(code)
Інтерпретатор мовою C
#include <stdio.h>
#define RAM 8
unsigned char cell[RAM];
char ptr=0;
void main(int argc,char *argv[])
{
FILE *prg;
if((prg=fopen(argv[1],"rb"))==NULL)
return ;
//INIT
char com;
while((com=(char)getc(prg))!=EOF)
{
switch(com)
{
case '>':
ptr++;
if(ptr>=RAM) ptr--;
break;
case '<':
ptr--;
if(ptr<0) ptr++;
break;
case '+':
cell[ptr]++;
break;
case '-':
cell[ptr]--;
break;
case '.':
putc(cell[ptr],stdout);
break;
case ',':
scanf("%d",&cell[ptr]);
break;
case '[':
if(cell[ptr]==(char)0){
while(getc(prg)!=']'){}
}
break;
case ']':
if(cell[ptr]!=(char)0){
do{
fseek(prg,-2,SEEK_CUR);
}while((com=getc(prg))!='[');
}//IF
break;
}//SWICTH
}//WHILE
fclose(prg);
}