Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 84
Текст из файла (страница 84)
Реализуйте letrec как производное выражение, переводя выражение letrec в выражениеlet, как показано в тексте раздела или в упражнении 4.18. То есть переменные letrec должнысоздаваться в let, а затем получать значение через set!.б. Хьюго Дум совсем запутался во всех этих внутренних определениях. Ему кажется, что есликому-то не нравятся define внутри процедуры, то пусть пользуются обычным let. Покажите,что́ в его рассуждениях неверно. Нарисуйте диаграмму, показывающую окружение, в которомвыполняется hостаток тела fi во время вычисления выражения (f 5), если f определена какв этом упражнении. Нарисуйте диаграмму окружений для того же вычисления, но только с letна месте letrec в определении f.Упражнение 4.21.Как ни удивительно, интуитивная догадка Хьюго (в упражнении 4.20) оказывается верной.
Действительно, можно строить рекурсивные процедуры без использования letrec (и даже безdefine), только способ это сделать намного тоньше, чем казалось Хьюго. Следующее выражениевычисляет факториал 10 с помощью рекурсивной процедуры27:((lambda (n)((lambda (fact)27 В этом примере показан программистский трюк, позволяющий формулировать рекурсивные процедуры безпомощи define. Самый общий прием такого рода называется Y-оператор (Y operator), и с его помощьюможно реализовать рекурсию в «чистом λ-исчислении».
(Подробности о лямбда-исчислении можно найти вStoy 1977, а демонстрацию Y -оператора на Scheme в Gabriel 1988.)4.1. Метациклический интерпретатор365(fact fact n))(lambda (ft k)(if (= k 1)1(* k (ft ft (- k 1)))))))10)а. Проверьте, что это выражение на самом деле считает факториалы (вычисляя его). Постройтеаналогичное выражение для вычисления чисел Фибоначчи.б. Рассмотрим следующую процедуру, включающую взаимно рекурсивные внутренние определения:(define (f x)(define (even? n)(if (= n 0)true(odd? (- n 1))))(define (odd? n)(if (= n 0)false(even? (- n 1))))(even? x))Восстановите пропущенные фрагменты так, чтобы получилось альтернативное определение f, гденет ни внутренних определений, ни letrec:(define (f x)((lambda (even? odd?)(even? even? odd? x))(lambda (ev? od? n)(if (= n 0) true (od? h??i h??i h??i)))(lambda (ev? od? n)(if (= n 0) false (ev? h??i h??i h??i)))))4.1.7. Отделение синтаксического анализа от выполненияНаписанный нами интерпретатор прост, но очень неэффективен, потому что синтаксический анализ выражений перемешан в нем с их выполнением.
Таким образом, сколько раз выполняется программа, столько же раз анализируется ее синтаксис. Рассмотрим,например, вычисление (factorial 4), если дано следующее определение факториала:(define (factorial n)(if (= n 1)1(* (factorial (- n 1)) n)))Каждый раз, когда вызывается factorial, интерпретатор должен определить, чтотело процедуры является условным выражением, и извлечь его предикат. Только послеэтого он может вычислить предикат и поступить в соответствии с его значением. Каждый раз, когда вычисляется выражение (* (factorial (- n 1)) n) или подвыражения (factorial (- n 1)) и (- n 1), интерпретатор должен произвести анализ366Глава 4. Метаязыковая абстракцияслучаев внутри eval, выяснить, что выражение является вызовом процедуры, а такжеизвлечь его оператор и операнды. Такой анализ недёшев. Проделывать его многократно — неразумно.Можно преобразовать интерпретатор так, чтобы синтаксический анализ проводилсятолько один раз, и повысить таким образом эффективность работы28 .
Мы разбиваемпроцедуру eval, которая принимает выражение и окружение, на две части. Analyzeберет только выражение. Она выполняет синтаксический анализ и возвращает новуюисполнительную процедуру (execution procedure). В этой процедуре упакована работа,которую придется проделать при выполнении выражения. Исполнительная процедураберет в качестве аргумента окружение и завершает вычисление. При этом экономитсяработа, потому что analyze будет для каждого выражения вызываться только один раз,а исполнительная процедура, возможно, многократно.После разделения анализа и выполнения eval превращается в(define (eval exp env)((analyze exp) env))Результатом вызова analyze является исполнительная процедура, которая применяется к окружению. Analyze содержит тот же самый анализ, который делал исходныйeval из раздела 4.1.1, однако процедуры, между которыми мы выбираем, только анализируют, а не окончательно выполняют выражение.(define (analyze exp)(cond ((self-evaluating? exp)(analyze-self-evaluating exp))((quoted? exp) (analyze-quoted exp))((variable? exp) (analyze-variable exp))((assignment? exp) (analyze-assignment exp))((definition? exp) (analyze-definition exp))((if? exp) (analyze-if exp))((lambda? exp) (analyze-lambda exp))((begin? exp) (analyze-sequence (begin-actions exp)))((cond? exp) (analyze (cond->if exp)))((application? exp) (analyze-application exp))(else(error "Неизвестный тип выражения -- ANALYZE" exp))))Вот самая простая из процедур анализа, которая обрабатывает самовычисляющиеся выражения.
Ее результатом является исполнительная процедура, которая игнорируетсвой аргумент-окружение и просто возвращает само выражение:(define (analyze-self-evaluating exp)(lambda (env) exp))В случае кавычки мы можем добиться некоторого выигрыша, извлекая закавыченноевыражение только один раз на стадии анализа, а не на стадии выполнения.28 Такое преобразование является неотъемлемой частью процесса компиляции, который мы рассмотрим вглаве 5.
Джонатан Рис написал для проекта T интерпретатор Scheme с похожей структурой приблизительно в1982 голу (Rees and Adams 1982). Марк Фили (Feeley 1986, см. также Feeley and Lapalme 1987) независимоизобрел этот метод в своей дипломной работе.4.1. Метациклический интерпретатор367(define (analyze-quoted exp)(let ((qval (text-of-quotation exp)))(lambda (env) qval)))Поиск переменной нужно проводить на стадии выполнения, поскольку при этом требуется знать окружение29 .(define (analyze-variable exp)(lambda (env) (lookup-variable-value exp env)))Анализ присваивания, analyze-assignment, также должен отложить само присваивание до времени выполнения, когда будет в наличии окружение.
Однако возможность(рекурсивно) проанализировать выражение assignmentvalue сразу, на стадии анализа, — это большой выигрыш в эффективности, поскольку теперь это выражение будетанализироваться только однажды. То же верно и для определений:(define (analyze-assignment exp)(let ((var (assignment-variable exp))(vproc (analyze (assignment-value exp))))(lambda (env)(set-variable-value! var (vproc env) env)’ok)))(define (analyze-definition exp)(let ((var (definition-variable exp))(vproc (analyze (definition-value exp))))(lambda (env)(define-variable! var (vproc env) env)’ok)))Для условных выражений мы извлекаем и анализируем предикат, следствие и альтернативу на стадии анализа.(define (analyze-if exp)(let ((pproc (analyze (if-predicate exp)))(cproc (analyze (if-consequent exp)))(aproc (analyze (if-alternative exp))))(lambda (env)(if (true? (pproc env))(cproc env)(aproc env)))))При анализе выражения lambda также достигается значительный выигрыш в эффективности: тело lambda анализируется только один раз, а процедура, получающаясяв результате выполнения lambda, может применяться многократно.29 Есть, впрочем, важная часть поиска переменной, которую все-таки можно осуществить во время синтаксического анализа.
Как мы покажем в разделе 5.5.6, можно определить позицию в структуре окружения, гдебудет находиться нужное значение, и таким образом избежать необходимости искать в окружении элемент,который соответствует переменной.368Глава 4. Метаязыковая абстракция(define (analyze-lambda exp)(let ((vars (lambda-parameters exp))(bproc (analyze-sequence (lambda-body exp))))(lambda (env) (make-procedure vars bproc env))))Анализ последовательности выражений (в begin или в теле lambda-выражения)более сложен30 . Каждое выражение в последовательности анализируется, и для каждогополучается исполнительная процедура. Эти исполнительные процедуры комбинируются в одну общую исполнительную процедуру, которая принимает в качестве аргументаокружение и последовательно вызывает каждую из частичных исполнительных процедур, передавая ей окружение как аргумент.(define (analyze-sequence exps)(define (sequentially proc1 proc2)(lambda (env) (proc1 env) (proc2 env)))(define (loop first-proc rest-procs)(if (null? rest-procs)first-proc(loop (sequentially first-proc (car rest-procs))(cdr rest-procs))))(let ((procs (map analyze exps)))(if (null? procs)(error "Пустая последовательность -- ANALYZE"))(loop (car procs) (cdr procs))))Для вызова процедуры мы анализируем оператор и операнды и строим исполнительную процедуру, которая вызывает исполнительную процедуру оператора (получая приэтом объект-процедуру, которую следует применить) и исполнительные процедуры операндов (получая аргументы).
Затем мы все это передаем в execute-application,аналог apply из раздела 4.1.1. Execute-application отличается от apply тем, чтотело составной процедуры уже проанализировано, так что нет нужды в дальнейшем анализе. Вместо этого мы просто вызываем исполнительную процедуру для тела, передаваяей расширенное окружение.(define (analyze-application exp)(let ((fproc (analyze (operator exp)))(aprocs (map analyze (operands exp))))(lambda (env)(execute-application (fproc env)(map (lambda (aproc) (aproc env))aprocs)))))(define (execute-application proc args)(cond ((primitive-procedure? proc)(apply-primitive-procedure proc args))((compound-procedure? proc)((procedure-body proc)(extend-environment (procedure-parameters proc)30 См.упражнение 4.23, в котором объясняются некоторые подробности обработки последовательностей.4.2. SCHEME с вариациями: ленивый интерпретатор369args(procedure-environment proc))))(else(error"Неизвестный тип процедуры -- EXECUTE-APPLICATION"proc))))В нашем новом интерпретаторе используются те же структуры данных, синтаксические процедуры и вспомогательные процедуры времени выполнения, что и в разделах 4.1.2, 4.1.3 и 4.1.4.Упражнение 4.22.Расширьте интерпретатор из этого раздела так, чтобы он поддерживал let.
(См. упражнение 4.6.)Упражнение 4.23.Лиза П. Хакер не понимает, зачем делать analyze-sequence такой сложной. Все остальные процедуры анализа — простые трансформации соответствующих вычисляющих процедур (или ветвейeval) из раздела 4.1.1. Лиза ожидала, что analyze-sequence будет выглядеть так:(define (analyze-sequence exps)(define (execute-sequence procs env)(cond ((null? (cdr procs)) ((car procs) env))(else ((car procs) env)(execute-sequence (cdr procs) env))))(let ((procs (map analyze exps)))(if (null? procs)(error "Пустая последовательность -- ANALYZE"))(lambda (env) (execute-sequence procs env))))Ева Лу Атор объясняет Лизе, что версия в тексте проделывает больше работы по вычислениюпоследовательности во время анализа. В Лизиной исполнительной процедуре вызовы частичныхисполнительных процедур, вместо того, чтобы быть встроенными, перебираются в цикле.
В результате, хотя отдельные выражения в последовательности оказываются проанализированы, самапоследовательность анализируется во время выполнения.Сравните две версии analyze-sequence. Рассмотрите, например, обычный случай (типичный для тел процедур), когда в последовательности только одно выражение. Какую работу будетделать исполнительная процедура, предложенная Лизой? А процедура из текста раздела? Как соотносятся эти две процедуры в случае последовательности из двух выражений?Упражнение 4.24.Спроектируйте и проведите несколько экспериментов, чтобы сравнить скорость исходного метациклического вычислителя и его версии из этого раздела. С помощью результатов этих опытовоцените долю времени, которая тратится на анализ и на собственно выполнение в различныхпроцедурах.4.2. Scheme с вариациями: ленивый интерпретаторТеперь, имея в своем распоряжении интерпретатор, выраженный в виде программы наЛиспе, мы можем экспериментировать с различными вариантами строения языка, просто370Глава 4.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
