 |
|
|
|
Обманчивая простота языка BF: генезис или мутация?
Обманчивая простота языка BF: Обычно новый язык программирования является либо стремлением увеличить эффективность программирования (сравните: машинные коды -> ассемблеры -> Fortran -> Algol -> ...), либо как ответ на недостаточность выразительных средств существующих языков для решения сложных задач обработки информации – списков, графов, деревьев, логических выводов... (IPL-V, Lisp и функциональное программирование, Snobol, Prolog и др.). Бывает, новый язык программирования рождается в процессе исследовательской работы (например, SQL). Тема настоящей статьи – язык программирования, чье появление во многом обусловлено интеллектуальной «шалостью» его создателя. В отличие от большинства таких забав, быстро появляющихся и еще быстрее исчезающих, та, которой посвящена эта статья, благополучно живет и развивается. Немного истории Язык программирования, о котором идет речь, никак нельзя назвать молодым – ему уже больше полутора десятков лет. В 1993 году швейцарский программист Урбан Мюллер (Urban Muller) задался целью разработать язык программирования с минимально возможным объемом компилятора (согласитесь, необычная обратная задача: разработать не компилятор для языка, а язык для компилятора так, чтобы размер последнего не превышал наперед заданного объема). Предполагаемый предельный объем компилятора составлял жалкие 1024 байта, но эта цель была перевыполнена: длина оригинального компилятора Мюллера, написанного на ассемблере для компьютера Amiga, составила всего 240 байт. Правда, исходный язык программирования получился весьма необычным – кое-чем пришлось «пожертвовать». Язык включал в себя всего восемь примитивных команд и требовал от программиста мобилизации серьезных интеллектуальных усилий при написании программ, из-за чего и получил недвусмысленное название Brainfuck. Переводить это название с английского на русский я не рискну – оно звучит откровенно неприлично (по-английски, впрочем, тоже). Видимо, именно поэтому достаточно быстро оригинальное название языка сократили до BF. Чтобы понять, почему язык получил такое необычное имя, давайте рассмотрим его описание. В отличие от подавляющего большинства других языков программирования, чьи описания нередко занимают сотни страниц, описание BF очень компактно. Это, разумеется, не означает, что программирование на BF простое занятие – как раз нет, но ограниченные рамки журнальной публикации не позволяют мне сколько-нибудь подробно останавливаться на этом, и поэтому заинтересованного читателя я отсылаю к ссылкам на ресурсы в конце статьи. Среда исполнения и синтаксис BF В распоряжении программиста имеется область памяти некоторого объема (исторически, обычно 215-1 ячеек, чего обычно вполне достаточно даже для весьма больших BF-программ). Графически удобно представлять область памяти как одномерный массив целых чисел, расположенный горизонтально (см. рис. 1).
Рисунок 1. Графическое представление область памяти Доступ к ячейкам памяти осуществляется по указателю, подобно тому, как это делается в языке C. В каждый момент времени указатель «обозревает» одну ячейку памяти. Те, кто не знаком с языком C, могут представить память просто как массив, а указатель как индекс массива (индексирование массива начинается с 0). Перед запуском программы на исполнение, все ячейки памяти инициализируются нулем, а указатель устанавливается на самую левую ячейку памяти. В классическом варианте языка BF программы и данные разделены: память служит только местом хранения данных; это отличительная особенность так называемой «гарвардской» архитектуры. Однако ничто не препятствует тому, чтобы и данные, и программы использовали общую память (архитектура «фон Неймана»): для этого, разумеется, необходимо изменить интерпретатор. В статье, однако, рассматривается классический вариант языка BF. Указатель может передвигаться вдоль памяти вперед (вправо) и назад (влево), последовательно переходя от одной ячейки к другой. Для этого в BF имеются соответствующие команды «>» и «<». В обозначениях языка C эти команды можно записать как «++pointer» и «--pointer» (здесь «pointer» – указатель на целое). Очевидно, что в силу ограниченности объема выделенной памяти необходимо следить за тем, чтобы указатель не выходил за границы отведенной памяти, и предпринимать соответствующие меры. Следующие две команды – всем хорошо знакомые команды увеличения и уменьшения. Первая из них («+») увеличивает на единицу значение, содержащееся в ячейке памяти под указателем, вторая («-») уменьшает на единицу значение в ячейке памяти под указателем. На языке C это было бы записано как «++*pointer» и «--*pointer». Опять же, при реализации BF необходимо следить за переполнением значений в ячейках. Для связи с внешним миром в языке BF имеются две команды. Первая из них «.» (точка) печатает на экране символ, чей ASCII-код хранится в ячейке памяти под указателем. Вторая команда «,» (запятая) приглашает к вводу символа с клавиатуры; ASCII-код этого символа запоминается в ячейке памяти под указателем. Следующая (по-видимому, минимальная) программа на BF иллюстрирует эти команды: ,. Первая команда ожидает ввода символа и сохраняет его ASCII-код в текущей ячейке памяти; указатель памяти остается без изменений. Вторая команда считывает число из текущей ячейки памяти, интерпретирует его как ASCII-код, переводит в соответствующее символьное представление и распечатывает. К этому моменту были рассмотрены шесть из восьми команд BF: остались две последние. Эти команды позволяют управлять выполнением программы и всегда работают «в паре». Вот эти команды: «[» и «]». Первая из них проверяет содержимое ячейки памяти под указателем и сравнивает его с нулем. Если содержимое этой ячейки равно 0, то управление выполнением программы передается на команду за парной ей скобкой «]». Если не 0, то выполняются команды, следующие после этой скобки вплоть до парной «]». Так реализуется передача управления вперед. Теперь о второй команде. Если содержимое ячейки под указателем памяти не 0, то управление передается назад, к первой команде после парной «[». Если же содержимое памяти под указателем 0, то выполняется команда, следующая за «]». Таким образом, эти две команды реализуют цикл, который подобен конструкции «while» знакомого по языкам программирования C или Java: цикл выполняется пока не 0. Выше я говорил о том, что команды «[» и «]» всегда «работают» совместно. Иными словами, точно так же, как и в арифметическом выражении, скобки «[» и «]» должны быть правильно вложены (сбалансированы). Ниже приведен пример правильного вложения: [[][[[]]]] А вот эти последовательности команд «[» и «]» вложены неправильно: [[][]]] [[[][]] К счастью, баланс скобок «[» и «]» легко проверяется на этапе компиляции (см. ниже). Вот, собственно, и все описание языка BF. Внимательный читатель, безусловно, спросит, а как быть с символами, не входящими в набор указанных восьми? А никак – они попросту игнорируются. Отсюда следует, что любой текст, за исключением указанных восьми символов, можно рассматривать как комментарий. Это весьма удобно, в чем читатель, безусловно, быстро убедится, когда будет составлять свои программы или разбирать программы, написанные другими. Чтобы читатель мог составить представление, как выглядит типичная BF-программа, привожу исходный код, печатающий каноническое «Hello World!»: >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++ [<++++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-] \ <.+++.------.--------.[-] >++++++++[<++++>-]<+.[-]++++++++++. Попытайтесь вручную «прокрутить» эту программу. Теперь стало понятней, почему язык получил свое имя? Интерпретатор Ниже приводится исходный код интерпретатора BF, написанный на Java. Для ясности восприятия исходный код несколько упрощен (в частности, не предпринимаются никакие действия при выходе за границы памяти и переполнении). Тех читателей, которые хотели бы написать свой интерпретатор или посмотреть его реализацию на других языках программирования, отсылаю к ссылкам в конце статьи (кстати, я сам оттуда же позаимствовал многие идеи и приемы). // Интерпретатор BrainFuck // Конструктор класса public BrainFuck (File f) throws IOException { code = open (f).toCharArray (); cleanCode (); checkBrackets (); // Инициализировать память и программный счетчик memory = new byte [MEMORY_SIZE]; for (int i = 0; i < MEMORY_SIZE; i++) memory [i] = 0; pc = pointer = l = 0; interpret (); }
// Собственно, интерпретатор private void interpret () { for (pc = 0; pc < code.length; pc++) { switch (code [pc]) { case '>': incrementPointer (); break; case '<': decrementPointer (); break; case '+': incrementByteAtPointer (); break; case '-': decrementByteAtPointer (); break; case '.': output (); break; case ',': input (); break; case '[': startJump (); break; case ']': endJump (); break; } } }
// Указатель на ячейку вправо public void incrementPointer () { if (++pointer > MEMORY_SIZE) System.out.println ("Выход за пределы памяти: " + MEMORY_SIZE); }
// Указатель на ячейку влево public void decrementPointer () { if (--pointer < 0) System.out.println ("Ошибка адресации указателя"); }
// Увеличить значение ячейки под указателем на 1 public void incrementByteAtPointer () { ++memory [pointer]; }
// Уменьшить значение ячейки под указателем на 1 public void decrementByteAtPointer() { --memory [pointer]; }
// Распечатать содержимое ячейки памяти под указателем public void output () { byte [] out = {memory [pointer]}; String s = new String (out); System.out.print(s); }
// Ввести значение в ячейку памяти под указателем public void input () { BufferedReader stream = new BufferedReader (new InputStreamReader (System.in)); try { String str = stream.readLine (); byte [] in = str.getBytes (); memory [pointer] = in [0]; } catch (IOException e) {System.out.println ("Ошибка чтения");} }
// // Если 0, то сдвинуться вперед до парной «]» public void startJump () { if (memory [pointer] == 0) { pc++; while (level > 0 || code [pc] != ']') { if (code [pc] == '[') level++; if (code [pc] == ']') level--; pc++; } } }
// Если не 0, то сдвинуться назад к парной «[» public void endJump () { if (memory [pointer] != 0) { pc--; while (level > 0 || code [pc] != '[') { if (code [pc] == ']') level++; if (code [pc] == '[') level--; pc--; } } }
// Открыть файл с исходным текстом программы на BrainFuck private String open (File f) { String s = "";
try { String line = ""; BufferedReader br = new BufferedReader (new FileReader (f)); while ((line = br.readLine ()) != null) { if (line.length () > 0) { line = line.trim (); } s += line; } br.close(); } catch (IOException ioe) { ioe.printStackTrace (); System.exit (0); } return s; }
// Удалить из исходного текста программы «лишние» символы private void cleanCode () { String newCode = "";
for (int i = 0; i < code.length; i++) { if (code [i] == '.' || code [i] == ',' || code [i] == '+' || code [i] == '-' || code [i] == '<' || code [i] == '>' || code [i] == ']' || code [i] == '[') { newCode += code [i]; } } code = newCode.toCharArray (); }
// Проверить баланс скобок "[" и "]" public void checkBrackets () { int counter = 0;
for (int i = 0; i < code.length; i++) { switch (code [i]) { case '[': counter++; break; case ']': counter--; break; } } // Если counter не 0, то скобки «[» и «]» несбалансированы
// Точка входа... public static void main (String [] args) { if (args.length > 0) { try {new BrainFuck (new File (args [0]));} catch (IOException ioe) { ioe.printStackTrace (); System.exit (0); } } else { System.out.println ("Синтаксис: java BrainFuck исходный_файл"); Учитывая простоту синтаксиса BF, интерпретатор реализован что называется «в лоб». В точке входа (метод main()) считывается имя файла с исходным текстом BF-программы. Содержимое файла сохраняется в строку, из которой удаляются все символы, не относящиеся к языку BF (метод cleanCode()); после такой «очистки» интерпретировать программу гораздо проще. Метод checkBrackets() сканирует эту строку и проверяет в нем баланс скобок «[» и «]» стандартным методом счетчика. Если скобки сбалансированы, то инициализируются область памяти, программный счетчик и указатель памяти, после чего начинается интерпретация кода (метод interpret()). Интерпретатор считывает команду за командой, передает управление соответствующему методу и увеличивает значение программного счетчика. Обратите внимание на методы startJump() и endJump(): их назначение – поиск в исходном коде парных скобок (соответственно, поиск «]» и «[») и корректировка значения программного счетчика (причем корректировка может происходить как в сторону увеличения, так и уменьшения – все зависит от того, какая скобка ищется). Переменная level отслеживает уровень вложенности и помогает искать парную скобку. Заключительные замечания Разумеется, язык BF абсолютно не практичен, но если вы ищете способ изысканно и нестандартно сойти с ума, то трудно найти что-либо сравнимое. Замечу, что с математической точки зрения язык BF полон по Тьюрингу, то есть при наличии достаточного объема памяти с его помощью можно вычислить все то, что может вычислить машина Тьюринга. И, следовательно, возможности языка BF не слабее возможностей любых других языков программирования, таких, к примеру, как ассемблер, C, Java и прочее. В это непросто поверить, но математика, из которой следует заключение (теория вычислимости и рекурсивных функций), не нуждается в вере. Язык BF, при всей его непрактичности, может служить примером (причем, еще не самым простым) так называемых «базисов» – минимальных конструкций, используемых для исследования алгоритмов и построении теоретических моделей вычислимых функций. Это, однако, совсем другая история. Напоследок (для тех, у кого остаются сомнения в возможностях языка BF) привожу результат работы BF-программы, строящей фрактальное множество Бенуа Мандельброта (см. рис. 2).
Рисунок 2. Фрактальное множество Бенуа Мандельброта, построенное BF-программой Вот, собственно, и все. Если читатель имеет склонность к решению сложных задач, то язык BF, пожалуй, способен удовлетворить такой взыскательный вкус. Желаю этому читателю успехов и открытий в освоении такого удивительно простого и одновременно такого сложного языка программирования, как BF.
|
АЛЕКСЕЙ ВТОРНИКОВКомментарии отсутствуют
| Добавить комментарий |
|
Комментарии могут оставлять только зарегистрированные пользователи |
|
