Beware of the Turing tar-pit in
which everything is possible
 but nothing of interest is easy.
Alan J. Perlis

В 1936 году, за семь лет до создания первого в мире электронного компьютера общего назначения, и за 22 года до изобретения интегральной схемы, перевернувшей весь мир цифровых вычислений, английский математик Алан Тьюринг предложил концепцию абстрактного исполнителя, который впоследствии был назван в честь своего автора – машина Тьюринга. Эта гипотетическая модель обладает удивительным свойством – любое вычисление, которое может быть описано при помощи машины Тьюринга, может быть реализовано физически, в виде некоего исполнительного устройства.

Существует несколько вариантов описания машины Тьюринга, однако основной считается модель с конечным управлением, ограниченной с одной стороны и бесконечной с другой лентой, разделённой на ячейки, и управляющим устройством-головкой, способным за один шаг заданным образом обрабатывать одну ячейку на ленте. В каждой ячейке может храниться только один символ, определённый конечным алфавитом, или "пустой" символ, причём изначально в некотором количестве ячеек хранится входная цепочка символов, задающая начальное поведение машины.

За один шаг машина способна просканировать значение текущей ячейки ленты и, в зависимости от состояния управляющего устройства, выполнить одно из нескольких возможных действий: изменить состояние управляющего устройства, представляющего собой конечный автомат, переписать символ, записанный в ячейке, передвинуть головку влево или вправо на одну ячейку.

"Машина Тьюринга в представлении художника.

Таким образом, машина Тьюринга – это абстрактное устройство, представляющее собой простейший вычислитель с памятью, имеющей линейную организацию. Данные в памяти преобразуются посредством элементарных действий, последовательность которых задаётся правилами перехода, причём число возможных действий конечно. Становится очевидно, что на машине Тьюринга можно реализовать любую алгоритмическую разрешимую функцию, множество которых называется вычислимым, причём из последнего вытекает определение полноты по Тьюрингу. Проще говоря, тьюринг-полным называется исполнитель, если на нём можно реализовать любую вычислимую функцию.

Я не буду погружаться в теорию – в контексте математической науки данная тема неисчерпаема. Между тем, я не зря начал с абстрактных определений, ведь ниже речь пойдёт об одном из наиболее известных эзотерических языков программирования, по своему устройству имитирующему самую настоящую машину Тьюринга. Речь идёт о языке с нецензурным названием – Brainfuck.

Brainfuck был придуман в 1993 году Урбаном Мюллером, который решил таким образом развлечься, а заодно создать язык программирования с минимальным компилятором. В результате у Мюллера получился язык с крайне примитивным синтаксисом – всего Brainfuck поддерживает восемь команд – и полнотой по Тьюрингу. Концептуально детище Мюллера сильно походит на машину Тьюринга: те же линейно организованная память, указатель ячейки памяти, который может либо перемещаться, либо изменять значение в текущей ячейке, и конечный набор состояний указателя. Главным отличием от машины Тьюринга является ограниченный объём памяти, однако реализовать бесконечность учёным и инженерам пока не удалось.

Мемориальная доска программиста на Brainfuck.

Из-за отсутствия каких-либо выразительных средств в языке Brainfuck, программировать на нём крайне трудозатратно (что, надо заметить, явно отражено в названии языка). Создание мало-мальски серьёзной программы требует нечеловеческого напряжения сил. Кстати говоря, примитивные языки, обладающие полнотой по Тьюрингу, называются "трясинами Тьюринга", и Алан Джей Перлис (первый лауреат премии Тьюринга, между прочим), настоятельно рекомендует избегать этих самых трясин (см. эпиграф).

Между тем, язык находит практическое применение, например, в экспериментах по генетическому программированию, где используется автоматическая генерация кода. Brainfuck со своим примитивным синтаксисом хорошо подходит для этих целей. Ещё одно применение языка, если исключить получение особого вида удовольствия от программирования на нём, имеет академическую составляющую. То есть, начинающие разработчики могут попытаться создать свой компилятор Brainfuck, я же сделаю вычислитель, опирающийся на систему команд этого языка в плате Марсоход2.

