Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 55
Текст из файла (страница 55)
3.3 показанаструктура окружений, создаваемая при вычислении выражения (square 5) в глобальном окружении, если square — процедура, порожденная на рисунке 3.2. Применение12 Присваивание вносит одну тонкость в шаг 1 правила вычисления. Как показано в упражнении 3.8, присваивание позволяет нам писать выражения, которые имеют различные значения в зависимости от того, в какомпорядке вычисляются подвыражения комбинации. Таким образом, чтобы быть точными, мы должны былибы указать порядок вычислений на шаге 1 (например, слева направо или справа налево). Однако этот порядок всегда должен рассматриваться как деталь реализации, и писать программы, которые зависят от порядкавычисления аргументов, не следует. К примеру, продвинутый компилятор может оптимизировать программу,изменяя порядок, в котором вычисляются подвыражения.Глава 3.
Модульность, объекты и состояние230глобальноеокружениедругие переменныеsquare:(define (square x)(* x x))параметры: xтело: (* x x)Рис. 3.2. Структура окружений, порождаемая вычислением (define (square x) (*x x)) в глобальном окружении.другие переменныеглобальноеокружение square:(square 5)E1параметры: xтело: (* x x)x:5(* x x)Рис. 3.3.
Окружение, создаваемое при вычислении (square 5) в глобальном окружении.процедуры приводит к созданию нового окружения, которое на рисунке обозначено какE1, и это окружение начинается с кадра, в котором x, формальный параметр процедуры,связан с аргументом 5. Указатель, который ведет из этого кадра вверх, показывает, чтообъемлющим для этого окружения является глобальное. Глобальное окружение выбирается потому, что именно на него ссылается процедурный объект square. Внутри E1 мывычисляем тело процедуры, (* x x). Поскольку значение x в E1 равно 5, результатомбудет (* 5 5), или 25.Модель вычисления с окружениями можно вкратце описать двумя правилами:• Процедурный объект применяется к набору аргументов при помощи создания кадра, связывания формальных параметров процедуры с аргументами вызова, и, наконец,вычисления тела процедуры в контексте этого свежесозданного окружения.
В качествеобъемлющего окружения новый кадр имеет окружение, содержащееся в применяемомпроцедурном объекте.3.2. Модель вычислений с окружениями231• Процедура создается при вычислении lambda-выражения по отношению к некоторому окружению. Получающийся процедурный объект есть пара, состоящая из текстаlambda-выражения и указателя на окружение, в котором процедура была создана.Кроме того, мы указываем, что когда символ определяется при помощи define,в текущем кадре окружения создается связывание, и символу присваивается указанное значение13.
Наконец, мы описываем поведение set!, операции, из-за которой нам,собственно, и пришлось ввести модель с окружениями. Вычисление выражения (set!hпеременнаяi hзначениеi) в некотором окружении заставляет интерпретатор найтисвязывание переменной в окружении и изменить это связывание так, чтобы оно указывало на новое значение. А именно, нужно найти первый кадр окружения, в которомсодержится связывание для переменной, и изменить этот кадр. Если переменная в окружении не связана, set! сигнализирует об ошибке.Все эти правила вычисления, хотя они значительно сложнее, чем в подстановочноймодели, достаточно просты.
Более того, модель вычислений, несмотря на свою абстрактность, дает правильное описание того, как интерпретатор вычисляет выражения. В главе 4 мы увидим, как эта модель может служить основой для реализации работающегоинтерпретатора. В последующих разделах анализ нескольких примеров программ раскрывает некоторые детали этой модели.3.2.2. Применение простых процедурКогда в разделе 1.1.5 мы описывали подстановочную модель, мы показали, как вычисление комбинации (f 5) дает результат 136, если даны следующие определения:(define (square x)(* x x))(define (sum-of-squares x y)(+ (square x) (square y)))(define (f a)(sum-of-squares (+ a 1) (* a 2)))Теперь мы можем проанализировать тот же самый пример, используя модель с окружениями. На рисунке 3.4 изображены три процедурных объекта, созданные вычислениемв глобальном окружении определений f, square, и sum-of-squares.
Каждый процедурный объект состоит из куска кода и указателя на глобальное окружение.На рисунке 3.5 мы видим структуру окружений, созданную вычислением выражения(f 5). Вызов f создает новое окружение E1, начинающееся с кадра, в котором a,формальный параметр f, связывается с аргументом 5. В окружении E1 мы вычисляемтело f:(sum-of-squares (+ a 1) (* a 2))13 Если в текущем кадре уже имелось связывание для указанной переменной, то это связывание изменяется. Это правило удобно, поскольку позволяет переопределять символы; однако оно означает, что при помощиdefine можно изменять значение символов, а это влечет за собой все проблемы, связанные с присваиванием,без явного использования set!. По этой причине некоторые предпочитают, чтобы переопределение существующего символа вызывало предупреждение или сообщение об ошибке.Глава 3.
Модульность, объекты и состояние232sum-of-squares:глобальноеокружение square:f:параметры: aтело: (sum-of-squares(+ a 1)(+ a 2))параметры: xтело: (= x x)параметры: x, yтело: (+ (square x)(square y))Рис. 3.4. Процедурные объекты в глобальном кадре окружения.глобальноеокружениеE1a:5 E2(sum-of-squares(+ a 1)(+ a 2))x:6y:10E3(+ (square x)(square y))x:6E4(* x x)x:10(* x x)Рис. 3.5. Окружения, созданные при вычислении (f 5) с использованием процедур,изображенных на рис.
3.43.2. Модель вычислений с окружениями233Для вычисления этой комбинации сначала мы вычисляем подвыражения. Значениепервого подвыражения, sum-of-squares — процедурный объект. (Обратите внимание,как мы находим этот объект: сначала мы просматриваем первый кадр E1, который несодержит связывания для переменной sum-of-squares. Затем мы переходим в объемлющее окружение, а именно глобальное, и там находим связывание, которое показано нарис. 3.4.) В оставшихся двух подвыражениях элементарные операции + и * применяютсяпри вычислении комбинаций (+ a 1) и (* a 2), и дают, соответственно, результаты6 и 10.Теперь мы применяем процедурный объект sum-of-squares к аргументам 6 и 10.При этом создается новое окружение E2, в котором формальные параметры x и y связываются со значениями аргументов.
Внутри E2 мы вычисляем комбинацию (+ (squarex) (square y)). Для этого нам требуется вычислить (square x), причем значениеsquare мы находим в глобальном окружении, а x равен 6. Мы опять создаем новоеокружение, E3, где x связан со значением 6, и где мы вычисляем тело square, то есть(* x x). Кроме того, как часть вычисления sum-of-squares, нам нужно вычислитьподвыражение (square y), где y равен 10.
Этот второй вызов square создает ещеодно окружение E4, в котором x, формальный параметр square, связан со значением10. Внутри E4 нам нужно вычислить (* x x).Важно заметить, что каждый вызов square создает новое окружение с новым связыванием для x. Теперь мы видим, как разделение кадров служит для того, чтобы разныелокальные переменные по имени x не смешивались. Заметим, кроме того, что все кадры,созданные процедурой square, указывают на глобальное окружение, поскольку указатель именно на это окружение содержится в процедурном объекте square.После того, как подвыражения вычисляются, они возвращают значения.
Значения,порожденные двумя вызовами square, складываются в sum-ofsquares, и этот результат возвращается процедурой f. Поскольку сейчас наше внимание сосредоточенона структурах окружений, мы не будем здесь разбираться, как значения передаются отвызова к вызову; однако на самом деле это важная часть процесса вычисления, и мыдетально рассмотрим ее в главе 5.Упражнение 3.9.В разделе 1.2.1 мы с помощью подстановочной модели анализировали две процедуры вычисленияфакториала, рекурсивную(define (factorial n)(if (= n 1)1(* n (factorial (- n 1)))))и итеративную(define (factorial n)(fact-iter 1 1 n))(define (fact-iter product counter max-count)(if (> counter max-count)product(fact-iter (* counter product)(+ counter 1)max-count)))234Глава 3.
Модульность, объекты и состояниеПродемонстрируйте, какие структуры окружений возникнут при вычислении (factorial 6) скаждой из версий процедуры factorial14.3.2.3. Кадры как хранилище внутреннего состоянияТеперь мы можем обратиться к модели с окружениями и рассмотреть, как можнос помощью процедур и присваивания представлять объекты, обладающие внутреннимсостоянием. В качестве примера возьмем «обработчик снятия денег со счета» из раздела 3.1.1, который создается вызовом процедуры(define (make-withdraw balance)(lambda (amount)(if (>= balance amount)(begin (set! balance (- balance amount))balance)"Недостаточно денег на счете")))Опишем вычисление(define W1 (make-withdraw 100))за которым следует(W1 50)На рисунке 3.6 показан результат определения make-withdraw в глобальном окружении. Получается процедурный объект, который содержит ссылку на глобальное окружение.
До сих пор мы не видим особых отличий от тех примеров, которые мы ужерассмотрели, кроме того, что тело процедуры само по себе является лямбда-выражением.Интересная часть вычисления начинается тогда, когда мы применяем процедуруmake-withdraw к аргументу:(define W1 (make-withdraw 100))Сначала, как обычно, мы создаем окружение E1, где формальный параметр balance связан с аргументом 100.
Внутри этого окружения мы вычисляем тело make-withdraw, аименно lambda-выражение. При этом создается новый процедурный объект, код которого определяется lambda-выражением, а окружение равно E1, окружению, в которомвычисляется lambda при создании процедуры. Полученный процедурный объект возвращается в качестве значения процедуры make-withdraw. Это значение присваиваетсяпеременной W1 в глобальном окружении, поскольку выражение define вычисляетсяименно в нем. Получившаяся структура окружений изображена на рисунке 3.7.Теперь можно проанализировать, что происходит, когда W1 применяется к аргументу:(W1 50)5014 Модель с окружениями неспособна проиллюстрировать утверждение из раздела 1.2.1, что интерпретаторможет, используя хвостовую рекурсию, вычислять процедуры, подобные fact-iter, в фиксированном объемепамяти.
Мы рассмотрим хвостовую рекурсию, когда будем изучать управляющую структуру интерпретатора вразделе 5.4.3.2. Модель вычислений с окружениями235глобальное make-withdraw:окружениепараметры: balanceтело: (lambda (amount)(if (>= balance amount)(begin (set! balance (- balance amount))balance)"Недостаточно денег на счете"))Рис. 3.6. Результат определения make-withdraw в глобальном окружении.make-withdraw:...глобальноеокружение W1:E1balance: 100параметры: balanceтело: ...параметры: amountтело: (if (>= balance amount)(begin (set! balance (-balance amount))balance)"Недостаточно денег на счете"))Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
