Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 22
Текст из файла (страница 22)
Введение в абстракцию данныхВ разделе 1.1.8 мы заметили, что процедура, которую мы используем как элементпри создании более сложной процедуры, может рассматриваться не только как последовательность определенных операций, но и как процедурная абстракция: детали того, какпроцедура реализована, могут быть скрыты, и сама процедура может быть заменена надругую с подобным поведением. Другими словами, мы можем использовать абстракциюдля отделения способа использования процедуры от того, как эта процедура реализована в терминах более простых процедур.
Для составных данных подобное понятиеназывается абстракция данных (data abstraction). Абстракция данных — это методология, которая позволяет отделить способ использования составного объекта данных отдеталей того, как он составлен из элементарных данных.Основная идея абстракции данных состоит в том, чтобы строить программы, работающие с составными данными, так, чтобы иметь дело с «абстрактными данными». Тоесть, используя данные, наши программы не должны делать о них никаких предположений, кроме абсолютно необходимых для выполнения поставленной задачи.
В то жевремя «конкретное» представление данных определяется независимо от программ, которые эти данные используют. Интерфейсом между двумя этими частями системы служитнабор процедур, называемых селекторами (selectors) и конструкторами (constructors),реализующих абстрактные данные в терминах конкретного представления. Чтобы проиллюстрировать этот метод, мы рассмотрим, как построить набор процедур для работыс рациональными числами.2.1.1. Пример: арифметические операции над рациональными числамиДопустим, нам нужно работать с рациональной арифметикой.
Нам требуется складывать, вычитать, умножать и делить рациональные числа, а также проверять, равны лидва рациональных числа друг другу.Для начала предположим, что у нас уже есть способ построить рациональное число94Глава 2. Построение абстракций с помощью данныхиз его числителя и знаменателя. Кроме того, мы предполагаем, что имея рациональноечисло, мы можем получить его числитель и знаменатель.
Допустим также, что этиконструктор и два селектора доступны нам в виде процедур:• (make-rat hni hdi) возвращает рациональное число, числитель которого целоеhni, а знаменатель — целое hdi.• (numer hxi) возвращает числитель рационального числа hxi.• (denom hxi) возвращает знаменатель рационального числа hxi.Здесь мы используем мощную стратегию синтеза: мечтать не вредно (wishful thinking).
Пока что мы не сказали, как представляется рациональное число и как должныреализовываться процедуры numer, denom и make-rat. Тем не менее, если бы этипроцедуры у нас были, мы могли бы складывать, вычитать, умножать, делить и проверятьна равенство с помощью следующих отношений:n2n1 d2 + n2 d1n1+=d1d2d1 d2n1n2n1 d2 − n2 d1−=d1d2d1 d2n1 n2n1 n2·=d1 d2d1 d2n1 d2n1 /d1=n2 /d2d1 n2n1n2=тогда и только тогда, когда n1 d2 = n2 d1d1d2Мы можем выразить эти правила в процедурах:(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))))2.1.
Введение в абстракцию данных95(define (equal-rat? x y)(= (* (numer x) (denom y))(* (numer y) (denom x))))Теперь у нас есть операции над рациональными числами, определенные в терминах процедур — селекторов и конструкторов numer, denom и make-rat. Однако самиэти процедуры мы еще не написали. Нам нужен какой-нибудь способ склеить вместечислитель и знаменатель, чтобы получить рациональное число.ПарыДля реализации конкретного уровня абстракции данных в нашем языке имеетсясоставная структура, называемая парой (pair), и она создается с помощью элементарнойпроцедуры cons.
Эта процедура принимает два аргумента и возвращает объект данных,который содержит эти два аргумента в качестве частей. Имея пару, мы можем получитьее части с помощью элементарных процедур car и cdr2 . Таким образом, использоватьcons, car и cdr можно так:(define x (cons 1 2))(car x)1(cdr x)2Заметим, что пара является объектом, которому можно дать имя и работать с ним,подобно элементарному объекту данных. Более того, можно использовать cons длясоздания пар, элементы которых сами пары, и так далее:(define x (cons 1 2))(define y (cons 3 4))(define z (cons x y))(car (car z))1(car (cdr z))3В разделе 2.2 мы увидим, что из этой возможности сочетать пары следует возможность их использовать как строительные блоки общего назначения при создании любых2 Cons означает construct (построить, сконструировать, собрать).
Имена car и cdr происходят из исходнойреализации Лиспа на IBM 704. Схема адресации этой машины позволяла обращаться к «адресной» и «декрементной» частям ячейки памяти. Car означает Contents of Address Part of Register (содержимое адреснойчасти регистра), а cdr (произносится «куддер») означает Contents of Decrement Part of Register (содержимоедекрементной части регистра).Глава 2.
Построение абстракций с помощью данных96сложных структур данных. Один-единственный примитив составных данных пара, реализуемый процедурами cons, car и cdr, — вот и весь клей, который нам нужен.Объекты данных, составленные из пар, называются данные со списковой структурой(list-structured data).Представление рациональных чиселПары позволяют нам естественным образом завершить построение системы рациональных чисел. Будем просто представлять рациональное число в виде пары двух целыхчисел: числителя и знаменателя.
Тогда make-rat, numer и denom немедленно реализуются следующим образом3 .(define (make-rat n d) (cons n d))(define (numer x) (car x))(define (denom x) (cdr x))Кроме того, когда нам требуется выводить результаты вычислений, мы печатаем рациональное число, сначала выводя его числитель, затем косую черту и затем знаменатель4:(define (print-rat x)(newline)(display (numer x))(display "/")(display (denom x)))Теперь мы можем опробовать процедуры работы с рациональными числами:(define one-half (make-rat 1 2))(print-rat one-half)1/23 Другойспособ определить селекторы и конструктор был бы(define make-rat cons)(define numer car)(define denom cdr)Первое определение связывает имя make-rat со значением выражения cons, то есть элементарной процедурой, которая строит пары.
Таким образом, make-rat и cons становятся именами для одного и того жеэлементарного конструктора.Такое определение конструкторов и селекторов эффективно: вместо того, чтобы заставлять make-rat вызывать cons, мы делаем make-rat и cons одной и той же процедурой, так что когда вызывается make-rat,происходит вызов только одной процедуры, а не двух. С другой стороны, это не дает работать отладочнымсредствам, которые отслеживают вызовы процедур или устанавливают на них контрольные точки: Вам можетпотребоваться следить за вызовами make-rat, но Вы уж точно никогда не захотите отслеживать каждыйвызов cons.В этой книге мы решили не использовать такой стиль определений.4 Display — элементарная процедура языка Scheme для печати данных.
Другая элементарная процедура,newline, переводит строку при печати. Эти процедуры не возвращают никакого полезного значения, так чтов примерах использования print-rat ниже, мы показываем только то, что печатает print-rat, а не то, чтоинтерпретатор выводит как значение print-rat.2.1. Введение в абстракцию данных97(define one-third (make-rat 1 3))(print-rat (add-rat one-half one-third))5/6(print-rat (mul-rat one-half one-third))1/6(print-rat (add-rat one-third one-third))6/9Как показывает последний пример, наша реализация рациональных чисел не приводит их к наименьшему знаменателю.
Мы можем исправить это упущение, изменивmake-rat. Если у нас есть процедура gcd, вычисляющая наибольший общий делительдвух целых чисел, вроде той, которая описана в разделе 1.2.5, мы можем с помощьюgcd сокращать числитель и знаменатель, прежде, чем построить пару:(define (make-rat n d)(let ((g (gcd n d)))(cons (/ n g) (/ d g))))Теперь мы имеем(print-rat (add-rat one-third one-third))2/3как нам того и хотелось.
Эта модификация была произведена путем изменения конструктора make-rat, и мы не тронули ни одну из процедур (скажем, add-rat илиmul-rat), которые реализуют сами операции.Упражнение 2.1.Определите улучшенную версию mul-rat, которая принимала бы как положительные, так иотрицательные аргументы. Make-rat должна нормализовывать знак так, чтобы в случае, еслирациональное число положительно, то и его числитель, и знаменатель были бы положительны, аесли оно отрицательно, то чтобы только его числитель был отрицателен.2.1.2. Барьеры абстракцииПрежде чем мы перейдем к другим примерам работы с составными данными и абстракцией данных, рассмотрим несколько вопросов, относящихся к примеру с рациональными числами. Мы определили операции над рациональными числами через конструкторmake-rat и селекторы numer и denom.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