Прежде всего, позволю себе небольшое лирическое отступление. Я – новичок в проектировании для ПЛИС и, в частности, на языке VHDL, поэтому предложенные мной решения опытные специалисты могут расценить как неоптимальные и неэффективные. Своё мнение по поводу правильности тех или иных вещей вы всегда можете оставить в комментариях. Я, в свою очередь, постараюсь учесть свои ошибки и не допускать их впредь в будущих проектах. Итак, приступим.

Как уже говорилось, система команд Brainfuck включает всего восемь позиций. Более подробнее с ней можно ознакомиться по таблице. Добавлю, что использованной мной версии отсутствует команда записи значения извне, взамен в набор включена команда останова, при считывании которой машина прекращает какие-либо действия. Объём памяти машины – 128 восьмиразрядных слов, отдельно предусмотрена память команд на 128 трёхразрядных слов, команды вводятся с клавиатуры вручную в полном соответствии с синтаксисом языка Brainfuck. Текст программы и результат её выполнения показываются на VGA-дисплее.

                    Таблица системы команд

Предусмотрено два указателя – для памяти команд и для памяти данных. Первый выбирает из памяти команд ячейку с той инструкцией, которая будет выполняться в данный момент времени, другой указывает на ячейку в основной памяти, над которой производится операция. Указатель память данных перемещается в соответствии с инструкциями машины, для указателя памяти команд предусмотрены несколько иные правила перехода, о чём я расскажу ниже.

Общий вид проекта.

Любой модуль на VHDL начинается с описания проектируемого объекта, его сущности, или Entity. Здесь обычно объявляются настраиваемые параметры и интерфейсная часть модуля – входные и выходные порты. Для Brainfuck-машины потребуются входы для тактового сигнала (clk), кода вводимой операции (opcode_in), подтверждения ввода (enter), переключателя в режим исполнения (exe_in) и перезагрузки (reset). Выходами будут служить сигналы для четырёх светодиодов платы Марсоход 2 (leds), 16-разрядный вектор, содержащий информацию для видеоадаптера, и 13-разрядный вектор, представляющий собой адрес знакоместа печатаемого символа.

После Entity следует описание архитектуры схемы, которое обычно также содержит объявления дополнительных вещей вроде компонентов, типов и подтипов данных, атрибутов, сигналов, процедур, функций и другого. Я ограничился объявлением двух типов, представляющих собой массивы из 128 восьмиразрядных и 128 трёхразрядных слов, описывающих память данных и команд соответственно. Также потребовалось "представить" компилятору соответствующие сигналы. Последняя (128-я) команда – это "111" или останов. Это необходимо, чтобы предотвратить зацикливание машины в том случае, если по недосмотру в конце программы останов не поставлен вручную. Потребовался ещё один сигнал, который будет говорить машине, в каком режиме ей следует работать – записывать команды или исполнять их.

Честно говоря, я принял не лучшее решение и описал всю схему в виде одного единственного процесса. В результате код получился довольно пугающим, но работоспособным. В процессе объявлены переменные – указатели и счётчик "глубины вложенности скобок [ и ]". Процесс запускается либо сигналом тактовой частоты, либо сигналом сброса. Последний устанавливает все возможные сигналы и переменные на нулевые значения и переводит машину в режим записи команд.

В режиме записи машина сохраняет команды, поступающие на вход opcode_in, в соответствующую память. При переполнении памяти (указатель на 128-м слове) на плате загораются все четыре светодиода. Команды вводятся с клавиатуры с интерфейсом PS/2, для её подключения использован шилд разъёмов и модуль контроллера с антидребезгом, позаимствованный на сайте eewiki.net, а для перевода скан-кодов клавиш в команды Brainfuck здесь применён модуль opcode_generator. Изначально он работал неправильно, но Николай его "починил".

