Brainfuck

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку
Brainfuck
Парадигмаезотерична
Дата появи1993
РозробникУрбан Мюллерd
Система типізаціївідсутня
Під впливом відP′′ і FALSE
Звичайні розширення файлів.b, .bf
Вебсайтbrainfuck.org

Brainfuck (англ. brain+fuck, укр. мозкоїб) — езотерична мова програмування, вигадана Урбаном Мюллером з метою забави. Складається з восьми команд, кожна з яких записується одним символом. Вихідний код програми на Brainfuck є послідовністю символів мови без жодного синтаксису.

Машина, якою керують команди Brainfuck, складається з упорядкованого набору комірок і покажчика поточної комірки, нагадуючи стрічку і голівку машини Тюринга. Крім того, в апараті наявний механізм взаємодії із зовнішнім світом (див. команди ,, .).

Команди мови

[ред. | ред. код]
8 команд мови Brainfuck
> — перейти до наступної комірки
< — перейти до попередньої комірки
+ — збільшити значення в поточній комірці на 1
- — зменшити значення в поточній комірці на 1
. — надрукувати значення поточної комірки
, — ввести ззовні значення і зберегти в поточну комірку
[ — якщо значення поточної комірки — нуль, перейти вперед по тексту програми до ] з урахуванням вкладеності
] — якщо значення поточної комірки не нуль, перейти назад по тексту програми до [ з урахуванням вкладеності

Попри зовнішню примітивність, мова Brainfuck з нескінченним набором комірок є повною за Тюрингом, але це зовсім не значить, що вона не поступається можливостями іншим сучасним мовам, подібним до C, Паскалю або Java, бо повнота за Тюрингом гарантує лише можливість зробити будь-яке числення, а є й ще інші аспекти, такі як багатонитковість, робота з пам'яттю тощо.

Brainfuck підходить для експериментів з генетичного програмування, що обумовлено простотою синтаксису, і, відповідно, генерації вихідного коду.

У «класичному» варіанті, що описаний Мюллером, розмір комірки — один байт, кількість комірок — 30 000.

У початковому стані покажчик розміщений в крайній лівій позиції, а всі комірки заповнені нулями. Збільшення/зменшення значень комірок відбувається за модулем 256. Введення та виведення також відбувається побайтово, з урахуванням кодування ASCII (тобто в результаті операції введення , символ 1 буде записаний у поточній комірці як число 0x31, а операція виведення ., виконана над коміркою, що містить 0x41, надрукує латинську А). В інших варіантах мови розмір і кількість комірок можуть бути іншими (більшими). Існують версії, де значення комірок не є цілочисельним (із рухомою комою).

Порівняння команд з мовою С

[ред. | ред. код]
Команди Brainfuck Еквівалент у C
(Початок програми) char array[30000];
char *ptr=array;
> ++ptr;
< --ptr;
+ ++*ptr;
- --*ptr;
. putchar(*ptr);
, *ptr=getchar();
[ while (*ptr) {
] }

Приклад програми

[ред. | ред. код]

Код програми, що виводить «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 <fstream>
#include <iostream>
#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

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;
    } // SWITCH
  }   // WHILE
  fclose(prg);
}

Примітки

[ред. | ред. код]

Посилання

[ред. | ред. код]