4.1 Метациклический интерпретатор

Наш интерпретатор Лиспа будет реализован как программа на Лиспе. Может показаться, что размышления о выполнении Лисп-программ при помощи интерпретатора, который сам написан на Лиспе, составляют порочный круг. Однако вычисление есть процесс, так что вполне логично описывать процесс вычисления с помощью Лиспа - в конце концов, это наш инструмент для описания процессов.3 Интерпретатор, написанный на языке, который он сам реализует, называется метациклическим (metacircular).

В сущности, метациклический интерпретатор является формулировкой на языке Scheme модели вычислений с окружениями, описанной в разделе 3.2. Напомним, что в этой модели было две основные части:

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

•Чтобы применить составную процедуру к набору аргументов, нужно выполнить тело процедуры в новом окружении. Для того, чтобы построить это окружение, нужно расширить окружение объекта-процедуры кадром, в котором формальные параметры процедуры связаны с аргументами, к которым процедура применяется.

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

3 Даже с учетом этого, остаются важные стороны процесса вычисления, которые в нашем интерпретаторе не проясняются. Самая важная из них - точные механизмы того, как одни процедуры вызывают другие и возвращают значения процедурам, которые их вызвали. Эти вопросы мы рассмотрим в главе 5, где мы исследуем процесс вычисления более внимательно, реализуя вычислитель как простую регистровую машину.

4Если нам дается возможность применять примитивы, то что остается сделать для реализации интерпретатора? Задача интерпретатора состоит не в том, чтобы определить примитивы языка, а в том, чтобы обеспечить связующие элементы - средства комбинирования и абстракции, - которые превращают набор примитивов в язык. А именно:

•Интерпретатор позволяет работать с вложенными выражениями. Например, чтобы вычислить значение выражения (+ 1 6), достаточно применения примитивов, но этого недостаточно для работы с выражением (+ 1 (* 2 3)). Сама по себе элементарная процедура + способна работать только с числами, и если передать ей аргумент - выражение (* 2 3), она сломается. Одна из важных задач интерпретатора - устроить вычисление так, чтобы (* 2 3) свелось к значению 6, прежде чем оно будет передано + как аргумент.

•Интерпретатор позволяет использовать переменные. Например, элементарная процедура сложения не знает, как работать с выражениями вроде (+ x 1). Нам нужен интерпретатор, чтобы следить за переменными и получать их значения, прежде чем запускать элементарные процедуры.

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

•Интерпретатор дает особые формы, вычисляющиеся иначе, чем вызовы процедур.

выражение, окружение

Рис. 4.1: Цикл eval-apply раскрывает сущность компьютерного языка.

двух основных процедур интерпретатора, eval и apply, описанных в разделе 4.1.1 (см. рис. 4.1).

Реализация интерпретатора будет зависеть от процедур, определяющих синтаксис (syntax) выполняемых выражений. При помощи абстракции данных мы сделаем интерпретатор независимым от представления языка. К примеру, вместо того, чтобы окончательно решать, что присваивание выражается в виде списка, в котором первым элементом стоит символ set!, мы пользуемся абстрактным предикатом assignment?, чтобы распознавать присваивание, и абстрактными селекторами assignment-variable и assignment-value, чтобы обращаться к его частям. Реализация выражений будет подробно рассмотрена в разделе 4.1.2. Имеются также операции, описанные в разделе 4.1.3, которые определяют представление процедур и окружений. Например, make-procedure порождает составные процедуры,lookup-variable-value извлекает значения переменных, а apply-primitive-procedure применяет элементарную процедуру к указанному списку аргументов.

4.1.1 Ядро интерпретатора

Процесс вычисления можно описать как взаимодействие двух процедур: eval и apply.

Eval

Процедура eval в качестве аргументов принимает выражение и окружение. Она относит выражение к одному из возможных классов и управляет его выполнением. Eval построена как разбор случаев в зависимости от синтаксического типа выполняемого выражения. Для того, чтобы процедура была достаточно общей, определение типа выражения мы формулируем абстрактно, не связывая себя никакой конкретной реализацией различных типов выражений. Для каждого типа выражений имеется предикат, который распознает этот тип, и абстрактные средства для выбора его частей. Такой абстрактный синтаксис (abstract syntax) позволяет легко видеть, как можно изменить синтаксис языка и использовать тот же самый интерпретатор, но только с другим набором синтаксических процедур.

процедура, аргументы

Элементарные выражения

•Для самовычисляющихся выражений, например, чисел, eval возвращает само выражение.

•Eval должен находить значения переменных, просматривая окружение. Особые формы

•Для выражений с кавычкой (quote), eval возвращает само закавыченное выражение.

•Присваивание переменной (или ее определение) должно вызвать eval рекурсивно, чтобы вычислить новое значение, которое требуется связать с переменной. Окружение нужно модифицировать, изменяя (или создавая) связывание для переменной.

•Выражение if требует специальной обработки своих частей: если предикат истинен, нужно выполнить следствие; если нет, альтернативу.

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

•Выражение begin требует выполнения своих подвыражений в том порядке, как они появляются.

•Разбор случаев (cond) преобразуется во вложенные выражения if и затем вычисляется.

Комбинации

•Для применения процедуры eval должна рекурсивно вычислить операцию и операнды комбинации. Получившиеся процедура и аргументы передаются apply, которая распоряжается собственно применением процедуры.

Вот определение eval:

(define (eval exp env)

(cond ((self-evaluating? exp) exp)

((variable? exp) (lookup-variable-value exp env)) ((quoted? exp) (text-of-quotation exp)) ((assignment? exp) (eval-assignment exp env)) ((definition? exp) (eval-definition exp env)) ((if? exp) (eval-if exp env)) ((lambda? exp) (make-procedure (lambda-parameters exp) (lambda-body exp) env))

((begin? exp)

(eval-sequence (begin-actions exp) env)) ((cond? exp) (eval (cond->if exp) env)) ((application? exp)

(apply (eval (operator exp) env)

(list-of-values (operands exp) env)))

(else

(error "Неизвестный тип выражения -- EVAL" exp))))