(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-se-quence будет выглядеть так:

(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 с вариациями: ленивый интерпретатор

Теперь, имея в своем распоряжении интерпретатор, выраженный в виде программы на Лиспе, мы можем экспериментировать с различными вариантами

строения языка, просто модифицируя этот интерпретатор. В самом деле, часто изобретение нового языка начинается с того, что пишут интерпретатор, который встраивает новый язык в существующий язык высокого уровня. Например, если нам хочется обсудить какую-то деталь предлагаемой модификации Лиспа с другим членом Лисп-сообщества, мы можем предъявить ему интерпретатор, в котором эта модификация реализована. Тогда наш адресат может поэкспериментировать с новым интерпретатором и послать в ответ свои замечания в виде дальнейших модификаций. Реализация на высокоуровневой основе не только упрощает проверку и отладку вычислителя; такое встраивание к тому же позволяет разработчику слизывать31 черты языка-основы, как наш встроенный интерпретатор Лиспа использовал примитивы и структуру управления нижележащего Лиспа. Только позже (да и то не всегда) разработчику приходится брать на себя труд построения полной реализации на низкоуровневом языке или в аппаратуре. В этом разделе и следующем мы изучаем некоторые вариации на тему Scheme, которые значительно увеличивают ее выразительную силу.

4.2.1 Нормальный порядок вычислений и аппликативный порядок вычислений

В разделе 1.1, где мы начали обсуждение моделей вычисления, мы указали, что Scheme - язык с аппликативным порядком вычисления (applicative-order language), а именно, что все аргументы процедур в Scheme вычисляются в момент вызова. Напротив, в языках с нормальным порядком вычисления (normal-order language) вычисление аргументов процедур задерживается до момента, когда действительно возникает нужда в их значениях. Если вычисление аргументов процедур откладывается как можно дольше (например, до того момента, когда они требуются какой-либо элементарной процедуре), то говорят о ленивом вычислении (lazy evaluation).32 Рассмотрим процедуру

(define (try a b)

(if (= a 0) 1 b))

Выполнение (try 0 (/10)) в Scheme приводит к ошибке. При ленивых вычислениях никакой ошибки не возникнет. Вычисление выражения даст результат 1, поскольку к аргументу (/ 1 0) обращаться не понадобится.

Примером использования ленивых вычислений может служить процедура unless:

(define (unless condition usual-value exceptional-value) (if condition exceptional-value usual-value))

которую можно использовать в выражениях вроде

31 Слизывать (snarf): «Брать, в особенности большой документ или файл, с целью использовать с разрешения владельца или без оного». Пролизывать (snarf down): «Слизывать, иногда с дополнительным значением восприятия, переработки или понимания». (Эти определения были слизаны из Steele et al. 1983. См. также Raymond 1993.)

32Терминологическая разница между выражениями «ленивый» и «нормальный порядок вычислений» несколько размыта. Обычно «ленивый» относится к механизмам конкретных интерпретаторов, а «нормальный порядок» к семантике языков независимо от способа реализации. Однако разделение здесь не жесткое, и часто эти термины употребляются как синонимы.

(unless (= b 0) (/ a b)

(begin (display "exception: returning 0")

0))

В аппликативном языке это не будет работать, потому что и обычное значение, и значение исключения будут выполнены еще до вызова unless (См. упражнение 1.6). Преимущество ленивых вычислений в том, что некоторые процедуры, например, та же unless, могут выполнять полезные действия, даже если вычисление некоторых их аргументов способно привести к ошибке или бесконечному циклу.

Если тело процедуры начинает выполняться прежде, чем вычисляется ее аргумент, то процедура называется нестрогой (non-strict) по этому аргументу. Если же аргумент вычисляется прежде, чем происходит вход в процедуру, то процедура называется строгой (strict) по этому аргументу.33 В чисто аппли-кативном языке все процедуры строги по всем своим аргументам. В языке с чисто нормальным порядком вычислений все составные процедуры нестроги по всем своим аргументам, а элементарные процедуры могут быть и такими, и такими. Бывают также языки (см. упражнение 4.31), которые дают программисту возможность явно обозначать строгость определяемых им процедур.

Яркий пример процедуры, которой может быть полезно оказаться нестрогой, - это cons (и вообще почти любой конструктор структур данных). Можно производить полезные вычисления, составлять из элементов структуры данных и работать с ними, даже если значения элементов неизвестны. Вполне имеет смысл задача, например, посчитать длину списка, не зная значений его отдельных элементов. В разделе 4.2.3 мы развиваем эту идею и реализуем потоки из главы 3 в виде списков, составленных из нестрогих cons-пар.

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

Предположим, что мы (в обычной Scheme с аппликативным порядком вычислений) определяем unless как показано выше, а затем определяем factorial через unless:

(define (factorial n) (unless (= n 1)

(* n (factorial (- n 1)))

1))

Что произойдет, если мы попытаемся вычислить (factorial 5)? Будут ли наши определения работать в языке с нормальным порядком вычислений?

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

Бен Битобор и Лиза П. Хакер расходятся во мнениях о важности ленивых вычислений для реализации конструкций вроде unless. Бен указывает, что при аппликативном порядке unless можно реализовать как особую форму. Лиза отвечает, что в таком случае unless будет просто синтаксисом, а не процедурой, которую можно использовать в сочетании с процедурами высших порядков. Проясните детали в обеих позициях. Покажите, как реализовать unless в виде производного выражения (вроде cond или let),

33Термины «строгий» и «нестрогий» означают, в сущности, то же самое, что «аппликативный» и «нормальный» порядок вычислений, но только они относятся к отдельным процедурам и их аргументам, а не к языку в целом. На конференциях по языкам программирования можно услышать, как кто-нибудь говорит: «В языке Hassle с нормальным порядком вычислений есть несколько строгих примитивов. Остальные процедуры принимают аргументы через ленивое вычисление».