Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 58
Текст из файла (страница 58)
Заметим, кроме того, что именно разделение позволяетнам сравнивать символы при помощи eq?, который просто проверяет равенство указателей.248Глава 3. Модульность, объекты и состояниеесли z1 и z2 определены как на рисунках 3.16 и 3.17, (eq? (car z1) (cdr z1))будет истинно, а (eq? (car z2) (cdr z2)) ложно.Как будет видно в последующих разделах, с помощью разделения данных мы значительно расширим репертуар структур данных, которые могут быть представлены черезпары.
С другой стороны, разделение сопряжено с риском, поскольку изменения в одних структурах могут затрагивать и другие структуры, разделяющие те части, которыеподвергаются изменению. Операции изменения set-car! и set-cdr! нужно использовать осторожно; если у нас нет точного понимания, какие из наших объектов разделяютданные, изменение может привести к неожиданным результатам20 .Упражнение 3.15.Нарисуйте стрелочные диаграммы, объясняющие, как set-to-wow! действует на структуры z1и z2 из этого раздела.Упражнение 3.16.Бен Битобор решил написать процедуру для подсчета числа пар в любой списковой структуре.«Это легко, — думает он. — Число пар в любой структуре есть число пар в car плюс число пар вcdr плюс один на текущую пару».
И он пишет следующую процедуру:(define (count-pairs x)(if (not (pair? x))0(+ (count-pairs (car x))(count-pairs (cdr x))1)))Покажите, что эта процедура ошибочна. В частности, нарисуйте диаграммы, представляющиесписковые структуры ровно из трех пар, для которых Бенова процедура вернет 3; вернет 4; вернет7; вообще никогда не завершится.Упражнение 3.17.Напишите правильную версию процедуры count-pairs из упражнения 3.16, которая возвращаетчисло различных пар в любой структуре.
(Подсказка: просматривайте структуру, поддерживая приэтом вспомогательную структуру, следящую за тем, какие пары уже были посчитаны.)Упражнение 3.18.Напишите процедуру, которая рассматривает список и определяет, содержится ли в нем цикл, тоесть, не войдет ли программа, которая попытается добраться до конца списка, продвигаясь пополям cdr, в бесконечный цикл. Такие списки порождались в упражнении 3.13.20 Тонкости работы с разделением изменяемых данных отражают сложности с понятием «идентичности» и«изменения», о которых мы говорили в разделе 3.1.3.
Там мы отметили, что введение в наш язык понятия изменения требует, чтобы у составного объекта была «индивидуальность», которая представляет собойнечто отличное от частей, из которых он состоит. В Лиспе мы считаем, что именно эта «индивидуальность»проверяется предикатом eq?, то есть сравнением указателей. Поскольку в большинстве реализаций Лиспауказатель — это, в сущности, адрес в памяти, мы «решаем проблему» определения индивидуальности объектов, постановив, что «сам» объект данных есть информация, хранимая в некотором наборе ячеек памятикомпьютера. Для простых лисповских программ этого достаточно, но такой метод не способен разрешитьобщий вопрос «идентичности» в вычислительных моделях.3.3. Моделирование при помощи изменяемых данных249Упражнение 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! y 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)Глава 3. Модульность, объекты и состояние250Операция(define q (make-queue)(insert-queue! q ’a)(insert-queue! q ’b)(delete-queue! q)(insert-queue! q ’c)(insert-queue! q ’d)(delete-queue! q)Результатaabbbcbcc ddРис.
3.18. Операции над очередью.Теоретически, чтобы описать поведение изменяемых данных, не требуется ничего,кроме присваивания. Как только мы вводим в наш язык set!, мы сталкиваемся со всемипроблемами, не только собственно присваивания, но и вообще изменяемых данных21 .Упражнение 3.20.Нарисуйте диаграммы окружений, изображающие выполнение последовательности выражений(define x (cons 1 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 С другой стороны, с точки зрения реализации, присваивание требует модификации окружения, котороесамо по себе является изменяемой структурой данных. Таким образом, присваивание и изменяемость данныхобладают равной мощностью: каждое из них можно реализовать при помощи другого.3.3.
Моделирование при помощи изменяемых данных251• конструктор (make-queue) возвращает пустую очередь (очередь, в которой нетни одного элемента).• два селектора: (empty-queue? hочередьi) проверяет, пуста ли очередь,(front-queue hочередьi) возвращает объект, находящийся в голове очереди. Еслиочередь пуста, он сообщает об ошибке. Очередь не модифицируется.• Два мутатора: (insert-queue! hочередьi hэлементi) вставляет элемент вхвост очереди и возвращает в качестве значения измененную очередь; (delete-queue!hочередьi) удаляет элемент в голове очереди и возвращает в качестве значения измененную очередь. Если перед уничтожением элемента очередь оказывается пустой, выводится сообщение об ошибке.Поскольку очередь есть последовательность элементов, ее, разумеется, можно былобы представить как обыкновенный список; головой очереди был бы car этого списка, вставка элемента в очередь сводилась бы к добавлению нового элемента в конецсписка, а уничтожение элемента из очереди состояло бы просто во взятии cdr списка.Однако такая реализация неэффективна, поскольку для вставки элемента нам пришлосьбы просматривать весь список до конца.
Поскольку единственный доступный нам метод просмотра списка — это последовательное применение cdr, такой просмотр требуетΘ(n) шагов для очереди с n членами. Простое видоизменение спискового представленияпреодолевает этот недостаток, позволяя нам реализовать операции с очередью так, чтобы все они требовали Θ(1) шагов; то есть, чтобы число шагов алгоритма не зависело отдлины очереди.Сложность со списковым представлением возникает из-за необходимости искать конец списка. Искать приходится потому, что, хотя стандартный способ представлениясписка в виде цепочки пар дает нам указатель на начало списка, легкодоступного указателя на конец он не дает.
Модификация, обходящая этот недостаток, состоит в том,чтобы представлять очередь в виде списка, и держать еще дополнительный указательна его последнюю пару. В таком случае, когда требуется вставить элемент, мы можемпросто посмотреть на этот указатель и избежать за счет этого просмотра всего списка.Очередь, таким образом, представляется в виде пары указателей, frontptr и rearptr, которые обозначают, соответственно, первую и последнюю пару обыкновенногосписка. Поскольку нам хочется, чтобы очередь была объектом с собственной индивидуальностью, соединить эти два указателя можно с помощью cons, так что собственно очередь будет результатом cons двух указателей.
Такое представление показано нарис. 3.19.Во время определения операций над очередью мы пользуемся следующими процедурами, которые позволяют нам читать и записывать указатели на начало и конец очереди:(define (front-ptr queue) (car queue))(define (rear-ptr queue) (cdr queue))(define (set-front-ptr! queue item) (set-car! queue item))(define (set-rear-ptr! queue item) (set-cdr! queue item))Теперь можно реализовать сами операции над очередью. Очередь будет считатьсяГлава 3. Модульность, объекты и состояние252qfront-ptrarear-ptrbcРис.
3.19. Реализация очереди в виде списка с указателями на начало и конец.пустой, если ее головной указатель указывает на пустой список:(define (empty-queue? queue) (null? (front-ptr queue)))Конструктор make-queue возвращает в качестве исходно пустой очереди пару, в которой и car, и cdr являются пустыми списками:(define (make-queue) (cons ’() ’()))При обращении к элементу в голове очереди мы возвращаем car пары, на которуюуказывает головной указатель:(define (front-queue queue)(if (empty-queue? queue)(error "FRONT вызвана с пустой очередью" queue)(car (front-ptr queue))))Чтобы вставить элемент в конец очереди, мы используем метод, результат которого показан на рисунке 3.20. Первым делом мы создаем новую пару, car которой содержитвставляемый элемент, а cdr — пустой список.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
