Ввод 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

вычислен:3

(define (evaluated-thunk? obj)

(tagged-list? obj evaluated-thunk))

(define (thunk-value evaluated-thunk) (cadr evaluated-thunk))

37Заметим, что, вычислив выражение, мы еще и стираем из санка окружение. Это не влияет на то, какие значения возвращает интерпретатор. Однако при этом экономится память, поскольку стирание ссылки из санка на env, когда она становится больше не нужна, позволяет подвергнуть эту структуру сборке мусора (garbage collection) и заново использовать ее память. Мы обсудим это в разделе 5.3.

Подобным образом можно было бы разрешить собирать как мусор ненужные окружения в мемо-изированных задержанных объектах из раздела 3.5.1: memo-proc, сохранив значение процедуры proc, делала бы что-нибудь вроде (set! proc ()), чтобы забыть саму процедуру (включающую окружение, где было вычислено delay).

(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) ()) ; забыть ненужное env result)) ((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: (вывод)

;;; Ввод L-Eval: w

;;; Значение L-Eval: ( вывод)

;;; Ввод L-Eval: count

;;; Значение L-Eval: ( вывод)

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

Eval, передавая оператор в apply, вычисляет его не при помощи eval, а через actual-value, чтобы вынудить. Приведите пример, который показывает, что такое вынуждение необходимо.

38Это упражнение показывает, что взаимодействие между ленивыми вычислениями и побочными эффектами может быть весьма запутанным. Ровно этого можно было ожидать после обсуждения в главе 3.

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

Придумайте пример программы, которая, по Вашему мнению, будет работать намного медленнее без мемоизации, чем с мемоизацией. Рассмотрим, помимо этого, следующую последовательность действий, в которой процедура id определена как в упражнении 4.27, а счетчик count начинает с 0:

(define (square x) (* x x))

;;; Ввод L-Eval: (square (id 10)) ;;; Значение L-Eval: (вывод)

;;; Ввод L-Eval: count

;;; Значение L-Eval: ( вывод)

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

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

a. Бен Битобор считает, что Пабло неправ. Он показывает ему процедуру for-each из упражнения 2.23 - важный пример последовательности с побочными эффектами:

(define (for-each proc items)

(if (null? items)

done

(begin (proc (car items))

(for-each proc (cdr items)))))

Он утверждает, что интерпретатор из текста (с исходным eval-sequence) правильно работает с этой процедурой:

;;; Ввод L-Eval:

(for-each (lambda (x) (newline) (display x)) (list 57 321 88))

57

321

88