Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 57
Текст из файла (страница 57)
Желание моделироватьсистемы, которые состоят из объектов, обладающих изменяющимся состоянием, вызывает потребность не только создавать составные объекты данных и иметь доступ к ихчастям, но и изменять их. Чтобы моделировать объекты с изменяющимся состоянием,мы будем проектировать абстракции данных, которые, помимо конструкторов и селекторов, включают мутаторы (mutators), модифицирующие объекты данных. Например,моделирование банковской системы требует от нас способности изменять балансы счетов. Таким образом, структура данных, изображающая банковский счет, может обладатьоперацией(set-balance! hсчетi hновое-значениеi)которая присваивает балансу указанного счета указанное значение. Объекты данных, для которых определены мутаторы, называются изменяемыми объектами данных(mutable data objects).В главе 2 в качестве универсального «клея» для построения составных данных мыввели пары.
Этот раздел мы начинаем с определения мутаторов для пар, так, чтобы парымогли служить строительным материалом для построения изменяемых объектов данных.Мутаторы значительно увеличивают выразительную силу пар и позволяют нам строитьструктуры данных помимо последовательностей и деревьев, с которыми мы имели делов разделе 2.2. Кроме того, мы строим несколько примеров моделей, где сложные системыпредставляются в виде множества объектов, обладающих внутренним состоянием.Глава 3.
Модульность, объекты и состояние242xcdabefyРис. 3.12. Списки x: ((a b) c d) и y: (e f).3.3.1. Изменяемая списковая структураБазовые операции над парами — cons, car и cdr — можно использовать для построения списковой структуры и для извлечения частей списковой структуры, однакоизменять списковую структуру они не позволяют. То же верно и для операций со списками, которые мы до сих пор использовали, таких, как append и list, поскольку этипоследние можно определить в терминах cons, car и cdr. Для модификации списковыхструктур нам нужны новые операции.Элементарные мутаторы для пар называются setcar! и set-cdr!.
Setcar! принимает два аргумента, первый из которых обязан быть парой. Он модифицирует этупару, подставляя вместо указателя car указатель на свой второй аргумент16 .В качестве примера предположим, что переменная x имеет значением список ((ab) 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)16 Значения, которые возвращают set-car! и set-cdr!, зависят от реализации. Подобно set!, эти операции должны использоваться исключительно ради своего побочного эффекта.17 Здесь мы видим, как операции изменения данных могут создавать «мусор», который не является частьюникакой доступной структуры. В разделе 5.3.2 мы увидим, что системы управления памятью Лиспа включают сборщик мусора (garbage collector), который находит и освобождает память, используемую ненужнымипарами.3.3. Моделирование при помощи изменяемых данных243xcdabefyРис.
3.13. Результат применения (set-car! x y) к спискам, изображенным нарис. 3.12.xcdabefzyРис. 3.14. Результат применения (define z (cons y (cdr x)) к спискам, показанным на рис. 3.12.Глава 3. Модульность, объекты и состояние244xcdabefyРис. 3.15. Результат применения (set-cdr! x y) к спискам с рис. 3.12.к спискам, изображенным на рис. 3.12, показан на рис. 3.15. Здесь указатель cdr всоставе x заменился указателем на (e f). Кроме того, список (c d), который былcdr-ом x, оказывается отделенным от структуры.Cons создает новую списковую структуру, порождая новые пары, а setcar! и setcdr! изменяют существующие. В сущности, мы могли бы реализовать cons при помощиэтих двух мутаторов и процедуры get-new-pair, которая возвращает новую пару,не являющуюся частью никакой существующей списковой структуры. Мы порождаемновую пару, присваиваем ее указателям car и cdr нужные значения, и возвращаемновую пару в качестве результата cons18 :(define (cons x y)(let ((new (get-new-pair)))(set-car! new x)(set-cdr! new y)new))Упражнение 3.12.В разделе 2.2.1 была введена следующая процедура для добавления одного списка к другому:(define (append x y)(if (null? x)y(cons (car x) (append (cdr x) y))))Append порождает новый список, по очереди наращивая элементы x в начало y.
Процедураappend! подобна append, но только она является не конструктором, а мутатором. Она склеивает списки вместе, изменяя последнюю пару x так, что ее cdr становится равным y. (Вызовappend! с пустым x является ошибкой.)18 Get-new-pair — одна из операций, которые требуется предоставить как часть системы управленияпамятью в рамках реализации Лиспа. Мы рассмотрим эти вопросы в разделе 5.3.1.3.3.
Моделирование при помощи изменяемых данных245(define (append! x y)(set-cdr! (last-pair x) y)x)Здесь last-pair — процедура, которая возвращает последнюю пару своего аргумента:(define (last-pair x)(if (null? (cdr x))x(last-pair (cdr x))))Рассмотрим последовательность действий(define x (list ’a ’b))(define y (list ’c ’d))(define z (appendx y))z(a b c d)(cdr x)hответi(define w (append! x y))w(a b c d)(cdr x)hответiКаковы будут пропущенные hответыi? Объясните, нарисовав стрелочные диаграммы.Упражнение 3.13.Рассмотрим следующую процедуру make-cycle, которая пользуется last-pair из упражнения 3.12:(define (make-cycle x)(set-cdr! (last-pair x) x)x)Нарисуйте стрелочную диаграмму, которая изображает структуру z, созданную таким кодом:(define z (make-cycle (list ’a ’b ’c)))Что случится, если мы попробуем вычислить (last-pair z)?Упражнение 3.14.Следующая процедура, хотя и сложна для понимания, вполне может оказаться полезной:(define (mystery x)(define (loop x y)Глава 3.
Модульность, объекты и состояние246z1xabРис. 3.16. Список z1, порождаемый выражением (cons x x).z1xabРис. 3.17. Список z2, порождаемый выражением (cons (list ’a ’b) (list ’a’b)).(if (null? x)y(let ((temp (cdr x)))(set-cdr! x y)(loop temp x))))(loop x ’()))Loop пользуется «временной» переменной temp, чтобы сохранить старое значение cdr пары x,поскольку set-cdr! на следующей строке его разрушает. Объясните, что за задачу выполняетmystery.
Предположим, что переменная v определена выражением (define v (list ’a ’b’c ’d). Нарисуйте диаграмму, которая изображает список, являющийся значением v. Допустим,что теперь мы выполняем (define w (mystery v)). Нарисуйте стрелочные диаграммы, которые показывают структуры v и w после вычисления этого выражения. Что будет напечатано вкачестве значений v и w?Разделение данных и их идентичностьВ разделе 3.1.3 мы упоминали теоретические вопросы «идентичности» и «изменения»,которые возникают с появлением присваивания. Эти вопросы начинают иметь практическое значение тогда, когда отдельные пары разделяются (are shared) между различнымиобъектами данных. Рассмотрим, например, структуру, которая создается таким кодом:(define x (list ’a ’b))(define z1 (cons x x))3.3.
Моделирование при помощи изменяемых данных247Как показано на рис. 3.16, z1 представляет собой пару, в которой car и cdr указываютна одну и ту же пару x. Разделение x между car и cdr пары z1 возникает оттого, чтоcons реализован простейшим способом. В общем случае построение списков с помощьюcons приводит к возникновению сложносвязанной сети пар, в которой многие парыразделяются между многими различными структурами.В противоположность рис.
3.16, рис. 3.17 показывает структуру, которая порождаетсякодом(define z2 (cons (list ’a ’b) (list ’a ’b)))В этой структуре пары двух списков (a b) различны, притом, что сами символы разделяются19 .Если мы рассматриваем z1 и z2 как списки, они представляют «один и тот же»список ((a b) a b). Вообще говоря, разделение данных невозможно заметить, еслимы работаем со списками только при помощи операций cons, car и cdr. Однако еслимы вводим мутаторы, работающие со списковой структурой, разделение данных начинаетиметь значение. Как пример случая, когда разделение влияет на результат, рассмотримследующую процедуру, которая изменяет car структуры, к которой она применяется:(define (set-to-wow! x)(set-car! (car x) ’wow)x)Несмотря на то, что z1 и z2 имеют «одинаковую» структуру, применение к ним процедуры set-to-wow! дает различные результаты.
В случае с z1 изменение car влияет ина cdr, поскольку здесь car и cdr — это одна и та же пара. В случае с z2, car и cdrразличны, так что set-to-wow! изменяет только car:z1((a b) a b)(set-to-wow! z1)((wow b) wow b)z2((a b) a b)(set-to-wow! z2)((wow b) a b)Один из способов распознать разделение данных в списковых структурах — это воспользоваться предикатом eq?, который мы ввели в разделе 2.3.1 как метод проверкидвух символов на равенство.
В более общем случае (eq? x y) проверяет, являютсяли x и y одним объектом (то есть, равны ли x и y друг другу как указатели). Так что,19 Пары различаются потому, что каждый вызов cons порождает новую пару. Символы разделяются; вScheme существует только один символ для каждого данного имени. Поскольку Scheme не дает возможностиизменять символ, это разделение невозможно заметить.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
