Иерархии типов в символьной алгебре

Наша система обработки многочленов показывает, как объекты одного типа (многочлены) могут на самом деле быть составными сущностями, содержащими в качестве частей объекты многих различных типов. При определении обобщенных операций это не составляет никакой реальной сложности. Нужно только установить соответствующие обобщенные операции для выполнения необходимых действий над частями составных типов. В сущности, мы видели, что многочлены образуют своего рода «рекурсивную абстракцию данных», в том смысле, что части многочленов сами по себе могут быть многочленами. Наши обобщенные операции и наш стиль программирования, управляемого данными, могут справиться с такими трудностями без особого труда.

С другой стороны, алгебра многочленов представляет собой систему, в которой типы данных нельзя естественным образом выстроить в виде башни. Например, могут существовать многочлены по x, коэффициенты которых являются многочленами по у. Но могут существовать и многочлены по у, коэффициенты которых являются многочленами по x. Никакой из этих типов не находится «выше» другого ни в каком естественным смысле, и тем не менее элементы этих двух множеств часто требуется складывать. Для этого существует несколько способов. Одна из возможностей состоит в том, чтобы преобразовывать один из многочленов к типу другого путем раскрытия и переупорядочения термов, так, чтобы у обоих многочленов оказалась одна и та же главная переменная. Можно навязать данным башнеподобную структуру путем упорядочения переменных, и, таким образом, всегда преобразовывать любой многочлен к «канонической форме», где переменная с наибольшим приоритетом всегда доминирует, а переменные с меньшим оказываются зарыты в коэффициенты. Такая стратегия работает довольно хорошо, только преобразование может без особой необходимости «раздуть» многочлен, так что его станет неудобно читать и, возможно, менее эффективно обрабатывать. Для этой области структура башни определенно не является естественной, как и для любой другой области, где пользователь может изобретать новые типы динамически, используя старые в различных комбинирующих формах, таких как тригонометрические функции, последовательности степеней или интегралы.

Не должно вызывать удивления то, что управление приведением типов представляет серьезную проблему при разработке крупных систем алгебраических манипуляций. Существенная часть сложности таких систем связана с отношениями между различными типами. В сущности, можно честно признать, что мы до сих пор не до конца понимаем приведение типов. Мы даже не до конца осознаем понятие типа данных. Однако то, что мы знаем, дает нам солидные принципы структурирования и модуляризации, которые помогают в разработке больших систем.

Упражнение 2.92.

Использовав упорядочение переменных, расширьте пакет работы с многочленами так, чтобы сложение и умножение многочленов работало для многочленов с несколькими переменными. (Это не простая задача!)

Расширенное упражнение: рациональные функции

Можно расширить обобщенную арифметическую систему и включить в нее рациональные функции (rational functions). Это «дроби», в которых числитель

и знаменатель являются многочленами, например

ж+ 1 ж3 + 1

Система должна уметь складывать, вычитать. умножать и делить рациональные функции, а также осуществлять вычисления вроде

ж + 1ж ж3 + 2ж2 + Зж + 1

x3 + 1 x2 - 1 x4 + x3 - x - 1

(здесь сумма упрощена при помощи сокращения общих множителей. Обычное «перекрестное умножение» дало бы многочлен четвертой степени в числителе и пятой в знаменателе.)

Если мы изменим пакет арифметики рациональных чисел так, чтобы он использовал обобщенные операции, то он будет делать то, что нам требуется, за исключением задачи приведения к наименьшему знаменателю.

Упражнение 2.93.

Модифицируйте пакет арифметики рациональных чисел, заставив его пользоваться обобщенными операциями, но при этом измените make-rat, чтобы она не пыталась сокращать дроби. Проверьте систему, применив make-rational к двум многочленам, и получив рациональную функцию

(define pl (make-polynomial x ((2 l)(0 l)))) (define p2 (make-polynomial x ((3 l)(0 l)))) (define rf (make-rational p2 pl))

Сложите теперь rf саму с собой, используя add. Вы увидите, что процедура сложения не приводит дроби к наименьшему знаменателю.

