Нас не должно смущать, что программы пользователя являются данными для интерпретатора. На самом деле, иногда бывает удобно игнорировать это различие и, предоставляя пользовательским программам доступ к eval, давать пользователю возможность явным образом вычислить объект данных как выражение Лиспа. Во многих диалектах Лиспа имеется элементарная процедура eval, которая в виде аргументов берет выражение и окружение, и вычисляет выражение в указанном окружении.21 Таким образом, как

(eval (* 5 5) user-initial-environment)

так и

(eval (cons * (list 5 5)) user-initial-environment) возвращают результат 25.22 Упражнение 4.15.

Если даны одноаргументная процедура p и объект a, то говорят, что p «останавливается» на a, если выражение (p a) возвращает значение (а не печатает сообщение об ошибке или выполняется вечно). Покажите, что невозможно написать процедуру halts?, которая бы точно определяла для любой процедуры p и любого объекта a, останавливается ли p на a. Используйте следующее рассуждение: если бы имелась такая процедура halts?, можно было бы написать следующую программу:

(define (run-forever) (run-forever)) (define (try p)

(if (halts? p p)

(run-forever)

halted))

Теперь рассмотрите выражение (try try) и покажите, что любое возможное завершение (остановка или вечное выполнение) нарушает требуемое поведение halts?.23

4.1.6 Внутренние определения

Наша модель вычислений с окружениями и метациклический интерпретатор выполняют определения по очереди, расширяя кадр окружения на одно определение за раз. Это особенно удобно для диалоговой разработки программы, когда программисту нужно свободно смешивать вызовы процедур с определениями новых процедур. Однако если мы внимательно поразмыслим над внутренними

21Предупреждение: эта процедура eval - не то же самое, что процедура eval, реализованная нами в разделе 4.1.1, потому что она работает с настоящими окружениями, а не с искусственными структурами окружений, которые мы построили в разделе 4.1.3. С этими настоящими окружениями пользователь не может работать, как с обычными списками; к ним нужно обращаться через eval или другие специальные операции. Подобным образом, элементарная процедура apply, упомянутая раньше, не то же самое, что метациклическая apply, поскольку она использует настоящие процедуры Scheme, а не объекты-процедуры, которые мы конструировали в разделах 4.1.3 и 4.1.4.

22Реализация MIT Scheme имеет процедуру eval, а также символ user-initial-environment, связанный с исходным окружением, в котором вычисляются выражения.

23Хотя здесь мы предположили, что halts? получает процедурный объект, заметим, что рассуждение остается в силе даже в том случае, когда на вход подается текст процедуры и ее окружение. В этом и состоит знаменитая теорема об остановке (Halting Theorem) Тьюринга, в которой был дан первый пример невычислимой (non-computable) задачи, т. е. корректно поставленного задания, которое невозможно выполнить с помощью вычислительной процедуры.

определениями, с помощью которых реализуется блочная структура (введенная в разделе 1.1.8), то мы увидим, что пошаговое расширение окружения - одно имя за другим - может оказаться не лучшим способом определения локальных переменных.

Рассмотрим процедуру с внутренними определениями, например

(define (f x)

(define (even? n) (if (= n 0) true

(odd? (- n 1))))

(define (odd? n)

(if (= n 0) false

(even? (- n 1))))

(остаток тела f))

Здесь нам хочется, чтобы имя odd? в теле процедуры even? ссылалось на процедуру odd? , которая определена позже, чем even? . Область действия имени odd? - это все тело f, а не только та его часть, которая лежит за точкой внутри f, где определяется odd? . В самом деле, ели заметить, что сама odd? определена с помощью even? - так что even? и odd? являются взаимно рекурсивными процедурами, - то становится ясно, что единственная удовлетворительная интерпретация двух define - рассматривать их так, как будто even? и odd? были добавлены в окружение одновременно. В общем случае, сферой действия локального имени является целиком тело процедуры, в котором вычисляется define.

