Личный сайт Алексея Григорьева

SICP: The Environment Model of Evaluation

Глава «The Environment Model of Evaluation» книги «Structure and implementation of computer programs» объясняет модель окружений (Environment Model), которая используется для вычисления процедур, а так же предоставляет возможности для разбивания программ на независимые модули.

По существу, глава рассказывает о механизме, лежащем в основе термина «замыкание». Этот механизм используется во многих современных языках программирования, таких, как python, java script и других. Сам термин «замыкание» авторами в этом смысле не употребляется, вместо него используется термин «окружение», в книге же closure используется для обозначения совсем другого свойства.

Ниже — переработанный конспект главы.

Модель окружений и её основные понятия

Связанная переменная (Bound variable) — переменная, определенная в некотором контексте и не действующая за пределами этого контекста.

Примеры связанных переменных:

Если заменить связанную переменную повсюду, где она встречается, то в результате будет получено эквивалентное выражение:

Свободная переменная (Free variable) — переменная, определенная за пределами пределами контекста.

Если свободную переменную заменить на другую, полученное выражение не будет эквивалентно исходному:

Окружение (Environment) — место, в котором хранятся значения переменных. Окружение представляет собой последовательность кадров (Frames).

Каждый кадр (Frame) — своего рода «таблица», в которой хранятся значения связанных переменных. Каждый кадр имеет указатель на родительский кадр.

Если переменная не связана ни с одним значением ни в одном из кадров, значит переменная является несвязанной (unbound).

A, B, C, D — указатели на окружения. C и D указывают на одно и то же окружение I. Переменные z и x являются связанными в окружении II, y и x — в окружении I; x в окружении II скрывает (shadows) переменную x в окружении I.

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

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

Для того, чтобы применить процедуру к переданным в неё аргументам, сначала необходимо создать новое окружение, в котором параметры процедуры связываются с переданными значениями. Для только что созданного окружения родительским является окружение, в котором функция определена. Для вычисления тела (body) процедуры необходимо подставить в него значения переменных из нового окружения.

Таким образом, модель окружения определяется двумя правилами:

  1. Процедурный объект применяется ко множеству аргументов с помощью создания нового окружения, в котором параметры процедуры связываются с переданными значениями, а затем выполняется тело процедуры в контексте нового окружения. Для только что созданного окружения родительским является окружение, в котором объявлена процедура.
  2. Процедура создается с помощью выполнения лямбда-выражения в некотором окружении. Результатом является пара, состоящая из текста лямбда-выражения и указателя на окружение, в котором процедура была создана.

Для объявления переменной используется ключевое слова define, которое в текущем окружении создает переменную и связывает ее с необходимым значением.

Оператор присваивания (set! <variable> <value>) находит окружение, в котором определена переменная variable и изменяет её.

Окружения, как средство хранения состояния

Рассмотрим, как можно использовать правила этой модели для создания объектов, имеющих внутренние состояние. Возьмем пример с созданием объекта, содержащего в себе текущий остаток на счету клиента в банке (assigment.scm)

(define (make-withdraw balance)
    (lambda (amount)
        (if (>= balance amount)
            (begin 
                (set! balance (- balance amount))
                balance)
            "Insufficient funds"
        )
    )
)

Теперь определим процедуру W1 и вызовем ее:

(define W1 (make-withdraw 100))
(W1 50)

При вызове (make-withdraw 100) создается переменная W1, которая связывается с процедурным объектом. Процедура W1 имеет ссылку не на глобальное окружение, а на внутреннее окружение E1, в котором хранится переданный процедуре make-withdraw параметр balance, равный 100.

При вызове процедуры W1 вычисляется её тело, при этом создается ещё одно окружение E2, в котором определяется значение переданного параметра amount. Окружение E2 имеет ссылку на оружение Е1.

При выполнении проверки (>= balance amount) значение amount будет взято из окружения E2. Так как переменная balance не определена в окружении Е2, значение для неё ищется в родительском для Е2 окружении - Е1.

Во время выполнения set! значение переменной balance изменяется в окружении E1, несмотря на то, что код выполняется в E2.

После того, как выполнение процедуры закончилось, значение переменной balance остается изменённым и хранится в окружении E1. Окружение E2 больше не нужно, т.к. на него ничто не ссылается.

При следующем вызове W1 будет создано новое окружение E3, которое ссылается на E1, и в котором имеет доступ к переменной balance.

E1 в данном случае служит местом, в котором хранятся значения локальных переменных для процедуры W1.

Что же случится, если вызвать еще один раз процедуру make-withdraw?

(define W2 (make-withdraw 100))

При этом будет создан еще один процедурный объект, ассоциированный с новым окружением, причём изменения в W1 не будут приводить к изменениям в W2.

Определения внутри определений

Нам известно, что внутри процедуры можно сделать объявление другой процедуры, и при этом внутренние объявление будут доступны только внутри "родителя". Взглянем на код вычисления квадратного корня из первой главы (sqrt-nested.scm):

(define (sqrt x)
    (define (sqrt-iter guess)
        (if (good-enough? guess)
            guess
            (sqrt-iter (improve guess))
        )
    )
 
    (define (good-enough? guess)
        (< (abs (- (square guess) x)) 0.001)
    )
 
    (define (improve guess)
        (average guess (/ x guess))
    )
 
    (sqrt-iter 1.0)
)

Процедура sqrt определяется в глобальном окружении. Во время её вызова формируется новое окружение Е1, родительским для которого является глобальное окружение. В окружении Е1 переменная х связывается с переданным в процедуру значением 2.

Во время вычисления тела процедуры sqrt определяется ряд внутренних процедур, а затем происходит вызов одной из них - процедуры с именем sqrt-iter.

При вычислении значения для sqrt-iter проверяется окружение Е1, в котором есть объявление с этим именем, поэтому подставляется процедурный объект, содержащийся в нем, и затем он вызывается. Теперь процедура sqrt-iter создает для себя новое окружение Е2, в котором параметр guess связан со переданным значением 1.0. Внутри sqrt-iter происходит обращение к процедуре с именем good-enough? Этого имени нет в окружении Е2, поэтому поиск производится в родительском для Е2 окружении Е1. good-enough? при вызове так же создает новое окружение Е3, которое является дочерним для Е1 - окружение, в котором объявлена good-enough? В Е3 с именем guess так же ассоциируется значение 1.0.

Хоть и обе процедуры good-enough? и sqrt-iter имеют переменные guess, эти переменные никак не связаны и относятся к разным окружениям E2 и E3, и поэтому, если внести изменение в одном окружении, это не приведет к изменению в другом.

 

Таким образом, данная модель имеет две ключевые особенности, которые делают внутренние объявление процедур отличным способом для организации модульных программ.

Источники

SICP, глава 3.2, The Environment Model of Evaluation
SICP, видео-лекция 5A: Assignment, State, and Side-effects

Дополнительный материал

Решения упражнений из SICP главы 3.2
Определение термина "замыкание"

Далее:

Воскресенье, 22 Июл 2012 в 18:10. Вы можете следить за комментариями к этой статье через RSS 2.0.