ты, и выбор представления может существенно влиять на запросы манипулирующих этими данными процессов к памяти и ко времени. Мы исследуем эти идеи в контексте символьного дифференцирования, представления множеств и кодирования информации.

После этого мы обратимся к задаче работы с данными, которые по-разному могут быть представлены в различных частях программы. Это ведет к необходимости ввести обобщенные операции (generic operations), которые обрабатывают много различных типов данных. Поддержка модульности в присутствии обобщенных операций требует более мощных барьеров абстракции, чем тех, что получаются с помощью простой абстракции данных. А именно, мы вводим программирование, управляемое данными (data-directed programming) как метод, который позволяет проектировать представления данных отдельно, а затем сочетать их аддитивно (additively) (т. е., без модификации). Чтобы проиллюстрировать силу этого подхода к проектированию систем, в завершение главы мы применим то, чему в ней научились, к реализации пакета символьной арифметики многочленов, коэффициенты которых могут быть целыми, рациональными числами, комплексными числами и даже другими многочленами.

2.1 Введение в абстракцию данных

В разделе 1.1.8 мы заметили, что процедура, которую мы используем как элемент при создании более сложной процедуры, может рассматриваться не только как последовательность определенных операций, но и как процедурная абстракция: детали того, как процедура реализована, могут быть скрыты, и сама процедура может быть заменена на другую с подобным поведением. Другими словами, мы можем использовать абстракцию для отделения способа использования процедуры от того, как эта процедура реализована в терминах более простых процедур. Для составных данных подобное понятие называется абстракция данных (data abstraction). Абстракция данных - это методология, которая позволяет отделить способ использования составного объекта данных от деталей того, как он составлен из элементарных данных.

Основная идея абстракции данных состоит в том, чтобы строить программы, работающие с составными данными, так, чтобы иметь дело с «абстрактными данными». То есть, используя данные, наши программы не должны делать о них никаких предположений, кроме абсолютно необходимых для выполнения поставленной задачи. В то же время «конкретное» представление данных определяется независимо от программ, которые эти данные используют. Интерфейсом между двумя этими частями системы служит набор процедур, называемых селекторами (selectors) и конструкторами (constructors), реализующих абстрактные данные в терминах конкретного представления. Чтобы проиллюстрировать этот метод, мы рассмотрим, как построить набор процедур для работы с рациональными числами.

2.1.1 Пример: арифметические операции над рациональными числами

Допустим, нам нужно работать с рациональной арифметикой. Нам требуется складывать, вычитать, умножать и делить рациональные числа, а также проверять, равны ли два рациональных числа друг другу.

Для начала предположим, что у нас уже есть способ построить рациональное число из его числителя и знаменателя. Кроме того, мы предполагаем, что имея рациональное число, мы можем получить его числитель и знаменатель. Допустим также, что эти конструктор и два селектора доступны нам в виде процедур:

•(make-rat (n) (d)) возвращает рациональное число, числитель которого целое (n), а знаменатель - целое (d).

•(numer (x)) возвращает числитель рационального числа (x).

•(denom (x)) возвращает знаменатель рационального числа (x).

Здесь мы используем мощную стратегию синтеза: мечтать не вредно (wishful thinking). Пока что мы не сказали, как представляется рациональное число и как должны реализовываться процедуры numer, denom и make-rat. Тем не менее, если бы эти процедуры у нас были, мы могли бы складывать, вычитать, умножать, делить и проверять на равенство с помощью следующих отношений:

щ П2 n-jd.2 + n2d\ di d2d\d2

ni n2 nid2 - n2 di

di d2did2

ni n2 ni n2 di d2 did2

ni/di nid2 n2/d2 di n2

ni n2

- = - тогда и только тогда, когда n\d2 = n2d\ di d2

Мы можем выразить эти правила в процедурах:

(define (add-rat x y)

(make-rat (+ (* (numer x) (denom y)) (* (numer y) (denom x))) (* (denom x) (denom y))))

(define (sub-rat x y)

(make-rat (- (* (numer x) (denom y)) (* (numer y) (denom x))) (* (denom x) (denom y))))

(define (mul-rat x y)

(make-rat (* (numer x) (numer y))

(* (denom x) (denom y))))

(define (div-rat x y)

(make-rat (* (numer x) (denom y))

(* (denom x) (numer y))))

(define (equal-rat? x y) (= (* (numer x) (denom y)) (* (numer y) (denom x))))

Теперь у нас есть операции над рациональными числами, определенные в терминах процедур - селекторов и конструкторов numer, denom и make-rat. Однако сами эти процедуры мы еще не написали. Нам нужен какой-нибудь способ склеить вместе числитель и знаменатель, чтобы получить рациональное число.

Пары

Для реализации конкретного уровня абстракции данных в нашем языке имеется составная структура, называемая парой (pair), и она создается с помощью элементарной процедуры cons. Эта процедура принимает два аргумента и возвращает объект данных, который содержит эти два аргумента в качестве частей. Имея пару, мы можем получить ее части с помощью элементарных процедур car и cdr.2 Таким образом, использовать cons, car и cdr можно так:

(define x (cons 1 2))

(car x) 1

(cdr x) 2

Заметим, что пара является объектом, которому можно дать имя и работать с ним, подобно элементарному объекту данных. Более того, можно использовать cons для создания пар, элементы которых сами пары, и так далее:

1

(car (cdr z)) 3

В разделе 2.2 мы увидим, что из этой возможности сочетать пары следует возможность их использовать как строительные блоки общего назначения при создании любых сложных структур данных. Один-единственный примитив составных данных пара, реализуемый процедурами cons, car и cdr, - вот и весь клей, который нам нужен. Объекты данных, составленные из пар, называются данные со списковой структурой (list-structured data).

2Cons означает construct (построить, сконструировать, собрать). Имена car и cdr происходят из исходной реализации Лиспа на IBM 704. Схема адресации этой машины позволяла обращаться к «адресной» и «декрементной» частям ячейки памяти. Car означает Contents of Address Part of Register (содержимое адресной части регистра), а cdr (произносится «куддер») означает Contents of Decrement Part of Register (содержимое декрементной части регистра).