[Перевод] Квазицитирование в Lisp
Аннотация
Квазицитирование (quasiquotation) — это технология, обычно используемая в Lisp для создания программ, генерирующих другие программы. В статье объясняется механизм работы квазицитирования, поясняется почему он работает именно так и каковы его ограничения, а также даётся экскурс в историю квазицитирования.
Примечания переводчика
Термин quasiquotation имеет два общепринятых перевода на русский язык: обратная блокировка и квазицитирование. Оба эти термина вполне описывают инструмент quasiquotation, но с разных точек зрения. Обратная блокировка соответствует операционной семантике, намекая на реализацию в интерпретаторах Lisp, останавливающих интерпретацию и передающих блок в кавычках как есть. Квазицитирование же описывает денотационную семантику, рассказывая о том, что мы как бы цитируем определённое выражение, но именно как бы, то есть вычисленное значение будет лишь напоминать это выражение. Поскольку контекст статьи ближе к денотационной семантике, мы будем использовать термин квазицитирование.
Квазицитирование родственно к интерполяции строк, но в оригинальной статье автор, увы, не упоминает этого термина напрямую.
Есть две версии этой статьи — более сжатая и расширенная, это перевод расширенной версии.
Переводчик благодарит М. Бахтерева (mikhanoid) за техническую редактуру и маму за литературную.
Введение
Квазицитирование — это параметризованная версия обычной блокировки интерпретации, в которой вместо того, чтобы указывать все значения точно, оставляют пропуски, чтобы заполнить их позже. Квазицитирование является своеобразным «шаблоном». Квазицитирование встречается в различных диалектах Lisp, включая Scheme [9] и Commmon Lisp[18], где оно используется для написания синтаксических расширений («макросов») и других программ, генерирующих программы.
Типичное использование квазицитирования в определении макроса выглядит так:
(define-macro (push expr var)
`(set! ,var (cons ,expr ,var)))В этом макро-определении квазицитирование используется для построения выражения set!.
Символ обратной кавычки (`) (quasiquote, прим. пер.) вводит квазицитирование, тогда как обычная блокировка интерпретации вводится символом одинарной кавычки ('). Внутри квазицитирования запятая (,) помечает выражения, значения которых необходимо подставить в результат. Это практически всё, что нужно знать программисту на Lisp, чтобы использовать квазицитирование. Основная идея тут очень проста. Но за простой идеей может стоять непростая история. В статье раскрывается развитие квазицитирования и его фундаментальные особенности:
- Это очень мощный механизм. Комбинация из квазицитирования и S-выражений Lisp даёт удивительно эффективную технологию построения и преобразования программ.
- Квазицитирование имеет сложную интерпретацию. В частности, когда квазицитирование используется для создания расширяемого выражения с квазицитированием (обратные кавычки «вложены») результат становится слабопредсказуемым.
- Его история очень интересна. Несмотря на выразительную мощь, которую можно получить, в результате комбинации квазицитирования и S-выражений, ушло почти двадцать лет на то, чтобы квазицитирование завоевало признание и стало общепринятой частью большинства диалектов Lisp.
- Оно имеет определённые ограничения. Построение программы обычно включает в себя построение выражений, на которые распространяются правила лексической области видимости, тогда как квазицитирование в Lisp этих областей не видит.
В разделе 2 статьи содержится мотивация и простые примеры квазицитирования в Lisp. Третий раздел рассматривает более продвинутые функции квазицитирования и их взаимодействие друг с другом. В разделе 4 показано, как можно использовать квазицитирование для того, чтобы помочь превратить интерпретатор в компилятор (прим. пер. см «Проекции Футамуры»). В пятом разделе обсуждается игнорирование лексической области видимости квазицитированием и рассматриваются методы преодоления этого ограничения. Раздел 6 содержит краткую историю квазицитирования. В разделе 7 показано, как можно использовать квазицитирование для решения известной головоломки. И, наконец, раздел 8 подытоживает наши выводы. В статье слово «Lisp» означает прежде всего диалекты Common Lisp и Scheme. Для большинства примеров используется диалект Scheme, тем не менее, пара примеров не будет работать в большинстве реализаций Scheme по причинам, раскрытым в приложении Б.
Зачем квазицитирование нужно?
Прежде чем рассматривать, как квазицитирование используется для написания программ-пишущих-программы на Lisp, давайте разберём, что происходит когда программа-пишущая-программы должна быть написана на C. Понимание того, что можно и что нельзя легко сделать на C, поможет выяснить, как именно должна выглядеть полезная и хорошо интегрированная в язык технология квазицитирования.
Квазицитирование в C
Самый простой способ написать программу на языке C, которая генерирует другую программу на языке C — это непосредственно сконструировать текстовое представление программы посредством манипуляций со строками. Генерирующая программа, вероятно, будет содержать много операторов, которые выглядят так:
fprintf( out, "for (i = 0; i < %s; i++)
%s[i] = %s;\n",
array_size,
array_name,
init_val);Функция fprintf является удобным способом написания желаемого кода на C. Без fprintf программисту пришлось бы написать:
fputs("for (i = 0; i < ", out);
fputs(array_size, out);
fputs("; i++) ", out);
fputs(array_name, out);
fputs("[i] = ", out);
fputs(init_val, out);
fputs(";\n", out);Легко проверить, что вызов fprintf генерирует синтаксически допустимый код C. Однако, чтобы сделать аналогичный вывод для последовательности вызовов fputs нам придётся приложить усилия.
Использование fprintf позволяет достичь основной цели квазицитирования: оно позволяет программисту писать выражения, максимально похожие на желаемый результат. Он может записать пример желаемого результата, а затем слегка лишь изменить его, параметризовав управляющими последовательностями, такими как "%s".
И хотя fprintf сильно облегчает написание программы на C, которая генерирует программу на C,
у этого подхода есть две проблемы, очевидные постоянному пользователю fprintf:
- Параметры связаны со своими значениями позиционно. То есть, чтобы сопоставить аргумент и соответствующий ему
"%s", нужно их пересчитывать. При большом количестве параметров это увеличивает риск возникновения ошибок. - Подстановка строк, лежащая в основе этой технологии не понимает синтаксическую структуру целевого языка программирования. В результате, особенные значения одного из параметров могут изменить смысл получаемого фрагмента кода самым неожиданным образом. (Подумайте, что произойдёт, если значением
array_nameстанет"*x": правила приоритета операторов C приведут к тому, что сгенерированный код будет читаться как*(x[i])вместо(*x)[i], на который мы рассчитывали.)
Первую проблему можно было бы решить, каким-либо образом переместив выражение параметра в шаблон вроде (реализовав интерполяцию строк, прим. пер.):
subst("for (i = 0; i < $array_size; i++)
$array_name[i] = $init_val;");Но даже если бы интерполяцию строк можно было заставить работать в C, осталась бы нерешённой вторая проблема: линейные строки символов не являются хорошим представлением для рекурсивных структур, таких как выражения. Действительно, программисты обычно принимают некоторые соглашения для вставки дополнительных круглых скобок в такие линейные строки символов, чтобы убедиться, что они анализируются должным образом. (Этот метод часто используется пользователями препроцессора C по той же причине. (#define sqr(x) ((x) * (x)), прим. пер.))
Приведённый анализ предлагает три требования для успешной реализации квазицитирования:
- Квазицитирование должно позволять программистам записывать желаемый вывод практически в окончательном виде, лишь слегка модифицированном для параметризации.
- Выражения параметров должны находиться в тех местах шаблона, куда будут вставлены их значения.
- Структуры, лежащие в основе квазицитирования, должны быть достаточно гибкими для представления рекурсивных структур, таких как выражения.
Выполнение последнего из требований — это то, в чём Lisp действительно блистает.
Квазицитирование в Lisp
Теперь рассмотрим ситуацию, когда программа на Lisp генерирует другую программу на Lisp. Было бы крайне неестественно решать эту задачу работая со строками символов, как это делал код на C в предыдущем подразделе, или даже работая с лексемами, подобно препроцессору C. Естественным способом для программы на Lisp создавать код на Lisp является работа с S-выражениями: списками, символами, числами и т.д. Итак, предположим, что наша цель — сгенерировать выражение Lisp вроде:
(do ((i 0 (+ 1 i)))
((>= i array-size))
(vector-set! array-name i init-value))Примитивнейший код Lisp, создающий это S-выражение:
(list 'do '((i 0 (+ 1 i)))
(list (list '>= 'i array-size))
(list 'vector-set! array-name 'i init-val))Остаётся открытым вопрос, является ли этот код более или менее читаемым, чем код на C из предыдущего подраздела, где использовались повторяющиеся вызовы fputs вместо fprintf.
Но механизм квазицитирования Lisp позволяет вместо этого написать:
`(do ((i 0 (+ 1 i)))
((>= i ,array-size))
(vector-set! ,array-name i ,init-val))Символ обратной кавычки предваряет шаблон, а символ запятой предшествует каждому выражению параметра внутри шаблона. (Запятая иногда описывается как означающая «unquote» («раскавычить», прим. пер.), поскольку она отключает кавычки, включённые обратной кавычкой.)
Ясно, что автор пытается выразить с помощью этого обозначения с обратной кавычкой, но как это реализовано в Lisp? Базовая технология для C-шной функции fprintf — это интерпретатор простого языка форматирования вывода. Что же является базовой технологией для обратной кавычки?
Ответ заключается в том, что два вышеприведённых выражения на самом деле являются идентичными S-выражениями! То есть, они идентичны в том самом смысле, в каком
(A B . (C D E . ()))и
(A B C D E)являются идентичными (одинакова денотационная семантика, прим. пер.). Парсер S-выражений (традиционно называемый «read») раскрывает обратную кавычку со следующим за ней шаблоном в Lisp код, который и конструирует нужное S-выражение. Таким образом, мы можем написать
`(let ((,x ',v)) ,body)и это будет в точности, как если бы мы написали
(list 'let
(list (list x (list 'quote v)))
body)Выражение с обратными кавычками — это просто удобное обозначение для написания сложных комбинаций вызовов конструкторов списков. Точное раскрытие выражений с обратными кавычками не специфицировано — read может создать любой код, создающий нужный результат.[^1] (Один из возможных вариантов алгоритма представлен в приложении А.) Таким образом, введение обратных кавычек не меняет того факта, что программа на Lisp, генерирующая программы, работает, манипулируя структурами списков Lisp.
Ясно, что этот подход с обратной кавычкой достигает по меньшей мере первых из трёх заявленных целей для квазицитирования: код очень похож на желаемый результат, и выражения параметров расположены непосредственно там, где будут вставлены их значения. Третья цель заключается в том, что базовые структуры данных, посредством которых работает квазицитирование, должны подходить для работы с выражениями языка программирования. Пока ещё не очень понятно, достигли мы этой цели или нет.
Структура «список» хоть и не столь «голая», как строки символов, но всё же довольно низкоуровневая. Возможно, нам было бы лучше, если бы наш механизм квазицитирования манипулировал не со списками, а со специальными объектами из набора абстрактных типов данных, сконструированных для каждого из различных синтаксических структур нашего языка (переменных, выражений, определений, cons-выражений, и т.д.). Мы отказались от строк символов под предлогом того, что они слишком низкоуровневые, а значит вполне естественным кажется желание продолжить восхождение к представлениям ещё более высокого уровня, которые охватывают всё большие объёмы предметной области.
К примеру, мы могли бы разработать набор абстрактных типов данных для различных конструкций языков программирования, что-то вроде «абстрактного синтаксиса», часто используемого при анализе программ. Такое представление могло бы помешать нам случайно использовать квазицитирование для создания программ с недопустимым синтаксисом. Ил, возможно, это бы защитило нас от непреднамеренного захвата переменных (проблема, обсуждаемая ниже, в разделе 5). Эта дополнительная безопасность могла бы оправдать дополнительную сложность. Или, возможно, представление более высокого уровня позволило бы нам выполнять более мощные операции над фрагментами языка, что-то большее, чем простая вставка в шаблоны квазицитирования. Такая дополнительная функциональность также может компенсировать возросшую сложность.
Несмотря на все эти перспективы, за последние двадцать лет не появилось ни одного лучшего решения. Хотя в последнее время (статья 1999 года, прим. пер.) на горизонте стало что-то появляться: проблема захвата переменных, обсуждаемая в разделе 5, стала широко обсуждаться. Возможно через некоторое время в результате этих исследований появится улучшенная версия квазицитирования.
Но на данный момент не видно веских причин что-либо усложнять, переходя к представлению ещё более высокого уровня. Квазицитирование, основанное на S-выражениях, достигает нашей третьей цели — использования подходящего представления для выражений языка программирования.
Синергия
Между квазицитированием и S-выражениями существует чудесная синергия. Они работают вместе, создавая механизм более мощный, чем простая сумма этих идей, взятых по-отдельности.
Как мы видели в предыдущем разделе, код Lisp, строящий нетривиальные S-выражения путём прямого вызова процедур построения списков, имеет тенденцию быть решительно нечитаемым. У самых опытных программистов на Lisp возникнут проблемы с расшифровкой выражения
(cons 'cond
(cons (list (list 'eq? var (list 'quote val))
expr)
more-clauses))но даже новичок легко поймёт, что делает эквивалентное квазицитирование:
`(cond ((eq? ,var ',val) ,expr)
. ,more-clauses)(Появление «точечной записи» в этом примере указывает на некоторую неадекватность механизма квазицитирования, представленного до сих пор. Мы вернёмся к этому примеру в разделе 3.1.)
S-выражения лежали в основе оригинальной версии Lisp’а Маккарти [13]. Возможность манипулирования программами всегда была важной частью Lisp. Но без квазицитирования работа с S-выражениями может быть крайне трудоёмкой. Квазицитирование исправляет важный недостаток изначального инструментария S-выражений.
Есть выгода и с другой стороны. Как мы видели, квазицитирование на основе символьной строки — это неаккуратный способ представления рекурсивных структур данных, таких как выражения. Но если наши данные представлены с помощью S-выражений, подстановка в шаблоны квазицитирования работает чисто. Таким образом, S-выражения исправляют неадекватность квазицитирования на основе строк (то есть, строковой интерполяции, прим. пер.).
Квазицитирование и S-выражения компенсируют недостатки друг друга. Вместе они образуют удивительно эффективный и гибкий механизм преобразования и генерации программ. Поэтому неудивительно, что, хотя квазицитирование в течение двадцати лет после изобретения Lisp не входило в спецификацию какого-либо диалекта языка, оно широко использовалось до стандартизации.
Тесная связь между квазицитированием и S-выражениями побудила некоторых программистов следовать стилю, в котором квазицитирование используется исключительно для создания программ. В этом стиле списки, используемые в качестве данных, всегда создаются явным образом с помощью вызовов примитивов структуры списка, таких как list и cons, тогда как списки, которые используются для представления программ (т.е. S-выражений), всегда строятся с использованием обратных кавычек.
Поскольку списки данных, как правило, несложны, очень мало что теряется при отказе от использования квазицитирования для их построения. В обмен на эту маленькую жертву мы получаем большой выигрыш в удобочитаемости благодаря чёткому разделению построения списков данных и списков S-выражений. В статье мы будем придерживаться этого стиля.
Украшения
Продемонстрировав, что квазицитирование является мощным и полезным инструментом, перейдём к деталям. Мы представим два важнейших момента в квазицитировании и его применении. Во-первых, мы введём дополнительную функцию, называемую «структурное раскрытие» («splicing», «сплайсинг», прим. пер.). А во-вторых, мы рассмотрим, что происходит, когда квазицитаты вложены друг в друга.
Мы очень близко подошли к необходимости структурного раскрытия в разделе 2.3. Вспомните:
`(cond ((eq? ,var ',val) ,expr)
. ,more-clauses)Значение переменной more-clauses предположительно представляет собой список дополнительных условных предложений, которые должны быть встроены в создаваемое нами условное выражение. Предположим, что мы знаем (по какой-то причине), что в этом списке нет предложения else, и мы хотим добавить его. Мы всегда можем написать:
`(cond ((eq? ,var ',val) ,expr)
. ,(append more-clauses
'((else #T))))Но вызовы таких вещей, как append, — это именно то, чего квазицитирование должно помочь нам избежать. Кажется, вместо этого мы должно были бы написать:
`(cond ((eq? ,var ',val) ,expr)
. ,more-clauses
(else #T))К сожалению, это злоупотребление «точечной записью» Lisp будет отвергнуто синтаксическим анализатором read. К счастью, подобная ситуация встречается достаточно часто, чтобы механизм квазицитирования содержал инструмент, позволяющий нам достичь нашей цели:
`(cond ((eq? ,var ',val) ,expr)
,@more-clauses
(else #T))Этот двухсимвольный префикс, запятая-«собака» (,@), похож на простую запятую в качестве префикса, за исключением того, что следующее за ним выражение должно быть «вклеено» в содержащий его список. (Рассматривая этот пример, читатель может задаться вопросом, почему вместо этого знака не был выбран префикс запятая-точка (,.). Раздел 6 отвечает на этот вопрос.)
Раскрытый код может выглядеть так (с точностью до денотационной семантики, прим. пер.):
(cons 'cond
(cons (list (list 'eq? var (list 'quote val))
expr)
(append more-clauses
'((else #T)))))Читать это, конечно, не очень легко, но простой пример должен всё прояснить: если значение X равно (1 2 3), то значение
`(normal= ,X splicing= ,@X see?)это
(normal= (1 2 3) splicing= 1 2 3 see?)Структурное раскрытие полезно во многих ситуациях. Взглянув на BNF грамматику для любого диалекта Lisp, вы обнаружите множество видов выражений, в которых встречается последовательность частей: аргументы в вызове функции, переменные в лямбда-выражении, предложения в условном выражении if, пары в let-выражении и т.д. При создании кода, использующего любой из этих видов выражений, объединение может оказаться полезным.
Различие между обычной заменой (,) и заменой со структурным раскрытием (,@) существует потому, что S-выражения представляют собой деревья, а не плоские последовательности. Квазицитирование, основанное на строках символов, не имеет возможности учесть это различие, поэтому пользователь вынужден подчёркивать его другими способами, например, явно вставляя скобки.
Вложенность
Иногда программа, генерирующая программу, фактически генерирует другую программу, генерирующую программу. В такой ситуации зачастую одно квазицитирование используется для построения другого квазицитирования. Квазицитаты оказываются вложенными.
«Вложенное квазицитирование» звучит чуть ли не как эзотерическая конструкция, которая понадобится только мудрейшим из разработчиков компиляторов, но на самом деле даже самые обычные программисты на Lisp могут легко оказаться в ситуации, когда им нужно вставить одно квазицитирование в другое. Это происходит потому, что макросы Lisp записываются на самом языке Lisp. (Большинство других языков программирования со средствами макропрограммирования использует другой язык для написания макросов, например, препроцессор C) Как только программист начинает писать какие-либо макросы, это лишь вопрос времени, когда он заметит, что он написал кучу похожих друг на друга макросов. Ясно, что его следующим шагом будет разработка макроса, генерирующего макросы, который он сможет использовать для автоматического создания всех этих похожих друг на друга определений. Для этого ему понадобится вложенное квазицитирование.
Чтобы проиллюстрировать это, представим, что программист написал такое макро-определение (синтетический пример, обычно макросы определяются не так):
(define-macro (catch var expr)
`(call-with-current-continuation
(lambda (,var) ,expr)))Это определяет catch как макро, так что вызов:
(catch escape
(loop (car x) escape))расширяется путём привязки var к символу escape и expr к списку (loop (car x) escape) и выполнения тела макроопределения. В этом примере тело макроопределения — это квазицитата, возвращающая:
(call-with-current-continuation
(lambda (escape)
(loop (car x) escape)))Это значение подставляется вместо изначального выражения catch.
Процедуры, которые принимают вспомогательную процедуру с одним аргументом и вызывают её каким-то особым образом, встречаются довольно часто. Вызовы таких процедур нередко записываются с использованием лямбда-выражений для создания вспомогательной функции. Поэтому позже программист может написать другое макро, похожее на catch:
(define-macro (collect var expr)
`(call-with-new-collector
(lambda (,var) ,expr)))Если программист подозревает, что ему придётся написать ещё много макро-определений подобного типа, он может решить автоматизировать процесс, написав макро-определяющее-макро:
(define-macro (def-caller abbrev proc)
`(define-macro (,abbrev var expr)
`(,',proc
(lambda (,var) ,expr))))Теперь предыдущие два макро-определения можно переписать как:
(def-caller catch
call-with-current-continuation)и
(def-caller collect
call-with-new-collector)Определение def-caller было бы элементарным, если бы не мистическое заклинание запятая-кавычка-запятая (,',). Откуда, чёрт побери, оно взялось? Это не какой-то новый примитив, как запятая-«собака» (,@). Это использование сочетания квазицитирования и традиционной блокировки интерпретации (') Lisp может быть легко выведено из их семантики.
Вот как мы можем получить определение def-caller. Во-первых, мы вручную раскрываем квазицитирование, используемое в определении catch:
(define-macro (catch var expr)
(list 'call-with-current-continuation
(list 'lambda (list var) expr)))Теперь нам не нужно беспокоиться о том, что нас могут запутать вложенные квазицитирования, и мы можем написать def-caller следующим образом:
(define-macro (def-caller abbrev proc)
`(define-macro (,abbrev var expr)
(list ',proc
(list 'lambda (list var) expr))))Затем, превратив вызовы list обратно в квазицитирование, приняв меры, чтобы ',proc интерпретировалось как выражение, а не как константа, мы получим исходное определение.
Конечно, ни один программист на Lisp не выводит заново запятая-кавычка-запятая каждый раз, когда ему это нужно. На практике это хорошо известное клише с вложенным квазицитированием. Каждый программист, использующий вложенное квазицитирование, знает три идиомы:
,X—Xпоявится как выражение в промежуточной квазицитате, и его значение, таким образом, будет подставлено в окончательный результат.,,X— значениеXпоявится как выражение в промежуточной квазицитате, и значение этого выражения, таким образом, будет подставлено в окончательный результат.,',X— значениеXпоявится как константа в промежуточной квазицитате и, таким образом, не изменится в конечном результате.
Чтобы понять или запомнить эти клише, может пригодится осознание того, что самая внутренняя запятая связана с самой внешней обратной кавычкой.
Вложенное структурное раскрытие
Взаимодействие вложенных квазицитирований со структурными раскрытиями даёт интересные плоды. Поскольку этот материал не является необходимым для понимания остальной части статьи, читатель может проглядеть по диагонали или даже пропустить оставшуюся часть этого раздела.
Семантика вложенного структурного раскрытия требует некоторого пояснения. Рассмотрим случай ``(,,@X). Когда никакой вложенности нет, `(,anything) эквивалентно (list anything). По-аналогии, ``(,,@X) должно соответствовать
`(list ,@X)Таким образом, элементы выражения X станут отдельными аргументами вызова list.
Конечно, когда вложенность отсутствует, `(,anything) также эквивалентно (cons anything '()), таким образом, мы могли бы сказать, что ``(,,@X) должно быть эквивалентно
`(cons ,@X '())Но эта конструкция явно проигрывает варианту с list, так как если только значение X не является списком из одного элемента, cons будет вызываться с неправильным количеством аргументов! Результат в терминах list является наиболее полезным из всех возможных вариантов, поэтому именно он используется для придания семантики вложенному структурному раскрытию.
Рассуждая аналогично, придём к мысли, что наиболее полезным раскрытием '(,@anything) является (append anything). Таким образом, чтобы придать вложенному соединению полезную семантику, код, построенный с помощью read для квазицитирования, вставляет всё, что следует за запятой (,),
в аргумент для перечисления, а всё, что следует за знаком (,@), в качестве аргумента append. Алгоритм раскрытия в приложении А следует вышеприведённым правилам.
Без структурного раскрытия на каждом этапе интерпретации вложенной квазицитаты могут произойти два момента: элемент может рассматриваться как константа и передаваться на следующий этап без изменений, или же элемент может рассматриваться как выражение, вычисленное значение которого появится на следующем этапе. Структурное раскрытие добавляет третью возможность: элемент может рассматриваться как выражение, значением которого станет список, который будет «вклеен» на следующем этапе.
Таблица 1. Двухстадийная разметка, используемая на практике.
Итак, два этапа с тремя возможными действиями на каждом этапе дают девять случаев для рассмотрения. Каждая строка таблицы 1 соответствует разному выбору на первом этапе, а каждый столбец соответствует разным вариантам выбора на втором этапе. В первых строке и столбце не предпринимается никаких действий на этом этапе. Во вторых строке и столбце
подставляется значение элемента на этом этапе. В последних строке и столбце вставляется значение элемента на этом этапе. Так, например, ,,@X означает, что значение X на первом этапе должно быть списком выражений, а отдельные значения этих выражений на втором этапе должны быть подставлены в окончательный результат. А ,@,@X означает, что значение X должно быть списком выражений, каждое из которых возвращает список значений.
Почему же таблица 1 не состоит просто из парных перестановок трех разных префиксов? Ответ заключается в том, что она могла бы, если бы программисты не применяли некоторые определённые оптимизации естественным образом. В качестве первого шага к пониманию, представьте, что произойдет, если мы наивно перепишем таблицу, используя запятую-кавычки (,'), когда мы хотим заблокировать интерпретацию на данном этапе, простую запятую (,), если мы хотим вычислить выражение, и знак (,@) когда мы хотим вычислить и вклеить результат. См. таблицу 2. Эта таблица выглядит почти так же, как и исходная — отличается только верхняя строка и нижняя левая ячейка.
Таблица 2. Попытка написать регулярную двухстадийную разметку.
Разницу в верхней строке легко объяснить: префикс запятой-кавычки, за которым следует S-выражение, не содержащее разметки квазикавычки, всегда можно заменить «голым» S-выражением. То есть, всегда можно устранить «самую внутреннюю» запятую-кавычку (,'), применение этого соображения даёт первую строку в таблице 1.
Нижний левый угол объяснить труднее. Мы наивно сгенерировали ,',@X, но это работает только в одном частном случае, когда значение X оказывается списком длины один! Проблему легко увидеть, переписав как ,(quote ,@X); верное выражение quote получится только если значение X является одноэлементным списком. А в исходной таблице стоит ,@',X, которая работает, передавая значение X первой стадии в виде списка на вторую стадию и затем выполняя структурное раскрытие, «вклейку».
Эти различия предполагают, что может существовать некая «алгебра» квазицитатной разметки, которая может объяснить, как таблица 1 (содержащая префиксы, которые на самом деле используют программисты) может быть механически получена путем упрощения записей в какой-то более регулярной таблице. Такая «алгебра» действительно существует, и мы можем обнаружить её путём изучения двадцати семи возможных случаев, когда квазицитаты вложены друг в друга на три уровня вглубь. Трехступенчатые префиксы, которые программисты будут использовать на практике, таковы:
Таблица 3. Трёхступенчатая разметка, используемая на практике.
Первый блок «три на три» содержит префиксы, используемые, когда на первом этапе не выполняется интерпретация. Второй блок содержит префиксы, используемые при простом вычислении на первом этапе. Третий блок содержит префиксы, используемые, когда на первом этапе происходит интерпретация, за которой следует структурное раскрытие, «вклейка». Внутри каждого блока действия второго и третьего этапов располагаются по-прежнему.
Наиболее ярким аспектом рисунка 3 является появление пар скобок в двух элементах. Обе эти записи также содержат на один знак больше, чем мы могли бы ожидать, учитывая количество этапов, которые включают в себя структурное раскрытие. Давайте проанализируем случай ,@'(,,@X), чтобы понять, что происходит. ,@'(,,@X) ожидает, что значение первой стадии X является списком выражений.
Каждое из этих выражений будет вычисляться на втором этапе. Возвращённые значения останутся нетронутыми на третьем этапе и появятся в конечном результате. Ключом к тому, как это работает, является префикс ,@'(...), сперва объединяющий в список значения, выданные на втором этапе, а затем структурно его раскрывающий, «вклеивающий» элементы этого списка в окончательный результат.
Таким образом, мы приходим к выводу, что префикс, который мы должны были использовать на стадии, не выполняющей никаких вычислений — это ,@'(...), а не ,', как мы предполагали ранее, в нашей первой попытке. Эти рассуждения дают нам таблицу 4.
Таблица 4. Правильная регулярная разметка.
В отличие от нашей первой наивной попытки, все записи в этой таблице работают во всех случаях. Программист может смело полагаться на составление «операторов» (,), (,@) и (,@'(...)) для достижения желаемого эффекта внутри произвольно вложенных квазицитирований.
Однако на практике программисты предпочитают использовать упрощённые префиксы из таблицы 1. Итак, какие же правила упрощения приводят к практически используемым префиксам? Их три, и каждое из них имеет простое обоснование:
,@'(expr)упрощается доexpr, еслиexprне содержит обратных кавычек. Мы уже встречались с этим правилом в более простой форме.,@'(expr)упрощается до,'expr, еслиexprсодержит обратные кавычки, но не выполняет никакого структурного раскрытия. Еслиexprбудет просто одним значением, нет смысла заключать его в список и разворачивать позже — мы можем просто вернуть его как есть.(,@expr)упрощается до',exprеслиexprне выполняет структурного раскрытия. Еслиexprвозвращает список значений, которые мы хотим раскрыть в список констант, мы можем просто использовать этот список напрямую.
Так, например, двойное применение правила 1 сводит ,@'(,@'(X)) к X. Правило 2 сводит ,@'(,X) к ,',X. И правило 3 приводит ,@'(,@X) к ,@',X.
Трёхэтапную таблицу 3 мы можем вывести подобным же образом. Две ячейки, в которых появляются пары круглых скобок, представляют собой случаи, когда ни одно из правил упрощения не применяется. (Первая из этих ячеек, ,@'(,,@X) представляет собой исторический интерес, поэтому она снова появится в разделе 6.)
Пример: превращаем интерпретатор в компилятор
В этом разделе представлен расширенный пример, сочетающий квазицитирование с ручным частичным вычислением для непосредственного создания простого компилятора. Этот пример служит двум целям. Во-первых, он показывает, как использовать квазицитирование для чего-то более впечатляющего, чем простая запись макросов. Во-вторых, он показывает «проблему окружения», которая будет темой раздела 5.
Простой интерпретатор
Начнём с простейшего интерпретатора Scheme. Его основной процедурой является evaluate, представляющая собой всего лишь большой диспетчер, каждая ветка которого обрабатывает свой тип выражений:
(define (evaluate exp vars vals)
((cond ((symbol? exp) eval-variable)
((pair? exp)
(case (car exp)
((quote) eval-quote)
((if) eval-if)
... ; другие специальные формы
((lambda)
(case (length (cadr exp))
((0) eval-lambda-0)
((1) eval-lambda-1)
((2) eval-lambda-2)
(else eval-lambda)))
(else
(case (length (cdr exp))
((0) eval-application-0)
((1) eval-application-1)
((2) eval
