Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 83
Текст из файла (страница 83)
Покажите, что невозможно написать процедуру 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. Внутренние определенияНаша модель вычислений с окружениями и метациклический интерпретатор выполняют определения по очереди, расширяя кадр окружения на одно определение за раз.Это особенно удобно для диалоговой разработки программы, когда программисту нужносвободно смешивать вызовы процедур с определениями новых процедур. Однако еслимы внимательно поразмыслим над внутренними определениями, с помощью которых реализуется блочная структура (введенная в разделе 1.1.8), то мы увидим, что пошаговоерасширение окружения — одно имя за другим — может оказаться не лучшим способомопределения локальных переменных.Рассмотрим процедуру с внутренними определениями, напримерокружений, которые мы построили в разделе 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) задачи, т.
е. корректно поставленного задания, которое невозможно выполнить спомощью вычислительной процедуры.4.1. Метациклический интерпретатор361(define (f x)(define (even? n)(if (= n 0)true(odd? (- n 1))))(define (odd? n)(if (= n 0)false(even? (- n 1))))hостаток тела fi)Здесь нам хочется, чтобы имя odd? в теле процедуры even? ссылалось на процедуруodd?, которая определена позже, чем even?. Область действия имени odd? — это всетело f, а не только та его часть, которая лежит за точкой внутри f, где определяетсяodd?. В самом деле, ели заметить, что сама odd? определена с помощью even? — такчто even? и odd? являются взаимно рекурсивными процедурами, — то становится ясно,что единственная удовлетворительная интерпретация двух define — рассматривать ихтак, как будто even? и odd? были добавлены в окружение одновременно.
В общемслучае, сферой действия локального имени является целиком тело процедуры, в которомвычисляется define.В нынешнем виде интерпретатор будет вычислять вызовы f правильно, но причина этого «чисто случайная»: поскольку определения внутренних процедур расположеныв начале, никакие их вызовы не вычисляются, пока они все не определены. Следовательно, к тому времени, когда выполняется even?, odd? уже определена.
Фактически,последовательный механизм вычисления дает те же результаты, что и механизм, непосредственно реализующий одновременное определение, для всякой процедуры, где внутренние определения стоят в начале тела, а вычисление выражений для определяемыхпеременных не использует ни одну из этих переменных. (Пример процедуры, которая неудовлетворяет этим требованиям, так что последовательное определение не равносильноодновременному, можно найти в упражнении 4.19.)24Однако имеется простой способ обрабатывать определения так, чтобы у локальноопределенных имен оказалась действительно общая сфера действия, — достаточно лишьсоздать все будущие внутренние переменные текущего окружения, прежде чем начнетсявычисление какого-либо из выражений, возвращающих значение.
Можно это сделать,например, путем синтаксического преобразования lambda-выражений. Прежде чем выполнять тело выражения lambda, мы «прочесываем» его и уничтожаем все внутренниеопределения. Локально определенные переменные будут созданы через let, а затем получат значения посредством присваивания. Например, процедура(lambda hпеременныеi(define u he1i)24 Нежелание зависеть в программах от этого механизма вычисления побудило нас написать «администрацияответственности не несет» в примечании 28 в главе 1. Настаивая на том, чтобы внутренние определения стоялив начале тела и не использовали друг друга во время вычисления самих определений, стандарт IEEE Schemeдает авторам реализаций некоторую свободу при выборе механизма вычисления этих определений.
Выбор тогоили иного правила вычисления может показаться мелочью, которая влияет только на интерпретацию «плохих»программ. Однако в разделе 5.5.6 мы увидим, что через переход к модели с одновременным определениемвнутренних переменных можно избежать некоторых досадных трудностей, которые бы в противном случаевозникли при написании компилятора.362Глава 4. Метаязыковая абстракция(define v he2i)he3i)преобразуется в(lambda hпеременныеi(let ((u ’*unassigned*)(v ’*unassigned*))(set! u he1i)(set! v he2i)he3i))где *unassigned* — специальный символ, который при поиске переменной вызывает сообщение об ошибке, если программа пытается использовать значение переменной,которой ничего еще не присвоено.Альтернативная стратегия поиска внутренних определений показана в упражнении 4.18. В отличие от преобразования, продемонстрированного только что, она навязывает программисту следующее ограничение: значение каждой определяемой переменнойдолжно вычисляться без обращения к значениям других определяемых переменных25.Упражнение 4.16.В этом упражнении мы реализуем только что описанный метод обработки внутренних определений.
Мы предполагаем, что интерпретатор поддерживает let (см. упражнение 4.6).а. Измените процедуру lookup-variable-value (раздел 4.1.3) так, чтобы она, обнаруживаяв качестве значения символ *unassigned*, сообщала об ошибке.б. Напишите процедуру scan-out-defines, которая берет тело процедуры и возвращает егоэквивалент без внутренних определений, выполняя описанное нами преобразование.в.
Вставьте scan-out-defines в интерпретатор, либо в make-procedure, либо в procedure-body. Какое из этих мест лучше? Почему?Упражнение 4.17.Нарисуйте диаграммы окружения, которое находится в силе в момент выполнения выраженияhe3i из процедуры выше по тексту, и сравните его устройство при последовательной обработкеопределений и при описанном выше преобразовании. Откуда в преобразованной программе берется дополнительный кадр? Объясните, почему это различие никогда не отражается на поведениикорректных программ.
Придумайте, как заставить интерпретатор реализовать правило «одновременной» сферы действия для внутренних определений без создания дополнительного кадра.Упражнение 4.18.Рассмотрим альтернативную стратегию обработки определений, которая переводит пример из текста в(lambda hпеременныеi(let ((u ’*unassigned*)25 Стандарт IEEE Scheme допускает различные стратегии реализации.
В нем говорится, что программистобязан подчиняться этому ограничению, но реализация может его не проверять. Некоторые реализации Scheme,включая MIT Scheme, используют преобразование, показанное выше. В таких реализациях будут работатьнекоторые из программ, которые это ограничение нарушают.4.1. Метациклический интерпретатор363(v ’*unassigned*))(let ((a he1i)(b he2i))(set! u a)(set! v b))he3i))Здесь a и b представляют новые имена переменных, созданные интерпретатором, которые невстречаются в пользовательской программе.
Рассмотрим процедуру solve из раздела 3.5.4:(define (solve f y0 dt)(define y (integral (delay dy) y0 dt))(define dy (stream-map f y))y)Будет ли эта процедура работать, если внутренние определения преобразуются так, как предлагается в этом упражнении? А если так, как в тексте раздела? Объясните.Упражнение 4.19.Бен Битобор, Лиза П. Хакер и Ева Лу Атор спорят о том, каким должен быть результат выражения(let ((a 1))(define (f x)(define b (+ a x))(define a 5)(+ a b))(f 10))Бен говорит, что следует действовать согласно последовательному правилу для define: b равно11, затем a определяется как 5, так что общий результат равен 16. Лиза возражает, что взаимнаярекурсия требует правила одновременной сферы действия для внутренних определений и нет причин рассматривать имена процедур отдельно от прочих имен.
То есть она выступает за механизм,реализованный в упражнении 4.16. При этом a оказывается не определено в момент, когда вычисляется b. Следовательно, по мнению Лизы, процедура должна выдавать ошибку. Ева не согласна собоими. Она говорит, что если определения вправду должны считаться одновременными, то 5 какзначение a должно использоваться при вычислении b. Следовательно, по мнению Евы, a должноравняться 5, b должно быть 15, а общий результат 20.
Какую из этих точек зрения Вы поддерживаете (если у Вас нет своей четвертой)? Можете ли Вы придумать способ реализации внутреннихопределений, который бы работал так, как предлагает Ева26 ?Упражнение 4.20.Поскольку внутренние определения выглядят последовательными, а на самом деле параллельны,некоторые предпочитают их вовсе избегать и вместо этого пользуются особой формой letrec.Letrec выглядит так же, как let, поэтому неудивительно, что переменные в нем связываютсяодновременно и имеют одинаковую для всех сферу действия. Можно переписать процедуру-примерf из текста без внутренних определений, но при этом в точности с тем же значением, так:26 Авторы MIT Scheme согласны с Лизой, и вот почему: в принципе права Ева — определения следуетрассматривать как одновременные. Однако придумать универсальный эффективный механизм, который вел бысебя так, как она требует, кажется трудным.
Если же такого механизма нет, то лучше порождать ошибку всложных случаях параллельных определений (мнение Лизы), чем выдавать неверный ответ (как хочет Бен).364Глава 4. Метаязыковая абстракция(define (f x)(letrec ((even?(lambda (n)(if (= n 0)true(odd? (- n 1)))))(odd?(lambda (n)(if (= n 0)false(even? (- n 1))))))hостаток тела fi))Выражение letrec имеет вид(letrec ((hпер1 i hвыр1 i) ... (hперn i hвырn i))hтелоi)и является вариантом let, в котором выражения hвырk i, устанавливающие начальные значениядля переменных hперk i, вычисляются в окружении, которое включает все связывания letrec.Это делает возможным рекурсию между связываниями, к примеру, взаимную рекурсию even? иodd? в последнем примере, или вычисление факториала 10 через(letrec ((fact(lambda (n)(if (= n 1)1(* n (fact (- n 1)))))))(fact 10))а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