В нынешнем виде интерпретатор будет вычислять вызовы f правильно, но причина этого «чисто случайная»: поскольку определения внутренних процедур расположены в начале, никакие их вызовы не вычисляются, пока они все не определены. Следовательно, к тому времени, когда выполняется even? , odd? уже определена. Фактически, последовательный механизм вычисления дает те же результаты, что и механизм, непосредственно реализующий одновременное определение, для всякой процедуры, где внутренние определения стоят в начале тела, а вычисление выражений для определяемых переменных не использует ни одну из этих переменных. (Пример процедуры, которая не удовлетворяет этим требованиям, так что последовательное определение не равносильно одновременному, можно найти в упражнении 4.19.)24

Однако имеется простой способ обрабатывать определения так, чтобы у локально определенных имен оказалась действительно общая сфера действия, - достаточно лишь создать все будущие внутренние переменные текущего окружения, прежде чем начнется вычисление какого-либо из выражений, возвращающих значение. Можно это сделать, например, путем синтаксического преобразования lambda-выражений. Прежде чем выполнять тело выражения lambda,

24 Нежелание зависеть в программах от этого механизма вычисления побудило нас написать «администрация ответственности не несет» в примечании 28 в главе 1. Настаивая на том, чтобы внутренние определения стояли в начале тела и не использовали друг друга во время вычисления самих определений, стандарт IEEE Scheme дает авторам реализаций некоторую свободу при выборе механизма вычисления этих определений. Выбор того или иного правила вычисления может показаться мелочью, которая влияет только на интерпретацию «плохих» программ. Однако в разделе 5.5.6 мы увидим, что через переход к модели с одновременным определением внутренних переменных можно избежать некоторых досадных трудностей, которые бы в противном случае возникли при написании компилятора.

мы «прочесываем» его и уничтожаем все внутренние определения. Локально определенные переменные будут созданы через let, а затем получат значения посредством присваивания. Например, процедура

(lambda (переменные) (define u (el)) (define v (e2)) (e3))

преобразуется в

(lambda (переменные)

(let ((u *unassigned*) (v *unassigned*)) (set! u (el)) (set! v (e2)) (e3)))

где *unassigned* - специальный символ, который при поиске переменной вызывает сообщение об ошибке, если программа пытается использовать значение переменной, которой ничего еще не присвоено.

Альтернативная стратегия поиска внутренних определений показана в упражнении 4.18. В отличие от преобразования, продемонстрированного только что, она навязывает программисту следующее ограничение: значение каждой определяемой переменной должно вычисляться без обращения к значениям других определяемых переменных.25

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

В этом упражнении мы реализуем только что описанный метод обработки внутренних определений. Мы предполагаем, что интерпретатор поддерживает let (см. упражнение 4.6).

a.Измените процедуру lookup-variable-value (раздел 4.1.3) так, чтобы она, обнаруживая в качестве значения символ *unassigned*, сообщала об ошибке.

b.Напишите процедуру scan-out-defines, которая берет тело процедуры и возвращает его эквивалент без внутренних определений, выполняя описанное нами преобразование.

c.Вставьте scan-out-defines в интерпретатор, либо в make-procedure, либо в procedure-body. Какое из этих мест лучше? Почему?

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

Нарисуйте диаграммы окружения, которое находится в силе в момент выполнения выражения (e3) из процедуры выше по тексту, и сравните его устройство при последовательной обработке определений и при описанном выше преобразовании. Откуда в преобразованной программе берется дополнительный кадр? Объясните, почему это различие никогда не отражается на поведении корректных программ. Придумайте, как заставить интерпретатор реализовать правило «одновременной» сферы действия для внутренних определений без создания дополнительного кадра.

25Стандарт IEEE Scheme допускает различные стратегии реализации. В нем говорится, что программист обязан подчиняться этому ограничению, но реализация может его не проверять. Некоторые реализации Scheme, включая MIT Scheme, используют преобразование, показанное выше. В таких реализациях будут работать некоторые из программ, которые это ограничение нарушают.