Поскольку мы установили процедуры сложения и умножения многочленов add-poly и mul-poly в обобщенной арифметической системе в качестве операций add и mul для типа polynomial, наша система оказывается автоматически способна производить операции над многочленами вроде

[(у + 1)x2 + (у2 + 1)x + (у - 1)] • [(у - 2)x + (у3 + 7)]

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

Представление списков термов

Наконец, мы сталкиваемся с задачей реализовать хорошее представление для списков термов. Список термов, в сущности, есть множество коэффициентов, проиндексированное порядком терма. Следовательно, любой из методов представления множеств, описанных в 2.3.3, годится для этой задачи. С другой стороны, наши процедуры add-terms и mul-terms всегда обрабатывают списки термов последовательно от наибольшего порядка к наименьшему, так что мы будем использовать некоторую разновидность упорядоченного представления.

Как нам устроить структуру данных, которая представляет список термов? Одно из соображений - «плотность» многочленов, с которыми мы будем работать. Многочлен называется плотным (dense), если в термах с большинством порядков у него ненулевые коэффициенты. Если же в нем много нулевых коэффициентов, он называется разреженным (sparse). Например,

A : x5 + 2x4 + 3x2 - 2x - 5

плотный многочлен, а

B : x100 + 2x2 + 1

разреженный.

Списки термов плотных многочленов эффективнее всего представлять в виде списков коэффициентов. Например, A в приведенном примере удобно представляется в виде (1 2 0 3 -2 -5). Порядок терма в таком представлении

57Чтобы все это работало совершенно гладко, потребуется добавить в нашу систему обобщенной арифметики возможность привести «число» к типу многочлена, рассматривая его как многочлен степени ноль, коэффициентом которого является данное число. Это нужно, если мы хотим осуществлять операции вроде

[x2 + (y + 1)x + 5] + [x2 + 2x + 1] где требуется сложить коэффициент y +1 с коэффициентом 2.

есть длина списка, начинающегося с этого коэффициента, уменьшенная на 1.58 Для разреженного многочлена вроде B такое представление будет ужасным: получится громадный список нулей, в котором изредка попадаются одинокие ненулевые термы. Более разумно представление разреженного многочлена в виде списка ненулевых термов, где каждый терм есть список, содержащий порядок терма и коэффициент при этом порядке. При такой схеме многочлен B эффективно представляется в виде ((100 1) (2 2) (0 1)). Поскольку большинство операций над многочленами применяется к разреженным многочленам, мы используем это представление. Мы предполагаем, что список термов представляется в виде списка, элементами которого являются термы, упорядоченные от большего порядка к меньшему. После того, как решение принято, реализация селекторов и конструкторов для термов и списков термов не представляет трудностей:59

(define (adjoin-term term term-list) (if (=zero? (coeff term)) term-list

(cons term term-list)))

(define(the-empty-termlist) ())

(define(first-term term-list) (carterm-list))

(define(rest-terms term-list) (cdrterm-list))

(define(empty-termlist? term-list)(null? term-list))

(define (make-term order coeff) (list order coeff)) (define (order term) (car term)) (define (coeff term) (cadr term))

где =zero? работает так, как определяется в упражнении 2.80 (см. также ниже упражнение 2.87).

Пользователи многочленного пакета будут создавать (помеченные) многочлены при помощи процедуры:

(define (make-polynomial var terms) ((get make polynomial) var terms))

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

Установите =zero? для многочленов в обобщенный арифметический пакет. Это позволит adjoin-term работать с многочленами, чьи коэффициенты сами по себе многочлены.

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

Расширьте систему многочленов так, чтобы она включала вычитание многочленов. (Подсказка: может оказаться полезным определить обобщенную операцию смены знака.)

58В этих примерах многочленов мы предполагаем, что реализовали обобщенную арифметическую систему при помощи механизма типов, предложенного в упражнении 2.78. Таким образом, коэффициенты, которые являются обыкновенными числами, будут представлены самими числами, а не парами с первым элементом - символом scheme-number.

59Хотя мы предполагаем, что списки термов упорядочены, мы реализовали adjoin-term путем простого cons к существующему списку термов. Нам это может сойти с рук, пока мы гарантируем, что процедуры (вроде add-terms), которые используют adjoin-term, всегда вызывают ее с термом большего порядка, чем уже есть в списке. Если бы нам не хотелось давать такую гарантию, мы могли бы реализовать adjoin-term подобно конструктору adjoin-set для представления множеств в виде упорядоченных списков (упражнение 2.61).

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

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

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

Допустим, что мы хотим реализовать систему многочленов, которая эффективна как для плотных, так и для разреженных многочленов. Один из способов это сделать заключается в том, чтобы разрешить в системе оба типа представления. Ситуация аналогична примеру с комплексными числами из раздела 2.4, где мы позволили сосуществовать декартову и полярному представлению. Чтобы добиться этого, нам придется различать виды списков термов и сделать операции над списками термов обобщенными. Перепроектируйте систему с многочленами так, чтобы это обобщение было реализовано. Это потребует большого труда, а не только локальных изменений.

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

Многочлены с одной переменной можно делить друг на друга, получая частное и х5 - 1

остаток. Например, --= х3 + х, остаток х - 1.

х2 - 1

Деление можно производить в столбик. А именно, разделим старший член делимого на старший член делителя. В результате получится первый терм частного. Затем умножим результат на делитель, вычтем получившийся многочлен из делимого и, рекурсивно деля разность на делитель, получим оставшуюся часть частного. Останавливаемся, когда порядок делителя превысит порядок делимого, и объявляем остатком то, что тогда будет называться делимым. Кроме того, если когда-нибудь делимое окажется нулем, возвращаем ноль в качестве и частного, и остатка.

Процедуру div-poly можно разработать, следуя образцу add-poly и mul-poly. Процедура проверяет, одна ли и та же у многочленов переменная. Если это так, div-poly откусывает переменную и передает задачу в div-terms, которая производит операцию деления над списками термов. Наконец, div-poly прикрепляет переменную к результату, который выдает div-terms. Удобно сделать так, чтобы div-terms выдавала и частное, и остаток при делении. Она может брать в качестве аргументов два терма и выдавать список, состоящий из списка термов частного и списка термов остатка.

Закончите следующее определение div-terms, вставив недостающие выражения. Используйте ее, чтобы реализовать div-poly, которая получает в виде аргументов два экземпляра poly, а выдает список из poly-частного и poly-остатка.

(define (div-terms Ll L2) (if (empty-termlist? Ll)

(list (the-empty-termlist) (the-empty-termlist))

(let ((tl (first-term Ll)) (t2 (first-term L2)))

(if (> (order t2) (order tl))

(list (the-empty-termlist) Ll) (let ((new-c (div (coeff tl) (coeff t2))) (new-o (- (order tl) (order t2)))) (let ((rest-of-result

(рекурсивно вычислить оставшуюся часть результата)

))

(сформировать окончательный результат)

))))))