Квазицитирование в 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. Итак, какие же правила упрощения приводят к практически используемым префиксам? Их три, и каждое из них имеет простое обоснование:

1. ,@'(expr) упрощается до expr, если expr не содержит обратных кавычек. Мы уже встречались с этим правилом в более простой форме.

2. ,@'(expr) упрощается до ,'expr, если expr содержит обратные кавычки, но не выполняет никакого структурного раскрытия. Если expr будет просто одним значением, нет смысла заключать его в список и разворачивать позже — мы можем просто вернуть его как есть.

3. (,@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-application-2)))))
         (else eval-constant))
   exp vars vals))

Анонимные функции и вызовы без аргументов, с одним и двумя аргументами обрабатываются отдельно, чтобы избежать неизбежной неэффективности общих случаев. Окружение, которое традиционно представляется в виде ассоциативного списка разделено на два изоморфных дерева: vars — дерево символов, представляющих имена переменных, и vals — дерево ассоциированных значений. Например, обычное окружение a-list

((a . 1) (b . 2) (c . 3))

может быть представлено с использованием vars:

((a . b) c)

и vals:

((1 . 2) 3)

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

Значение лямбда-выражения с двумя аргументами – это процедура, которая при вызове соответствующим образом расширяет vars и vals, а затем вызывает eval-sequence, чтобы вычислить выражение для его тела:

(define (eval-lambda-2 exp vars vals)
  (lambda (arg0 arg1)
    (eval-sequence (cddr exp)
                   (list (caadr exp) (cadadr exp) vars)
                   (list arg0 arg1 vars))))

Чтобы вычислить значение условного выражения, мы сначала вычисляем значение условия. Если значение условия #T, мы должны вычислить значение второго аргумента, а если нет, то третьего:

(define (eval-if exp vars vals)
  (if (evaluate (cadr exp) vars vals)
      (evaluate (caddr exp) vars vals)
      (evaluate (cadddr exp) vars vals)))

Чтобы вычислить результат вызова процедуры с двумя аргументами, мы сначала должны вычислить выражение для процедуры и выражения для аргументов. Затем полученная процедура применяется к значениям аргументов:

(define (eval-application-2 exp vars vals)
  ((evaluate (car exp) vars vals)
   (evaluate (cadr exp) vars vals)
   (evaluate (caddr exp) vars vals)))

Компилятор «шитого» кода

Теперь мы преобразуем этот интерпретатор в компилятор, который генерирует «шитый» код, построенный из замыканий. Это может быть достигнуто путём каррирования функции evaluate:

(define (evaluate exp vars vals)
  ((compile exp vars) vals))

Процедура compile применяется к исходному коду выражения exp и дереву имён переменных vars. Она преобразует выражение в функцию (замыкание), которая позже будет применена к дереву, в котором мы храним значения переменных vals. Эта сгенерированная процедура вычислит данное выражение намного быстрее, чем наш исходный интерпретатор, потому что большая часть накладных расходов на интерпретацию будет выполнена во время компиляции. (Для подробного рассмотрения этой техники см. Freeley and Lapalme [7].)

Диспетчеризация, выполняемая исходной evaluate, теперь производится функцией compile:

(define (compile exp vars)
  ((cond ((symbol? exp) compile-variable)
         ((pair? exp)
          (case (car exp)
            ((quote) compile-quote)
            ((if) compile-if)
            ...   ; другие специальные формы
            ((lambda)
             (case (length (cadr exp))
               ((0) compile-lambda-0)
               ((1) compile-lambda-1)
               ((2) compile-lambda-2)
               (else compile-lambda)))
          (else
           (case (length (cdr exp))
             ((0) compile-application-0)
             ((1) compile-application-1)
             ((2) compile-application-2)
             (else compile-application)))))
         (else compile-constant))
   exp vars))

Заметим, что дерево значений переменных vals нигде не присутствует в определении compile; каждый отдельный генератор кода (compile-if и т.д.) ответственен за создание процедуры, которая затем будет применена к дереву значений vals.

Лямбда-выражение с двумя аргументами может быть скомпилировано так:

