Лисп на Лиспе

То, что нами было проделано, можно представлять себе, как реализацию интерпретатора для языка продукций, но с иной точки зрения, это также является и точным описанием того, как работает такой язык. Теперь мы сделаем то же самое на примере некоторого элементарного языка, оперирующего символами. Будем называть этот язык MICRO (МИКРО), поскольку это будет как бы упрощенный Микролисп.

Простой язык оперирования символами можно интерпретировать с помощью небольшого числа функций Лиспа

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

Как и полагается, начнем с выбора обозначений.

• Все функции в языке MICRO начинаются с М-. Так, M-CAR, M-CDR, M-CONS, М-EQUAL и М-АТОМ аналогичны CAR, CDR, CONS, EQUAL и ATOM языка Лисп.
• Все функции, определенные в Лиспе, необходимые для реализации языка MICRO, начинаются с MICRO-. Так, MICRO-EVAL, MICRO-APPLY,-MICRO-DEFINE - все являются теми важными функциями, которые определены в Лиспе и необходимы для интерпретации выражений языка MICRO.

Ключевыми функциями являются MICRO-EVAL и MICRO- APPLY. На самом деле, вся работа может быть выполнена только с использованием MICRO-EVAL и MICRO-APPLY, но этого не делается, поскольку наличие вспомогательных функций упрощает систему и облегчает ее понимание. Работа интерпретирующей программы следующим образом распределяется между MICRO-EVAL и MICRO-APPLY:

• MICRO-EVAL воспринимает программы в форме s-выражений. Если данное s-выражение является атомом, то возвращается его значение. В противном случае MICRO-EVAL ищет специальные формы М-QUOTE и М-COND, и если ни одна из них не присутствует, то устанавливается стандартный порядок выполнения в глубину, слева направо.
• MICRO-APPLY узнает и выполняет элементарные функции М CAR, M-CDR, M-CONS, М-АТОМ и M-EQVAL. MICRO-APPLY находит определения для всех встреченных функций, которые не совпадают с указанными пятью элементарными. MICRO-APPLY, кроме того, сохраняет значения переменных, по мере того как происходит обращение к M-LAMBDA-выражениям и их выполнение.

Обратите внимание на то, что переменные и значения переменных хранятся в виде пар в переменной a-список (сокращение от "ассоциативный список", по-английски a-list). Рассмотрим a-список со следующим значением:

((ВАЗА КУВШИН) (ПРЕДЛОЖЕНИЕ (ПЕРЕД НАМИ ВАЗА))...)

Он указывает, что значением переменной ПРЕДЛОЖЕНИЕ является список (ПЕРЕД НАМИ ВАЗА), а значением переменной ВАЗА является КУВШИН. Эти значения при необходимости извлекаются посредством новой функции ASSOC с помощью С ADR.

• Первый аргумент функции ASSOC используется в качестве ключа, совпадение с которым отыскивается в a-списке, являющемся вторым аргументом. Во время работы функция ASSOC продвигается вдоль a-списка, пока не будет найден такой его элемент, CAR от которого совпадает с данным ключом. Значением ASSOC является обнаруженный элемент вместе с ключом. Если совпадения с ключом нет, то значением является NIL.

В указанном определении функции MICRO-EVAL необходим также тест для М-QUOTE, потому что в языке MICRO необходимо иметь некоторый эквивалент механизма одиночной кавычки Лиспа. Функция М-QUOTE годится потому, что в отличие от других функций она не оценивает своего аргумента, таким образом защищая выражения точно так же, как это делает одиночная кавычка в языке Лисп. На самом деле, имеется тесная аналогия с тем, как в действительности обрабатывается одиночная кавычка в Лиспе.

• Когда коды Лиспа считываются из некоторого файла в оперативную память, знаки одиночной кавычки переводятся в применения функции QUOTE. Это нужно, потому что интерпретатор Лиспа требует, чтобы и программы, и данные были строго выражены в однородной форме s-выражений. Механизм одиночной кавычки не входит в рамки определения s-выражения, хотя он делает программы яснее и облегчает этап обучения. Таким образом, между системой Лисп и текстом, подготавливаемым программистом, стоит буферная программа, которая, помимо прочего, выполняет также и следующую трансляцию:

