(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 в начало у. Процедура append! подобна append, но только она является не конструктором, а мутатором. Она склеивает списки вместе, изменяя последнюю пару x так, что ее cdr становится равным у. (Вызов append! с пустым x является ошибкой.)

(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 (append x у)) z

(a b c d)

(cdr x)

(ответ)

(define w (append! x y)) w

(a b c d)

(cdr x)

( ответ)

Каковы будут пропущенные (ответы)? Объясните, нарисовав стрелочные диаграммы. ления памятью в рамках реализации Лиспа. Мы рассмотрим эти вопросы в разделе 5.3.1.

zi-

471

Рис. 3.16: Список zi, порождаемый выражением (cons x x).

x

b

a

Упражнение 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) (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) между различными объектами данных. Рассмотрим, например, структуру, которая создается таким кодом:

43

b

Рис. 3.17: Список z2, порождаемый выражением (cons (list a b) (list a b)).

x

a

(define x (list a b)) (define zl (cons x x))

Как показано на рис. 3.16, zl представляет собой пару, в которой car и cdr указывают на одну и ту же пару x. Разделение x между car и cdr пары z1 возникает оттого, что cons реализован простейшим способом. В общем случае построение списков с помощью cons приводит к возникновению сложносвязан-ной сети пар, в которой многие пары разделяются между многими различными структурами.

В противоположность рис. 3.16, рис. 3.17 показывает структуру, которая порождается кодом

(define z2 (cons (list a b) (list a b)))

В этой структуре пары двух списков (a b) различны, притом, что сами символы разделяются.14

Если мы рассматриваем zl и z2 как списки, они представляют «один и тот же» список ((a b) a b). Вообще говоря, разделение данных невозможно заметить, если мы работаем со списками только при помощи операций cons, car и cdr. Однако если мы вводим мутаторы, работающие со списковой структурой, разделение данных начинает иметь значение. Как пример случая, когда разделение влияет на результат, рассмотрим следующую процедуру, которая изменяет car структуры, к которой она применяется:

(define (set-to-wow! x) (set-car! (car x) wow)

x)

Несмотря на то, что zl и z2 имеют «одинаковую» структуру, применение к ним процедуры set-to-wow! дает различные результаты. В случае с zl изменение car влияет и на cdr, поскольку здесь car и cdr - это одна и та же пара. В случае с z2, car и cdr различны, так что set-to-wow! изменяет только car:

19Пары различаются потому, что каждый вызов cons порождает новую пару. Символы разделяются; в Scheme существует только один символ для каждого данного имени. Поскольку Scheme не дает возможности изменять символ, это разделение невозможно заметить. Заметим, кроме того, что именно разделение позволяет нам сравнивать символы при помощи eq?, который просто проверяет равенство указателей.