zl

((a b) a b)

(set-to-wow! zl) ((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 друг другу как указатели). Так что, если zi и z2 определены как на рисунках 3.16 и 3.17, (eq? (car zi) (cdr zi)) будет истинно, а (eq? (car z2) (cdr z2)) ложно.

Как будет видно в последующих разделах, с помощью разделения данных мы значительно расширим репертуар структур данных, которые могут быть представлены через пары. С другой стороны, разделение сопряжено с риском, поскольку изменения в одних структурах могут затрагивать и другие структуры, разделяющие те части, которые подвергаются изменению. Операции изменения set-car! и set-cdr! нужно использовать осторожно; если у нас нет точного понимания, какие из наших объектов разделяют данные, изменение

20

может привести к неожиданным результатам.20 Упражнение 3.15.

Нарисуйте стрелочные диаграммы, объясняющие, как set-to-wow! действует на структуры zl и z2 из этого раздела.

Упражнение 3.16.

Бен Битобор решил написать процедуру для подсчета числа пар в любой списковой структуре. «Это легко, - думает он. - Число пар в любой структуре есть число пар в car плюс число пар в cdr плюс один на текущую пару». И он пишет следующую процедуру:

(define (count-pairs x)

(if (not (pair? x))

0

(+ (count-pairs (car x)) (count-pairs (cdr x))

l)))

20Тонкости работы с разделением изменяемых данных отражают сложности с понятием «идентичности» и «изменения», о которых мы говорили в разделе 3.1.3. Там мы отметили, что введение в наш язык понятия изменения требует, чтобы у составного объекта была «индивидуальность», которая представляет собой нечто отличное от частей, из которых он состоит. В Лиспе мы считаем, что именно эта «индивидуальность» проверяется предикатом eq?, то есть сравнением указателей. Поскольку в большинстве реализаций Лиспа указатель - это, в сущности, адрес в памяти, мы «решаем проблему» определения индивидуальности объектов, постановив, что «сам» объект данных есть информация, хранимая в некотором наборе ячеек памяти компьютера. Для простых лисповских программ этого достаточно, но такой метод не способен разрешить общий вопрос «идентичности» в вычислительных моделях.

Покажите, что эта процедура ошибочна. В частности, нарисуйте диаграммы, представляющие списковые структуры ровно из трех пар, для которых Бенова процедура вернет 3; вернет 4; вернет 7; вообще никогда не завершится.

Упражнение 3.17.

Напишите правильную версию процедуры count-pairs из упражнения 3.16, которая возвращает число различных пар в любой структуре. (Подсказка: просматривайте структуру, поддерживая при этом вспомогательную структуру, следящую за тем, какие пары уже были посчитаны.)

Упражнение 3.18.

Напишите процедуру, которая рассматривает список и определяет, содержится ли в нем цикл, то есть, не войдет ли программа, которая попытается добраться до конца списка, продвигаясь по полям cdr, в бесконечный цикл. Такие списки порождались в упражнении 3.13.

Упражнение 3.19.

Переделайте упражнение 3.18, используя фиксированное количество памяти. (Тут нужна достаточно хитрая идея.)

Изменение как присваивание

Когда мы вводили понятие составных данных, в разделе 2.1.3 мы заметили, что пары можно представить при помощи одних только процедур:

(define (cons x y) (define (dispatch m) (cond ((eq? m car) x) ((eq? m cdr) y)

(else (error "Неопределенная операция -- CONS" m)))) dispatch)

(define (car z) (z car))

(define (cdr z) (z cdr))

То же наблюдение верно и для изменяемых данных. Изменяемые объекты данных можно реализовать при помощи процедур и внутреннего состояния. Например, можно расширить приведенную реализацию пар, так, чтобы set-car! и set-cdr! обрабатывались аналогично тому, по аналогии с реализацией банковских счетов через make-account в разделе раздела 3.1.1:

(define (cons x y)

(define (set-x! v) (set! x v)) (define (set-y! v) (set! у v)) (define (dispatch m) (cond ((eq? m car) x) ((eq? m cdr) y) ((eq? m set-car!) set-x!) ((eq? m set-cdr!) set-y!)

(else (error "Неопределенная операция -- CONS" m)))) dispatch)

(define (car z) (z car))

(define (cdr z) (z cdr))

(define (set-car! z new-value) ((z set-car!) new-value)

z)

(define (set-cdr! z new-value) ((z set-cdr!) new-value)

z)

Теоретически, чтобы описать поведение изменяемых данных, не требуется ничего, кроме присваивания. Как только мы вводим в наш язык set! , мы сталкиваемся со всеми проблемами, не только собственно присваивания, но и вообще изменяемых данных.21

Упражнение 3.20.

Нарисуйте диаграммы окружений, изображающие выполнение последовательности выражений

(define x (cons l 2)) (define z (cons x x)) (set-car! (cdr z) 17)

(car x) 17

с помощью вышеприведенной процедурной реализации пар. (Ср. с упражнением 3.11.)

3.3.2 Представление очередей

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

Очередь (queue) представляет собой последовательность, в которую можно добавлять элементы с одного конца (он называется хвостом (rear)) и убирать с другого (он называется головой (front)). На рисунке 3.18 изображено, как в изначально пустую очередь добавляются элементы a и b. Затем a убирается из очереди, в нее добавляются c и d, потом удаляется b. Поскольку элементы удаляются всегда в том же порядке, в котором они были добавлены, иногда очередь называют буфером FIFO (англ. first in, first out - первым вошел, первым вышел).

С точки зрения абстракции данных, можно считать, что очередь определяется следующим набором операций:

21С другой стороны, с точки зрения реализации, присваивание требует модификации окружения, которое само по себе является изменяемой структурой данных. Таким образом, присваивание и изменяемость данных обладают равной мощностью: каждое из них можно реализовать при помощи другого.