(define (compile-lambda-2 exp vars)
  (let ((run (compile-sequence (cddr exp)
                               (list (caadr exp)
                                     (cadadr exp)
                                     vars))))
       (lambda (vals)
         (lambda (arg0 arg1)
           (run (list arg0 arg1 vals))))))

Тело лямбда-выражения компилируется заранее процедурой compile-sequence, сгенерированная ей процедура является просто замыканием run, содержащим внутри себя скомпилированный код.

Условные выражения и двухаргументные вызовы компилируются следующим образом:

(define (compile-if exp vars)
  (let ((run-test (compile (cadr exp) vars))
        (run-true (compile (caddr exp) vars))
        (run-false (compile (cadddr exp) vars)))
       (lambda (vals)
         (if (run-test vals)
             (run-true vals)
             (run-false vals)))))

(define (compile-application-2 exp vars)
  (let ((run-fun (compile (car exp) vars))
        (run-arg0 (compile (card exp) vars))
        (run-arg1 (compile (carddr exp) vars)))
       (lambda (vals)
         ((run-fun vals) (run-arg0 vals) (run-arg1 vals)))))

В обоих случая мы сначала компилируем три подвыражения, а затем создаём замыкание.

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

Важным источником эффективности сгенерированного кода является поведение процедуры compile-variable. Наиболее эффективной процедурой, которую может вернуть compile-variable является один из методов доступа к структуре примитивного списка. Например, такой вызов:

(compile-variable 'y '(x (y z)))

должен вернуть примитив caadr.

Компилятор из Scheme в Scheme

Затратив совсем немного сил, мы можем преобразовать наш компилятор так, чтобы он генерировал код на Scheme. Каррирование, которое мы применили к изначальной процедуре evaluate сводилось к выполненному вручную частичному вычислению: мы разделили аргументы процедуры интерпретации на статические (exp и vars) и динамические (vals), а затем мы переупорядочили вычисления так, чтобы зависеть лишь от статической информации, когда мы вызываем compile. Теперь, всё, что нам нужно сделать, это изменить кодогенератор так, чтобы вместо замыканий он записывал код на Scheme.

Так как процедура compile не генерирует никакого кода внутри своего тела, мы её не меняем.

Чтобы преобразовать compile-lambda-2 из генератора замыканий в кодогенератор обычного кода на Scheme нам нужно вставить лишь два символа:

(define (compile-lambda-2 exp vars)
  (let ((run (compile-sequence (cddr exp)
                               (list (caadr exp)
                                     (cadadr exp)
                                     vars))))
       `(lambda (vals)
          (lambda (arg0 arg1)
            (,run (list arg0 arg1 vals))))))

Очень внимательный читатель может заметить, что мы вставили обратную кавычку перед лямбда-выражением, которое раньше создавало возвращаемую функцию, и запятую перед переменной run.

Кодогенераторы для условных выражений и двухаргументных вызовов также могут быть преобразованы в кодогенераторы Scheme кода буквально несколькими обратными кавычками и запятыми:

(define (compile-if exp vars)
  (let ((run-test (compile (cadr exp) vars))
        (run-true (compile (caddr exp) vars))
        (run-false (compile (cadddr exp) vars)))
       `(lambda (vals)
          (if (,run-test vals)
              (,run-true vals)
              (,run-false vals)))))

