(define acc2 (make-account 100))

Каким образом удается не смешивать внутренние состояния двух счетов? Какие части структуры окружений общие у acc и acc2?

3.3 Моделирование при помощи изменяемых данных

В главе 2 составные данные использовались как средство построения вычислительных объектов, состоящих из нескольких частей, с целью моделирования объектов реального мира, обладающих несколькими свойствами. В этой главе мы ввели дисциплину абстракции данных, согласно которой структуры данных описываются в терминах конструкторов, которые создают объекты данных, и селекторов, которые обеспечивают доступ к частям составных объектов. Однако теперь мы знаем, что есть еще один аспект работы с данными, который остался незатронутым в главе 2. Желание моделировать системы, которые состоят из объектов, обладающих изменяющимся состоянием, вызывает потребность не только создавать составные объекты данных и иметь доступ к их частям, но и изменять их. Чтобы моделировать объекты с изменяющимся состоянием, мы будем проектировать абстракции данных, которые, помимо конструкторов и селекторов, включают мутаторы (mutators), модифицирующие объекты данных. Например, моделирование банковской системы требует от нас способности изменять балансы счетов. Таким образом, структура данных, изображающая банковский счет, может обладать операцией

(set-balance! (счет) (новое-значение))

которая присваивает балансу указанного счета указанное значение. Объекты данных, для которых определены мутаторы, называются изменяемыми объектами данных (mutable data objects).

В главе 2 в качестве универсального «клея» для построения составных данных мы ввели пары. Этот раздел мы начинаем с определения мутаторов для пар, так, чтобы пары могли служить строительным материалом для построения изменяемых объектов данных. Мутаторы значительно увеличивают выразительную силу пар и позволяют нам строить структуры данных помимо последовательностей и деревьев, с которыми мы имели дело в разделе 2.2. Кроме того, мы строим несколько примеров моделей, где сложные системы представляются в виде множества объектов, обладающих внутренним состоянием.

3.3.1 Изменяемая списковая структура

Базовые операции над парами - cons, car и cdr - можно использовать для построения списковой структуры и для извлечения частей списковой структуры, однако изменять списковую структуру они не позволяют. То же верно и для операций со списками, которые мы до сих пор использовали, таких, как append и list, поскольку эти последние можно определить в терминах cons, car и cdr. Для модификации списковых структур нам нужны новые операции.

Элементарные мутаторы для пар называются setcar! и set-cdr!. Set-car! принимает два аргумента, первый из которых обязан быть парой. Он

x-H t •

• •--- •

т •-• t

b

• •--- •

Рис. 3.12: Списки x: ((a b) c d) и y: (e f) .

d

c

a

y

f

e

модифицирует эту пару, подставляя вместо указателя car указатель на свой второй аргумент.16

В качестве примера предположим, что переменная x имеет значением список ((a b) c d) , а переменная y список (e f) , как показано на рисунке 3.12. Вычисление выражения (set-car! x y) изменяет пару, с которой связана переменная x, заменяя ее car на значение y. Результат этой операции показан на рисунке 3.13. Структура x изменилась, и теперь ее можно записать как ((e f) c d). Пары представляющие список (a b), на которые указывал замененный указатель, теперь отделены от исходной структу-ры.17

Сравните рисунок 3.13 с рис. 3.14, на котором представлен результат выполнения (define z (cons y (cdr x))) , где x и y имеют исходные значения с рис. 3.12. Здесь переменная z оказывается связана с новой парой, созданной операцией cons; список, который является значением x, не меняется.

Операция set-cdr! подобна set-car!. Единственная разница состоит в том, что заменяется не указатель car, а указатель cdr. Результат применения (set-cdr! x y) к спискам, изображенным на рис. 3.12, показан на рис. 3.15. Здесь указатель cdr в составе x заменился указателем на (e f) . Кроме того, список (c d), который был cdr-ом x, оказывается отделенным от структуры.

Cons создает новую списковую структуру, порождая новые пары, а set-car! и set-cdr! изменяют существующие. В сущности, мы могли бы реализовать cons при помощи этих двух мутаторов и процедуры get-new-pair, которая возвращает новую пару, не являющуюся частью никакой существующей списковой структуры. Мы порождаем новую пару, присваиваем ее указателям car и cdr нужные значения, и возвращаем новую пару в качестве результата cons:18

16Значения, которые возвращают set-car! и set-cdr!, зависят от реализации. Подобно set!, эти операции должны использоваться исключительно ради своего побочного эффекта.

17Здесь мы видим, как операции изменения данных могут создавать «мусор», который не является частью никакой доступной структуры. В разделе 5.3.2 мы увидим, что системы управления памятью Лиспа включают сборщик мусора (garbage collector), который находит и освобождает память, используемую ненужными парами.

18Get-new-pair - одна из операций, которые требуется предоставить как часть системы управ-

x-H t •

Рис. 3.13: Результат применения (set-car! на рис. 3.12.

Рис. 3.14: Результат применения (define z показанным на рис. 3.12.

x-H t t

b

x y) к спискам, изображенным

(cons y

b

(cdr x)) к спискам,

b

d

c

a

y

f

e

x

d

c

z

a

y

f

e

d

c

a

y

f

e

Рис. 3.15: Результат применения (set-cdr! x y)

к спискам с рис. 3.12.