Brainfuck | это... Что такое Brainfuck? (original) (raw)

Brainfuck

Brainfuck (англ. brain мозг + fuck) — один из известнейших эзотерических языков программирования, придуман Урбаном Мюллером (нем. Urban Müller) в 1993 году для забавы. Язык имеет восемь команд, каждая из которых записывается одним символом. Исходный код программы на Brainfuck представляет собой последовательность этих символов без какого-либо дополнительного синтаксиса.

Одним из мотивов Урбана Мюллера было создание языка с как можно меньшим компилятором. Отчасти он был вдохновлён языком FALSE, для которого существовал компилятор размера 1024 байта. Существуют компиляторы языка Brainfuck размера меньше 200 байт.[1] Программы на языке Brainfuck писать сложно, за что его иногда называют языком для мазохистов. Но при этом важно отметить, что Brainfuck является вполне естественным, полным и простым языком и может использоваться при определении понятия вычислимости.

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

Язык Brainfuck можно описать с помощью эквивалентов языка Си (предполагается, что переменная p объявлена как указатель на байт):

Несмотря на внешнюю примитивность, Brainfuck с бесконечным набором ячеек имеет тьюринговскую полноту, а, следовательно, по потенциальным возможностям не уступает «настоящим» языкам, подобным Си, Паскалю или Java.

Brainfuck подходит для экспериментов по генетическому программированию из-за простоты синтаксиса, и, соответственно, генерации исходного кода.

В «классическом» Brainfuck, описанном Мюллером, размер ячейки — один байт, количество ячеек 30 000. В начальном состоянии указатель находится в крайней левой позиции, а все ячейки заполнены нулями. Увеличение/уменьшение значений ячеек происходит по модулю 256. Ввод/вывод также происходит побайтно, с учётом кодировки ASCII (то есть в результате операции ввода (,) символ 1 будет записан в текущую ячейку как число 0x31 (49), а операция вывода (.), совершённая над ячейкой, содержащей 0x41 (65), напечатает латинскую А). В других вариантах языка размер и количество ячеек может быть другим (бо́льшим). Есть версии, где значение ячеек не целочисленно (с плавающей точкой).

Содержание

• 1 Пример программы
• 2 Интерпретатор Brainfuck
• 3 Программирование на языке Brainfuck
• 4 Языки на основе Brainfuck
• 5 См. также
  • 5.1 Диалекты и реализации
  • 5.2 Другие абстрактные исполнители и формальные системы вычислений
• 6 Примечания
• 7 Ссылки

Пример программы

Программа на языке Brainfuck, печатающая «_Hello World!_»:

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

Разбор программы:

В принципе, печать «Hello World!» можно реализовать проще, но программа будет в три с лишним раза больше, чем приведённый выше оптимизированный вариант:

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

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

----.-----------------------.

Интерпретатор Brainfuck

Ниже приведён код интерпретатора Brainfuck'а, написанный на языке Perl

#!/usr/bin/perl open F,shift; @code=grep{/[+-.,[]><]/}split'',; for(my$=0;$<@code;++$){ cpu[cpu[cpu[i]++if$code[$]eq'+'; cpu[cpu[cpu[i]--if$code[$]eq'-'; i−−ifi--ifi−−ifcode[$]eq'<'; i++ifi++ifi++ifcode[$]eq'>'; print chr$cpu[$i]if$code[$]eq'.'; cpu[cpu[cpu[i]=ordif$code[$]eq','; if($code[$]eq'['){ if(!$cpu[$i]){ ++$brc; while($brc){ ++$; brc++ifbrc++ifbrc++ifcode[$]eq'['; brc−−ifbrc--ifbrc−−ifcode[$]eq']'; } }else{ next; } }elsif($code[$]eq']'){ if(!$cpu[$i]){ next; }else{ brc++ifbrc++ifbrc++ifcode[$]eq']'; while($brc){ --$; brc−−ifbrc--ifbrc−−ifcode[$]eq'['; brc++ifbrc++ifbrc++ifcode[$]eq']'; } --$_; } } }

Программирование на языке Brainfuck

Каждый начинающий программировать на Brainfuck немедленно сталкивается со следующими проблемами:

• отсутствие операции копирования значения
• отсутствие промежуточной (аккумуляторной) памяти
• отсутствие условных операторов в их привычном виде
• отсутствие привычной арифметики, операций умножения и деления

Эти проблемы могут быть решены.

Обозначим через @(k) сдвиг на k ячеек вправо, если k>0, и влево, если k<0 Соответственно, @(k) = >…k раз…> либо <…-k раз…<
zero(): обнуление текущей ячейки: [-]

[+]
add(k): прибавление значения ячейки n (текущей) к значению ячейки n+k: [ — @(k) + @(-k) ] при этом значение ячейки n теряется (обнуляется).
mov(k): копирование значения ячейки n (текущей) в ячейку n+k с потерей (обнулением) значения ячейки n: @(k) zero() @(-k) add(k)

