Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 41
Текст из файла (страница 41)
Для неедоступ к модулю и аргументу тривиален, но для получения действительной и мнимой44 Функция взятия арктангенса, которая здесь используется, вычисляется процедурой Scheme atan. Онаберет два аргумента y и x и возвращает угол, тангенс которого равен y/x. Знаки аргументов определяют, вкаком квадранте находится угол.2.4. Множественные представления для абстрактных данных175части ей приходится использовать тригонометрические тождества.
Вот представлениеЛизы:(define (real-part z)(* (magnitude z) (cos (angle z))))(define (imag-part z)(* (magnitude z) (sin (angle z))))(define (magnitude z) (car z))(define (angle z) (cdr z))(define (make-from-real-imag x y)(cons (sqrt (+ (square x) (square y)))(atan y x)))(define (make-from-mag-ang r a) (cons r a))Дисциплина абстракции данных обеспечивает то, что одни и те же реализации процедур add-complex, sub-complex, mul-complex и div-complex будут работатькак с Беновым представлением, так и с Лизиным.2.4.2. Помеченные данныеМожно рассматривать абстракцию данных как применение принципа «наименьшихобязательств».
Реализуя систему обработки комплексных чисел в разделе 2.4.1, мы можем использовать либо декартово представление от Бена, либо полярное от Лизы. Барьерабстракции, который образуют селекторы и конструкторы, позволяет нам до последнего момента отложить выбор конкретного представления для наших объектов данных, итаким образом сохранить максимальную гибкость в проекте нашей системы.Принцип наименьших обязательств можно довести до еще бо́льших крайностей. Еслинам понадобится, мы можем сохранить неопределенность представления даже после того,как мы спроектировали селекторы и конструкторы, и использовать и представление Бена,и представление Лизы.
Однако если оба представления участвуют в одной и той жесистеме, нам потребуется какой-нибудь способ отличить данные в полярной форме отданных в декартовой форме. Иначе, если нас попросят, например, вычислить magnitudeот пары (3, 4), мы не будем знать, надо ли ответить 5 (интерпретируя число в декартовойформе) или 3 (интерпретируя его в полярной форме). Естественный способ добитьсянеобходимого различия состоит в том, чтобы использовать метку типа (type tag) —символ rectangular или polar — как часть каждого комплексного числа. Тогда,когда нам понадобится что-то делать с комплексным числом, мы можем при помощиэтой метки решить, который селектор требуется применить.Чтобы работать с помеченными данными, мы предположим, что у нас есть процедуры type-tag и contents, которые извлекают из элемента данных метку и собственно содержимое (полярные либо декартовы координаты, если речь идет о комплексномчисле). Кроме того, мы постулируем процедуру attach-tag, которая берет метку и176Глава 2.
Построение абстракций с помощью данныхсодержимое, и выдает помеченный объект данных. Простейший способ реализовать этипроцедуры — использовать обыкновенную списковую структуру:(define (attach-tag type-tag contents)(cons type-tag contents))(define (type-tag datum)(if (pair? datum)(car datum)(error "Некорректные помеченные данные -- TYPE-TAG" datum)))(define (contents datum)(if (pair? datum)(cdr datum)(error "Некорректные помеченные данные -- CONTENTS" datum)))При помощи этих процедур мы можем определить предикаты rectangular? иpolar?, которые распознают, соответственно, декартово и полярное представление:(define (rectangular? z)(eq? (type-tag z) ’rectangular))(define (polar? z)(eq? (type-tag z) ’polar))Теперь, когда у нас имеются метки типов, Бен и Лиза могут переделать свой кодтак, чтобы позволить своим разнородным представлениям сосуществовать в одной итой же системе.
Каждый раз, когда Бен создает комплексное число, он помечает егокак декартово. Каждый раз, когда Лиза создает комплексное число, она помечает егокак полярное. В дополнение к этому, Бен и Лиза должны сделать так, чтобы не былоконфликта имен между названиями их процедур. Один из способов добиться этого —Бену добавить слово rectangular к названиям всех своих процедур представленияданных, а Лизе добавить polar к своим. Вот переработанное декартово представлениеБена из раздела 2.4.1:(define (real-part-rectangular z) (car z))(define (imag-part-rectangular z) (cdr z))(define (magnitude-rectangular z)(sqrt (+ (square (real-part-rectangular z))(square (imag-part-rectangular z)))))(define (angle-rectangular z)(atan (imag-part-rectangular z)(real-part-rectangular z)))(define (make-from-real-imag-rectangular x y)(attach-tag ’rectangular (cons x y)))2.4.
Множественные представления для абстрактных данных177(define (make-from-mag-ang-rectangular r a)(attach-tag ’rectangular(cons (* r (cos a)) (* r (sin a)))))а вот переработанное полярное представление Лизы:(define (real-part-polar z)(* (magnitude-polar z) (cos (angle-polar z))))(define (imag-part-polar z)(* (magnitude-polar z) (sin (angle-polar z))))(define (magnitude-polar z) (car z))(define (angle-polar z) (cdr z))(define (make-from-real-imag-polar x y)(attach-tag ’polar(cons (sqrt (+ (square x) (square y)))(atan y x))))(define (make-from-mag-ang-polar r a)(attach-tag ’polar (cons r a)))Каждый обобщенный селектор реализуется как процедура, которая проверяет меткусвоего аргумента и вызывает подходящую процедуру для обработки данных нужноготипа.
Например, для того, чтобы получить действительную часть комплексного числа,real-part смотрит на метку и решает, звать ли Бенову real-part-rectangularили Лизину real-part-polar. В каждом из этих случаев мы пользуемся процедуройcontents, чтобы извлечь голый, непомеченный элемент данных и передать его либо вдекартову, либо в полярную процедуру:(define (real-part z)(cond ((rectangular? z)(real-part-rectangular (contents z)))((polar? z)(real-part-polar (contents z)))(else (error "Неизвестный тип -- REAL-PART" z))))(define (imag-part z)(cond ((rectangular? z)(imag-part-rectangular (contents z)))((polar? z)(imag-part-polar (contents z)))(else (error "Неизвестный тип -- IMAG-PART" z))))(define (magnitude z)(cond ((rectangular? z)(magnitude-rectangular (contents z)))((polar? z)178Глава 2. Построение абстракций с помощью данныхПрограммы, использующие комплексные числаadd-complex sub-complex mul-complex div-complexПакет комплексной арифметикиreal-part imag-part magnitude angleДекартово представлениеПолярное представлениеСписковая структура и элементарная машинная арифметикаРис.
2.21. Структура обобщенной системы комплексной арифметики.(magnitude-polar (contents z)))(else (error "Неизвестный тип -- MAGNITUDE" z))))(define (angle z)(cond ((rectangular? z)(angle-rectangular (contents z)))((polar? z)(angle-polar (contents z)))(else (error "Неизвестный тип -- ANGLE" z))))Для реализации арифметических операций с комплексными числами мы по-прежнемуможем использовать старые процедуры add-complex, sub-complex, mul-complex иdiv-complex из раздела 2.4.1, поскольку вызываемые ими селекторы обобщенные и,таким образом, могут работать с любым из двух представлений.
Например, процедураadd-complex по-прежнему выглядит как(define (add-complex z1 z2)(make-from-real-imag (+ (real-part z1) (real-part z2))(+ (imag-part z1) (imag-part z2))))Наконец, нам надо решить, порождать ли комплексные числа в Беновом или Лизиномпредставлении. Одно из разумных решений состоит в том, чтобы порождать декартовычисла, когда нам дают действительную и мнимую часть, и порождать полярные числа,когда нам дают модуль и аргумент:(define (make-from-real-imag x y)(make-from-real-imag-rectangular x y))(define (make-from-mag-ang r a)(make-from-mag-ang-polar r a))Структура получившейся системы комплексной арифметики показана на рисунке 2.21.Система разбита на три относительно независимых части: операции арифметики комплексных чисел, полярная реализация Лизы и декартова реализация Бена. Полярная и2.4.
Множественные представления для абстрактных данных179декартова реализации могли быть написаны Беном и Лизой по отдельности, и любуюиз них может использовать в качестве внутреннего представления третий программист,чтобы реализовать процедуры арифметики комплексных чисел в терминах абстрактногоинтерфейса конструкторов и селекторов.Поскольку каждый объект данных помечен своим типом, селекторы работают сданными обобщенным образом.
Это означает, что каждый селектор по определению обладает поведением, которое зависит от того, к какому типу данных он применяется.Следует обратить внимание на общий механизм доступа к отдельным представлениям: внутри любой данной реализации представления (скажем, внутри полярного пакетаЛизы) комплексное число представляется нетипизированной парой (модуль, аргумент).Когда обобщенный селектор обращается к данным полярного типа, он отрывает метку ипередает содержимое Лизиному коду. И наоборот, когда Лиза строит число для общегопользования, она помечает его тип, чтобы процедуры более высокого уровня могли егодолжным образом распознать. Такая дисциплина снятия и добавления меток при передаче объектов данных с уровня на уровень может быть ценной стратегией организацииданных и программ, как мы увидим в разделе 2.5.2.4.3.
Программирование, управляемое данными, и аддитивностьОбщая стратегия проверки типа данных и вызова соответствующей процедуры называется диспетчеризацией по типу (dispatching on type). Это хороший способ добитьсямодульности при проектировании системы. С другой стороны, такая реализация диспетчеризации, как в разделе 2.4.2, имеет два существенных недостатка. Один заключаетсяв том, что обобщенные процедуры интерфейса (real-part, imag-part, magnitudeи angle) обязаны знать про все имеющиеся способы представления.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