Сам модуль opcode_generator представляет собой три процесса. Один превращает длинный сигнал PS2_code_new, которым контроллер клавиатуры оповещает о готовности очередного скан-кода, в короткий импульс. Другой использует этот импульс для конечного подтверждения нажатия клавиши. Кстати говоря, принятое значение скан-кода при этом сравнивается с байтом 0xf0 – всё потому, что при нажатии и отпускании клавиши генерируется три кода (нажатие, служебный 0xf0 и отпускание), причём первый и третий идентичны. Очевидно, что после 0xf0 следует "полезный" байт со скан-кодом, который передаётся в третий процесс вместе с сигналом подтверждения ввода, где происходит его "перевод" в шестизначный вектор. Старший разряд этого вектора даёт подтверждение ввода, потом идёт сигнал сброса, сигнал запуска, а тройка младший разрядов кодируют команду Brainfuck. Команды записываются в память только тогда, когда старший разряд вектора имеет высокое логическое состояние, сигналы сброса и запуска имеют действие также только при этом условии.

Отмечу, что можно было бы обойтись и без "мостика" между машиной Brainfuck и контроллером клавиатуры. Возможно, в гипотетической "версии 2.0" схема записи команд будет переработана.

Все команды, которые записываются в память, также выводятся на монитор. Я использовал текстовый VGA-адаптер, который был спроектирован Николаем и применялся в других проектах для платы Марсоход 2. Команды выводятся в виде соответствующих символов, причём зелёным цветом (чтобы отличать их от вывода самой программы). Белый квадрат с символом "<" говорит о готовности машины записывать команды, квадрат с символом ">" предваряет вывод программы.

Когда запись программы закончена, машину можно переключить в режим исполнения (указатель памяти команд при этом перемещается в нулевую позицию). Операции с ячейками памяти данных происходят элементарно: значение ячейки либо увеличивается на 1, либо уменьшается на 1, две другие команды перемещают указатель ячейки либо на 1 вперёд, либо на 1 назад. Несколько сложнее происходит обработка команд [ и ], которыми на языке Brainfuck обрабатываются циклы. Когда считывается, например, команда [, и значение текущей ячейки памяти данных равно нулю, указатель памяти команд должен найти парную закрывающую скобку и переместиться за неё (с учётом вложенности, то есть, на пути указателя может встретиться несколько других открытых и закрытых скобок). По команде ] ищется соответствующая открывающая скобка, и указатель перемещается на неё, если значение в текущей ячейке памяти данных не равно нулю.

Специально для работы со скобками была добавлена переменная depth. Если эта переменная равна нулю, все команды исполняются в обычном режиме. Между тем, если считывается команда [ или ] и соблюдены условия перехода, значение depth увеличивается или уменьшается на 1 соответственно. С этого момента обычные команды перестают исполняться, а указатель памяти команд начинает двигаться в поисках парной скобки в возрастающую сторону, если depth положительно, или убывающую – если depth отрицательно. Встречающиеся по пути скобки [ и ] увеличивают и уменьшают значение depth на 1 соответственно, таким образом, в момент нахождения парной скобки значение depth станет равно нулю, и исполнение команд продолжится в обычном режиме. Отсутствие парной скобки или ошибки вложенности приведут к "зависанию" программы.

Вот и всё, модуль машины Brainfuck готов. В проект остаётся только добавить модуль PLL, генерирующий частоту 106.5 МГц, необходимую видеоадаптеру. От этой же частоты будут питаться и прочие модули. После назначения выводов на ПЛИС и компиляции проект будет готов для прошивки в плату Марсоход 2.

В качестве тестового примера я ввёл следующую программу на языке Brainfuck:

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

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

Если машина работает верно, эта чудная последовательность превратится в знакомое программистам "Hello World!"

Скачать проект с исходниками можно здесь: