SICP Exercise 2.90

It’s a lot of coding!

(define (apply-generic op . args)
  (let ((type-tags (map type-tag args)))
    (let ((proc (get op type-tags)))
      (if proc
          (apply proc (map contents args))
          (if (= (length args) 2)
              (let ((type1 (car type-tags))
                    (type2 (cadr type-tags))
                    (a1 (car args))
                    (a2 (cadr args)))
                (let ((t1->t2 (get-coercion type1 type2))
                      (t2->t1 (get-coercion type2 type1)))
                  (cond (t1->t2
                         (apply-generic op (t1->t2 a1) a2))
                        (t2->t1
                         (apply-generic op a1 (t2->t1 a2)))
                        (else
                         (error "No method for these types"
                                (list op type-tags))))))
              (error "No method for these types"
                     (list op type-tags)))))))

(define put 2d-put!)
(define (get x-key y-key)
  (let ((1d-table (2d-get-alist-x x-key)))
    (let ((type-f (assoc y-key 1d-table)))
      (if type-f (cdr type-f) false))))
(define put-coercion put)
(define get-coercion get)

(define (type-tag datum)
  (cond ((pair? datum) (car datum))
        ((number? datum) 'scheme-number)
        (else (error "Bad tagged datum -- TYPE-TAG" datum))))
(define (contents datum)
  (cond ((pair? datum) (cdr datum))
        ((number? datum) datum)
        (else (error "Bad tagged datum -- CONTENTS" datum))))
(define (attach-tag type-tag contents)
  (if (number? contents)
      contents
      (cons type-tag contents)))

(define (add x y) (apply-generic 'add x y))
(define (sub x y) (apply-generic 'sub x y))
(define (negation x) (apply-generic 'negation x))
(define (mul x y) (apply-generic 'mul x y))
(define (div x y) (apply-generic 'div x y))
(define (equ? x y) (apply-generic 'equ? x y))
(define (=zero? x) (apply-generic '=zero? x))

;; scheme number package
(define (install-scheme-number-package)
  (define (tag x)
    (attach-tag 'scheme-number x))
  (put 'add '(scheme-number scheme-number)
       (lambda (x y) (tag (+ x y))))
  (put 'sub '(scheme-number scheme-number)
       (lambda (x y) (tag (- x y))))
  (put 'negation '(scheme-number)
       (lambda (x) (tag (- x))))
  (put 'mul '(scheme-number scheme-number)
       (lambda (x y) (tag (* x y))))
  (put 'div '(scheme-number scheme-number)
       (lambda (x y) (tag (/ x y))))
  (put 'equ? '(scheme-number scheme-number) =)
  (put '=zero? '(scheme-number)
       (lambda (x) (= x 0)))
  (put 'make 'scheme-number
       (lambda (x) (tag x)))
  'done)
(define (make-scheme-number n)
  ((get 'make 'scheme-number) n))

; install-polynomial-package
(define (install-polynomial-package)
  ;; procedures
  (define (make-dense-poly variable term-list)
    ((get 'make-poly 'dense) variable term-list))
  (define (make-sparse-poly variable term-list)
    ((get 'make-poly 'sparse) variable term-list))
  (define (add-poly p1 p2)
    (apply-generic 'add-poly p1 p2))
  (define (add-poly-num p x)
    (apply-generic 'add-poly-num p x))
  (define (add-num-poly x p)
    (apply-generic 'add-num-poly x p))
  (define (sub-poly p1 p2)
    (apply-generic 'sub-poly p1 p2))
  (define (neg-poly p)
    (apply-generic 'neg-poly p))
  (define (mul-poly p1 p2)
    (apply-generic 'mul-poly p1 p2))
  (define (mul-poly-num p x)
    (apply-generic 'mul-poly-num p x))
  (define (mul-num-poly x p)
    (apply-generic 'mul-num-poly x p))
  (define (=zero?-poly p)
    (apply-generic '=zero?-poly p))

  ;; interface to rest of the system
  (define (tag p) (attach-tag 'polynomial p))
  (put 'add '(polynomial polynomial)
       (lambda (p1 p2)
         (tag (add-poly p1 p2))))
  (put 'add '(polynomial scheme-number)
       (lambda (p x)
         (tag (add-poly-num
               p (attach-tag 'scheme-number x)))))
  (put 'add '(scheme-number polynomial)
       (lambda (x p)
         (tag (add-num-poly
               (attach-tag 'scheme-number x) p))))
  (put 'sub '(polynomial polynomial)
       (lambda (p1 p2)
         (tag (add-poly p1 (neg-poly p2)))))
  (put 'sub '(polynomial scheme-number)
       (lambda (p x)
         (tag (add-poly-num
               p
               (negation (attach-tag 'scheme-number x))))))
  (put 'sub '(scheme-number polynomial)
       (lambda (x p)
         (tag (add-num-poly (attach-tag 'scheme-number x)
                            (neg-poly p)))))
  (put 'negation '(polynomial)
       (lambda (p) (tag (neg-poly p))))
  (put 'mul '(polynomial polynomial)
       (lambda (p1 p2)
         (tag (mul-poly p1 p2))))
  (put 'mul '(polynomial scheme-number)
       (lambda (p x)
         (tag (mul-poly-num p x))))
  (put 'mul '(scheme-number polynomial)
       (lambda (x p)
         (tag (mul-num-poly x p))))
  (put '=zero? '(polynomial)
       (lambda (p) (=zero?-poly p)))
  (put 'make-dense-polynomial 'polynomial
       (lambda (variable term-list)
         (tag (make-dense-poly variable term-list))))
  (put 'make-sparse-polynomial 'polynomial
       (lambda (variable term-list)
         (tag (make-sparse-poly variable term-list))))
  'done)

;; outside constructor
(define (make-dense-polynomial variable term-list)
  ((get 'make-dense-polynomial 'polynomial) variable term-list))
(define (make-sparse-polynomial variable term-list)
  ((get 'make-sparse-polynomial 'polynomial) variable term-list))

(define (install-dense-poly-package)
  (define (make-poly variable term-list)
    (cons variable (remove-leading-zeros term-list)))
  (define (remove-leading-zeros L)
    (cond ((null? L) '())
          ((=zero? (car L)) (remove-leading-zeros (cdr L)))
          (else L)))
  (define (variable p) (car p))
  (define (term-list p) (cdr p))
  (define (variable? x) (symbol? x))
  (define (same-variable? v1 v2)
    (and (variable? v1) (variable? v2) (eq? v1 v2)))
  ;; representation of terms and term lists
  (define (adjoin-term term term-list)
    (cond ((=zero? (coeff term)) term-list)
          ((= (order term) (length term-list))
           (cons (coeff term) term-list))
          (else (adjoin-term term (cons 0 term-list)))))
  (define (the-empty-termlist) '())
  (define (first-term L)
    (make-term (- (length L) 1) (car L)))
  (define (rest-terms term-list) (cdr term-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))

  (define (add-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (make-poly (variable p1)
                   (add-terms (term-list p1)
                              (term-list p2)))
        (error "Polys not in same var -- ADD-POLY"
               (list p1 p2))))
  (define (add-terms L1 L2)
    (cond ((empty-termlist? L1) L2)
          ((empty-termlist? L2) L1)
          (else
           (let ((t1 (first-term L1)) (t2 (first-term L2)))
             (cond ((> (order t1) (order t2))
                    (adjoin-term
                     t1 (add-terms (rest-terms L1) L2)))
                   ((< (order t1) (order t2))
                    (adjoin-term
                     t2 (add-terms L1 (rest-terms L2))))
                   (else
                    (adjoin-term
                     (make-term (order t1)
                                (add (coeff t1) (coeff t2)))
                     (add-terms (rest-terms L1)
                                (rest-terms L2)))))))))
  (define (sub-poly p1 p2)
    (add-poly p1 (neg-poly p2)))
  (define (neg-poly p)
    (make-poly (variable p)
               (neg-terms (term-list p))))
  (define (neg-terms L)
    (if (empty-termlist? L)
        L
        (let ((t (first-term L)))
          (adjoin-term (make-term (order t) (negation (coeff t)))
                       (neg-terms (rest-terms L))))))
  (define (mul-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (make-poly (variable p1)
                   (mul-terms (term-list p1)
                              (term-list p2)))
        (error "Polys not in same var -- MUL-POLY"
               (list p1 p2))))
  (define (mul-terms L1 L2)
    (if (empty-termlist? L1)
        (the-empty-termlist)
        (add-terms (mul-term-by-all-terms (first-term L1) L2)
                   (mul-terms (rest-terms L1) L2))))
  (define (mul-term-by-all-terms t1 L)
    (if (empty-termlist? L)
        (the-empty-termlist)
        (let ((t2 (first-term L)))
          (adjoin-term
           (make-term (+ (order t1) (order t2))
                      (mul (coeff t1) (coeff t2)))
           (mul-term-by-all-terms t1 (rest-terms L))))))
  (define (add-num-poly x p)
    (make-poly (variable p)
               (add-x-list x (term-list p))))
  (define (add-x-list x L)
    (cond ((empty-termlist? L) (list x))
          ((null? (cdr L)) (list (+ x (car L))))
          (else (cons (car L) (add-x-list x (cdr L))))))
  (define (mul-num-poly x p)
    (make-poly (variable p)
               (mul-x-list x (term-list p))))
  (define (mul-x-list x L)
    (map (lambda (y) (* x y)) L))
  (define (sparse->dense p)
    (let ((s-p (contents p)))
      (let ((v (car s-p))
            (s-L (cdr s-p)))
        (let ((d-L (term-list-sparse->dense s-L)))
          (tag (make-poly v d-L))))))
  (define (term-list-sparse->dense s-L)
    (if (null? s-L)
        '()
        (let ((term (car s-L)))
          (let ((ord (car term))
                (coe (cadr term)))
            (adjoin-term
             (make-term ord coe)
             (term-list-sparse->dense (cdr s-L)))))))

  ;; interface to the rest of the system
  (define (tag x) (attach-tag 'dense x))
  (put 'add-poly '(dense dense)
       (lambda (p1 p2) (tag (add-poly p1 p2))))
  (put 'add-poly-num '(dense scheme-number)
       (lambda (p x) (tag (add-num-poly x p))))
  (put 'add-num-poly '(scheme-number dense)
       (lambda (x p) (tag (add-num-poly x p))))
  (put 'sub-poly '(dense dense)
       (lambda (p1 p2) (tag (sub-poly p1 p2))))
  (put 'neg-poly '(dense)
       (lambda (p) (tag (neg-poly p))))
  (put 'mul-poly '(dense dense)
       (lambda (p1 p2) (tag (mul-poly p1 p2))))
  (put 'mul-poly-num '(dense scheme-number)
       (lambda (p x) (tag (mul-num-poly x p))))
  (put 'mul-num-poly '(scheme-number dense)
       (lambda (x p) (tag (mul-num-poly x p))))
  (put '=zero?-poly '(dense)
       (lambda (p) (empty-termlist? (term-list p))))
  (put 'make-poly 'dense
       (lambda (v t) (tag (make-poly v t))))
  (put-coercion 'sparse 'dense  sparse->dense)
  'done)

(define (install-sparse-poly-package)
  ;; internal procedures
  (define (make-poly variable term-list)
    (cons variable (remove-zeros term-list)))
  (define (remove-zeros L)
    (filter (lambda (term) (not (=zero? (coeff term)))) L))
  (define (filter predicate sequence)
    (cond ((null? sequence) '())
          ((predicate (car sequence))
           (cons (car sequence)
                 (filter predicate (cdr sequence))))
          (else (filter predicate (cdr sequence)))))
  (define (variable p) (car p))
  (define (term-list p) (cdr p))
  (define (variable? x) (symbol? x))
  (define (same-variable? v1 v2)
    (and (variable? v1) (variable? v2) (eq? v1 v2)))
  ;; representation of terms and term lists
  (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) (car term-list))
  (define (rest-terms term-list) (cdr term-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))

  (define (add-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (make-poly (variable p1)
                   (add-terms (term-list p1)
                              (term-list p2)))
        (error "Polys not in same var -- ADD-POLY"
               (list p1 p2))))
  (define (add-terms L1 L2)
    (cond ((empty-termlist? L1) L2)
          ((empty-termlist? L2) L1)
          (else
           (let ((t1 (first-term L1)) (t2 (first-term L2)))
             (cond ((> (order t1) (order t2))
                    (adjoin-term
                     t1 (add-terms (rest-terms L1) L2)))
                   ((< (order t1) (order t2))
                    (adjoin-term
                     t2 (add-terms L1 (rest-terms L2))))
                   (else
                    (adjoin-term
                     (make-term (order t1)
                                (add (coeff t1) (coeff t2)))
                     (add-terms (rest-terms L1)
                                (rest-terms L2)))))))))
  (define (sub-poly p1 p2)
    (add-poly p1 (neg-poly p2)))
  (define (neg-poly p)
    (make-poly (variable p)
               (neg-terms (term-list p))))
  (define (neg-terms L)
    (if (empty-termlist? L)
        L
        (let ((t (first-term L)))
          (adjoin-term (make-term (order t) (negation (coeff t)))
                       (neg-terms (rest-terms L))))))
  (define (mul-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (make-poly (variable p1)
                   (mul-terms (term-list p1)
                              (term-list p2)))
        (error "Polys not in same var -- MUL-POLY"
               (list p1 p2))))
  (define (mul-terms L1 L2)
    (if (empty-termlist? L1)
        (the-empty-termlist)
        (add-terms (mul-term-by-all-terms (first-term L1) L2)
                   (mul-terms (rest-terms L1) L2))))
  (define (mul-term-by-all-terms t1 L)
    (if (empty-termlist? L)
        (the-empty-termlist)
        (let ((t2 (first-term L)))
          (adjoin-term
           (make-term (+ (order t1) (order t2))
                      (mul (coeff t1) (coeff t2)))
           (mul-term-by-all-terms t1 (rest-terms L))))))
  (define (add-num-poly x p)
    (make-poly (variable p)
               (add-terms (list (make-term 0 x))
                          (term-list p))))
  (define (mul-num-poly x p)
    (make-poly (variable p)
               (map (lambda (term) (list (car term) (* x (cadr term))))
                    (term-list p))))

  (define (dense->sparse p)
    (let ((d-p (contents p)))
      (let ((v (car d-p))
            (d-L (cdr d-p)))
        (let ((s-L (term-list-dense->sparse d-L)))
          (tag (make-poly v s-L))))))
  (define (term-list-dense->sparse d-L)
    (if (null? d-L)
        '()
        (let ((coe (car d-L))
              (ord (- (length d-L) 1)))
          (adjoin-term
           (make-term ord coe)
           (term-list-dense->sparse (cdr d-L))))))

  ;; interface to the rest of the system
  (define (tag x) (attach-tag 'sparse x))
  (put 'add-poly '(sparse sparse)
       (lambda (p1 p2) (tag (add-poly p1 p2))))
  (put 'add-poly-num '(sparse scheme-number)
       (lambda (p x) (tag (add-num-poly x p))))
  (put 'add-num-poly '(scheme-number sparse)
       (lambda (x p) (tag (add-num-poly x p))))
  (put 'sub-poly '(sparse sparse)
       (lambda (p1 p2) (tag (sub-poly p1 p2))))
  (put 'neg-poly '(sparse)
       (lambda (p) (tag (neg-poly p))))
  (put 'mul-poly '(sparse sparse)
       (lambda (p1 p2) (tag (mul-poly p1 p2))))
  (put 'mul-poly-num '(sparse scheme-number)
       (lambda (p x) (tag (mul-num-poly x p))))
  (put 'mul-num-poly '(scheme-number sparse)
       (lambda (x p) (tag (mul-num-poly x p))))
  (put '=zero?-poly '(sparse)
       (lambda (p) (empty-termlist? (term-list p))))
  (put 'make-poly 'sparse
       (lambda (v t) (tag (make-poly v t))))
  (put-coercion 'dense 'sparse dense->sparse)
  'done)

; tests
(install-scheme-number-package)
(install-polynomial-package)
(install-dense-poly-package)
(install-sparse-poly-package)

(define ca-d (make-dense-polynomial 'x '(2 3 1)))
(define ca-s (make-sparse-polynomial 'x '((2 2) (1 3) (0 1))))

(define cb-d (make-dense-polynomial 'x '(4 0 1 0)))
(define cb-s (make-sparse-polynomial 'x '((3 4) (1 1))))

(define cc-d (make-dense-polynomial 'x '(1 10)))
(define cc-s (make-sparse-polynomial 'x '((1 1) (0 10))))

(define cd-d (make-dense-polynomial 'x '(-4 0 -1 0)))
(define cd-s (make-sparse-polynomial 'x '((3 -4) (1 -1))))

(define ce-d (make-dense-polynomial 'x '(5 0 0 0 0 3 0 0 0)))
(define ce-s (make-sparse-polynomial 'x '((8 5) (3 3))))

(define p1-d (make-dense-polynomial 'y (list ca-d cb-d cc-d)))
(define p1-s (make-sparse-polynomial 'y (list (list 2 ca-s)
                                              (list 1 cb-s)
                                              (list 0 cc-s))))
(define p1-m (make-dense-polynomial 'y (list ca-s cb-d cc-s)))

(define p2-d (make-dense-polynomial 'y (list ca-d cb-d)))
(define p2-s (make-sparse-polynomial 'y (list (list 1 ca-s)
                                              (list 0 cb-s))))
(define p2-m (make-sparse-polynomial 'y (list (list 1 ca-s)
                                              (list 0 cb-d))))

(define p3-d (make-dense-polynomial 'y (list ca-d cd-d cc-d)))
(define p3-s (make-sparse-polynomial 'y (list (list 2 ca-s)
                                              (list 1 cd-s)
                                              (list 0 cc-s))))
(define p3-m (make-dense-polynomial 'y (list ca-s cd-s cc-s)))

(define p4-d (make-dense-polynomial
              'y (list cd-d
                       (make-dense-polynomial 'x '())
                       (make-dense-polynomial 'x '())
                       cc-d
                       (make-dense-polynomial 'x '()))))
(define p4-s (make-sparse-polynomial
              'y (list (list 4 cd-s) (list 1 cc-s))))
(define p4-m (make-sparse-polynomial
              'y (list (list 4 cd-d) (list 1 cc-d))))

(add 2.5 ce-d)
;Value: (polynomial dense x 5 0 0 0 0 3 0 0 2.5)
(add 2.5 ce-s)
;Value: (polynomial sparse x (8 5) (3 3) (0 2.5))

(add cc-d 4)
;Value: (polynomial dense x 1 14)
(add cc-s 4)
;Value: (polynomial sparse x (1 1) (0 14))

(add ca-d cb-d)
;Value: (polynomial dense x 4 2 4 1)
(add ca-s cb-s)
;Value: (polynomial sparse x (3 4) (2 2) (1 4) (0 1))
(add ca-s cb-d)
;Value: (polynomial dense x 4 2 4 1)
(add ca-d cb-s)
;Value: (polynomial sparse x (3 4) (2 2) (1 4) (0 1))

(add cb-d cd-d)
;Value: (polynomial dense x)
(add cb-s cd-d)
;Value: (polynomial dense x)
(add cb-d cd-s)
;Value: (polynomial sparse x)

(add ce-d ca-d)
;Value: (polynomial dense x 5 0 0 0 0 3 2 3 1)
(add ce-s ca-s)
;Value: (polynomial sparse x (8 5) (3 3) (2 2) (1 3) (0 1))

(mul ca-d cc-d)
;Value: (polynomial dense x 2 23 31 10)
(mul ca-s cc-s)
;Value: (polynomial sparse x (3 2) (2 23) (1 31) (0 10))
(mul ca-s cc-d)
;Value: (polynomial dense x 2 23 31 10)

(mul ce-d cd-d)
;Value: (polynomial dense x -20 0 -5 0 0 -12 0 -3 0 0 0 0)
(mul ce-d cd-s)
;Value: (polynomial sparse x (11 -20) (9 -5) (6 -12) (4 -3))

(add p1-d p2-d)
;Value: (polynomial dense y (polynomial dense x 2 3 1)
;                           (polynomial dense x 4 2 4 1)
;                           (polynomial dense x 4 0 2 10))
(add p1-s p2-s)
;Value: (polynomial sparse y (2 (polynomial sparse x (2 2) (1 3) (0 1)))
;                            (1 (polynomial sparse x (3 4) (2 2) (1 4) (0 1)))
;                            (0 (polynomial sparse x (3 4) (1 2) (0 10))))
(add p1-m p2-m)
;Value: (polynomial sparse y (2 (polynomial sparse x (2 2) (1 3) (0 1)))
;                            (1 (polynomial sparse x (3 4) (2 2) (1 4) (0 1)))
;                            (0 (polynomial dense x 4 0 2 10)))
(add p1-s p1-m)
;Value: (polynomial dense y (polynomial sparse x (2 4) (1 6) (0 2))
;                           (polynomial dense x 8 0 2 0)
;                           (polynomial sparse x (1 2) (0 20)))

(mul p2-d p3-d)
;Value: (polynomial dense y (polynomial dense x 4 12 13 6 1)
;                           0
;                           (polynomial dense x -16 0 -8 2 22 31 10)
;                           (polynomial dense x 4 40 1 10 0))
(mul p2-m p3-s)
;Value: (polynomial sparse y (3 (polynomial sparse x (4 4) (3 12) (2 13) (1 6) (0 1)))
;                            (1 (polynomial sparse x (6 -16) (4 -8) (3 2) (2 22) (1 31) (0 10)))
;                            (0 (polynomial sparse x (4 4) (3 40) (2 1) (1 10))))

(mul p2-s p3-m)
;Value: (polynomial dense y (polynomial sparse x (4 4) (3 12) (2 13) (1 6) (0 1))
;                           0
;                           (polynomial sparse x (6 -16) (4 -8) (3 2) (2 22) (1 31) (0 10))
;                           (polynomial sparse x (4 4) (3 40) (2 1) (1 10) (0 0)))

(mul p1-d p4-d)
;Value: (polynomial y dense (polynomial dense x -8 -12 -6 -3 -1 0)
;                           (polynomial dense x -16 0 -8 0 -1 0 0)
;                           (polynomial dense x -4 -40 -1 -10 0)
;                           (polynomial dense x 2 23 31 10)
;                           (polynomial dense x 4 40 1 10 0)
;                           (polynomial dense x 1 20 100)
;                           0)
(mul p1-s p4-m)
;Value: (polynomial sparse y (6 (polynomial dense x -8 -12 -6 -3 -1 0))
;                            (5 (polynomial dense x -16 0 -8 0 -1 0 0))
;                            (4 (polynomial dense x -4 -40 -1 -10 0))
;                            (3 (polynomial dense x 2 23 31 10))
;                            (2 (polynomial dense x 4 40 1 10 0))
;                            (1 (polynomial dense x 1 20 100)))
(mul p4-m p1-m)
;Value: (polynomial dense y (polynomial sparse x (5 -8) (4 -12) (3 -6) (2 -3) (1 -1))
;                           (polynomial dense x -16 0 -8 0 -1 0 0)
;                           (polynomial sparse x (4 -4) (3 -40) (2 -1) (1 -10))
;                           (polynomial sparse x (3 2) (2 23) (1 31) (0 10))
;                           (polynomial dense x 4 40 1 10 0)
;                           (polynomial sparse x (2 1) (1 20) (0 100))
;                           0)

(sub cb-d cd-d)
;Value: (polynomial dense x 8 0 2 0)
(sub cb-s cd-s)
;Value: (polynomial sparse x (3 8) (1 2))
(sub cb-s cd-d)
;Value: (polynomial dense x 8 0 2 0)
(sub cb-d cd-s)
;Value: (polynomial sparse x (3 8) (1 2))

(sub p1-d p2-d)
;Value: (polynomial dense y (polynomial dense x 2 3 1)
;                           (polynomial dense x 4 -2 -2 -1)
;                           (polynomial dense x -4 0 0 10))
(sub p1-s p2-s)
;Value: (polynomial sparse y (2 (polynomial sparse x (2 2) (1 3) (0 1)))
;                            (1 (polynomial sparse x (3 4) (2 -2) (1 -2) (0 -1)))
;                            (0 (polynomial sparse x (3 -4) (0 10))))
(sub p1-s p2-d)
;Value: (polynomial dense y (polynomial sparse x (2 2) (1 3) (0 1))
;                           (polynomial dense x 4 -2 -2 -1)
;                           (polynomial dense x -4 0 0 10))
(sub p1-m p2-s)
;Value: (polynomial sparse y (2 (polynomial sparse x (2 2) (1 3) (0 1)))
;                            (1 (polynomial sparse x (3 4) (2 -2) (1 -2) (0 -1)))
;                            (0 (polynomial sparse x (3 -4) (0 10))))
(sub p1-m p2-m)
;Value: (polynomial sparse y (2 (polynomial sparse x (2 2) (1 3) (0 1)))
;                            (1 (polynomial sparse x (3 4) (2 -2) (1 -2) (0 -1)))
;                            (0 (polynomial dense x -4 0 0 10)))

(sub p1-d p3-d)
;Value: (polynomial dense y (polynomial dense x 8 0 2 0) 0)
(sub p1-s p3-m)
;Value: (polynomial dense y (polynomial sparse x (3 8) (1 2)) 0)
(sub p1-m p3-s)
;Value: (polynomial sparse y (1 (polynomial sparse x (3 8) (1 2))))

(sub p4-d p2-d)
;Value: (polynomial dense y (polynomial dense x -4 0 -1 0)
;                           0 0
;                           (polynomial dense x -2 -2 9)
;                           (polynomial dense x -4 0 -1 0))
(sub p4-s p2-s)
;Value: (polynomial sparse y (4 (polynomial sparse x (3 -4) (1 -1)))
;                            (1 (polynomial sparse x (2 -2) (1 -2) (0 9)))
;                            (0 (polynomial sparse x (3 -4) (1 -1))))
(sub p4-m p2-m)
;Value: (polynomial sparse y (4 (polynomial dense x -4 0 -1 0))
;                            (1 (polynomial sparse x (2 -2) (1 -2) (0 9)))
;                            (0 (polynomial dense x -4 0 -1 0)))