Приводить дроби многочленов к наименьшему знаменателю мы можем, используя ту же самую идею, которой мы воспользовались для целых чисел: изменить make-rat, чтобы она делила и числитель, и знаменатель на их наибольший общий делитель. Понятие «наибольшего общего делителя» имеет смысл для многочленов. Более того, вычислять НОД для многочленов можно с помощью, в сущности, того же алгоритма Евклида, который работает на целых числах.60 Вот целочисленная версия:

(define (gcd a b) (if (= b 0)

a

(gcd b (remainder a b))))

Взяв ее за основу, мы можем проделать очевидные изменения и определить операцию извлечения НОД, которая работает на списках термов:

60То, что алгоритм Евклида работает для многочленов, в алгебре формализуется утверждением, что многочлены образуют структуру, называемую евклидовым кольцом (Euclidean ring). Евклидово кольцо - это структура, на которой определены сложение, вычитание и коммутативное умножение, а также некоторый способ сопоставить каждому элементу кольца x «меру» - неотрицательное целое число m(x), обладающую следующими свойствами: m(xy) > m(x) для любых ненулевых x и у, а также для любых x и y существует q, такое, что y = qx + r и либо r = 0, либо m(r) < m(x). С абстрактной точки зрения, это все, что нужно, чтобы доказать, что алгоритм Евклида работает. В случае целых чисел, мера m каждого числа есть его модуль. Для структуры многочленов мерой служит степень многочлена.

(define (gcd-terms a b) (if (empty-termlist? b) a

(gcd-terms b (remainder-terms a b))))

где remainder-terms извлекает компоненту списка, соответствующую остатку, из списка, который возвращает операция деления списков термов div-terms, реализованная в упражнении 2.91.

Упражнение 2.94.

Используя div-terms, напишите процедуру remainder-terms, и с ее помощью определите gcd-terms, как показано выше. Напишите теперь процедуру gcd-polys, которая вычисляет НОД двух многочленов. (Процедура должна сообщать об ошибке, если входные объекты являются многочленами от разных переменных.) Установите в систему обобщенную операцию greatest-common-divisor, которая для многочленов сводится к gcd-poly, а для обыкновенных чисел к обыкновенному gcd. В качестве проверки, попробуйте ввести

(define pi (make-polynomial x ((4 i) (3 -i) (2 -2) (i 2)))) (define p2 (make-polynomial x ((3 i) (i -i)))) (greatest-common-divisor pi p2)

и проверьте результат вручную.

Упражнение 2.95.

Пусть P1, P2 и P3 - многочлены

Pi : x2 - 2x + 1 P2 : 11x2 + 1 P3 : 13x + 5

Теперь пусть Q1 будет произведение P1 и P2, а Q2 произведение P1 и P3. При помощи greatest-common-divisor (упражнение 2.94) вычислите НОД Q1 и Q2. Обратите внимание, что ответ не совпадает с P1. Этот пример вводит в вычисление операции с нецелыми числами, и это создает сложности для алгоритма вычисления НОД.61 Чтобы понять, что здесь происходит, попробуйте включить трассировку в gcd-terms при вычислении НОД либо проведите деление вручную.

Проблему, которую демонстрирует упражнение 2.95, можно решить, если мы используем следующий вариант алгоритма вычисления НОД (который работает только для многочленов с целыми коэффициентами). Прежде, чем проводить деление многочленов при вычислении НОД, мы умножаем делимое на целую константу, которая выбирается так, чтобы в процессе деления не возникло никаких дробей. Результат вычисления будет отличаться от настоящего НОД на целую константу, но при приведении рациональных функций к наименьшему знаменателю это несущественно; будет проведено деление и числителя, и знаменателя на НОД, так что константный множитель сократится.

Выражаясь более точно, если P и Q - многочлены, определим O\ как порядок P (то есть порядок его старшего терма), а O2 как порядок Q. Пусть c будет коэффициент старшего терма Q. В таком случае, можно показать, что если мы

61В системах вроде MIT Scheme получится многочлен, который на самом деле является делителем q1 и q2, но с рациональными коэффициентами. Во многих других реализациях Scheme, где при делении целых чисел могут получаться десятичные числа ограниченной точности, может оказаться, что мы не получим правильного делителя.