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

Теперь пора подумать, как мы будем осуществлять арифметические операции над многочленами. В нашей упрощенной системе мы рассмотрим только сложение и умножение. Более того, мы будем настаивать, чтобы два многочлена, над которыми проводится операция, имели одну и ту же переменную.

К проектированию системы мы приступим, следуя уже знакомой нам дисциплине абстракции данных. Мы будем представлять многочлены в виде структуры данных под названием poly, которая состоит из переменной и набора термов. Мы предполагаем, что имеются селекторы variable и term-list, которые получают из poly эти данные, и конструктор make-poly, который собирает poly из переменной и списка термов. Переменная будет просто символом, так что для сравнения переменных мы сможем использовать процедуру same-variable? из раздела 2.3.2. Следующие процедуры определяют сложение и умножение многочленов:

(define (add-poly pi p2)

(if (same-variable? (variable pi) (variable p2)) (make-poly (variable pi)

(add-terms (term-list pi)

(term-list p2)))

(error "Многочлены от разных переменных -- ADD-POLY"

(list pi p2))))

(define (mul-poly pi p2)

(if (same-variable? (variable pi) (variable p2)) (make-poly (variable pi)

(mul-terms (term-list pi)

(term-list p2)))

(error "Многочлены от разных переменных -- MUL-POLY"

(list pi p2))))

Чтобы включить многочлены в нашу обобщенную арифметическую систему, нам потребуется снабдить их метками типа. Мы будем пользоваться меткой polynomial и вносить соответствующие операции над помеченными многочленами в таблицу операций. Весь свой код мы включим в процедуру установки пакета многочленов, подобно пакетам из раздела 2.5.1:

(define (install-polynomial-package) ;; внутренние процедуры ;; представление poly (define (make-poly variable term-list) (cons variable term-list))

55В случае многочленов с одной переменной задание значений многочлена в определенном множестве точек может быть особенно удачным представлением. Арифметика многочленов получается чрезвычайно простой. Чтобы получить, скажем, сумму двух представленных таким образом многочленов, достаточно сложить значения в соответствующих точках. Чтобы перейти обратно к более привычному представлению, можно использовать формулу интерполяции Лагранжа, которая показывает, как восстановить коэффициенты многочлена степени n, имея его значения в n + 1 точке.

(define (variable p) (car p)) (define (term-list p) (cdr p))

(процедуры same-variable? и variable? из раздела 2.3.2)

;; представление термов и списков термов (процедуры adjoin-term ... coeff из текста ниже)

(define (add-poly pl p2) ... ) (процедуры, которыми пользуется add-poly)

(define (mul-poly pl p2) ... ) (процедуры, которыми пользуется mul-poly)

;; интерфейс к остальной системе (define (tag p) (attach-tag polynomial p)) (put add (polynomial polynomial)

(lambda (pl p2) (tag (add-poly pl p2))))

(put mul (polynomial polynomial)

(lambda (pl p2) (tag (mul-poly pl p2))))

(put make polynomial

(lambda (var terms) (tag (make-poly var terms)))) done)

Сложение многочленов происходит по термам. Термы одинакового порядка (то есть имеющие одинаковую степень переменной многочлена) нужно скомбинировать. Это делается при помощи порождения нового терма того же порядка, в котором коэффициент является суммой коэффициентов слагаемых. Термы одного слагаемого, для которых нет соответствия в другом, просто добавляются к порождаемому многочлену-сумме.

Для того, чтобы работать со списками термов, мы предположим, что имеется конструктор the-empty-termlist, который возвращает пустой список термов, и конструктор adjoin-term, который добавляет к списку термов еще один. Кроме того, мы предположим, что имеется предикат empty-termlist?, который говорит, пуст ли данный список, селектор first-term, который получает из списка термов тот, у которого наибольший порядок, и селектор rest-terms, который возвращает все термы, кроме того, у которого наибольший порядок. Мы предполагаем, что для работы с термами у нас есть конструктор make-term, строящий терм с указанными порядком и коэффициентом, и селекторы order и coeff, которые, соответственно, возвращают порядок и коэффициент терма. Эти операции позволяют нам рассматривать и термы, и их списки как абстракции данных, о конкретной реализации которых мы можем позаботиться отдельно.

Вот процедура, которая строит список термов для суммы двух многочле-нов:56

(define (add-terms Ll L2)

(cond ((empty-termlist? Ll) L2)

56Эта операция очень похожа на процедуру объединения множеств union-set, которую мы разработали в упражнении 2.62. На самом деле, если мы будем рассматривать многочлены как множества, упорядоченные по степени переменной, то программа, которая порождает список термов для суммы, окажется почти идентична union-set.

((empty-termlist? L2) Li) (else

(let ((ti (first-term Li)) (t2 (first-term L2)))

(cond ((> (order ti) (order t2)) (adjoin-term ti (add-terms (rest-terms Li) L2))) ((< (order ti) (order t2)) (adjoin-term t2 (add-terms Li (rest-terms L2)))) (else (adjoin-term (make-term (order ti)

(add (coeff ti) (coeff t2)))

(add-terms (rest-terms Li)

(rest-terms L2)))))))))

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

Чтобы перемножить два списка термов, мы умножаем каждый терм из первого списка на все термы второго, используя в цикле mul-term-by-all-terms , которая умножает указанный терм на все термы указанного списка. Получившиеся списки термов (по одному на каждый терм в первом списке) накапливаются и образуют сумму. Перемножение двух термов дает терм, порядок которого равен сумме порядков множителей, а коэффициент равен произведению коэффициентов множителей:

(define (mul-terms Li L2) (if (empty-termlist? Li) (the-empty-termlist)

(add-terms (mul-term-by-all-terms (first-term Li) L2) (mul-terms (rest-terms Li) L2))))

(define (mul-term-by-all-terms ti L) (if (empty-termlist? L) (the-empty-termlist)

(let ((t2 (first-term L)))

(adjoin-term (make-term (+ (order ti) (order t2))

(mul (coeff ti) (coeff t2)))

(mul-term-by-all-terms ti (rest-terms L))))))

Вот и все, что нам требуется для сложения и умножения многочленов. Обратите внимание, что, поскольку мы работаем с термами при помощи обобщенных процедур add и mul , наш пакет работы с многочленами автоматически оказывается в состоянии обрабатывать любой тип коэффициента, о котором знает обобщенный арифметический пакет. Если мы подключим механизм приведения типов, подобный тому, который обсуждался в разделе 2.5.2, то мы автоматически окажемся способны производить операции над многочленами с коэффициентами различных типов, например

2

[Зж2 + (2 + 3i)x + 7] • [ж4 + -ж2 + (5 + 3*)]