Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 23
Текст из файла (страница 23)
В общем случае основная идея абстракции данных состоит в том, чтобы определить для каждого типа объектов данных набор базовыхопераций, через которые будут выражаться все действия с объектами этого типа, и затемпри работе с данными использовать только этот набор операций.Мы можем представить себе структуру системы работы с рациональными числамитак, как это показано на рис. 2.1. Горизонтальные линии обозначают барьеры абстракции (abstraction barriers), которые отделяют различные «уровни» системы друг от друга.Глава 2. Построение абстракций с помощью данных98Программы, использующие рациональные числаРациональные числа в предметной областиadd-rat sub-rat ...Рациональные числа как числители со знаменателямиmake-rat numer denomРациональные числа как парыcons car cdrТо, как реализуются парыРис. 2.1.
Барьеры абстракции данных в пакете для работы с рациональными числами.На каждом из этих уровней барьер отделяет программы, которые используют абстрактные данные (сверху) от программ, которые реализуют эту абстракцию данных (внизу).Программы, использующие рациональные числа, работают с ними исключительно в терминах процедур, которые пакет работы с рациональными числами предоставляет «дляобщего пользования»: add-rat, sub-rat, mul-rat, div-rat и equal-rat?. В своюочередь, эти процедуры используют только конструктор и селекторы make-rat, numerи denom, которые сами реализованы при помощи пар.
Детали реализации пар не имеютзначения для остальной части пакета работы с рациональными числами; существеннотолько, что с парами можно работать при помощи cons, car и cdr. По существу,процедуры на каждом уровне являются интерфейсами, которые определяют барьеры абстракции и связывают различные уровни.У этой простой идеи много преимуществ. Одно из них состоит в том, что программыстановится намного проще поддерживать и изменять. Любая сложная структура можетбыть представлена через элементарные структуры данных языка программирования многими способами.
Разумеется, выбор представления влияет на программы, работающиес этим представлением; так что, если когда-нибудь позднее его нужно будет изменить,соответственно придется изменить и все эти программы. В случае больших программэта задача может быть весьма трудоемкой и дорогой, если зависимость от представленияне будет при проектировании ограничена несколькими программными модулями.Например, другим способом решения задачи приведения рациональных чисел к наименьшему знаменателю было бы производить сокращение не тогда, когда мы конструируем число, а каждый раз, как мы к нему обращаемся. При этом потребуются другиеконструктор и селекторы:(define (make-rat n d)(cons n d))(define (numer x)(let ((g (gcd (car x) (cdr x))))2.1.
Введение в абстракцию данных99(/ (car x) g)))(define (denom x)(let ((g (gcd (car x) (cdr x))))(/ (cdr x) g)))Разница между этой реализацией и предыдущей состоит в том, когда мы вычисляемНОД с помощью gcd. Если при типичном использовании рациональных чисел к числителю и знаменателю одного и того же рационального числа мы обращаемся по многураз, вычислять НОД лучше тогда, когда рациональное число конструируется. Если нет,нам может быть выгодно подождать с его вычислением до времени обращения. В любомслучае, когда мы переходим от одной реализации к другой, нам ничего не нужно менятьв процедурах add-rat, sub-rat и прочих.То, что мы ограничиваем зависимость от представления несколькими интерфейснымипроцедурами, помогает нам и проектировать программы, и изменять их, поскольку такимобразом мы сохраняем гибкость и получаем возможность рассматривать другие реализации. Продолжая наш простой пример, представим себе, что мы строим пакет работыс рациональными числами и не можем сразу решить, вычислять ли НОД при построении числа или при обращении к нему.
Методология абстракции данных позволяет намотложить это решение, не теряя возможности продолжать разработку остальных частейсистемы.Упражнение 2.2.Рассмотрим задачу представления отрезков прямой на плоскости. Каждый отрезок представляетсякак пара точек: начало и конец. Определите конструктор make-segment и селекторы startsegment и end-segment, которые определяют представление отрезков в терминах точек.
Далее,точку можно представить как пару чисел: координата x и координата y. Соответственно, напишите конструктор make-point и селекторы x-point и y-point, которые определяют такое представление. Наконец, используя свои селекторы и конструктор, напишите процедуру midpointsegment, которая принимает отрезок в качестве аргумента и возвращает его середину (точку,координаты которой являются средним координат концов отрезка).
Чтобы опробовать эти процедуры, Вам потребуется способ печатать координаты точек:(define (print-point p)(newline)(display "(")(display (x-point p))(display ",")(display (y-point p))(display ")"))Упражнение 2.3.Реализуйте представление прямоугольников на плоскости. (Подсказка: Вам могут потребоватьсярезультаты упражнения 2.2.) Определите в терминах своих конструкторов и селекторов процедуры,которые вычисляют периметр и площадь прямоугольника. Теперь реализуйте другое представлениедля прямоугольников.
Можете ли Вы спроектировать свою систему с подходящими барьерамиабстракции так, чтобы одни и те же процедуры вычисления периметра и площади работали слюбым из Ваших представлений?100Глава 2. Построение абстракций с помощью данных2.1.3. Что значит слово «данные»?Свою реализацию рациональных чисел в разделе 2.1.1 мы начали с определения операций над рациональными числами add-rat, sub-rat и так далее в терминах трехнеопределенных процедур: make-rat, numer и denom. В этот момент мы могли думать об операциях как определяемых через объекты данных — числители, знаменатели и рациональные числа, — поведение которых определялось тремя последними процедурами.Но что в точности означает слово данные (data)? Здесь недостаточно просто сказать«то, что реализуется некоторым набором селекторов и конструкторов».
Ясно, что нелюбой набор из трех процедур может служить основой для реализации рациональныхчисел. Нам нужно быть уверенными в том, что если мы конструируем рациональноечисло x из пары целых n и d, то получение numer и denom от x и деление их друг надруга должно давать тот же результат, что и деление n на d. Другими словами, makerat, numer и denom должны удовлетворять следующему условию: для каждого целогочисла n и не равного нулю целого d, если x есть (make-rat n d), тоn(numer x)=(denom x)dЭто на самом деле единственное условие, которому должны удовлетворять make-rat,numer и denom, чтобы служить основой для представления рациональных чисел. Вобщем случае можно считать, что данные — это то, что определяется некоторым наборомселекторов и конструкторов, а также некоторыми условиями, которым эти процедурыдолжны удовлетворять, чтобы быть правильным представлением5.Эта точка зрения может послужить для определения не только «высокоуровневых»объектов данных, таких как рациональные числа, но и объектов низкого уровня.
Рассмотрим понятие пары, с помощью которого мы определили наши рациональные числа.Мы ведь ни разу не сказали, что такое пара, и указывали только, что для работы спарами язык дает нам процедуры cons, car и cdr. Но единственное, что нам надознать об этих процедурах — это что если мы склеиваем два объекта при помощи cons,то с помощью car и cdr мы можем получить их обратно. То есть эти операции удовлетворяют условию, что для любых объектов x и y, если z есть (cons x y), то (carz) есть x, а (cdr z) есть y.
Действительно, мы упомянули, что три эти процедурывключены в наш язык как примитивы. Однако любая тройка процедур, которая удовлетворяет вышеуказанному условию, может использоваться как основа реализации пар.5 Как ни странно, эту мысль очень трудно строго сформулировать. Существует два подхода к такой формулировке.
Один, начало которому положил Ч. А. Р. Хоар (Hoare 1972), известен как метод абстрактныхмоделей (abstract models). Он формализует спецификацию вида «процедуры плюс условия» вроде описаннойвыше в примере с рациональными числами. Заметим, что условие на представление рациональных чисел былосформулировано в терминах утверждений о целых числах (равенство и деление). В общем случае абстрактныемодели определяют новые типы объектов данных в терминах типов данных, определенных ранее.
Следовательно, утверждения об объектах данных могут быть проверены путем сведения их к утверждениям об объектахданных, которые были определены ранее. Другой подход, который был введен Зиллесом из MIT, Гогеном, Тэтчером, Вагнером и Райтом из IBM (см. Thatcher, Wagner, and Wright 1978) и Гаттэгом из университета Торонто(см. Guttag 1977), называется алгебраическая спецификация (algebraic specification). Этот подход рассматривает «процедуры» как элементы абстрактной алгебраической системы, чье поведение определяется аксиомами,соответствующими нашим «условиям», и использует методы абстрактной алгебры для проверки утвержденийоб объектах данных. Оба этих метода описаны в статье Лисков и Зиллеса (Liskov and Zilles 1975).2.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
