;;; Значение L-Eval: done

Объясните, почему Бен прав насчет поведения for-each.

b.Пабло соглашается с Беном по поводу примера с for-each, но говорит, что, предлагая изменить eval-sequence, он имел в виду другой тип программ. Он определяет в ленивом интерпретаторе следующие две процедуры:

(define (p1 x)

(set! x (cons x (2)))

x)

(define (p2 x) (define (p e) e

x)

(p (set! x (cons x (2)))))

Какие значения вернут (p1 1) и (p2 1) с исходной eval-sequence? Каковы будут значения с изменением, которое предлагает Пабло?

c.Пабло указывает также, что изменение eval-sequence, которое он предлагает, не влияет на поведение примера из части а. Объясните, почему это так.

d.Как, по-Вашему, нужно работать с последовательностями в ленивом интерпретаторе? Что Вам нравится больше: подход Пабло, подход, приведенный в тексте, или что-нибудь третье?

Упражнение 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.3 Потоки как ленивые списки

В разделе 3.5.1 мы показали, как реализовать потоки в виде задержанных списков. Мы ввели особые формы delay и cons-stream, которые позволили

нам строить «обещания» вычислить cdr потока, не выполняя эти обещания до более позднего времени. Можно было бы использовать этот же метод и вводить новые особые формы всякий раз, когда нам требуется детальное управление процессом вычисления, но это было бы весьма неуклюже. Прежде всего, особая форма, в отличие от процедуры, не является полноправным объектом, и ее нельзя использовать в сочетании с процедурами высших порядков.39 Кроме того, нам пришлось ввести потоки как новый тип объектов данных, похожий на списки, но отличный от них, и из-за этого потребовалось заново переписать для работы с потоками множество обычных операций над списками (map, append и тому подобное).

Когда у нас есть ленивое вычисление, списки и потоки можно считать одним и тем же типом, так что не возникает нужды в особых формах и в отдельных наборах операций для списков и потоков. Все, что нам требуется, - это так устроить дела, чтобы cons оказалась нестрогой. Можно сделать это, расширив интерпретатор и разрешив нестрогие элементарные процедуры, а затем реализовать cons как одну из таких процедур. Однако проще вспомнить (из раздела 2.1.3), что вообще не существует особой нужды реализовывать cons как примитив. Вместо этого можно представлять пары в виде процедур:40

(define (cons x y)

(lambda (m) (m x y)))

(define (car z)

(z (lambda (p q) p)))

(define (cdr z)

(z (lambda (p q) q)))

Выраженные через эти базовые операции, стандартные определения операций над списками будут работать как с бесконечными списками (потоками), так и с конечными, а потоковые операции можно определить как операции над списками. Вот несколько примеров:

(define (list-ref items n)

(if (= n 0)

(car items)

(list-ref (cdr items) (- n 1)))) (define (map proc items)

(if (null? items)

()

(cons (proc (car items))

(map proc (cdr items)))))

(define (scale-list items factor) (map (lambda (x) (* x factor)) items))

39Это как раз тот вопрос, который возник по отношению к процедуре unless в упражнении 4.26.

40Это процедурное представление, описанное в упражнении 2.4. В сущности, подошла бы и любая другая процедурная реализация (например, на основе передачи сообщений). Обратите внимание, что внести эти определения в ленивый интерпретатор можно, просто набрав их в управляющем цикле. Если мы изначально включили cons, car и cdr как примитивы в глобальное окружение, они будут переопределены. (См. также упражнения 4.33 и 4.34.)

(define (add-lists list1 list2)

(cond ((null? list1) list2) ((null? list2) list1)

(else (cons (+ (car list1) (car list2))

(add-lists (cdr list1) (cdr list2))))))

(define ones (cons 1 ones))

(define integers (cons 1 (add-lists ones integers)))

;;; Ввод L-Eval: (list-ref integers 17) ;;; Значение L-Eval: 18

Заметим, что ленивые списки еще ленивее, чем потоки в главе 3: задерживается не только cdr списка, но и car.41 На самом деле, даже доступ к car или cdr ленивой пары не обязательно вынуждает значение элемента списка. Значение будет вынуждено только тогда, когда это действительно нужно - например, чтобы использовать его в качестве аргумента примитива или напечатать в качестве ответа.

Ленивые пары также помогают с решением проблемы, которая возникла в разделе 3.5.4, где мы обнаружили, что формулировка потоковых моделей систем с циклами может потребовать оснащения программы явными операциями delay, помимо тех, что встроены в cons-stream. При ленивом вычислении все аргументы процедур единообразно задерживаются. Например, можно реализовать процедуры для интегрирования списка и решения дифференциальных уравнений так, как мы изначально намеревались в разделе 3.5.4:

(define (integral integrand initial-value dt) (define int

(cons initial-value

(add-lists (scale-list integrand dt)

int)))

int)

(define (solve f y0 dt)

(define y (integral dy y0 dt)) (define dy (map f y))

y)

;;; Ввод L-Eval:

;: (list-ref (solve (lambda (x) x) 1 .001) 1000)

;;; Значение L-Eval:

2.176924

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

Приведите несколько примеров, которые показывают разницу между потоками из гла-

41 Благодаря этому можно реализовать задержанные версии не только последовательностей, но и более общих видов списковых структур. В Hughes 1990 обсуждаются некоторые применения «ленивых деревьев».