@(k) [-] @(-k) [ — @(k) + @(-k) ]
copy(k,t): копирование значения ячейки n (текущей) в ячейку n+k c использованием промежуточной ячейки n+k+t, благодаря чему значение ячейки n не теряется (сохраняется). @(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): если текущая ячейка>0, то выполняется условие true если текущая ячейка=0, то выполняется условие false t-относительный номер вспомогательной ячейки: @(t)[-]+@(-t) устанавливаем флаг 1 для случая else [ здесь действия ветки true @(t)[-]@(-t) устанавливаем флаг 0 для случая else [-] выход из цикла ] @(t) [@(-t) здесь действия ветки false @(t)[-] выход из цикла ] @(-t-1)

Brainfuck почти не используется для практического программирования (за исключением работ отдельных энтузиастов), а используется преимущественно для головоломок и задач для соревнований.

Языки на основе Brainfuck

См. также

• Тьюринговская трясина

Диалекты и реализации

• Spoon
• LOLCODE
• Whitespace
• Feckfeck

Ещё описание множества диалектов этого языка можно найти в вики-энциклопедии эзотерических языков[2]

Другие абстрактные исполнители и формальные системы вычислений

• Алгоритм Маркова (продукционное программирование)
• Машина Тьюринга (автоматное программирование)
• Машина Поста (автоматное программирование)
• Рекурсивная функция (теория вычислимости)
• Лямбда-исчисление (функциональное программирование)

Примечания

1. ↑ например, исходник компилятора размером 166 байт. Архивировано из первоисточника 25 августа 2011. Проверено 18 августа 2010.
2. ↑ Category:Brainfuck_derivatives, esolangs.org

Ссылки

• Немного о brainfuck на русском языке и пара инструментов для работы с ним
• Оригинальное описание BF на английском языке и ссылки на BF-ресурсы
• Brainfuck interpreter with integrated debugger (IDE) for Windows
• ru_brainfucker — русское ЖЖ-сообщество любителей эзотерических языков
• статья на rsdn.ru об эзотерических языках программирования
• Processing_BF — оптимизирующий интерпретатор и транслятор в PHP, написанный на языке PHP
• BrainfuckInterpreter — кроссплатформенный оптимизирующий интерпретатор на Java, переехал на Brainfuck Interpreter bfrun
• esco — универсальный интерпретатор эзотерических языков
• Интерпретатор brainfuck на JavaScript с открытым исходным кодом
• Переводчик с brainfuck на Perl и обратно с открытым исходным кодом
• Интерпретатор brainfuck с открытым исходным кодом
• Статья о создании транслятора brainfuck в C
• The Brainfuck Archive
• Brainfuck on the Esolang (Esoteric Languages) wiki
• Visual brainfuck, a brainfuck IDE compatible with Windows 7 x86 and x64.
• Brainfuck Developer, Brainfuck IDE for Windows (also works with WINE under Linux)
• Brainfuck в каталоге ссылок Open Directory Project (dmoz).
• bf2c, a Brainfuck to C translator.
• ookie, a Brainfuck and Ook! language interpreter
• Ook.jar, another Ook! and Brainfuck language interpreter, this time written in Java.
• BrainForce, compiler (wrap gcc) and C translator (has lots of options to control wrapping values, cell sizes, etc.)
• esolang, a Brainfuck interpreter for iPhone written in objective c.
• Le Brainfuck, a Javascript based optimizing interpreter. Also has many options, including memory dumping.
• Brainfuck C, a lightweight Brainfuck interpreter written in C.
• Brainfuck Java, an interpreter for the Brainfuck language and its dialects written in the Java programming language.
• lex/yacc-based Brainfuck interpreter in C and Python
• Bfck, open-source Brainfuck interpreter written in C.

Основные языки программирования (сравнение • IDE • история • хронология)
Используемыев разработке	Ада • APL • Язык ассемблера • ActionScript • ABAP/4 • AutoIt • AWK • Бейсик • Си • Кобол • C++ • C# • Cω • Clarion • Clojure • ColdFusion • Common Lisp • D • dBase • Delphi • Eiffel • Erlang • Euphoria • F# • Форт • Фортран • Gambas • Go • Groovy • HAL/S • Haskell • Icon • Java • JavaScript • Limbo • Lua • Модула-3 • Object Pascal • Objective-C • OCaml • Oz • Parser • Паскаль • Компонентный Паскаль • Perl • PHP • PowerBASIC • Python • ПЛ/1 • Пролог • Ruby • Scala • Scheme • Smalltalk • SQL • PL/SQL • Tcl • Vala • Visual Basic (.NET)
Академические	Agda • Clean • Curry • Лого • ML • РЕФАЛ • Симула • Оберон
IEC 61131-3	Instruction List • ST • FBD • Ladder Diagram (LD) • SFC
Прочие	Алгол • Алгол 68 • Модула-2 • Миранда • Hope
Эзотерические	HQ9+/HQ9++ • INTERCAL • Brainfuck • Brainfork • Befunge • Malbolge • Piet • Spoon • Unlambda • Whitespace • FALSE • LOLCODE
Визуальные	G (LabVIEW) • Microsoft VPL • Sikuli • VisSim • Алиса • ДРАКОН • Скретч