2.5.3 · Обобщенная символьная алгебра

Пакет многочленов как операции над данными с метками

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

Вопрос для размышления

Как система обобщенной арифметики может управлять структурой многочленов, не раскрывая детали списка членов в клиентском коде?

Представление разреженного многочлена в виде переменной и членов в порядке убывания степеней
Объединение одинаковых степеней при сложении двух списков членов
Распределение одного члена по всему многочлену при умножении
Удаление членов с нулевыми коэффициентами на границе представления
Диспетчеризация сложения и умножения многочленов через методы с метками типов
Отклонение операций над многочленами с несовпадающими переменными

Первая программа представляет каждый член порядком и коэффициентом и хранит члены от старшего порядка к младшему. Процедура add-terms выполняет то же упорядоченное слияние, что применялось ранее для множеств: старший порядок копируется, равные порядки складываются, а adjoin-term опускает нулевой результат. Пакет многочленов инкапсулирует это представление и предоставляет один метод add с меткой типа. Сложение x² + 2x + 1 и x² − 1 поэтому дает 2x² + 2x без явного нулевого свободного члена. Многочлен от y возвращает different-variables вместо неявного объединения несвязанных переменных.

Вторая программа умножает один член на каждый член другого многочлена, сдвигает порядки сложением, перемножает коэффициенты и объединяет промежуточные произведения через add-terms. Умножение x + 1 на x − 1 создает два взаимно уничтожающихся средних члена, оставляя x² − 1. Отдельный вычислитель использует селекторы пакета и сообщает 8 при x = 3. Этот урок моделирует разреженные многочлены от одной переменной с целыми коэффициентами, включая сложение, умножение, нормализацию и вычисление с метками типов.

Код SICP2,685 из 1,048,576 байт UTF-8

(begin
  (define (attach-tag type contents) (cons type contents))
  (define (type-tag object) (car object))
  (define (contents object) (cdr object))
  (define (make-term order coefficient)
    (list order coefficient))
  (define (order term) (car term))
  (define (coefficient term) (cadr term))
  (define (adjoin-term term terms)
    (if (= (coefficient term) 0)
        terms
        (cons term terms)))
  (define (add-terms left right)
    (cond ((null? left) right)
          ((null? right) left)
          (else
           (let ((left-term (car left))
                 (right-term (car right)))
             (cond ((> (order left-term) (order right-term))
                    (adjoin-term
                      left-term
                      (add-terms (cdr left) right)))
                   ((< (order left-term) (order right-term))
                    (adjoin-term
                      right-term
                      (add-terms left (cdr right))))
                   (else
                    (adjoin-term
                      (make-term
                        (order left-term)
                        (+ (coefficient left-term)
                           (coefficient right-term)))
                      (add-terms (cdr left) (cdr right)))))))))
  (define (make-polynomial variable terms)
    (attach-tag 'polynomial (cons variable terms)))
  (define (variable polynomial-contents)
    (car polynomial-contents))
  (define (term-list polynomial-contents)
    (cdr polynomial-contents))
  (define (add-polynomial-contents left right)
    (if (eq? (variable left) (variable right))
        (make-polynomial
          (variable left)
          (add-terms (term-list left) (term-list right)))
        'different-variables))
  (define operation-table
    (list
      (cons (list 'add 'polynomial 'polynomial)
            add-polynomial-contents)))
  (define (lookup-entry key table)
    (cond ((null? table) #f)
          ((equal? key (car (car table)))
           (cdr (car table)))
          (else (lookup-entry key (cdr table)))))
  (define (apply-generic operation left right)
    (let ((method
            (lookup-entry
              (list operation (type-tag left) (type-tag right))
              operation-table)))
      (if method
          (method (contents left) (contents right))
          'no-method)))
  (define p
    (make-polynomial
      'x
      (list (make-term 2 1)
            (make-term 1 2)
            (make-term 0 1))))
  (define q
    (make-polynomial
      'x
      (list (make-term 2 1)
            (make-term 0 -1))))
  (define y
    (make-polynomial 'y (list (make-term 1 1))))
  (list (apply-generic 'add p q)
        (apply-generic 'add p y)))

(begin
  (define (attach-tag type contents) (cons type contents))
  (define (type-tag object) (car object))
  (define (contents object) (cdr object))
  (define (make-term order coefficient)
    (list order coefficient))
  (define (order term) (car term))
  (define (coefficient term) (cadr term))
  (define (adjoin-term term terms)
    (if (= (coefficient term) 0)
        terms
        (cons term terms)))
  (define (add-terms left right)
    (cond ((null? left) right)
          ((null? right) left)
          (else
           (let ((left-term (car left))
                 (right-term (car right)))
             (cond ((> (order left-term) (order right-term))
                    (adjoin-term
                      left-term
                      (add-terms (cdr left) right)))
                   ((< (order left-term) (order right-term))
                    (adjoin-term
                      right-term
                      (add-terms left (cdr right))))
                   (else
                    (adjoin-term
                      (make-term
                        (order left-term)
                        (+ (coefficient left-term)
                           (coefficient right-term)))
                      (add-terms (cdr left) (cdr right)))))))))
  (define (make-polynomial variable terms)
    (attach-tag 'polynomial (cons variable terms)))
  (define (variable polynomial-contents)
    (car polynomial-contents))
  (define (term-list polynomial-contents)
    (cdr polynomial-contents))
  (define (add-polynomial-contents left right)
    (if (eq? (variable left) (variable right))
        (make-polynomial
          (variable left)
          (add-terms (term-list left) (term-list right)))
        'different-variables))
  (define operation-table
    (list
      (cons (list 'add 'polynomial 'polynomial)
            add-polynomial-contents)))
  (define (lookup-entry key table)
    (cond ((null? table) #f)
          ((equal? key (car (car table)))
           (cdr (car table)))
          (else (lookup-entry key (cdr table)))))
  (define (apply-generic operation left right)
    (let ((method
            (lookup-entry
              (list operation (type-tag left) (type-tag right))
              operation-table)))
      (if method
          (method (contents left) (contents right))
          'no-method)))
  (define p
    (make-polynomial
      'x
      (list (make-term 2 1)
            (make-term 1 2)
            (make-term 0 1))))
  (define q
    (make-polynomial
      'x
      (list (make-term 2 1)
            (make-term 0 -1))))
  (define y
    (make-polynomial 'y (list (make-term 1 1))))
  (list (apply-generic 'add p q)
        (apply-generic 'add p y)))

Примеры

Результат—

Вывод: —
Значение: —
Диагностика: —

Трасса выполнения0 / 0 событий

Ожидаемый результат

Программа сложения возвращает ((polynomial x (2 2) (1 2)) different-variables). Программа умножения возвращает ((polynomial x (2 1) (0 -1)) 8).

На что обратить внимание в трассе

При сложении проследите за сравнением порядков по убыванию и найдите сумму коэффициентов равных порядков, которая отбрасывает нулевой свободный член. При умножении проследите за каждым сдвигом порядка, произведением коэффициентов, рекурсивным промежуточным произведением и слиянием через add-terms, которое взаимно уничтожает два члена порядка 1. Проверка переменных происходит до начала любой операции над представлением.

Попробуйте сами

Измените программу и сравните результат.

Умножьте x² + x + 1 на x − 1, определите разреженный список членов и вычислите значение результата при x = 2.

Показать подсказку

Сформируйте по одному промежуточному произведению для каждого левого члена, затем объедините одинаковые порядки. Взаимное уничтожение членов порядка 1 и порядка 0 происходит на разных этапах.

Завершить этот урок

В этой главе пройдено 0 из 20 уроков0%