Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 79
Текст из файла (страница 79)
Ядро интерпретатораПроцесс вычисления можно описать как взаимодействие двух процедур: eval иapply.EvalПроцедура eval в качестве аргументов принимает выражение и окружение. Она относит выражение к одному из возможных классов и управляет его выполнением. Evalпостроена как разбор случаев в зависимости от синтаксического типа выполняемоговыражения. Для того, чтобы процедура была достаточно общей, определение типа выражения мы формулируем абстрактно, не связывая себя никакой конкретной реализациейразличных типов выражений. Для каждого типа выражений имеется предикат, которыйраспознает этот тип, и абстрактные средства для выбора его частей.
Такой абстрактный синтаксис (abstract syntax) позволяет легко видеть, как можно изменить синтаксисязыка и использовать тот же самый интерпретатор, но только с другим набором синтаксических процедур.340Глава 4. Метаязыковая абстракцияЭлементарные выражения• Для самовычисляющихся выражений, например, чисел, 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)))4.1.
Метациклический интерпретатор341(else(error "Неизвестный тип выражения -- EVAL" exp))))Ясности ради, eval реализована как перебор альтернатив через cond. Недостатокэтой реализации — наша процедура обрабатывает только несколько указанных типоввыражений, и, не меняя определение eval, новые типы добавить нельзя. В большинствереализаций Лиспа распределение выражений по типам сделано в стиле, управляемомданными. Это дает пользователю возможность добавлять новые типы выражений, которые eval будет способен распознать, не меняя само определение eval.
(См. упражнение 4.3.)ApplyПроцедура apply принимает два аргумента: процедуру и список аргументов, к которым ее надо применить. Apply делит процедуры на два класса: для применения примитивов она зовет apply-primitive-procedure; составные процедуры она применяет,по очереди вычисляя выражения, составляющие тело процедуры. Окружение, в которомвычисляется тело составной процедуры, получается из базового окружения, хранящегосяв процедуре, добалением кадра, где параметры процедуры связываются с аргументами, ккоторым процедура применяется. Вот определение apply:(define (apply procedure arguments)(cond ((primitive-procedure? procedure)(apply-primitive-procedure procedure arguments))((compound-procedure? procedure)(eval-sequence(procedure-body procedure)(extend-environment(procedure-parameters procedure)arguments(procedure-environment procedure))))(else(error"Неизвестный тип процедуры -- APPLY" procedure))))Аргументы процедурОбрабатывая применение процедуры, eval получает список аргументов, к которым процедуру надо применить, при помощи list-of-values.
Процедура list-ofvalues в качестве аргумента берет список операндов комбинации. Она вычисляет каждый аргумент и возвращает список соответствующих значений5.(define (list-of-values exps env)(if (no-operands? exps)5 Ветку application? в eval можно было бы упростить, используя map (и постановив, что operandsвозвращает список) вместо того, чтобы писать явным образом процедуру list-of-values.
Мы решили неиспользовать здесь map, чтобы подчеркнуть, что интерпретатор можно написать без обращения к процедурамвысших порядков (а следовательно, его можно написать на языке, в котором нет таких процедур), притом, чтоязык, поддерживаемый интерпретатором, содержит процедуры высших порядков.Глава 4.
Метаязыковая абстракция342’()(cons (eval (first-operand exps) env)(list-of-values (rest-operands exps) env))))Условные выраженияПроцедура eval-if вычисляет предикатную часть выражения if в данном окружении. Если результат истинен, eval-if выполняет следствие, если нет, — альтернативу:(define (eval-if exp env)(if (true? (eval (if-predicate exp) env))(eval (if-consequent exp) env)(eval (if-alternative exp) env)))Использование true? в eval-if подчеркивает вопрос о связи между реализуемымязыком и языком реализации.
Выражение if-predicate выполняется в реализуемомязыке, и, следовательно, результат его является значением этого языка. Предикат интерпретатора true? переводит это значение в значение, которое может быть провереновыражением if в языке реализации: метациклическое представление истины может несовпадать с ее представлением в нижележащей Scheme6 .ПоследовательностиПроцедура eval-sequence вызывается из apply для выполнения последовательности выражений в теле процедуры, а также из eval для обработки последовательностивыражений в выражении begin. Она принимает в виде аргументов последовательностьвыражений и окружение, и выполняет выражения в том порядке, в котором они ей даны.Возвращаемое значение совпадает со значением последнего выражения.(define (eval-sequence exps env)(cond ((last-exp? exps) (eval (first-exp exps) env))(else (eval (first-exp exps) env)(eval-sequence (rest-exps exps) env))))Присваивания и определенияСледующая процедура обрабатывает присваивание переменным.
При помощи evalона находит значение, которое требуется присвоить, и передает переменную и получившееся значение в процедуру set-variable-value! для включения в текущее окружение.(define (eval-assignment exp env)(set-variable-value! (assignment-variable exp)(eval (assignment-value exp) env)env)’ok)6 В нашем случае, язык реализации и реализуемый язык совпадают. Размышления о значении true? расширяют наше сознание безотносительно к материальной сущности истины.4.1. Метациклический интерпретатор343Определения переменных обрабатываются сходным образом7 :(define (eval-definition exp env)(define-variable! (definition-variable exp)(eval (definition-value exp) env)env)’ok)В качестве возвращаемого значения для присваивания или определения мы выбралисимвол ok8 .Упражнение 4.1.Заметим, что мы не можем сказать, вычисляет ли метациклический интерпретатор операнды слева направо или справа налево.
Порядок вычисления наследуется от нижележащего Лиспа: еслиаргументы cons в процедуре list-of-values вычисляются слева направо, то и операнды вlist-of-values будут вычисляться слева направо. Если же вычисление аргументов cons происходит справа налево, то и list-of-values будет вычислять операнды справа налево.Напишите версию list-of-values, которая вычисляет операнды слева направо, вне зависимости от порядка вычислений в нижележащем Лиспе. Напишите также версию, которая вычисляетоперанды справа налево.4.1.2. Представление выраженийИнтерпретатор напоминает программу символьного дифференцирования, описаннуюв разделе 2.3.2. Обе программы работают с символьными выражениями. В обеих результат работы с составным выражением определяется рекурсивной обработкой частейвыражения и сочетанием частичных результатов, причем способ сочетания зависит оттипа выражения.
И там, и там мы использовали абстракцию данных, чтобы отделитьобщие правила работы от деталей того, как представлены выражения. Для программыдифференцирования это означало, что одна и та же процедура взятия производной могла работать с алгебраическими выражениями в префиксной, инфиксной или какой-либодругой записи. Для интерпретатора это означает, что синтаксис языка определяется исключительно процедурами, которые классифицируют выражения и выделяют их части.Вот описание синтаксиса нашего языка:• К самовычисляющимся объектам относятся только числа и строки:(define (self-evaluating? exp)(cond ((number? exp) true)((string? exp) true)(else false)))• Переменные представляются в виде символов:(define (variable? exp) (symbol? exp))7 Эта реализация define не учитывает один тонкий вопрос в обработке внутренних определений, хотя вбольшинстве случаев работает правильно.
В чем состоит проблема и как ее решить, мы увидим в разделе 4.1.6.8 Как мы упоминали при введении define и set!, их значения в Scheme зависят от реализации — то естьавтор реализации имеет право выбрать такое значение, какое он хочет.344Глава 4. Метаязыковая абстракция• Выражения с кавычкой имеют форму (quote hзакавыченное-выражениеi):(define (quoted? exp)(tagged-list? exp ’quote))(define (text-of-quotation exp) (cadr exp))Quoted? определена посредством процедуры tagged-list?, которая распознает списки, начинающиеся с указанного символа9 :(define (tagged-list? exp tag)(if (pair? exp)(eq? (car exp) tag)false))• Присваивания имеют форму (set! hпеременнаяi hвыражениеi):(define (assignment? exp)(tagged-list? exp ’set!))(define (assignment-variable exp) (cadr exp))(define (assignment-value exp) (caddr exp))• Определения имеют вид(define hпеременнаяi hзначениеi)или(define (hпеременнаяi hпараметр1 i ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
