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

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 86)

Таким образом, если задержанное значение добираетсядо цикла чтение-вычисление-печать, то оно, прежде чем печататься, будет разморожено.Кроме того, чтобы показать, что работа идет с ленивым интерпретатором, мы изменимподсказки:(define input-prompt ";;; Ввод L-Eval:")(define output-prompt ";;; Значение L-Eval:")(define (driver-loop)(prompt-for-input input-prompt)(let ((input (read)))(let ((output(actual-value input the-global-environment)))(announce-output output-prompt)(user-print output)))(driver-loop))Внеся эти изменения, мы можем запустить интерпретатор и протестировать его.Успешное вычисление выражения try, описанного в разделе 4.2.1, показывает, что интерпретатор проводит ленивое вычисление:(define the-global-environment (setup-environment))(driver-loop);;; Ввод L-eval:4.2.

SCHEME с вариациями: ленивый интерпретатор375(define (try a b)(if (= a 0) 1 b));;; Значение L-Eval:ok;;; Ввод L-eval:(try 0 (/ 1 0));;; Значение L-Eval:1Представление санковНаш интерпретатор должен устроить работу так, чтобы при применении процедур каргументам порождались санки, и чтобы потом они вынуждались. Выражение в санкедолжно запаковываться вместе с окружением, так, чтобы потом можно было по нимвычислить аргумент. Чтобы вынудить санк, мы просто извлекаем из него выражение иокружение, и вычисляем выражение в окружении.

Мы используем при этом не eval,а actual-value, так что если результат выражения сам окажется санком, мы и еговынудим, и так пока не доберемся до не-санка.(define (force-it obj)(if (thunk? obj)(actual-value (thunk-exp obj) (thunk-env obj))obj))Простой способ упаковать выражение вместе с окружением — создать список извыражения и окружения.

Таким образом, мы порождаем санк так:(define (delay-it exp env)(list ’thunk exp env))(define (thunk? obj)(tagged-list? obj ’thunk))(define (thunk-exp thunk) (cadr thunk))(define (thunk-env thunk) (caddr thunk))Однако на самом деле нам в интерпретаторе нужны не такие санки, а мемоизированные. Мы сделаем так, чтобы санк при вынуждении превращался в вычисленный санк.Для этого мы будем заменять хранимое в нем выражение на значение и менять меткусанка, чтобы можно было понять, что он уже вычислен37 .37 Заметим, что, вычислив выражение, мы еще и стираем из санка окружение.

Это не влияет на то, какиезначения возвращает интерпретатор. Однако при этом экономится память, поскольку стирание ссылки из санкана env, когда она становится больше не нужна, позволяет подвергнуть эту структуру сборке мусора (garbagecollection) и заново использовать ее память. Мы обсудим это в разделе 5.3.Подобным образом можно было бы разрешить собирать как мусор ненужные окружения в мемоизированныхзадержанных объектах из раздела 3.5.1: memo-proc, сохранив значение процедуры proc, делала бы чтонибудь вроде (set! proc ’()), чтобы забыть саму процедуру (включающую окружение, где было вычисленоdelay).376Глава 4.

Метаязыковая абстракция(define (evaluated-thunk? obj)(tagged-list? obj ’evaluated-thunk))(define (thunk-value evaluated-thunk) (cadr evaluated-thunk))(define (force-it obj)(cond ((thunk? obj)(let ((result (actual-value(thunk-exp obj)(thunk-env obj))))(set-car! obj ’evaluated-thunk)(set-car! (cdr obj) result); заменить exp на его значение(set-cdr! (cdr obj) ’()) ; забыть ненужное envresult))((evaluated-thunk? obj)(thunk-value obj))(else obj)))Заметим, что одна и та же процедура delay-it работает и с мемоизацией, и без нее.Упражнение 4.27.Допустим, мы вводим в ленивый интерпретатор следующее выражение:(define count 0)(define (id x)(set! count (+ count 1))x)Вставьте пропущенные значения в данной ниже последовательности действий и объясните своиответы38 :(define w (id (id 10)));;; Ввод L-Eval:count;;; Значение L-Eval:hвыводi;;; Ввод L-Eval:w;;; Значение L-Eval:hвыводi;;; Ввод L-Eval:count;;; Значение L-Eval:hвыводi38 Это упражнение показывает, что взаимодействие между ленивыми вычислениями и побочными эффектамиможет быть весьма запутанным.

