и приведите пример ситуации, когда имеет смысл, чтобы unless была процедурой, а не особой формой.

4.2.2 Интерпретатор с ленивым вычислением

В этом разделе мы реализуем язык с нормальным порядком вычислений, который отличается от Scheme только тем, что все составные процедуры по всем аргументам нестроги. Элементарные процедуры по-прежнему будут строгими. Совсем несложно, модифицируя интерпретатор из раздела 4.1.1, добиться, чтобы интерпретируемый язык вел себя таким образом. Почти что все требуемые изменения сосредоточены вокруг механизма процедурного вызова.

Основная идея состоит в том, что при вызове процедуры интерпретатор должен определить, какие аргументы требуется вычислить, а какие задержать. Задержанные аргументы не вычисляются, а преобразуются в объекты, называемые санками (thunks).34* В санке должна содержаться информация, необходимая, чтобы вычислить значение аргумента, когда оно потребуется, и сделать это так, как будто оно вычислено во время вызова. Таким образом, санк должен содержать выражение-аргумент и окружение, в котором вычисляется вызов процедуры.

Процесс вычисления санка называется вынуждением (forcing a thunk)35 Вообще говоря, санк вынуждается только тогда, когда требуется его значение: когда он передается в элементарную процедуру, использующую его значение; когда он служит предикатом в условном выражении; или когда он является значением оператора, который нужно применить как процедуру. Мы должны решить, будем ли мы мемоизировать (memoize) санки, как мы делали с задержанными объектами в разделе 3.5.1. При использовании мемоизации, когда санк вынуждается в первый раз, он запоминает вычисленное значение. Последующие вызовы только возвращают запомненное значение, не вычисляя его заново. Мы делаем выбор в пользу мемоизации, поскольку для многих приложений это эффективнее. Здесь, однако, имеются тонкости.36

34 Название «санк» было придумано в неформальной группе, которая обсуждала реализацию вызова по имени в Алголе 60. Было замечено, что большую часть анализа («обдумывания», thinking about) выражения можно производить во время компиляции; таким образом, во время выполнения выражение будет уже большей частью «обдумано» (thunk about - намеренно неверно образованная английская форма) (Ingerman et al. 1960).

*В русскоязычной литературе слово thunk иногда переводится как «переходник». Нам кажется, что в данном случае такой перевод мешал бы пониманию текста. - прим. перев.

35Это аналогично использованию слова force («вынудить», «заставить») для задержанных объектов, при помощи которых в главе 3 представлялись потоки. Основная разница между тем, что мы делаем здесь, и тем, чем мы занимались в главе 3, состоит в том, что теперь мы встраиваем задержку и вынуждение в интерпретатор, и они применяются автоматически и единообразно во всем языке.

36Ленивые вычисления, совмещенные с мемоизацией, иногда называют методом передачи аргументов с вызовом по необходимости (call by need), в отличие от вызова по имени (call by name). (Вызов по имени, введенный в Алголе 60, аналогичен немемоизированному ленивому вычислению.) Как проектировщики языка мы можем сделать интерпретатор мемоизирующим или немемоизиру-ющим, или же оставить это на усмотрение программистов (упражнение 4.31). Как можно было ожидать из главы 3, этот выбор вызывает к жизни вопросы, особенно тонкие и запутанные в присутствии присваивания. (См. упражнения 4.27 и 4.29.) В замечательной статье Клингера (Clinger 1982) делается попытка прояснить многомерную путаницу, которая здесь возникает.

Преобразование интерпретатора

Основная разница между ленивым интерпретатором и интерпретатором из раздела 4.1.1 состоит в обработке вызовов процедур внутри eval и apply. Ветка application? в eval принимает вид

((application? exp) (apply (actual-value (operator exp) env) (operands exp) env))

Это почти тот же код, что был в ветке application? в eval из раздела 4.1.1. Однако при ленивом вычислении мы зовем apply с выражениями операндов, а не с аргументами, которые получаются при их вычислении. Мы также передаем apply окружение, поскольку оно понадобится для построения санков, если нам хочется, чтобы аргуметы вычислялись с задержкой. Оператор мы по-прежнему вычисляем, потому что сама применяемая процедура нужна apply, чтобы выбрать действие на основании ее типа (элементарная или составная) и применить ее.

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

(define (actual-value exp env) (force-it (eval exp env)))

чтобы, если значение выражения является санком, оно было вынуждено.

Наша новая версия apply также почти совпадает с версией из раздела 4.1.1. Разница состоит в том, что eval передает ей невычисленные выражения: для элементарных процедур (они строгие) мы вычисляем все аргументы и затем вызываем примитив; для составных процедур (они нестрогие) мы прежде применения процедуры замораживаем все аргументы.

(define (apply procedure arguments env) (cond ((primitive-procedure? procedure) (apply-primitive-procedure procedure

(list-of-arg-values arguments env))) ; изменение ((compound-procedure? procedure) (eval-sequence (procedure-body procedure) (extend-environment (procedure-parameters procedure)

(list-of-delayed-args arguments env) ; изменение (procedure-environment procedure)))) (else (error

"Неизвестный тип процедуры -- APPLY" procedure))))

Процедуры, обрабатывающие аргументы, почти такие же, как list-of-values из раздела 4.1.1, но только list-of-delayed-args замораживает аргументы, вместо того, чтобы их вычислять, а в list-of-arg-values вместо eval используется actual-value:

(define (list-of-arg-values exps env) (if (no-operands? exps)

(cons (actual-value (first-operand exps) env) (list-of-arg-values (rest-operands exps)

env))))

(define (list-of-delayed-args exps env) (if (no-operands? exps) ()

(cons (delay-it (first-operand exps) env)

(list-of-delayed-args (rest-operands exps)

env))))

Кроме того, нам требуется изменить в интерпретаторе обработку if, где вместо eval мы должны вызывать actual-value, чтобы значение предикатного выражения вычислялось прежде, чем мы проверим, истинно оно или ложно:

(define (eval-if exp env)

(if (true? (actual-value (if-predicate exp) env)) (eval (if-consequent exp) env) (eval (if-alternative exp) env)))

Наконец, нужно изменить процедуру driver-loop (раздел 4.1.4), чтобы она звала actual-value вместо eval. Таким образом, если задержанное значение добирается до цикла чтение-вычисление-печать, то оно, прежде чем печататься, будет разморожено. Кроме того, чтобы показать, что работа идет с ленивым интерпретатором, мы изменим подсказки:

(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: (define (try a b)

(if (= a 0) 1 b))

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