Языки программирования концепции и принципы (стр. 15 )

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

В настоящее время конкретизирующее программирование интенсивно развивается и у нас, и за рубежом. Конкретизатор в литературе называют иногда специализатором, а также смешанным вычислителем (за то, что он проводит вычисления и над данными, и над программами).

Отметим, что любые языковые конструкты можно при желании считать частью аппарата связывания. Ведь с их помощью аргументы программы связываются с ее результатами на той или иной стадии обработки ее текста. Воспользуемся этим наблюдением, чтобы продемонстрировать еще одно применение аппарата связывания - уточним терминологию и укажем некоторые перспективы в теории трансляции. Это же наблюдение положено в основу трансформационного подхода к программированию [3].

3.4.1. Связывание и теория трансляции

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

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

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

Введем понятие "универсального специализатора". Вслед за Бэкусом назовем формой функцию высшего порядка, т. е. функцию, аргумент и (или) результат которой также представляет собой некоторую функцию. "Универсальный специализатор" s - это форма, которая по произвольной функции двух переменных F(X, Y) и заданному ее аргументу х0 выдает в качестве результата функцию одного аргумента s(F, x0), такую, что для всех допустимых значений параметра Y справедливо определяющее соотношение

(**) s(F, x0) (Y) = F(x0,Y) ,

так что s(F, x0) - это и есть остаточная функция после связывания первого параметра функции F с аргументом х0.

Покажем, как получить объявленный основной результат. Допустим, что все рассматриваемые функции и формы реализованы подходящими программами. Сохраним для этих программ те же обозначения. Так что s(F, x0) можно теперь считать программой, полученной по исходной программе F с помощью программы s.

Замечание. Важно понимать, что о качестве получаемых специализированных (остаточных) программ в определении универсального специализатора ничего не сказано. Тривиальное преобразование программ может состоять, например, в том, что в остаточной программе просто содержится вызов вида F(x0,Y).

Упражнение. Запишите тривиальную остаточную программу на одном из известных вам ЯП.

Рассмотрим теперь язык программирования L и его интерпретатор i. С одной стороны, i - это такая программа, что для всякой правильной программы р на языке L и исходных данных d

i(p, d) = r,

где r - результат применения программы р к данным d. Другими словами, программа i реализует семантику языка L - ставит в соответствие программе р результат ее выполнения с данными d. С другой стороны, i - это форма от двух аргументов (а именно так называемая ограниченная аппликация - она применяет свой первый аргумент-функцию р ко второму аргументу d, причем пригодна только для программ из L).

Интерпретатор может быть реализован аппаратно, т. е. быть отдельным устройством, предназначенным для выполнения программ на L. Однако для нас интереснее случай, когда интерпретатор реализован программой. Программа эта написана, конечно, на каком-то языке программирования М. Будем считать, что М отличен от L. Программная реализация интерпретатора интересна именно потому, что в этом случае интерпретатор представлен написанным на языке М текстом-программой, и вполне можно ожидать, что в общем случае из этого текста можно систематическими преобразованиями получать другие программы. Например, программы компилятора и суперкомпилятора, также написанные на языке М.

Мы намерены делать это посредством специализатора s. Для определенности будем считать, что программа-специализатор s также написана на языке М, применима к текстам программ, написанным на М, и выдает в качестве результатов программы, написанные все на том же языке М.

Специализация интерпретатора. Посмотрим, что собой представляет s(i, p), т. е. во что специализатор s превращает интерпретатор i после его связывания с конкретной программой р? (Ведь i - форма от двух аргументов, так что специализатор s к ней применим; при этом в соответствии со смыслом s с i связывается первый аргумент интерпретатора - р, а второй остается свободным параметром). Применяя (**), получаем

s(i, p)(d) = i(p, d) = r.

Обратите внимание, чтобы выписать результат специализатора, нужно "передвинуть" функциональные скобки на позицию вправо и опустить символ специализатора.

Другими словами, s(i, p) - это такая программа р', которая после применения к данным d дает результат г. Следовательно, р' эквивалентна программе р. Но р' написана уже на языке М, а не на L! Следовательно, р' - это перевод программы р на язык М. Итак, связав интерпретатор (написанный на языке М) с исходной программой на языке L, получили ее перевод на М.

Кратко это можно выразить так: специализация интерпретатора по программе дает ее перевод.

Подумайте, что в общем случае можно сказать о качестве полученного перевода -
скорости работы, объеме памяти; а что - о скорости перевода?

Специализация специализатора. Итак, при различных i специализатор дает переводы с разных языков. Нетрудно теперь догадаться, что при фиксированном i специализатор s представляет собой компилятор с языка L на язык М. Ведь, как мы видели, в этом случае он по заданной р получает ее перевод р'. Действительно, посмотрим, что такое s(s, i)? Вновь применяя (**), получаем

s(s, i)(p) = s(i, p).

Но ведь s(i, p) это р', перевод программы р на язык М! Так что s(s, i) (написанный на М) - это компилятор KLM с языка L на язык М.

Кратко выразим это так: специализация специализатора по интерпретатору дает компилятор. Или еще короче: автоспециализация по интерпретатору дает компилятор.

Снова есть повод подумать о возможном качестве компилятора и затратах на его
получение в общем случае.

Двойная автоспециализация. Специализатор может выступать и в роли суперкомпилятора. Ведь по заданному интерпретатору i (который можно считать описанием языка L), специализатор выдает компилятор с языка L на язык М. Действительно, посмотрим, что такое s(s, s)? Опять применяя (**), получаем

s(s, s)(i) = s(s, i).

Но ведь s(s, i) = KLM! Так что s(s, s) - это действительно суперкомпилятор над языком М (в свою очередь написанный на М).

Кратко выразим это так: двойная автоспециализация дает суперкомпилятор.

Вопрос. Нельзя ли получить что-либо интересное тройной автоспециализацией?

Подсказка. А что если подставлять различные воплощения специализатора s?

Три последовательных применения специализатора удобно наглядно выразить следующей серией соотношений:

s(s, s)(i)(p)(d) = s(s, i)(p)(d) =s(i, p)(d) = i(p, d) = r.

Другими словами, s(s, s) воспринимает описание языка L (т. е. i) и выдает компилятор s(s, i), который, в свою очередь, воспринимает исходную программу р на языке L и выдает ее перевод s(i, p), который уже воспринимает исходные данные d и выдает результат r.

Таким образом, мы убедились, что абстракция связывания (точнее, частичное связывание) позволяет с единых, позиций рассмотреть важнейшие понятия теории трансляции и вывести полезные закономерности. Именно, связав i с р, получили перевод; связав s c i, получили компилятор; связав s с s - суперкомпилятор.

Строго говоря, мы имеем здесь дело не с суперкомпилятором, а с более универсальной программой.

Вопрос. В чем это проявляется?

Приведенные выше соотношения называют соотношениями Футамуры-Турчина. Способ их изложения позаимствован у .

Замечание (о сущности трансляционных понятий). Хотя непосредственное практическое значение соотношений Футамуры-Турчина пока проблематично, они помогают увидеть заманчивые перспективы, а также четче выделять понятия.

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

Вопрос. Можно ли иными средствами задать семантику ЯП? Предложите свои средства.

Написание интерпретаторов на машинных или ранее реализованных языках - хорошо известный, естественный и для многих целей удобный способ реализации ЯП. Для некоторых из них (Лисп, Апл, Бейсик) - единственный способ полной реализации. Это справедливо для всех языков, в которых программа может меняться в процессе исполнения - только "шаг за шагом" и можно уследить за таким изменением.

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

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