Возвращаясь к функции MICRO-EVAL, заметим, что обычно все аргументы получают значение. Сама функция, оцененные аргументы и текущий а-список - все три поступают в функцию MICRO-APPLY:

Вскоре станет ясно, что ключевым моментом для всего является оценка М-ламбда-выражений. Заметим, что они поступают в MICRO-EVAL в следующей форме:

Такие выражения передаются в MICRO-APPLY, при этом переменным MICRO-APPLY присваиваются значения:

Функция MICRO-APPLY строит список пар переменных и аргументов, помещает его в a-список, а затем передает тело М-ламбда-выражения назад в функцию MICRO-EVAL с новым, расширенным значением для a-списка. Функция MICRO-APPLY разрушает М-ламбда-выражения, создавая материал для функции MICRO-EVAL из их кусков.

Схожим образом рассматриваются определенные пользователем функции, поскольку в рамках нашей реализации определения функций хранятся в свойстве M-EXPR в форме М-ламбда-выражений. Таким образом, М-ламбда-выражения языка MICRO представляют собой как раз то, как выглядят все функции, когда они передаются для оценивания. Когда в позиции функции находится имя атома, то оно лишь замещает там М-ламбда-выражение, которое скрыто в списке свойств этого атома.

Используются также две вспомогательные функции, одна из которых обеспечивает специфический синтаксис функции M-COND, а другая - строит пары из переменных и их значений:

Заметим, что при таком определении функции MICRO-EVALCOND, у предложений функции М-COND допускается лишь два элемента, как в некоторых старых версиях Лиспа.

Остается вопрос выполнения пяти основных примитивов языка MICRO. Как показывает определение MICRO-APPLY, они непосредственно имитируются эквивалентными функциями Лиспа, работающими со списком аргументов, связанным с атомом ARGS (АРГУМЕНТЫ).

Помещением определений функций в список свойств занимается функция MICRO-DEFINE, которая преобразует определения функций из обычной формы в форму М-ламбда:

На этом в основном завершается построение MICRO. Далее можно все более и более расширять возможности системы, пользуясь собственным механизмом определения функций, присущим системе MICRO. Так, например, функции М-NULL и M-APPEND могут быть определены через примитивы системы:

В действительности MICRO можно было бы поднять на уровень Лиспа, делая такие добавления, а также усиливая возможности интерпретатора, главным образом, чтобы включить в рассмотрение числа, формы типа PROG и функциональные определения в виде FEXPR.

Лисп лучше всего определять через Лисп

Было бы жульничеством заявлять, что MICRO похож на Лисп, потому что MICRO по существу - это переодетый Лисп. Если отбросить приставки М- и MICRO- в определении интерпретатора, то становится ясно, что это Лисп!

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

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

То, что это может быть сделано с использованием лишь простых функций, которые описаны приведенными программами на Лиспе, наводит на мысль, что может быть создан некоторый примитивный, медленный Лисп путем построения этих функций на другом языке, используя описание Лиспа как руководство^*. Однако демонстрация этого не была здесь самоцелью. До сих пор мы объясняли довольно поверхностно, почти неряшливо, что в действительности происходит, когда функция получает определение и используется. Было сказано, что описания функций каким-то образом запоминаются, каким-то образом извлекаются и каким-то образом применяются к аргументам, которые сами по себе обычно оцениваются слева направо. Мы уточнили это описание в языке MICRO, чтобы показать работу Лиспа на более глубоком уровне.

^* ( По-видимому, на этом пути М. Нордстремом и Э. Сандеволлом был создан Лисп F1, реализованный на Фортране. В последнее время он был значительно расширен М. Нордстремом и получил название Лисп F. 3.- Прим. перев)

Мы более или менее подробно рассмотрели, что делает Лисп, когда сталкивается с функцией, определенной пользователем. Лисп на самом деле обращается к списку свойств за М-ламбда-определением.

Изощренные управляющие структуры обычно начинаются как интерпретаторы Лиспа

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