Абельсон Х., Сассман Д.Д. Структура и интерпретация компьютерных программ

Подождите немного. Документ загружается.

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-of-

values в качестве аргумента берет список операндов комбинации. Она вычисляет к аж-

дый аргумент и возвращает список соответствующих значений

(define (list-of-values exps env)

(if (no-operands? exps)

Ветку application? в eval можно было бы упростить, используя map (и постанови в, что operands

возвращает список) вместо того, чтобы писать явным образом процедуру list-of-values. Мы решили не

использовать здесь map, чтобы подчеркнуть, что интерпретатор можно написать без обращения к процедурам

высших порядков (а следовательно, его можно написать на языке, в котором нет таких процедур), притом, что

язык, поддерживаемый интерпретатором, содержит процедуры высших порядков.

342

Глава 4. Метаязыковая абстракция

’()

(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 в языке реализаци и: метациклическое представление истины может не

совпадать с ее представлением в нижележащей Scheme

По следовательности

Процедура 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)

В нашем случае, язык реализации и реализуемый язык совпадают. Размышления о значен ии true? рас-

ширяют наше сознание безотноси тельно к материальной сущности истины.

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

343

Определения переменных обрабатываются сходным образом

(define (eval-definition exp env)

(define-variable! (definition-variable exp)

(eval (definition-value exp) env)

env)

’ok)

В качестве возвращаемого значения для присваивания или определения мы выбрали

символ ok

Упражнение 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))

Эта реализация define не учитывает один тонкий вопрос в обработке внутренних определений, хотя в

большинстве случаев работает правильно. В чем состоит проблема и как ее решить, мы увидим в разделе 4.1.6.

Как мы упоминали при введении 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?, которая распознает спис-

ки, начинающиеся с указанного символа

(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параметр

i ... hпараметр

hтелоi)

Вторая форма (стандартное определение процедуры) является синтаксическим сахаром

для

