From: Oleg Mazonka, Daniel Cristofani
Newsgroups: email
Date: Mon, 20 Sep 2004 18:21:07 +0000 (UTC)
Subject: Демонстрация создания самоинтерпретатора
Brainfuck: очень короткий самоинтерпретатор
Олег Мазонка и Даниел Кристофани
21 Ноября 2003
Абстракт: В этой статъе мы хотим представить очень короткий
самоинтерпретатор, основанный на примитивном и полным по Тюрингу языке.
Этот интерпретатор явно обрабатывает команды языка, что значит что
интерпретатор содержит в себе описание этого же языка. Статъя не требует
никаких специфических знаний, однако опыт программирования и живое
воображение желательно.
Введение
В течении нескольких десятилетий множество людей было увлечено квайнами
- самопроизводящими программами (те которые печатают свой исходный текст
без чтения данных) [1]. И это не удивительно, потому что такие программы
обладают некоторыми привлекательными свойствами. В них есть какое-то
парадоксальное ссылание на саму себя, что делает не простым их
написание. Они могут быть написаны на разных языках. Они имеют
определенный минимальный размер на каждом языке. И к тому же они не
имеют значительного практического смысла.
В этой статъе мы рассматриваем вопрос на один шаг дальше: если квайн
содержит информацию о самом себе, тогда как бы выглядела программа
содержащая информацию о языке на котором она написана? Такую программу
мы будем называть самоинтерпретатор.
Что бы написать квайн нужно выбрать алгоритм который использует
закодированную версию самого себя и производит закодированную и
незакодированную версии самого себя, но который не слишком длинный в
обоих случаях. Что бы написать маленький самоинтерпретатор нужно выбрать
язык который доволно простой для разбора и исполнения его команд, но в
то же время довольно мощный что бы выразить эти опрации кратко.
Почему интерпретатор? Компиляторы есть на самом деле трансляторы с
одного языка на другой. Они проявляют детали второго языка больше чем
поведение программы написанной на первом языке. Так что интерпретаторы
больше похожи на чистое описание языка - то есть соответствие текста
программы и ее семантики. Мы также моги бы заметить что компилятор для
полного по Тюрингу языка может иногда быть написан на не полном по
Тюрингу языке, в то время как интерпретатор не может быть.
Самоинтерпретатор который мы хотим представить в этой статъе был
первоначально написан Даниелом Кристофани в июле 2002-го и позже улучшен
и сокращен то его настоящей формы.
Самоинтерпретация
Каждый язык живет в своей собственной среде. Определение языка может
быть дано на основе абстрактной машины, но любая реальная реализация
должна быть сделана с принятием во внимание где именно эта абстрактная
машина реализуеться. Другими словами, должны существовать вполне
определенные правила которые описывают как произвести вычислительный
процесс и как наблюдать поведение. В реальных компьютерах такими
правилами есть компиляторы, интерпретаторы, командная оболочка, и ввод и
вывод программы. Этот сорт информации называется прагматикой языка и
иногда включен в полное описание языка. Однако, прагматика стоит как бы
вне языка и обычно не включена в формальное описание. Прагматику можно
считать третей составляющей языка, две другие это синтаксис и семантика.
Определание языка это поведение абстрактной машины, которая читает текст
программы - последовательность символов - и производит какое-то
наблюдаемое поведение, например вывод. Язык полный по Тюрингу
соответствует полной по Тюрингу абстрактной машине.
Интерпретатор - это реализация абстрактной машины. Он потребляет
программу и производит соответсвующий результат. Абстрактная машина
может быть реализована многими различными способами и разными
алгоритмами. Единственная вещь которая должна быть общая для различных
реализаций - это их поведение - одна и та же правильная программа
исполняемая на разных интерпретаторах должна проявлять одно и то же
поведение.
Поскольку интерпретатор задает конкретную реализацию абстрактной машины,
можно использовать поведение интерпретатора для определения языковой
семантики одновременно игнорируя его внутренную структуру. Такое полное
определение языка включит также определение языкового синтаксиса и
областей неопределенного поведения. Так что любой другой интерпретатор
будет также правилным определением языка если он проявляет одинаковое
поведение для всех синтаксически правильных программ поведение которых
определено.
Мы определяем самоинтерпретатор как интерпретатор который написан на том
же самом языке который он интерпретирует, удовлетворяя следующие три
требования:
язык должен быть полный по Тюрингу;
поведение программ во время интерпретирования самоинтерпретатором должно
быть таким же как поведение во время интерпретирования любым другим
интерпретатором, то есть оба должны произвести идентичный наблюдаемый
вывод для любого корректного ввода, хотя не обязательно с той же самой
скоростъю; и
самоинтерпретатор не должен использовать конструкций предназначенных для
разпознавания и интерпретации этих и других языковых конструкций
(самоинтерпретация), например ЛИСП-овский eval.
Второе требование выглядит как тавтология выражающая что
самоинтерпретатор - это интерпретатор. Тем не менее это требование
исключает языки, прагматика которых не достаточна для написания
самоинтерпретатора. Позже мы покажем что не всякий полный по Тюрингу
язык может иметь самоинтерпретатор в этом смысле. Это свойство формирует
различие между языками: некоторые языки полные в среде, в то время как
другие нет. Полнота по Тюрингу происходит от семантики языка и полнота в
среде от его прагматики.
Язык
----
Для написания самоинтерпретатора мы выбрали как основу язык Мозгоебка
[2]. Этот язык очень простой по сравнению с другими языками
программирования. В то же время было доказано что он полный по Тюрингу
[3]. Мы изменили его слегка что бы сделать возможным написание
самоинтерпретатора, но мы не адаптировали его для получения лучшего
результата - получить еще короче самоинтерпретатор - по двум причинам.
Во первых, мы не хотели сильно отклоняться ни от уже известной и
популярной Мозгоебки, ни от четких правил переносимости этого языка [4].
Во вторых, в этой статъе мы хотели бы представить общие идеи написания
короткого и реально работающего примера. Мы обсудим возможные сокращения
в секции 4.4.
Мозгоебка-dbfi
--------------
Язык реализует абстрактную машину работающую на массиве, неограниченном
справа, ячеек памяти, каждая из которых имеет емкость по крайней мере
байта и инициализирована в ноль. Есть указатель, который изначально
стоит на самой левой ячейке памяти. Машина имеет входной и выходной
потоки символов. Вычислительный процесс состоит сначала из чтения
программы из ввода, потом распознавания инструкций и интерпретации их.
Программа скормленная на вход машине - это последовательность символов
состоящая из двух частей: код и данные. Эти части разделены самым первым
'!' символом.
Машина распознает следующие 8 инструкций (их коды соответствуют ASCII):
> сдвинуть указатель на одну ячейку вправо;
< сдвинуть указатель на одну ячейку влево;
+ увеличить на 1 ячейку памяти под указателем;
- уменьшить на 1 ячейку памяти под указателем;
, записать в ячейку памяти под указателем ASCII код символа полученного из ввода данных;
. вывести содержимое ячейки памяти под указателем как ASCII символ;
[ если ячейка памяти под указателем содержит ноль, то идти на команду
следующую за соответствующей ']', a иначе выполнять следующую инструкцию;
] если ячейка памяти под указателем содержит не ноль, то идти на
команду следующую за соответствующей '[', а иначе выполнять следующую инструкцию.
Все символы в коде, за исключением этих 8 указаных в таблице и '!'
игнорируються. Инструкция ',' потребляет символ из данных ввода.
Например, программа ",>,!ab" превратит память "'0 0 0 0 ... " в "97 '98
0 0 ... " (апостроф обозначает указатель).
После исполнения одной инструкции исполняеться следующая инструкция если
она одна из '<', '>', '+', '-', '.', ','. Программа останавливается
после самой последней инструкции, которая стоит перед '!'. После
инструкций ']' и '[' исполняеться либо следующая инструкция, либо та
которая стоит после соответствующей '[' или ']' инструкции, в
зависимости от значения ячейки под указателем.
Допустимая глубина вложений скобок неопределена, хотя любая реализация
должна быть способна обрабатывать не меньше чем 124 (глубина 7 доказана
что достаточна для полноты по Тюрингу [5]).
Если ввод окончен или случилась ошибка ввода, тогда инструкция ввода не
должна изменять значение ячейки если она была ноль перед инструкцией
ввода; в противном случае поведение программы зависит от реализации.
Существуют некоторые другие аспекты языка которые намеренно остались
неопределены, подразумевая что поведение интерпретатора может быть
неопределено в некоторых случаях. Каждая реализация свободна в выборе
поведеня в таких ситуациях, и все равно будет считаться удовлетворяющей
определению языка. Такие аспекты это: размер ячейки, переход указателя
влево от первой ячейки, уменьшение нуля, увеличение максимального
значения ячейки, или несоответствие открывающих и закрывающих скобок.
Вот простые примеры программ: ",+.!a" выводит "b", "a!" не делает
ничего, ",[>+>+<<-]>.>.!X" выводит "XX", а это квайн
">,[.>,]<[<]>[.>]!>,[.>,]<[<]>[.>]!".
Мозгоебка и ее самоинтерпретатор
--------------------------------
Оригинальный язык [6] почти такой же как описан выше за исключением того
что он не определяет разделитель '!'. Программа написанная на Мозгоебке
полностью отделена от ввода; программа либо откомпилирована и ввод дан
исполняющему файлу, либо она дана вместе с ее вводом интерпретатору по
разным каналам; обычно интерпретатор читает программу из файла и ее ввод
с клавиатуры.
Интерпретатор Мозгоебки написанный на Мозгоебке не может воспроизвести
это поведение, потому что его взаимодействие с окружением ограничено -
только лишь один вводной канал в наличии, так что интерпретатор должен
получить и программу (код) и данные через этот канал. Оригинальный
интерпретатор Франса Фаазе [7] ожидает их разделенными '!'; dbfi
поступает так же. Это сделано для того что бы придерживаться тех же
самых спецификаций и переносимости.
Только диалект с таким дополнением, или каким-то другим дополнением или
модификацией предназначенными для этой же цели способен иметь
самоинтерпретатор в нашем понимании, в следствии требования (2).
Оригинальный язык не может быть использован для написания интерпретатора
Мозгоебки который бы взаимодействовал с окружением таким же образом как
и обычный интерпретатор; прагматика языка не позволяет этого.
Dbfi
----
Самоинтерпретатор который мы описываем в нашей статье называеться dbfi.
Его код дан полностью в секции 4.2.
Модель
------
Интерпретатор состоит из двух частей. Первая часть читает код программы
и помещает ее в память в специальном формате. Вторая часть декодирует и
исполняет последовательно инструкции.
Размещение в памяти достаточно простое. Инструкции программы записаны
как числа согласно таблице:
] [ > < . - , +
1 2 3 4 5 6 7 8
Они помещены последовательно начиная с первой ячейки, за исключением
того что симулятор указателя инструкций представлен как пара нулей слева
от инструкции которую предстоит исполнить; так что изначально эти 2 нуля
занимают первую и вторую ячейки слева, перед закодированными
инструкциями.
После последней закодированной инструкции опять два нуля, и дальше
симулятор массива памяти программы. Каждая симулированная ячейка
представлена ввиде двух ячеек: правая содержит значение симулированной
ячейки и левая содержит маркер: 2 для ячейки где находиться симулятор
указателя данных, 2 для всех ячеек слева, и 0 для ячеек справа от
симулятора указателя данных. Такое расположение делает легким поиск
ячейки под симулятором указателя.
Например, если dbfi исполняет программу ",[.[-],]!a" и симулирующая
программа собираеться напечатать "a" инструкцией точка, массив будет
выглядеть так:
7 2 0 0 5 2 6 1 7 1 0 0 2 97 0 0 0 0 0 0 ...
Дальше в объяснении симулятор указателя инструкций и симулятор указателя
данных названы симулятор IP и симулятор указателя; указатель, без
прилагательного, обозначает реальный указатель. Что бы отличать коды
инструкций (1-8) от ASCII кодов инструкций в программе, мы будем
называть первые закодированными инструкциями.
С последующими объяснениями было бы полезно наблюдать как dbfi исполняет
программу, используя какую-нибудь реализацию которая позволяет
просматривать массив.
Первая часть кода занимаеться инициализацией памяти: симулятор IP (два
нуля), закодированные инструкции, другие два нуля, и первый маркер 2.
Основная идея в том что назначая коды для разных инструкций в обратном
ASCII порядке, мы можем сохранить разницы между ASCII кодами для разных
инструкций в массиве, затем отнимать их от введенного символа поочереди
проверяя на точное соответствие каждый раз.
инструкция ! + , - . < > [ ]
ASCII 33 43 44 45 46 60 62 91 93
закодированная инструкция 8 7 6 5 4 3 2 1
Итак.
>>>+[ (1)
В этом цикле читаеться один символ за одну итерацию. Указатель стартует
с ячейки на одну справа от той где должна быть закодированная инструкция
символа, если это инструкция, а не символ комментария.
[-]>>[-]
Мы обнуляем ячеку с которой начинаем цикл - это был всего лишь флажок
говорящий что еще есть на входе символы для обработки - и мы обнуляем
другую ячейку которая могла бы иметь значение оставшееся от предыдущей
итерации цикла.
Тут мы создаем массив разниц что бы конфигурация была такая
... ? ? 0 0 0 2 29 2 14 1 1 1 10 '32 i 0 0 ... ,
где i ячейка содержащая вводной символ для обработки. Затем мы входим в
цикл который проходим каждый раз за одну разницу. Символически мы бы
могли характеризовать это состояние как 0 r 0 d d ... 'd i 0 0 0 , где r
представляет обратную форму закодированной инструкции: она
инкрементируется каждый раз когда мы вычитаем один d от i, и потом когда
мы получаем точное соответствие мы отнимаем r от 10 что бы получить
закодированную инструкцию. Положение указателя показано апострофом.
[>[->>]<[>>]<<-] (3)
Этот кусок имеет эффект установки i в i-d или в 0, в зависимости что
больше. Также d устанавливаеться в 0. Это работает так что внешний цикл
исполняеться d раз, декрементируя d каждый раз; первый внутренний цикл
который декрементирует i исполняеться если i не было уже уменьшено до
нуля, и второй внутренний цикл исполняеться если было.
После этого вычитания существует три варианта.
Если i равно 0, оно было изначально меньше чем инструкция с которой мы
сейчас сравниваем; значит это комментарий а не инструкция. Тогда мы
хотели бы продолжить с циклом (2) обработки d как обычно, и очистить все
остальные d.
Если i равно 1, у нас точное соответствие: i изначально было инструкцией
на которую мы проверяем. Нам надо очистить остаток массива d, и
продолжить обработку инструкции.
Если i больше чем 1, то оно либо будущая инструкция либо коментарий. Мы
продолжаем с циклом обработки d как обычно, но сначала надо передвинуть
i на одну ячейку влево.
<[<]<+>>[>]>
В любом случае сначала идем к r и инкрементируем его.
[<+>- (4)
Если мы вошли в этот цикл, то i по крайней мере 1. Мы устанавливаем
флажок f в ячейке первоначально хранящей d, которая было установлена в 0
в цикле (3), и уменьшаем i на 1:
0 r 0 d d ... d f 'i 0 0 .
[[<+>-]>] (5)
Если i было 2 или больше, передвигаем i влево на f восстанавливая
единицу которую мы только что отняли от i, и передвигаем указатель
вправо что бы пропустить следующий цикл.
<[ (6)
Если мы вошли сюда значит мы на флажке f который мы только что
установили; это значит что первоначальное значение i точно соответствует
инструкции с которой мы сейчас проверяем.
[[-]<]
Бежим влево обнуляя все d.
++<-[ (7)
Устанавливаем "0 'r 2 0 0 ..." и отнимаем 1 от r. Если r было больше
чем 1, тогда i не было первоначально '!', а было одной из восьми
инструкций, и мы входим в цикл. В этом случае 2 будет служить нам как
``обрабатывай следуюший символ'' флажок для самого внешнего цикла (1).
Но если r было 1, тогда i было '!' и мы пропускаем этот цикл; в этом
случае 2 будет служить как первый маркер ячейки.
?
°
?
Ю
и
-
?
?
ha
hНg
hНg
hНg
h
??
??????
" и отнимаем r от 9 что бы получить "c '0 2 0 0 ...", где c это
закодированная инструкция. Затем двигаемся на две ячейки вправо.
]>>
Теперь мы либо имеем "c 0 2 0 0 '0 ..." если инструкция была обычной
инструкцией, либо "0 0 2 '0 0 ..." если инструкция была '!' и мы
перескочили сюда с (7).
]
Теперь опять те же две возможности, либо "0 r 0 d d ... d i '0 0 0 ..."
если мы не нашли точного соответствия и i было перенесено с помощью (5)
и цикл (6) был пропущен.
]<<
Теперь те же три возможности плюс еще одна - если i было 0 в (4) и цикл
(4) был пропущен. В любом случае указатель был передвинут на две ячейки
влево. Так что расклад такой:
c 0 2 '0 0 0 ... если мы нашли точное соответствие;
0 '0 2 0 0 ... если мы нашли '!';
0 r 0 d d ... 'd i 0 0 0 ... если мы не нашли еще, но возможно найдем позже;
0 r 0 d d ... 'd 0 0 0 0 ... если i раво 0 и не нашли соответствия
(символ был меньше чем инструкция с которой мы сравнивали следовательно коментарий) .
0 r '0 i 0 ... и 0 r '0 0 0 ... специальные подслучаи третьей и
четвертой возможностей, если никаких d не осталось.
]<
Если мы нашли соответствие или если никаких d не осталось, то мы в нуле
и значит выходим и цикла (2); если же нет, мы продолжаем обработку
следующей разницы. В третьем и четвертом случаях каждая итерация цикла
(2) оканчиваеться: уменьшением i на величину равнию последнему d, до тех
пор пока i не обнулено; обнулением этого же d в процессе;
инкрементированием r; проверкой на соответствие; передвижением i влево;
- все как описано выше. Но в четвертом случае известно что соответствия
быть не может и r не будет использовано; цикл (4) будет пропущен каждый
раз, и целый процесс всего лишь медленный способ очищения оставшихся d.
Когда же мы выходим из цикла то возможности такие:
c 0 '2 0 0 0 ... если соответствие инструкции найдено (чей код теперьc);
'0 0 2 0 0 ... если найден '!';
0 'r 0 i 0 ... если мы прошли через все разницы и ничего не нашли. i
может быть, а может и не быть 0.
]<
Если мы нашли соответствие инструкции, или не нашли ничего, мы выполняем
цикл ввода и обработки символов (2) опять: и в том и в другом случае мы
находимся на ненулевом флажке сразу справа от ячейки куда следующая
закодированная инструкция пойдет. Но если мы нашли '!', мы закончили: мы
в 0, так что выходим из цикла (1). В этом случае 2 находиться в нужном
месте что бы быть первым маркером, и мы подвидаемся влево на крайнюю
закодированную инструкцию справа.
[ (8)
Теперь мы закончили весь цикл чтения программы и готовы к исполнению
симулируемой программы. За каждый проход через главный цикл dbfi
исполняет одну симулируемую инструкцию. Этот цикл проверяет ячейку
которая изначально содержит самую последнюю закодированную инструкцию -
код инструкции стоящей перед '!' в программе. Когда эта инструкция будет
исполнена и передвинута влево перед симулятором IP, проверка покажет
отрицательный результат и цикл будет прекращен.
[<]>[[>]>>[>>]+[<<]<[<]<+>>-] (9)
Способ которым dbfi декодирует закодированные инструкции и исполняет их
немного не простой. Сначала мы идем к симулятору IP. Мы хотим
передвинуть симулятор IP на следующую позицию - например изменить "2 0 0
4 1" в "2 4 0 0 1" и поскольку симулятор IP состоит из двух нулей, все
что надо зделать это передвинуть закодированную инструкцию на 2 ячейки
влево. Но одновременно мы хотим сделать копию закодированной инструкции
которую мы создаем в альтернативной форме: как строчку единиц в
маркерных ячейках справа от симулятора указателя. (Причины этого будут
скоро ясны.) Каждый раз в длинном цикле сверху, мы проходим через
симулируемый код и данные "[>]>>[>>]" за симулятор указателя и
устанавливаем следующую маркерную ячейку в 1, затем бежим назад
"[<<]<[<]" к симулятору IP и переносим следуюшцую единицу от
закодированной инструкции на две ячейки влево; так продолжаеться до тех
пор пока целая закодированная инструкция не будет перенесена на две
ячейки влево за симулятор IP; к этому времени длинна строчки из единиц в
маркерных ячейках будет равна закодированной инструкции которая была
перенесена.
Например, если симулируемый массив был "97 '98 0 0 0 ..." и
интерпретатор собираеться исполнить '<' инструкцию в коде "[<]", тогда
реальный массив может выглядеть так:
Дальше мы идем в промежуток между симулируемым кодом и данными, затем
бежим вправо по маркерным ячейкам симулируемого массива данных, те
которые до симулятора указателя изменяються с 2 на 1, те которые
являються строчкой кода инструкции изменяються с 1 на 0, и мы
останавливаемся на первой маркерной ячейке справа от этой строчки.
Продолжая предыдущий пример получим:
Теперь указатель на n +1 маркерных ячеек справа от симулятора указателя
(крайняя правая ненулевая маркерная ячейка), где n закодированная
инструкция для исполнения. Мы можем передвигать указатель влево на одну
маркерную ячейку за один раз, проверяя каждый раз достигли ли мы
симулятора указателя; как быстро мы его достигнем будет означать какую
инструкцию исполнять. Вся эта конструкция служит в общем как case
операция. Мы делаем тест с помощью восьми case циклов, каждый из которых
содержит код исполнения определенной инструкции. Каждый цикл также
оставляет указатель где бы он был если бы закодированная инструкция была
9 - то есть достаточно далеко справа для того что бы пропустить
последующие циклы - за исключением трех которые передают управление к
последующим циклам для экономии. Эти три случая будут объяснены позже
индивидуально.
<<<<[
Если мы входим в этот цикл, значит закодированная инструкция для
выполнения была 1, то есть ']', и движение указателя на 2 маркерные
ячейки влево было достаточно что бы достигнуть симулятор указателя -
крайняя правая маркерная ячейка которая не ноль.
Основной метод передвижения симулятора IP до соответствующей скобки
одинаковый для '[' и ']'. Мы передвигаем закодированные инструкции за
симулятор IP один за другим, одновременно считая глубину вложеных скобок
(сохраняя число в одний из ячеек симулятора IP). Когда эта глубина
достигает нуля, значит мы только что прошли соответствующую скобку. Надо
начать изнутри скобок с глубиной 1.
[<<]<[<]+<<
Идем к симулятору IP. Код исполняемой ']' уже перемещен влево, в
нормальном перемещении симулятора IP; так что локальная конфигурация "1
0 '0". Конфигурация которую мы хотим получить "'1 0 1", где первая
единица представляет глубину (сохраненная в левой ячейке симулятора IP)
и вторая представляет текущую ']' инструкцию, перенесенную назад вправо
что бы поместить симулятор IP внутрь цикла. Код для достижения этого
всего лишь "+<<", он также включает мысленный шаг: ']' слева теперь
считаеться счетчиком глубины.
[ (10)
Это главный цикл переноса инструкций, который продолжаеться до тeх пор
пока счетчик глубины не станет 0. Закодированные инструкции двигаються
на 2 ячейки вправо; счетчик глубины инкрементируется на каждой ']' и
декрементируется на каждой '['. Мы используем вложенные циклы для
регулирования глубины основываясь на закодированных инструкциях.
+>+<<-[ (11)
Счетчик глубины инкрементируется, что правильно, если инструкция ']'.
Одна единица закодированной инструкции перенесена вправо. Если это
обнулило закодированную инструкцию, значит она действительно была ']',
так что пропускаем остаток обработки.
>-->+<<-[ (12)
Счетчик глубины декрементирован дважды - один раз что бы восполнить
предыдущее инкрементирование и еще раз что бы декрементировать дальше
для того что бы проверить была ли инструкция '['. Вторая единица кода
перенесена вправо. Если это обнуляет закодированную инструкцию, это была
'[', так что пропускаем оставшуюся обработку.
>+<[>>+<<-]
Если мы дошли сюда значит закодированная инструкция была больше чем 2 -
инструкция не скобка. Инкрементируем счетчик глубины что бы восполнить
предыдущее декрементирование; затем передвигаем остаток закодированной
инструкции вправо.
]]>[<+>-]<]
Это место куда мы попали из (11) или (12) если инструкция была '[' или
']'. Счетчик глубины теперь правильный в любом случае. Передвигаем его
влево и проверяем на ноль. Если не ноль, продолжаем цикл переноса
инструкций (10).
++>>-->[>]>>[>>]]
Теперь симулятор IP слева от соответствующей '[' инструкции, и наша
работа выполнена. Мы бы могли просто пойти назад вправо, и оставить
указатель на 8 маркерных ячеек справа от симулятора указателя, так что
следующие семь case циклов были бы пропущены. Однако вместо этого мы
делаем немного больше озорства: мы оставляем указатель на одну маркерную
ячейку справа от симулятора указателя, так что мы входим в следуюший
case цикл и исполняем инструкцию '[' немедленно, без необходимости идти
через весь процесс доставки инструкций еще раз. Естественно, мы двигаем
инструкцию '[' налево от симулятора IP сначала, поскольку это там где
нормальный процесс разкодирования инструкций оставил бы ее.
<<[
Это случай инструкции '['.
>>+
Мы собираемся сделать подобный трюк здесь: после исполнения этой '[' мы
оставляем указатель на две маркерные ячейки справа от симулятора
указателя, вместо семи, так что управление передаеться к случаю '<'. Что
бы восполнить эффект этого мы будем должны исполнить операцию
соответствующую инструкции '>' перед тем как покинем этот цикл, то есть
надо передвинуть симулятор указателя вправо с помощью установки
следующей маркерной ячейки в 1; и как кажеться сейчас самое лучшее время
сделать это.
<[[<]<]>[ (13)
Теперь мы идем к ячейке симулируемой ячейки в первоначальной позиции
симулятора указателя. Если ячейка содержит 0 тогда первый цикл
пропускаеться, мы идем к новой маркерной ячейке, входим в большой цикл
который переносит симулятор IP. Но если ячека симулируемой ячейки не
ноль, тогда мы идем к первому из двих нулей которые отделяют
симулируемый код от данных, затем мы идем ко второму из тех нулей и
пропускаем большой цикл.
[<<]<[<]+
Идем к симулятору IP; мы внутри '[' уже, так что просто устанавливаем
глубину в 1.
[-<+>>-[<<+>++>-[<->[<<+>>-]]]<[>+<-]>]
Этот цикл переноса инструкций аналогичен тому что для случая ']'. Когда
он заканчиваеться указатель будет во второй нулевой ячейке симулятора
IP, и симулятор IP находиться сразу справа от соответствующей ']' как и
должно быть.
>[>]>]
Теперь идем ко второй нулевой ячейке отделяющей симулируемый код от
данных, и выходим из большого цикла; так что указатель теперь тут в
обоих случаях: либо мы исполняли цикл, либо перескочили из (13).
>[>>]>>]
Оставляем указатель на две ячейки справа от новой (временно) не нулевой
маркерной ячейки, так, что мы войдем в случай '<', который обнулит эту
маркерную ячейку снова.
<<[>>+>>+>>]
Следующие шесть случаев для остальных шести инструкций очень короткие.
Вот эта для '>' установит другую маркерную ячейку в 1. Но также сделает
трюк как упомянутый выше: установит две маркерные ячейки в 1, затем
передаст управление к случаю '<' который обнулит одну из них.
<<[->>>>>>>>]
Случай для '<' обнулит последную маркерную ячейку и перескочит
следуюшцие четыре случая. Случаи '[' и '>' тоже попадут сюда, и ']'
попадет в '[' который тоже попадет сюда.
<<[>.>>>>>>>]
<<[>->>>>>]
<<[>,>>>]
<<[>+>]
Каждый из этих четырех случаев работает непосредственно на симулируемых
ячейках соответствующих симулятору указателя, перескакивая последующие
случаи.
<<[+<<]<]
Это место где все пути сходяться. Что бы ни случилось раньше указатель
попадет обратно к симулятору указателя как раз во время что бы войти в
этот цикл и пробежать влево востанавливая маркерные ячейки до симулятора
указателя из единиц в двойки. Затем указатель будет передвинут обратно в
начальное положение самой правой закодированной инструкции для теста
главного цикла исполнения инструкций (8).
Возможные сокращения
--------------------
Есть несколько очевидных возможностей сделать этот самоинтерпретатор
короче. Первая часть интерпретатора была бы почти тривиальной если
использовать другую кодировку (не ASCII). Возможно было бы сократить
первую часть если бы язык запрещал использование других символов
(коментариев) в коде программы. Язык также оставляет поведение
неопределенным в случаях таких как декрементирование нуля или
инкрементирование максимального значения ячейки, так что интерпретатор
выполняет некоторые лишние инструкции что бы избежать этого поведения.
В этой статье мы не преследовали цели добиться любой ценой кратчайшего
самоинтерпретатора. Поскольку много людей знают и признают язык
Мозгоебку, мы пытались избегать лишних ограничений и изменений языка.
Заключение
----------
В этой статье мы представили очень короткий самоинтерпретатор. Он не
тривиальный и даже не простой, но конечно же никто бы не ожидал простоты
в симуляции машины полной по Тюрингу. Мы не отрицаем возможности более
короткого самоинтерпретатора. Один из способов создать более короткий
самоинтерпретатор - это найти ухищрения или лучший алгоритм. Другой
способ - изобрести другой язык позволяющий сконструировать более
короткий самоинтерпретатор. Интересный момент здесь тот что такой язык
должен быть достаточно прост что бы его самоописание было коротким в
тоже время он должен быть достаточно богат что бы выразить это
самоописание в лаконичной форме. Другими словами, самоинтерпретатор
сложного языка будет длинный из-за большого количества особенностей и
самоинтерпретатор очень простого языка может быть длинным из-за плохой
выразительности. В этой статье мы также показали что не каждый полный по
Тюрингу язык может иметь самоинтерпретатор.
Дополнение
----------
Этот интерпретатор написанный на C++ пример интерпретатора
Мозгоебки-dbfi. Он не оптимизирован по скорости или по памяти. Его
спецификации следующие. Ячейка памяти равна байту. Декрементирование
нуля или инкрементирование максимального значения замкнуто. Поведение
неопределено для несбалансированных скобок. Ошибка ввода не изменяет
ячейку памяти (как C++ фунцкция istream::get). Нет установленного
ограничения по памяти.
#include <iostream>
#include <string>
#include <map>
int main() {
std::string c;
std::map<int,char> m;
std::getline(std::cin,c,'!');
int p = 0, l;
for( int i = 0; i < c.size(); i++ ){
l=1;
if( c[i] == ']' && m[p] ) while(l){
i--;l+=(c[i]==']')-(c[i]=='['); }
Эта работа была финансирована и поддержана чистым энтузиазмом авторов и
их любовью и преданностью к красоте интеллектуального искуства.
Ссылки
1. Смотри квайны на интернете, например,
http://www.nyx.net/~gthompso/quine.htm
2. Язык Мозгоебка был изобретен Урбаном Мюллером в 1993 и его
оригинальное название brainfuck. Вероятно это имя обрекло язык на
распространение только по интернету и на то что он никогда не был
опубликован до сих пор. Язык привлекает своей черезвычайной простотой.
Кажеться что он мог бы быть полезен в некоторых исследовательских
областях, например, искуственный интеллект и сложность Колмогорова.
Заметьте что dbfi следует спецификациям оригинального интерпретатора
Франса Фаазе (http://home.planet.nl/~faase009/Ha_bf_inter.html), который
вполне переносимый в большинстве отношений. (Единственное исключение это
то что количество ячеек доступное симулируемой программе ограничено
емкостью ячеек исполняющего интерпретатора; dbfi не имеет этого
ограничения.) Интерпретатор Фаазе инициировал использование '!' как
разделителя кода и данных.
Vova