(define (compile-application-2 exp vars)
  (let ((run-fun (compile (car exp) vars))
        (run-arg0 (compile (card exp) vars))
        (run-arg1 (compile (carddr exp) vars)))
       `(lambda (vals)
          ((,run-fun vals) (,run-arg0 vals) (,run-arg1 vals)))))

Во всех трёх случаях выражения, созданные квазицитированием, не содержат никаких свободных переменных кроме примитивов Scheme. Переменные, которые были бы свободными (run, run-test, run-fun и прочие), сейчас предваряются запятыми. Таким образом, на каждом этапе процесса compile возвращает замкнутое выражение (то есть, использующее только примитивы Scheme), и каждый элементарный кодогенератор также имеет это свойство.

При компиляции переменных мы теперь должны возвращать не сам примитив (caadr), а его имя. Выражение:

(compile-variable 'y '(x (y z)))

теперь возвращает символ 'caadr.

Скомпилировав с помощью новой версии compile выражение

(lambda (n)
  (if (< n 2)
      1
      (* (fact (- n 1))
         n)))

мы получим (после нескольких тривиальных β-редукций):

(lambda (vals)
  (lambda (arg0)
    ((lambda (vals)
       (if (< (car vals) '2)
              '1
              (* (fact (- (car vals) '1))
                 (car vals))))
     (cons arg0 vals))))

После того, как мы передадим вывод compile какому-нибудь из обычных компиляторов Scheme, тот сгенерирует вполне разумный машинный код.

Конечно, мы могли бы передать наш исходный код в компилятор Scheme напрямую, чтобы получить ещё лучший машинный код. Но наше упражнение отнюдь не бессмысленно, поскольку мы можем проделать всё то же самое с интерпретатором для какого-нибудь нового языка, который мы сами же и придумаем. Выполнив те же шаги, мы получим компилятор, который компилирует наш новый язык в обыкновенный Scheme. А после этого мы можем скомпилировать этот код Scheme в машинный код обычным компилятором Scheme (скажем, популярным в данный момент Chez Scheme или оптимизирующим компилятором Stalin, прим. пер.).

Проблема Окружения

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

Сама проблема

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

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

(define (make-list-proc expr const)
  `(lambda (x) (list x ,expr const)))

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

Если мы вычислим (make-list-proc '(+ x 1) 'foo), результатом станет:

(lambda (x) (list x (+ x 1) const))

А тут есть две проблемы:

• Выражение, которое мы передали make-list-proc, в качестве первого аргумента содержало свободную переменную x, которая непреднамеренно стала связанной лямбда-выражением, созданным make-list-proc. Мы могли бы это назвать проблемой «захвата снизу».

• Переменная const в построенном выражении свободна — она никоим образом не ссылается на предоставленную нами константу foo, несмотря на то, что второй аргумент make-list-proc был назван const. Мы могли бы это назвать проблемой «убегания вверх».

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

(define (make-list-proc expr const)
  (let ((x (gensym)))
    `(lambda (,x) (list ,x ,expr ',const))))

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

Возможные решения

В традиционных диалектах Lisp (включая Common Lisp) программистам инструментарий не помогает избежать проблем с окружением, за исключением возможности создавать уникальные символы (обычно с помощью процедуры gensym). Эта техника используется в исправленной версии make-list-proc. Используя сгенерированные символы и другие тщательно подобранные имена, программист может написать макрос, который на 100% свободен от проблем с захватом, но это может быть весьма трудоёмко. Большинство же авторов заботятся только о том, чтобы предотвратить наиболее вероятные проблемы с захватом имён, но на практике этого, как правило, достаточно.

С середины 1980-х сообщество Scheme экспериментирует с различными технологиями, которые позволяют (или заставляют) программистов легко писать макросы, не связанные с проблемами окружения. Некоторые из этих технологий представляют собой высокоуровневые средства определения макросов, которые вообще не используют квазицитирование [5, 10], поэтому здесь они нам не интересны. Другие добавляют новые низкоуровневые инструменты, которые используются в сочетании с квазицитированием [1, 3].

В одной из этих низкоуровневых систем определение макроса, такое как:

(define-macro (push expr var)
  `(set! ,var (cons ,expr ,var)))

может быть переписано в виде:

(define-macro (push expr var)
  (let ((*set! (rename 'set!))
        (*cons (rename 'cons)))
    `(,*set! ,var (,*cons ,expr ,var))))

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

«Синтаксические макросы для C» Weise и Crew [22] решают проблему окружения точно также, как она решается в традиционном Lisp: программист получает механизм квазицитирования для построения синтаксических деревьев программ на C, а также средство gensym. Не удивляет, что они так сильно подражали традиционному Lisp, ведь их целью был просто перенос преимуществ макросов Lisp в C.

В последнее время растёт интерес к «поэтапным вычислениям» [4, 6, 8, 20]. Такие системы обычно используют для построения кода механизм, похожий на квазицитирование, и поэтому должны каким-то образом решить проблему окружения.

Язык Mini-ML◻ за авторством Davies и Pfenning [4] использует тот же минималистичный подход, что и компилятор в предыдущем разделе: код, построенный с помощью его операции квазицитирования (называемой «box»), всегда закрыт, поэтому непреднамеренный захват переменной окружения исключён. Такое строгое разделение этапов в языке поиска вполне разумно, но оно может быть неудобным в инструменте, используемом передовыми программистами.

Любая практическая система поэтапных вычислений, вероятно, будет обладать свойством, которые Taha и Sheard называют «cross-stage persistance» («постоянство между этапами») [20]. Система обладает «cross-stage persistance» если на переменные, связанные на более ранних этапах, можно ссылаться на более поздних этапах. Их язык MetaML обладает этим свойством, также как и язык `C [6].

Одна из причин, по которой наша первая версия make-list-proc потерпела неудачу, заключалась в том, что квазицитирование Lisp не обладает «cross-stage persistance»: символ const, появляющийся в шаблоне квазицитирования, не имел связи с переменной const, связанной в окружении, в котором была написана квазицитата. Когда же «cross-stage persistance» присутствует, переменные в сконструированном коде могут ссылаться на переменные из лексического окружения. В такой системе объекты кода, создаваемые квазицитированием должны быть сложнее, чем простые S-выражения; чтобы захватить лексическое окружение, в котором написана квазицитата, эти объекты должны быть замыканиями. [^2]

Объекты кода с «cross-stage persistance» аналогичны параметризованным объектам Lamping'а [11]. Lamping также руководствовался желанием манипулировать выражениями так, как это позволяло бы квазицитирование, но без отрыва этих выражений от контекста, из которого они произошли. Его data-выражения — ещё один пример чего-то вроде квазицитирования, производящего что-то вроде замыканий.

История

Название «Quasi-Quotation» было придумано W.V. Quine [16] около 1940 года. Квазицитирование Quine основывалось на строках символов. Он использовал «угловые кавычки» (┌...┐) для обозначения квазицитирования, и у него не было явного маркера для «отмены блокировки интерпретации», вместо этого любая греческая буква неявно помечалась для замены. Так, например, если φ означает слово "bar", то

┌foo(φ)┐

будет означать строку "foo(bar)".

Quine использовал квазицитирование для построения выражений из матлогики, и, как мы и предсказывали из нашего опыта представления выражений из C, он был вынужден принять различные соглашения и сокращения, включающие круглые скобки. (Он мог бы избежать этих трудностей, используй он S-выражения!)

McCarthy разработал Lisp и S-выражения [13] примерно в 1960 году, но не предложил никакой формы квазицитирования на основе S-выражений. Учитывая, что он был вдохновлён λ-исчислением, в котором есть собственное понятие подстановки, нельзя не задаться вопросом, на что был бы похож Lisp, если бы он также попытался внедрить квазицитирование.

В течение 1960-х и 70-х годов сообщество программистов искусственного интеллекта приложило массу усилий, чтобы научиться программировать с помощью S-выражений и списков. Многие из программ искусственного интеллекта тех лет привели к разработке методологий программирования на Lisp, включавших сопоставление шаблонов S-выражений и создание экземпляров шаблонов способами, которые связаны с современной технологией квазицитирования S-выражений. В частности, понятие «структурного раскрытия» («splicing», прим. пер.), описанное в разделе 3.1, явно происходит от этих методологий.

Но ничто из тех лет не напоминает современные обозначения столь сильно, как синтаксис языка Conniver за авторством McDermott и Sussman [14]. В синтаксисе Conniver `X, ,X и ,@X записывались как !"X, @X и !X соответственно, но идея была в сущности той же (в Conniver также присутствовала конструкция ,X, которую можно было рассматривать примерно как @X, поэтому вполне возможно, что именно так символ запятой (,) в конечном итоге стал занимать свою нишу в механизме квазицитирования).

После Conniver квазицитирование вошло в набор инструментов программиста на Lisp. К середине 1970-х многие программисты на Lisp использовали свои собственные версии квазицитирования. Но оно ещё не было встроено ни в один из диалектов Lisp.

Моё личное знакомство с этой историей началось в 1977 году, когда я начал программировать для проекта Lisp Machine в MIT. В то время квазицитирование было частью системы Lisp Machine. Обозначения были почти как современные, за исключением того, что вместо ,@X для обозначения структурного раскрытия использовалось ,,X. Это, очевидно, мешало бы вложенному квазицитированию, но это никого не беспокоило, поскольку повсеместно считалось, что вложенное квазицитирование не «работает как должно».

Я решил выяснить, почему вложенные квазицитаты не работают. Используя тот же процесс рассуждений, который я изложил выше в разделе 3.2, я разработал несколько тестовых программ и опробовал их. К моему удивлению, в действительности они работали идеально. Проблема в том, что никто не мог заставить вложенные квазицитаты делать то, что им было нужно, а не в том, что существовала ошибка в коде раскрытия. (то есть, программисты не владели этим инструментом в совершенстве, прим. пер.) [^3]

Выяснив, что вложенное квазицитирование работает правильно, мы захотели начать его использовать, и поэтому нужно было найти новое обозначение для структурного раскрытия. Я предложил .X, потому что .,X уже выполняет своего рода структурное раскрытие (см. раздел 3.1). Я думал, что это будет неплохой каламбур. Другие члены нашей группы решили, что это может сбивать с толку. Вероятно вдохновлённые Scheme, которая в те дни использовала только @X для обозначения структурного раскрытия [19], мы, наконец, остановились на ,@X [21]. [^4]

Тем временем McDermott слегка изменил синтаксис Conniver, введя |"X вместо !"X. В этой форме он появился в первом издании Artificial Intelligence Programming [2] в 1980 году.

Насколько мне известно, проблемы вложенного структурного раскрытия не были решены до 1982 года. В январе того же года Guy Steele распространил пример квазицитирования с трёхуровневой вложенностью. Он заметил, что ,',',X было «достаточно очевидным», но ему «пришлось попотеть», чтобы начать правильно использовать ,,@X [17]. В моём ответе я привёл анализ вложенного структурного раскрытия (очень похожий на приведённый в разделе 3.3), в котором я отметил, что для того, чтобы структурное раскрытие было последовательным и полезным, нужно использовать алгоритм, подобный представленному в приложении А. Правильная семантика и алгоритм раскрытия для квазицитирования, основанный на этом наблюдении появился во втором издании Common LISP: The Language [18].

Guy Steele любезно переслал мне все связанные с квазицитированием сообщения из своего архива электронной почты за январь 1982 года. Среди этих сообщений есть ещё один пример тройного квазицитирования. Он встречается в сообщении, отправленном Стилу Биллом Лонгом [12], и содержащим некоторый код, первоначально написанный David McAllester'ом. Код содержит конструкцию ,@',(list ,@params). Поскольку ,(list expr) эквивалентно (,expr), код McAllester'а может быть переписан как ,@'(,,@params), в чём читатель легко узнает один из двух простейших примеров вложенного структурного раскрытия из раздела 3.3, который не может быть выражен без использования круглых скобок. Так что McAllester, вполне возможно, является первым, покорившим эту вершину квазицитирования.

Где-то в 1980-х мы начали писать «quasi-quote» без дефиса. Возможно, это результат принятия в Scheme специальной формы под названием quasiquote.

К концу 1980-х годов в стандарты Common Lisp [18] и Scheme [9] были включены современные обозначения квазицитирования.

Самогенерация

Ни одна статья о квазицитировании в Lisp не может считаться законченной без упоминания вклада квазицитирования в извечную задачу написания выражения на Lisp, значением которого является оно само. Квазицитирование даёт множество элегантных решений этой задачи. Следующее забавное решение принадлежит Mike McMahon:

(let ((let '`(let ((let ',let))
               ,let)))
  `(let ((let ',let))
  ,let))

Заключение

Квазицитирование — это простая идея, синергетическое сочетание которой с S-выражениями Lisp (тоже простой идеей!) создаёт мощный инструмент построения программ. Как часто это бывает с простыми идеями, возникает немало сложных мест, когда мы учитываем все детали («гладко было на бумаге, да забыли про овраги», прим. пер.). В случае квазицитирования, полный учёт вложенного взаимодействия со структурным раскрытием даёт интересную «алгебру unquotation».

У квазицитирования есть ограничение как у инструмента построения программ: оно не принимает во внимание области видимости переменных, которым подчиняются создаваемые выражения. Для преодоления этого ограничения было предложено множество различных подходов. До сих пор это активная область исследований. (даже сейчас, в 2023, прим. пер.)

Несмотря на мощную синергию между квазицитированием и S-выражениями, с момента изобретения Lisp потребовалось почти двадцать лет, чтобы квазицитирование получило широкое признание. Современная эра квазицитирования продлилась ещё примерно два десятилетия. Если в ближайшие двадцать лет и появятся какие-либо изменения в механизме квазицитирования, то это, скорее всего, будет добавление какого-то решения проблемы окружений.

Благодарности

Части этой статьи берут начало из двух электронных переписок, которые у меня произошли в 1982 году, одна с Drew McDermott и другая с Guy Steele. Собирая дополнительную информацию, я провел полезные беседы с Robert Muller, Brian C. Smith, Gerald Jay Sussman, John Lamping, Glenn Burke, Jonathan Bachrach, Daniel Weise, Mitch Wand, Kent Dybvig, Guy Steele, David McAllester, David Moon, Bill Long and Marc Feeley. Pandora Berman помогала в исследовании. Olivier Danvy, Julia Lawall и Charles Stewart предоставили полезные отзывы о различных черновиках этой статьи — ответственность за все оставшиеся недочёты лежит целиком и полностью на мне.

Приложение А

Это приложение содержит корректный алгоритм раскрытия квазицитирования S-выражений. Предположим, что какой-то более примитивный парсер Lisp уже прочитал квазицитаты, которые нужно раскрыть, и проставил соответствующую разметку. Допустим, что этот примитивный парсер также предоставляет четыре примитива:

• tag-backquote? — этот предикат будет истинным, если терм представляет собой обратную кавычку (`), за которой следует S-выражение.
• tag-comma? — этот предикат будет истинным для терма, являющегося запятой (,), за которой следует S-выражение.
• tag-comma-atsign? — этот предикат будет истинным для терма, представляющего собой символ ,@, за которым следует S-выражение.
• tag-data — эта функция определена только на объектах, удовлетворяющих любому из вышеперечисленных предикатов. При применении возвращает S-выражение, следовавшее за символом разметки квазицитирования.

Основной процедурой является qq-expand, которую следует применять к выражению, непосредственно следующему за символом обратной кавычки (`). (То есть, символ обратной кавычки должен быть удален до вызова qq-expand.)

(define (qq-expand x)
  (cond ((tag-comma? x)
         (tag-data x))
        ((tag-comma-atsign? x)
         (error "Illegal"))
        ((tag-backquote? x)
         (qq-expand (qq-expand (tag-data x))))
        ((pair? x)
         `(append ,(qq-expand-list (car x))
                  ,(qq-expand (cdr x))))
        (else `',x)))

Обратите внимание, что любые встроенные квазицитаты, обнаруженные qq-expand, рекурсивно раскрываются, и раскрытие затем обрабатывается так, как будто оно было встречено вместо изначального текста.

qq-expand-list вызывается для раскрытия тех частей квазицитат, которые встречаются внутри списка, где допустимо использование структурного раскрытия. Она очень похожа на qq-expand, за исключением того, что qq-expand конструирует код, возвращающий значение, а qq-expand-list — код, который возвращает список, содержащий это значение.

(define (qq-expand-list x)
  (cond ((tag-comma? x)
         `(list ,(tag-data x)))
        ((tag-comma-atsign? x)
         (tag-data x))
        ((tag-backquote? x)
         (qq-expand-list (qq-expand (tag-data x))))
        ((pair? x)
         `(list (append ,(qq-expand-list (car x))
                        ,(qq-expand (cdr x)))))
        (else `'(,x))))

Код, созданный qq-expand и qq-expand-list, выполняет построение всех списков с помощью append или list. Ни в коем случае нельзя использовать cons. Как объяснялось в разделе 3.3, это важно для правильной работы вложенного квазицитирования, содержащего структурное раскрытие.

Представленный выше код корректен, но далёк от оптимального по быстродействию. В реальной реализации Lisp потребуется более оптимизированный вариант. Подобный код для Common Lisp приведён в [18, Приложение C].

Приложение Б

Стандарт Scheme [9] затрудняет реализацию вложенного структурного раскрытия, описанную в этой статье. В стандарте явно указано, что `X, ,X и ,@X должны читаться как (quasiquote X), (unquote X) и (unquote-splicing X), соответственно. Это означает, что код ``(,,@abc) должен быть эквивалентен:

(quasiquote (quasiquote ((unquote (unquote-splicing abc)))))

и если значение abc равно (a b c), то выражение выше должно раскрываться в:

(quasiquote ((unquote a b c)))

Однако, стандарт ничего не говорит о том, что же означает unquote, если он используется не с одним подвыражением, а сразу несколькими. Часть реализаций Scheme игнорирует второе и последующее подвыражения, обрабатывая (unquote a b c) так, как если бы это было (unquote a). Другие же сигнализируют в таком случае об ошибке.

Поначалу это выглядит ужасно: кажется, что задав чрезмерно сильное определение unquote, стандарт Scheme сломал возможность реализовать структурное раскрытие как в Common Lisp.

К счастью, мы всё ещё можем восстановить правильное поведение вложенного структурного раскрытия, создав совместимое расширение стандарта Scheme, которое придаёт полезное значение выражениям unquote и unquote-splicing, содержащим больше одного подвыражения. Это расширение является аналогом правил этапа чтения, приведённых в подразделе 3.3, только оно работает на этапе раскрытия макросов. А именно, когда квазицитирование раскрывается, каждая последовательность подвыражений, найденная внутри unquote, должна обрабатываться так, как если бы они были последовательными аргументами в вызове list. Аналогично, каждая последовательность подвыражений, найденная внутри unquote-splicing, должна обрабатываться так, как если бы они были последовательными аргументами в вызове append. Тогда код

(quasiquote (a (unquote x y) b))

должен вести себя как

(list 'a x y 'b)

и код

(quasiquote (a (unquote-splicing x y) b))

должен вести себя как

(append '(a) x y '(b))

Процедура qq-expand в таком случае отличается от процедуры из приложения А тем, что она применяется на этапе раскрытия макросов, а не на этапе чтения. По этой же причине она должна вести счёт обратным кавычкам, чтобы можно было сопоставить вхождения unquote и unquote-splicing с правильной заключающей их quasiquote. Этим подсчётом занимается аргумент depth в коде ниже, при первом вызове он должен быть установлен в 0.

Как и раньше, самая внешняя quasiquote должна быть удалена перед вызовом qq-expand.

(define (qq-expand x depth)
  (if (pair? x)
      (case (car x)
        ((quasiquote)
         `(cons 'quasiquote
                ,(qq-expand (cdr x) (+ depth 1))))
        ((unquote unquote-splicing)
         (cond ((> depth 0)
                `(cons ',(car x)
                ,(qq-expand (cdr x) (- depth 1))))
               ((and (eq? 'unquote (car x))
                     (not (null? (cdr x)))
                     (null? (cddr x)))
                (cadr x))
               (else
                (error "Illegal"))))
        (else
         `(append ,(qq-expand-list (car x) depth)
                  ,(qq-expand (cdr x) depth))))
  `' ,x))

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

(define (qq-expand-list x depth)
  (if (pair? x)
      (case (car x)
        ((quasiquote)
         `(list (cons 'quasiquote
                      ,(qq-expand (cdr x) (+ depth 1)))))
        ((unquote unquote-splicing)
         (cond ((> depth 0)
                `(list (cons ',(car x)
                             ,(qq-expand (cdr x) (- depth 1)))))
               ((eq? 'unquote (car x))
                `(list . ,(cdr x)))
               (else
                `(append . ,(cdr x)))))
        (else
         `(list (append ,(qq-expand-list (car x) depth)
                        ,(qq-expand (cdr x) depth)))))
  `'(,x)))

Примечания

[^1]: На самом деле в Scheme [9] точное раскрытие специфицировано: квазицитирование раскрывается в специальное quasiquote выражение. Но в практических применениях это бесполезно, и мы забудем об этом до приложения Б.

[^2]: Квазицитирование в этих поэтапных вычислительных системах во многом отличается от квазицитирования в Lisp. Они манипулируют только объектами кода, представляющими выражения, поэтому в них нет опасности создания синтаксически некорректного объекта кода. Объекты кода имеют такие типы как «код, возвращающий int», поэтому нет опасности создания объекта кода, в котором тип не проверяется. А поскольку не существует объектов кода, представляющих последовательность чего-либо, нет необходимости в каком-либо понятии структурного раскрытия.

[^3]: Код, раскрывающий макросы, в тот момент неправильно работал с вложенным структурным раскрытием, но я этого не заметил.

[^4]: Когда квазицитирование было перенесено из MacLisp [15] обозначение ,.X было выбрано для «деструктивного» структурного раскрытия. Считается, что это неплохая шутка. Эта обозначение также принято в Common Lisp [15].

Библиография

1. Alan Bawden and Jonathan Rees. Syntactic closures. In Proc. Symposium on Lisp and Functional Programming, pages 86-95. ACM, July 1988.

2. Eugene Charniak, Christopher K. Riesbeck, and Drew V. McDermott. Artificial Intelligence Programming. Lawrence Erlbaum Assoc., Hillsdale, NJ, first edition, 1980.

3. William Clinger. Hygienic macros through explicit renaming. LISP Pointers, 4(4):25—-28, December 1991.

4. Rowan Davies and Frank Pfenning. A modal analysis of staged computation. In Proc. Symposium on Principles of Programming Languages, pages 258-283. ACM, January 1996.

5. R. Kent Dybvig, Robert Hieb, and Carl Bruggeman. Syntactic abstraction in Scheme. Lisp and Symbolic Computation, 5(4):295-326, December 1992.

6. Dawson R. Engler, Wilson C. Hsieh, and M. Frans Kaashoek. ‘C: A language for fast, efficient, high-level dynamic code generation. In Proc. Symposium on Principles of Programming Languages, pages 131-144. ACM, January 1996.

7. Marc Feeley and Guy Lapalme. Using closures for code generation. Journal of Computer Languages, 12(1):47-66, 1987.

8. Ulrik Jorring and William L. Scherlis. Compilers and staging transformations. In Proc. Symposium on Principles of Programming Languages, pages 86-96. ACM, January 1986.

9. Richard Kelsey, William Clinger, and Jonathan Rees. Revised® report on the algorithmic language Scheme. Higher-Order and Symbolic Computation, 11(1):7-105, 1998. Also appears in ACM SIGPLAN Notices 33(9), September 1998.

10. Eugene M. Kohlbecker, Daniel P. Friedman, Matthias Felleisen, and Bruce Duba. Hygienic macro expansion. In Proc. Symposium on Lisp and Functional Programming, pages 151-161. ACM, August 1986.

11. John Lamping. A unified system of parameterization for programming languages. In Proc. Symposium on Lisp and Functional Programming, pages 316-326. ACM, July 1988.

12. William J. Long, January 1982. Electronic mail message to Guy Steele. Available on-line from ftp://ftp.bawden.org/archive/wjl-to-gls-11Jan1982.txt (уже нет, прим. пер.)

13. John McCarthy. LISP 1.5 Programmer’s Manual. MIT Press, 1962.

14. Drew V. McDermott and Gerald Jay Sussman. The Conniver reference manual. Memo 259a, MIT AI Lab, May 1972.

15. Kent M. Pitman. The revised MacLisp manual. TR 295, MIT LCS, May 1983.

16. Willard Van Orman Quine. Mathematical Logic. Harvard University Press, revised edition, 1981.

17. Guy L. Steele Jr., January 1982. Electronic mail message. Available on-line from
    ftp://ftp.bawden.org/archive/gls-15Jan1982.txt (уже нет, прим. пер.)

18. Guy L. Steele Jr. Common LISP: The Language. Digital Press, second edition, 1990.

19. Guy L. Steele Jr. and Gerald Jay Sussman. The revised report on SCHEME: A dialect of Lisp. Memo 452, MIT AI Lab, January 1978.

20. Walid Taha and Tim Sheard. Multi-stage programming with explicit annotations. In SIGPLAN Workshop on Partial Evaluation and Semantics-Based Program Manipulation, pages
    203-217. ACM, June 1997.

21. Daniel Weinreb and David Moon. Lisp Machine Manual. Symbolics Inc., July 1981.

22. Daniel Weise and Roger Crew. Programmable syntax macros. In Proc. Conference on Programming Language Design and Implementation, pages 156-165. ACM, June 1993.