(define hпеременнаяi

(lambda (hпараметр

i ... hпараметр

hтелоi))

Соответствующие синтаксические процедуры выглядят так:

(define (definition? exp)

(tagged-list? exp ’define))

(define (definition-variable exp)

(if (symbol? (cadr exp))

В разделе 2.3.1 упоминается, что интерпретатор рассматривает закавыченное выражение как список, на-

чинающийся с quote, даже если выражение напечатано через знак кавычки. Например, выражение ’a будет

выглядеть для интерпретатора как (quote a). См. упражнение 2.55.

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

345

(cadr exp)

(caadr exp)))

(define (definition-value exp)

(if (symbol? (cadr exp))

(caddr exp)

(make-lambda (cdadr exp)

(cddr exp))))

• Lambda-выражения являются списками, которые начинаются с символа lambda:

(define (lambda? exp) (tagged-list? exp ’lambda))

(define (lambda-parameters exp) (cadr exp))

(define (lambda-body exp) (cddr exp))

Мы приводим также конструктор для lambda-выражений. Он используется в вышепри-

веденной процедуре definition-value:

(define (make-lambda parameters body)

(cons ’lambda (cons parameters body)))

• Условные выражения начинаются с if и имеют преди кат, следствие и (необяза-

тельную) альтернативу. Если в выражении нет части-альтернативы, мы указываем в ее

качестве false

(define (if? exp) (tagged-list? exp ’if))

(define (if-predicate exp) (cadr exp))

(define (if-consequent exp) (caddr exp))

(define (if-alternative exp)

(if (not (null? (cdddr exp)))

(cadddr exp)

’false))

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

цедура cond->if для преобразования выражений cond в выражения if:

(define (make-if predicate consequent alternative)

(list ’if predicate consequent alternative))

Значение выражения if в случае, когда предикат ложен, а альтернатива отсутствует, в Scheme не определе-

но; здесь мы решили сделать его ложным. Мы будем поддерживать переменные true и false в выполняемых

выражениях путем связывания их в глобальном окружении. См. раздел 4.1.4.

346

Глава 4. Метаязыковая абстракция

• Begin упаковывает последовательность выражений в одно выражение. В синтак-

сические операции над выражениями begin мы включаем извлечение самой последова-

тельности из выражения begin, а также селекторы, которые возвращают первое выра-

жение и ос таток выражений в последовательности

(define (begin? exp) (tagged-list? exp ’begin))

(define (begin-actions exp) (cdr exp))

(define (last-exp? seq) (null? (cdr seq)))

(define (first-exp seq) (car seq))

(define (rest-exps seq) (cdr seq))

Кроме того, мы даем конструктор sequence->exp (для использования в процедуре

cond->if), который преобразует последовательность в единое выражение, используя,

если надо, begin:

(define (sequence->exp seq)

(cond ((null? seq) seq)

((last-exp? seq) (first-exp seq))

(else (make-begin seq))))

(define (make-begin seq) (cons ’begin seq))

• Вызов процедуры — это любое составное выражение, не попадающее ни в один из

перечисленных типов. Его car — это оператор, а cdr — список операндов:

(define (application? exp) (pair? exp))

(define (operator exp) (car exp))

(define (operands exp) (cdr exp))

(define (no-operands? ops) (null? ops))

(define (first-operand ops) (car ops))

(define (rest-operands ops) (cdr ops))

Производные выражения

Некоторые особые формы языка можно опр еделить через выражения, включающие

другие особые формы, вме сто того, чтобы задавать их напрямую. Как пример рассмот-

рим cond, который можно реализовать как гнездо выражений if. Например, задачу

вычисления выражения

Эти селекторы для списка выражений, а также соответствующие им селекторы для списка операндов,

не предназначаю тся для абстракции данных. Они введены в качестве мнемонических имен для основных

списковых операций, чтобы легче было понимать вычислитель с явным управлением из раздела 5.4.

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

347

(cond ((> x 0) x)

((= x 0) (display ’zero) 0)

(else (- x)))

можно свести к задаче вычисления следующего выражения, состоящего из форм if и

begin:

(if (> x 0)

(if (= x 0)

(begin (display ’zero)

(- x)))

Так ая реализация обработки cond упрощает интерпретатор, поскольку она умен ьшает

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

Мы включаем в интерпретатор синтаксические процедуры, которые определя ют до-

ступ к ч астям выражения cond, а также процедуру cond->if, которая преобразует вы-

ражения cond в выражен ия if. Анализ случаев начинается с cond и состоит из списка

ветвей-вариантов вида предикат-действие. Вариант считается умолчательным, если его

предикатом являе тся символ else

(define (cond? exp) (tagged-list? exp ’cond))

(define (cond-clauses exp) (cdr exp))

(define (cond-else-clause? clause)

(eq? (cond-predicate clause) ’else))

(define (cond-predicate clause) (car clause))

(define (cond-actions clause) (cdr clause))

(define (cond->if exp)

(expand-clauses (cond-clauses exp)))

(define (expand-clauses clauses)

(if (null? clauses)

’false ; нет ветви else

(let ((first (car clauses))

(rest (cdr clauses)))

(if (cond-else-clause? first)

(if (null? rest)

(sequence->exp (cond-actions first))

(error "Ветвь ELSE не последняя -- COND->IF"

clauses))

(make-if (cond-predicate first)

Значение выражения cond, когда все предикаты ложны, а вариант по умолчанию else отсутствует, в

языке Scheme не определено; здесь мы решили сделать его ложным.

348

Глава 4. Метаязыковая абстракция

(sequence->exp (cond-actions first))

(expand-clauses rest))))))

Выражения (вроде cond), которые мы желаем реализовать через синтаксические пре-

образования, называются производными (derived expressions). Выражения let также

являются производными (см. у пражнение 4.6)

Упражнение 4.2.

Хьюго Дум хочет переупорядочить ветви cond так, чтобы ветвь для вызова процедур распо-

лагалась перед веткой для присваивания. Он утверждает, что при этом интерпретатор с танет

эффективнее: поскольку в программах обычно больше вызовов процедур, чем присваиваний, опре-

делений и т. д., его усовершенствованный eval обычно будет рассматривать меньше вариантов,

чем исходный, при распознавании типа выражения.

а. Что за ошибка содержится в плане Хьюго? (Подсказка: что сделает его интерпретатор с

выражением (define x 3)?)

б. Хьюго расстроен, что его план не с работал. Он го тов пойти на любые жертвы, чтобы поз-

волить интерпретатору распознавать вызовы процедур до того, как он проверяет все остальные

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

процедур начинались с символа call. Например, вместо (factorial 3) нам теперь придется

писать (call factorial 3), а вместо (+ 1 2) — (call + 1 2).

Упражнение 4.3.

Перепишите eval так, чтобы диспетчеризация происходила в стиле, управляемом данными. Срав-

ните результат с дифференцированием, управляемым данными, из у пражнения 2.73. (Можно ис-

пользовать car составного выражения в качестве типа этого выражения, так как это хорошо

сочетается с синтаксисом, р еализованным в этом разделе.)

Упражнение 4.4.

Вспомним определения особых форм and и or из главы 1 :

• and: выражения вычисляются слева направо. Если значение какого-то из них оказывается

ложным, возвращается ложь; оставшиеся выражения не вычисляются. Если все выражения ока-

зываются истинными, возвращается значение последнего из них. Если нет ни одного выражения,

возвращается истина.

• or: выражения вычисляются слева направо. Если значение какого-то из них оказывается

истинным, возвращается это значение; оставш иеся выражения не вычисляются. Если все выраже-

ния оказываются ложными, или нет ни одного выражения, возвращается ложь.

Введите and и or в качестве новых особых форм интерпр етатора, определив соответствующие

синтаксические процедуры и процедуры выполнения eval-and и eval-or. В качестве альтерна-

тивы покажите, как можно реализовать and и or в виде производных выражений.

Практические Лисп-системы предоставляют механизм, который дает пользователю возможность добавлять

новые производные выражения и определять их значения через синтаксические преобразования, не внося из-

менений в вычислитель. Такое преобразован ие, определяемое пользователем, называется макрос (macro). До-

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

проблемы конфликта имен. Множество исследований посвящено поиску механизмов определения макросов, в

которых такие проблемы не возникают. См., например, Kohlbecker 1986, Clinger and Rees 1991 и Hanson 1991 .

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

349

Упражнение 4.5.

В языке Scheme есть дополнительная разновидность синтаксиса вариантов cond, (hпровер-

каi => hпотребительi). Если результат вычисления hпроверкиi оказывается истинным зна-

чением, то вычисляется hпотребительi. Его значение должно быть одноместной процедурой; эта

процедура вызывается со значением hпроверкиi в качестве аргумента, и результат этого вызова

возвращается как значение выражения cond. Например,

(cond ((assoc ’b ’((a 1) (b 2))) => cadr)

(else false))

имеет значение 2. Измените о бработку cond так, чтобы она поддерживала этот расширенный

синтаксис.

Упражнение 4.6.

Выражения let производны, поскольку

(let ((hпер

ihвыр

i) ... (hпер

ihвыр

i))

hтелоi)

эквивалентно

((lambda (hпер

i ... hпер

hтелоi)

hвыр

...

hвыр

Напишите синтаксическое преобразование let->combination, ко торое сводит вычисление let-

выражений к вычислению комбинаций указанного вида, и добавьте соответствующую ветку для

обработки let к eval.

Упражнение 4.7.

Особая форма let* подобна let, но только связывания переменных в let* происходят последо-

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

Например,

(let* ((x 3)

(y (+ x 2))

(z (+ x y 5)))

(* x z))

возвращает значение 39. Объясните, каким образом можно переписать выражение let* в виде

набора вложенных выражений let, и напишите процедуру let*->nested-lets, которая про-

делывает это преобразование. Если мы уже реализовали let (упражнение 4.6) и хотим теперь

расш ирить интерпретатор так, чтобы он обрабатывал let*, достаточно ли будет добавить в eval

ветвь, в котор ой действием записано

(eval (let*->nested-lets exp) env)

или нужно я вным образом преобразовывать let* в набор непроизводных выражений?

Упражнение 4.8.

«Именованный let» — это вариант let, который имеет вид

(let hпеременнаяi hсвязываниеi hтелоi)

350

Глава 4. Метаязыковая абстракция

hСвязываниеi и hтелоi такие же, как и в обычном let, но только hпеременнаяi связана в hтелеi

с процедурой, у которой тело hтелоi, а имена параметров — переменные в hсвязыванияхi. Та-

ким образом, можно неоднократно выполнять hтелоi, вызывая процедуру по имени hпеременнаяi.

Например, итеративную процедуру для порождения чисел Фибоначчи (раздел 1.2.2) можно пере-

писать при помощи именованного let как

(define (fib n)

(let fib-iter ((a 1)

(b 0)

(count n))

(if (= count 0)

(fib-iter (+ a b) a (- count 1)))))

Измените преобразование let->combination из упражнения 4.6 так, чтобы оно поддерживало

именованный let.

Упражнение 4.9.

Во многих языках имеются различные конструкции для построения циклов, например, do, for,

while и until. В Scheme итеративные процессы можно выразить через обычные вызовы проце-

дур, так что о собые конструкции не дают никаког о существенного выигрыша в вычислительной

мощности. С другой стороны, часто они удобны. Придумайте какие-нибудь конструкции для ите-

рации, дайте примеры их использования и покажите, как их реализовать в виде производных

выражений.

Упражнение 4.10.

При помощи абстракции данных мы смогли написать процедуру eval так, что она не зависит

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

разработайте новый синтаксис для Scheme, изменив процедуры из этого раздела и ничего не

трогая в eval и apply.

4.1.3. Структуры данных интерпретатора

Помимо внешнего синтаксиса выражений, реализация интерпретатора должна опре-

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

нения программы, в частности, представление процедур и окружений, а также истинных

и ложных значений.

Проверка предикатов

В условных выражениях м ы воспринимаем в качестве истины все, кроме специаль-

ного ложного объекта false.

(define (true? x)

(not (eq? x false)))

(define (false? x)

(eq? x false))