Х. Абельсон, Дж. Дж. Сассман, Дж. Сассман - Структура и интерпретация компьютерных программ (1108516), страница 40
Текст из файла (страница 40)
Более того, поскольку часто большие программы создаются путем комбинирования существующих модулей,созданных независимо друг от друга, нам требуются соглашения, которые позволяли быпрограммистам добавлять модули к большим системам аддитивно (additively), то естьбез перепроектирования и переписывания этих модулей.В этом разделе мы научимся работать с данными, которые могут быть представлены вразных частях программы различными способами.
Это требует построения обобщенныхпроцедур (generic procedures) — процедур, работающих с данными, которые могут бытьпредставлены более чем одним способом. Наш основной метод построения обобщенныхпроцедур будет состоять в том, чтобы работать в терминах объектов, обладающих метками типа (type tags), то есть объектов, явно включающих информацию о том, как ихнадо обрабатывать. Кроме того, мы обсудим программирование, управляемое данными(data-directed programming) — мощную и удобную стратегию реализации, предназначенную для аддитивной сборки систем с обобщенными операциями.Мы начнем с простого примера комплексных чисел. Мы увидим, как метки типаи стиль, управляемый данными, позволяют нам создать отдельные декартово и полярное представления комплексных чисел, и при этом поддерживать понятие абстрактногообъекта «комплексное число» .
Мы добьемся этого, определив арифметические процедуры для комплексных чисел (add-complex, sub-complex, mul-complex и divcomplex) в терминах обобщенных селекторов, которые получают части комплексногочисла независимо от того, как оно представлено. Получающаяся система работы с комплексными числами, как показано на рис. 2.19, содержит два типа барьеров абстракции.«Горизонтальные» барьеры играют ту же роль, что и на рис. 2.1.
Они отделяют «высокоуровневые» операции от «низкоуровневых» представлений. В дополнение к этому,существует еще «вертикальный» барьер, который дает нам возможность отдельно разрабатывать и добавлять альтернативные представления.В разделе 2.5 мы покажем, как с помощью меток типа и стиля программирования,управляемого данными, создать арифметический пакет общего назначения.
Такой пакетдает пользователю процедуры (add, mul и т.д.), с помощью которых можно манипулировать всеми типами «чисел», и если нужно, его можно легко расширить, когда потре-Глава 2. Построение абстракций с помощью данных172Мнимыеz = x + iy = reAiAДействительныеРис. 2.20. Комплексные числа как точки на плоскостибуется новый тип чисел. В разделе 2.5.3 мы покажем, как использовать обобщеннуюарифметику в системе, работающей с символьной алгеброй.2.4.1. Представления комплексных чиселВ качестве простого, хотя и нереалистичного, примера программы, использующейобобщенные операции, мы разработаем систему, которая производит арифметическиеоперации над комплексными числами.
Начнем мы с обсуждения двух возможных представлений комплексного числа в виде упорядоченной пары: декартова форма (действительная и мнимая части) и полярная форма (модуль и аргумент)43. В разделе 2.4.2 будетпоказано, как оба представления можно заставить сосуществовать в рамках одной программы при помощи меток типа и обобщенных операций.Подобно рациональным числам, комплексные числа естественно представлять в видеупорядоченных пар. Множество комплексных чисел можно представлять себе как двумерное пространство с двумя перпендикулярными осями: «действительной» и «мнимой»(см. рис.
2.20). С этой точки зрения комплексное число z = x + iy (где i2 = −1) можно представить как точку на плоскости, действительная координата которой равна x,а мнимая y. В этом представлении сложение комплексных чисел сводится к сложениюкоординат:Действительная-часть(z1 + z2 ) == Действительная-часть(z1) + Действительная-часть(z2)Мнимая-часть(z1 + z2 ) = Мнимая-часть(z1 ) + Мнимая-часть(z2)43 В реальных вычислительных системах, как правило, декартова форма предпочтительнее полярной из-заошибок округления при преобразованиях между этими двумя формами.
Именно поэтому пример с комплексными числами нереалистичен. Тем не менее, он служит ясной иллюстрацией строения системы, использующейобобщенные операции, и хорошим введением в более содержательные системы, которые мы строим далее походу этой главы.2.4. Множественные представления для абстрактных данных173При умножении комплексных чисел естественней думать об их представлении в полярной форме, в виде модуля и аргумента (r и A на рис. 2.20). Произведение двухкомплексных чисел есть вектор, получаемый путем растягивания одного комплексногочисла на модуль другого и поворота на его же аргумент:Модуль(z1 · z2 ) = Модуль(z1 ) · Модуль(z2 )Аргумент(z1 · z2 ) = Аргумент(z1 ) + Аргумент(z2 )Таким образом, есть два различных представления для комплексных чисел, и каждое из них удобнее для какого-то набора операций.
Однако с точки зрения человека,который пишет программу с использованием комплексных чисел, принцип абстракцииданных утверждает, что все операции, работающие с комплексными числами, должныработать независимо от того, какую интерпретацию использует компьютер. Например,часто бывает нужно получить модуль комплексного числа, представленного в декартовыхкоординатах. Подобным образом, часто полезно уметь определять действительную частькомплексного числа, представленного в полярных координатах.При разработке такой системы мы можем следовать той самой стратегии абстракцииданных, которую мы использовали в пакете работы с рациональными числами в разделе 2.1.1.
Предположим, что операции над комплексными числами реализованы в терминах четырех селекторов: real-part, imag-part, magnitude и angle. Предположимеще, что у нас есть две процедуры для построения комплексных чисел: make-fromreal-imag возвращает комплексное число с указанными действительной и мнимой частями, а make-from-mag-ang возвращает комплексное число с указанными модулем иаргументом. Эти процедуры обладают такими свойствами, что для любого комплексногочисла z(make-from-real-imag (real-part z) (imag-part z))и(make-from-mag-ang (magnitude z) (angle z))порождают комплексные числа, равные z.Используя такие конструкторы и селекторы, мы можем реализовать арифметику комплексных чисел через «абстрактные данные», определяемые этими конструкторами иселекторами, в точности как мы это делали для рациональных чисел в разделе 2.1.1.Как показывают вышеуказанные формулы, можно складывать и вычитать комплексныечисла в терминах действительной и мнимой части, а умножать и делить в терминахмодуля и аргумента:(define (add-complex z1 z2)(make-from-real-imag (+ (real-part z1) (real-part z2))(+ (imag-part z1) (imag-part z2))))(define (sub-complex z1 z2)(make-from-real-imag (- (real-part z1) (real-part z2))(- (imag-part z1) (imag-part z2))))174Глава 2.
Построение абстракций с помощью данных(define (mul-complex z1 z2)(make-from-mag-ang (* (magnitude z1) (magnitude z2))(+ (angle z1) (angle z2))))(define (div-complex z1 z2)(make-from-mag-ang (/ (magnitude z1) (magnitude z2))(- (angle z1) (angle z2))))Для того, чтобы придать пакету работы с комплексными числами окончательныйвид, нам осталось выбрать представление и реализовать конструкторы и селекторы втерминах элементарных чисел и элементарной списковой структуры. Есть два очевидных способа это сделать: можно представлять комплексное число как пару в «декартовойформе» (действительная часть, мнимая часть) либо в «полярной форме» (модуль, аргумент).
Какой вариант мы выберем?Чтобы говорить о конкретных вариантах, предположим, что двое программистов, БенБитобор и Лиза П. Хакер, независимо друг от друга разрабатывают представления длясистемы, работающей с комплексными числами. Бен решает представлять комплексныечисла в декартовой форме. При таком решении доступ к действительной и мнимой частям комплексного числа, а также построение его из действительной и мнимой частейреализуются прямолинейно. Чтобы найти модуль и аргумент, а также чтобы построитькомплексное число с заданными модулем и аргументом, он использует тригонометрические соотношенияx = r cos Ay = r sin A;pr = x2 + y 2 A = arctg(y, x)которые связывают действительную и мнимую части (x, y) с модулем и аргументом(r, A)44 . Таким образом, реализация Бена определяется следующими селекторами и конструкторами:(define (real-part z) (car z))(define (imag-part z) (cdr z))(define (magnitude z)(sqrt (+ (square (real-part z)) (square (imag-part z)))))(define (angle z)(atan (imag-part z) (real-part z)))(define (make-from-real-imag x y) (cons x y))(define (make-from-mag-ang r a)(cons (* r (cos a)) (* r (sin a))))Напротив, Лиза решает представить комплексные числа в полярной форме.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