Ровно этого можно было ожидать после обсуждения в главе 3.4.2. SCHEME с вариациями: ленивый интерпретатор377Упражнение 4.28.Eval, передавая оператор в apply, вычисляет его не при помощи eval, а через actual-value,чтобы вынудить. Приведите пример, который показывает, что такое вынуждение необходимо.Упражнение 4.29.Придумайте пример программы, которая, по Вашему мнению, будет работать намного медленнеебез мемоизации, чем с мемоизацией. Рассмотрим, помимо этого, следующую последовательностьдействий, в которой процедура id определена как в упражнении 4.27, а счетчик count начинаетс 0:(define (square x)(* x x));;; Ввод L-Eval:(square (id 10));;; Значение L-Eval:hвыводi;;; Ввод L-Eval:count;;; Значение L-Eval:hвыводiУкажите, как будет выглядеть вывод в случае с мемоизирующим интерпретатором и с немемоизирующим.Упражнение 4.30.Пабло Э. Фект, бывший программист на языке C, беспокоится, что ленивый интерпретатор невынуждает выражения в последовательности, и оттого некоторые побочные эффекты могут никогда не произойти.

Поскольку ни у одного выражения в последовательности, помимо конечного,значение не используется (выражение стоит там только ради своего эффекта, например, чтобы присвоить значение переменной или что-нибудь напечатать), у значения такого выраженияне может впоследствии быть применения, для которого его потребуется вынудить (например, вкачестве аргумента элементарной процедуры). Поэтому П.Э. Фект считает, что при выполнениипоследовательности нужно все выражения, кроме последнего, вынуждать. Он предлагает изменитьeval-sequence из раздела 4.1.1 так, чтобы она вместо eval использовала actual-value:(define (eval-sequence exps env)(cond ((last-exp? exps) (eval (first-exp exps) env))(else (actual-value (first-exp exps) env)(eval-sequence (rest-exps exps) env))))а.

Бен Битобор считает, что Пабло неправ. Он показывает ему процедуру for-each из упражнения 2.23 — важный пример последовательности с побочными эффектами:(define (for-each proc items)(if (null? items)’done(begin (proc (car items))(for-each proc (cdr items)))))Он утверждает, что интерпретатор из текста (с исходным eval-sequence) правильно работает сэтой процедурой:378Глава 4. Метаязыковая абстракция;;; Ввод L-Eval:(for-each (lambda (x) (newline) (display x))(list 57 321 88))5732188;;; Значение L-Eval:doneОбъясните, почему Бен прав насчет поведения for-each.б. Пабло соглашается с Беном по поводу примера с for-each, но говорит, что, предлагаяизменить eval-sequence, он имел в виду другой тип программ. Он определяет в ленивом интерпретаторе следующие две процедуры:(define (p1 x)(set! x (cons x ’(2)))x)(define (p2 x)(define (p e)ex)(p (set! x (cons x ’(2)))))Какие значения вернут (p1 1) и (p2 1) с исходной eval-sequence? Каковы будут значения сизменением, которое предлагает Пабло?в.

Пабло указывает также, что изменение eval-sequence, которое он предлагает, не влияетна поведение примера из части a. Объясните, почему это так.г. Как, по-Вашему, нужно работать с последовательностями в ленивом интерпретаторе? Что Вамнравится больше: подход Пабло, подход, приведенный в тексте, или что-нибудь третье?Упражнение 4.31.Подход, принятый в этом разделе, нехорош тем, что вносит изменение в Scheme, не сохраняяее семантику.

Было бы приятнее реализовать ленивые вычисления как совместимое расширение(upward-compatible extension), то есть так, чтобы обычные программы на Scheme работали какпрежде. Этого можно добиться, расширив синтаксис определений процедур, так, чтобы пользователь мог решать, нужно ли задерживать аргументы. При этом можно еще предоставить пользователю выбор между задержкой с мемоизацией и без нее.

Например, определение(define (f a (b lazy) c (d lazy-memo))...)делало бы f процедурой от четырех аргументов, причем первый и третий вычисляются при вызовепроцедуры, второй задерживается, а четвертый задерживается и мемоизируется. Таким образом,обыкновенные определения процедур будут задавать такое же поведение, как в обычной Scheme, адобавление декларации lazy-memo к каждому параметру каждой составной процедуры приведет кповедению, как у ленивого интерпретатора, описанного в этом разделе. Разработайте и реализуйтеизменения, с помощью которых можно получить такое расширение Scheme.

Вам придется реализовать новые синтаксические процедуры для нового синтаксиса define. Кроме того, надо будетдобиться, чтобы eval и apply определяли, когда надо задерживать аргументы, и соответствующим образом задерживали и вынуждали их. Наконец, придется обеспечить,чтобы вынуждениебыло с мемоизацией или без оной, смотря по обстоятельствам.4.2. SCHEME с вариациями: ленивый интерпретатор3794.2.3.

Характеристики

Список файлов книги