3. Машина Тьюринга

Классическая задача для суперкомпилятора - превращение интерпретатора в компилятор. На примере машины Тьюринга эта задача решается в полном объеме.

Любой интерпретатор для любого языка программирования в качестве входных данных получает, во первых, текст интерпретируемой программы и, во вторых, исходные данные для нее.

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

Машина Тьюринга была придумана в 30-е годы в качестве теоретического механизма для обоснования понятия алгоритма и для доказательства алгоритмической неразрешимости некоторых проблем. Описание одного из возможных вариантов машины мы привели в turing.txt.

Машина Тьюринга очень просто устроена, поэтому на ее примере полностью решается задача для суперкомпилятора по превращению интерпретатора в компилятор.

Данная тема весьма благоприятна для всяческих экспериментов с суперкомпилятором по разным причинам. Можно работать с собственными программами для машины Тьюринга. Можно модифицировать предлагаемые здесь интерпретаторы машины Тьюринга.

Предлагаются три варианта интерпретатора машины Тьюринга:

ВАРИАНТ 1. trint.ref. Интерпретатор сугубо теоретической машины Тьюринга. Лента предполагается актуально бесконечной в обе стороны (т.е. при попытке выхода головки за пределы ленты в исполняемой программе происходит "отождествление невозможно"; чтобы этого избегать, необходимо при запуске на счет добавлять требуемой количество пробелов с обеих сторон) . Предполагается, что все требуемые инструкции для машины Тьюринга имеются в описании ее программы (т.е. при отсутствии инструкции в исполняемой программе происходит "отождествление невозможно").

ВАРИАНТ 2. trint1.ref. Интерпретатор машины Тьюринга, которая работает с потенциально бесконечной в обе стороны лентой (т.е. пробелы с обеих сторон добавляются по мере надобности при исполнении результирующей программы). При отсутствии нужной инструкции происходит остановка машины Тьюринга в аварийной ситуации, но не "отождествление невозможно" рефала.

ВАРИАНТ 3. turing.ref. Вариант интерпретатора, поставляемый вместе с реализацией суперкомпилятора, содержит комментарии на английском языке и примеры для контрольного пуска интерпретатора на счет до его суперкомпиляции. Практически совпадает с trint1.ref, но результирующие программы не всегда совпадают.

Предлагаются пять примеров программ для машины Тьюринга. Мы указываем MST-схему и результат суперкомпиляции для интерпретатора trint.ref, оставляя остальные возможные примеры для самостоятельной работы.

ПРИМЕР 1. tur1.mst , r-tur1.ref . Простые замены 1 и 2. Если брать еще более простые примеры, то у суперкомпилятора появляются возможности таких оптимизаций, в результате которых трудно узнать исходный алгоритм.

ПРИМЕР 2. tur2.mst , r-tur2.ref . Удвоение количества единиц.

ПРИМЕР 3. tur3.mst , r-tur3.ref . Проверка скобочной структуры. Между звездочками находятся левые и правые скобки. В случае правильной скобочной структуры к ним приписывается 1, в случае неправильной - 0.

ПРИМЕР 4. tur4.mst , r-tur4.ref . Между двумя точками находится последовательность из единиц и пробелов. Программа уплотняет единицы, как бы убирая пробелы.

ПРИМЕР 5. tur5.mst .Определение остатка от деления на 3 заданного числа (если остаток равен нулю, то число делится на 3). Результирующую программу мы здесь не приводим из-за ее большого объема.

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

Построение компилятора. Во всех всех приведенных примерах реально происходит компиляция программы для машины Тьюринга в программу на языке рефал. С этой точки зрения механизм решения задачи выглядит не очень понятно, а именно, в MST-схеме мы задаем имя какой-то функции TUR и какую-то переменную e.1.

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

trcomp.ref , comp1.mst , r-comp1.ref . В MST-схеме задаем

<COMP <текст программы для машины Тьюринга> >;

Суперкомпилятор обрабатывает эту схему и рефал-программу trcomp.ref, в которой начальное состояние ленты вводится посредством функции Card. В результате получается, подчеркнем, готовая к исполнению рефал-программа, например, r_comp1.ref.

Все равно остается какая-то неудовлетворенность. Хочется иметь текст программы для машины Тьюринга в качестве файла, а компилятору сообщать имя этого файла.

Имея в виду реализацию суперкомпилятора, в которой входным языком будет рефал-5, мы подготовили соответствующую программу trint5.ref .

УПРАЖНЕНИЯ.

1. Любая программа для машины Тьюринга.

2. Расширение возможностей входного языка.

3. Исследование свойств суперкомпилятора на простых примерах - тождественная функция, простые замены и т.д.