SICP 読み (85) 2.5.3 例: 記号代数
問題 2.90 の続き
なんつーか進捗が悪くて微妙。昨晩、dense な試験を一気に作ってドハマリだったんで、順番に確認入れながら作成を。
まず、dense-termlist から。試験は以下ですが自信ナシ。
("dense-termlist (first-term)"
("no element"
(assert-equal '()
(apply-generic 'first-term '(dense)))
)
("1 element"
(assert-equal '(term 0 5)
(apply-generic 'first-term '(dense (0 5))))
)
("6 elements"
(assert-equal '(term 5 3)
(apply-generic 'first-term
'(dense (5 3) (4 4) (3 5) (2 6) (1 7) (0 8))))
)
)
("dense-termlist (rest-terms)"
("1 element"
(assert-equal '(dense) (apply-generic 'rest-terms '(dense (2 5))))
)
("6 elements"
(assert-equal '(dense (7 4) (6 5) (4 6) (2 7) (0 8))
(apply-generic 'rest-terms
'(dense (9 3) (7 4) (6 5) (4 6) (2 7) (0 8))))
)
)
("dense-termlist (empty-termlist?)"
("empty dense-termlist"
(assert-true (apply-generic 'empty-termlist? '(dense)))
)
("zero"
(assert-true (apply-generic 'empty-termlist? '(dense (0 0))))
)
("no empty"
(assert-false (apply-generic 'empty-termlist? '(dense (0 1))))
)
)
("dense-termlist (the-empty-termlist) -- no use"
("..."
(assert-true (apply-generic 'empty-termlist?
((get 'the-empty-termlist 'dense))))
)
("..."
(assert-equal '(dense) ((get 'the-empty-termlist 'dense)))
)
)
("dense-termlist (adjoin-term)"
("3x+4 + 2x^2"
(assert-equal '(dense (2 2) (1 3) (0 4))
((apply-generic 'adjoin-term '(dense (1 3) (0 4))) '(term 2 2)))
)
("0 + 2x^2"
(assert-equal '(dense (2 2))
((apply-generic 'adjoin-term '(dense)) '(term 2 2)))
)
("x + 2x^3"
(assert-equal '(dense (3 2) (1 1))
((apply-generic 'adjoin-term '(dense (1 1))) '(term 3 2)))
)
)で、実装を。試験によれば
- first-term
- 項リストが空だったら '() を返してよい (本当かなぁ
- 項リストが空でなければ car に 'dense というタグを付加して戻す
- rest-terms
- 項リストに 1 要素しかない場合、空の項リストを返す
- 項リストの cdr を返す
- empty-termlist?
- 項リストが空なら真
- 項リストが 0 でも真 (これは dense なソレでは微妙?)
- それ以外は偽
- the-empty-termlist (使ってない)
- 空の項リストを返す
- adjoin-term
- 項リストに項を追加
- 基本的には項リストの最高次の項より高次の項が追加される
基本的には問題 2.88 あたりの実装をパクれば良いはず。
で、試験してみたんですが、
- first-term に空の項リストを渡すのは dense な仕様としてあり得ん。ので、試験は抹消。
- term にして返却してない輩がおられる (first-term)
- (dense (0 0)) は empty と判断してない (ってかあり得ないのかな?
- (term 2 2) 等をそのまま cons しとる (adjoin-term)
- tag を付けて返してない (adjoin-term)
というトホホな結果に。直そう。
てーか、first-term に空の項リストを渡すな、は仕様としても empty なソレの違いは許容範囲内なのかなぁ。細かい部分ですが気になる。現時点での dense-termlist な実装を以下に。
(define (install-dense-termlist)
(define (adjoin-term term-list)
(lambda (term)
(if (=zero? (coeff term))
(tag term-list)
(tag (cons (list (order term) (coeff term)) term-list)))))
(define (first-term term-list) (make-term (car (car term-list))
(cadr (car term-list))))
(define (rest-terms term-list) (cdr term-list))
(define (the-empty-termlist) '())
(define (empty-termlist? term-list) (null? term-list))
(define (tag t) (attach-tag 'dense t))
(put 'first-term '(dense)
(lambda (t) (first-term t)))
(put 'rest-terms '(dense)
(lambda (t) (tag (rest-terms t))))
(put 'empty-termlist? '(dense)
(lambda (t) (empty-termlist? t)))
(put 'the-empty-termlist 'dense
(lambda () (tag (the-empty-termlist))))
(put 'adjoin-term '(dense)
(lambda (t) (adjoin-term t)))
'done)一応試験はパスしているようなので、dense-operation な試験を。これもコピペベースで大丈夫かなぁ。まず足し算から。
("dense polynomial operation (add)"
("different variable"
(assert-error (lambda () (add (make-dense-polynomial 'x '((0 5)))
(make-dense-polynomial 'y '((0 5))))))
)
("add 0 to 5 (1)"
(let ((test (add (make-dense-polynomial 'x '((0 0)))
(make-dense-polynomial 'x '((0 5))))))
(assert-equal 'polynomial (car test))
(assert-equal 'x (cadr test))
(assert-equal '(dense (0 5)) (cddr test)))
)
("add 0 to 5 (2)"
(let ((test (add (make-dense-polynomial 'x '())
(make-dense-polynomial 'x '((0 5))))))
(assert-equal 'polynomial (car test))
(assert-equal 'x (cadr test))
(assert-equal '(dense (0 5)) (cddr test)))
)
("add 5 to 0 (1)"
(let ((test (add (make-dense-polynomial 'x '((0 5)))
(make-dense-polynomial 'x '((0 0))))))
(assert-equal 'polynomial (car test))
(assert-equal 'x (cadr test))
(assert-equal '(dense (0 5)) (cddr test)))
)
("add 5 to 0 (2)"
(let ((test (add (make-dense-polynomial 'x '((0 5)))
(make-dense-polynomial 'x '()))))
(assert-equal 'polynomial (car test))
(assert-equal 'x (cadr test))
(assert-equal '(dense (0 5)) (cddr test)))
)
("normal"
(assert-equal '(polynomial x dense (5 3) (2 2) (0 4))
(add (make-dense-polynomial 'x '((5 2) (2 1) (0 2)))
(make-dense-polynomial 'x '((5 1) (2 1) (0 2)))))
)
("x+2 + 2x^2+2x+2 -> 2x^2+3x+4"
(assert-equal '(polynomial x dense (5 2) (3 3) (1 4))
(add (make-dense-polynomial 'x '((3 1) (1 2)))
(make-dense-polynomial 'x '((5 2) (3 2) (1 2)))))
)
("2x^2+2x+2 + x+2 -> 2x^2+3x+4"
(assert-equal '(polynomial x dense (2 2) (1 3) (0 4))
(add (make-dense-polynomial 'x '((2 2) (1 2) (0 2)))
(make-dense-polynomial 'x '((1 1) (0 2)))))
)
("0x^3+0x^2+0x+0 + x^3+2x^2+3x+4 -> x^3+2x^2+3x+4"
(assert-equal '(polynomial x dense (3 1) (2 2) (1 3) (0 4))
(add (make-dense-polynomial 'x '((3 0) (2 0) (1 0) (0 0)))
(make-dense-polynomial 'x '((3 1) (2 2) (1 3) (0 4)))))
)
("x^3+2x^2+3x+4 + 0x^3+0x^2+0x+0 -> x^3+2x^2+3x+4"
(assert-equal '(polynomial x dense (3 1) (2 2) (1 3) (0 4))
(add (make-dense-polynomial 'x '((3 1) (2 2) (1 3) (0 4)))
(make-dense-polynomial 'x '((3 0) (2 0) (1 0) (0 0)))))
)
("0 + x^3+2x^2+3x+4 -> x^3+2x^2+3x+4"
(assert-equal '(polynomial x dense (3 1) (2 2) (1 3) (0 4))
(add (make-dense-polynomial 'x '())
(make-dense-polynomial 'x '((3 1) (2 2) (1 3) (0 4)))))
)
("x^3+2x^2+3x+4 + 0 -> x^3+2x^2+3x+4"
(assert-equal '(polynomial x dense (3 1) (2 2) (1 3) (0 4))
(add (make-dense-polynomial 'x '((3 1) (2 2) (1 3) (0 4)))
(make-dense-polynomial 'x '())))
)
("1 - 1 -> 0"
(assert-equal '(polynomial x dense)
(add (make-dense-polynomial 'x '((0 1)))
(make-dense-polynomial 'x '((0 -1)))))
)
)基本的に sparse のソレをコピペ。パス。次はかけ算を。
("dense polynomial operation (mul)"
("different variable"
(assert-error (lambda () (mul (make-dense-polynomial 'x '((0 5)))
(make-dense-polynomial 'y '((0 5))))))
)
("p1 is not variable"
(assert-error (lambda () (mul (make-dense-polynomial 1 '((0 5)))
(make-dense-polynomial 'x '((0 5))))))
)
("p2 is not variable"
(assert-error (lambda () (mul (make-dense-polynomial 'x '((0 5)))
(make-dense-polynomial 2 '((0 5))))))
)
("1 * 1 -> 1"
(assert-equal '(polynomial x dense (0 1))
(mul (make-dense-polynomial 'x '((0 1)))
(make-dense-polynomial 'x '((0 1)))))
)
;; !! it's not _the-empty-termlist_ !!
;; mmmm....
("0 * 1 -> 0"
(assert-equal '(polynomial x dense)
(mul (make-dense-polynomial 'x '())
(make-dense-polynomial 'x '((0 1)))))
)
("1 * 0 -> 0"
(assert-equal '(polynomial x dense)
(mul (make-dense-polynomial 'x '((0 1)))
(make-dense-polynomial 'x '())))
)
("0 * 1 -> 0"
(assert-equal '(polynomial x dense)
(mul (make-dense-polynomial 'x '((0 0)))
(make-dense-polynomial 'x '((0 1)))))
)
("1 * 0 -> 0"
(assert-equal '(polynomial x dense)
(mul (make-dense-polynomial 'x '((0 1)))
(make-dense-polynomial 'x '((0 0)))))
)
("6x+5 * 2x^2+3 -> 12x^3+10x^2+18x+15"
(assert-equal '(polynomial x dense (3 12) (2 10) (1 18) (0 15))
(mul (make-dense-polynomial 'x '((1 6) (0 5)))
(make-dense-polynomial 'x '((3 2) (0 3)))))
)
)微妙ですが勘弁して下さい。で、試験したんですが 1 failure との事。
expected:<(polynomial x dense (3 12) (2 10) (1 18) (0 15))> but was:<(polynomial x dense (4 12) (3 10) (1 18) (0 15))> in 6x+5 * 2x^2+3 -> 12x^3+10x^2+18x+15
あらら? なんかヤッチャってるぽ。
と思ったら、2x^3 にしてるし ...
# 上記コードの一番下部分ですね。とほほほ。
次は =zero? と neg ですが一気にコピペ。いくつか通りそうにない (仕様的に) んがありますが構わず書く。
("dense polynomial operation (=zero?)"
("() is zero"
(assert-true (=zero? (make-dense-polynomial 'x '())))
)
("() is zero (2)"
(assert-true (=zero? '(polynomial x dense)))
)
("(0 0 0 0) is zero"
(assert-true (=zero? '(polynomial x dense (3 0) (2 0) (1 0) (0 0))))
)
("(y + 1)x + (-y - 1)x is zero"
(let ((py1 (make-dense-polynomial 'y '((1 1) (0 1))))
(py2 (make-dense-polynomial 'y '((1 -1) (0 -1)))))
(assert-true (=zero? (add (make-dense-polynomial 'x '((1 py1) (0 0)))
(make-dense-polynomial 'x ((1 py2) (0 0)))))))
)
)
("dense polynomial operation (neg)"
("first (1x - 1x = 0)"
(assert-true (=zero? (add (make-dense-polynomial 'x '((1 1))
(neg (make-dense-polynomial 'x '((1 1))))))))
)
("2nd (1x - 0 = 1x)"
(let ((p (make-dense-polynomial 'x '((1 1)))))
(assert-equal p (add p (neg (make-dense-polynomial 'x '())))))
)
("3rd (1x - 0x = 1x)"
(let ((p1 (make-dense-polynomial 'x '((1 1))))
(p2 (make-dense-polynomial 'x '())))
(assert-equal p1 (add p1 (neg p2))))
)
("4th polynomial neg"
(let ((p1 (make-dense-polynomial 'x '((5 1) (3 2) (1 3) (0 4))))
(p2 (make-dense-polynomial 'x '((5 -1) (3 -2) (1 -3) (0 -4)))))
(assert-equal p1 (neg p2))
(assert-equal p2 (neg p1)))
)
)で、試験したら不具合出た。
expected:<#t> but was:<#f> in (0 0 0 0) is zero E ./test/test-2.5.3.scm:534: (assert-true (=zero? (add (make-dense-polynomial 'x '((1 py1) (0 0))) (make-dense-polynomial 'x ((1 py2) (0 0)))))) Error occurred in (y + 1)x + (-y - 1)x is zero *** ERROR: invalid application: (0 0) ./test/test-2.5.3.scm:534: (assert-true (=zero? (add (make-dense-polynomial 'x '((1 py1) (0 0))) (make-dense-polynomial 'x ((1 py2) (0 0)))))) -- (test case) dense polynomial operation (neg): E ./test/test-2.5.3.scm:541: (assert-true (=zero? (add (make-dense-polynomial 'x '((1 1)) (neg (make-dense-polynomial 'x '((1 1)))))))) Error occurred in first (1x - 1x = 0) *** ERROR: wrong number of arguments for #<closure make-dense-polynomial> (required 2, got 3) ./test/test-2.5.3.scm:541: (assert-true (=zero? (add (make-dense-polynomial 'x '((1 1)) (neg (make-dense-polynomial 'x '((1 1))))))))
dense は null? が真にならんと empty とは見ないので_(0 0 0 0) is zero_という試験は削除の方向で。次の_(y + 1)x + (-y - 1)x is zero_はなんかおかしい。add の第二引数な make に渡している引数が quote されとらん。しかも 0 になってるな。あ、0 は良いのか。
がしかし、quote 付けたら違うエラーになった。最後のヤツは括弧が足りてない。add に渡している最初の make を閉じる括弧。で、違うエラーってのが以下。
./lib/2.5.3.scm:122: (make-term (order t1) (add (coeff t1) (coeff t2))) Error occurred in (y + 1)x + (-y - 1)x is zero *** ERROR: Bad tagged datum -- TYPE TAG py1 ./lib/2.5.3.scm:122: (make-term (order t1) (add (coeff t1) (coeff t2)))
quote してるから変数として評価されてません。試験を以下のように修正。
("(y + 1)x + (-y - 1)x is zero"
(let ((py1 (make-dense-polynomial 'y '((1 1) (0 1))))
(py2 (make-dense-polynomial 'y '((1 -1) (0 -1)))))
(assert-true (=zero? (add (make-dense-polynomial 'x (list (list 1 py1)
'(0 0)))
(make-dense-polynomial 'x (list (list 1 py2)
'(0 0)))))))
)一応 ut は全部通った (はず)。
$ test/run-test.scm -vv - (test suite) 2.5.3 -- (test case) install package: .... -- (test case) term: ... -- (test case) make polynomial: .. -- (test case) sparse-termlist (first-term): ... -- (test case) sparse-termlist (rest-terms): .. -- (test case) sparse-termlist (empty-termlist?): ... -- (test case) sparse-termlist (the-empty-termlist) -- no use: .. -- (test case) sparse-termlist (adjoin-term): ... -- (test case) sparse polynomial operation (add): ............. -- (test case) sparse polynomial operation (mul): ......... -- (test case) sparse polynomial operation (=zero?): .... -- (test case) sparse polynomial operation (neg): .... -- (test case) dense-termlist (first-term): .. -- (test case) dense-termlist (rest-terms): .. -- (test case) dense-termlist (empty-termlist?): .. -- (test case) dense-termlist (the-empty-termlist) -- no use: .. -- (test case) dense-termlist (adjoin-term): ... -- (test case) dense polynomial operation (add): ............. -- (test case) dense polynomial operation (mul): ......... -- (test case) dense polynomial operation (=zero?): ... -- (test case) dense polynomial operation (neg): .... 92 tests, 112 assertions, 112 successes, 0 failures, 0 errors Testing time: 0.029567 $
もう少しチェック入れてみて、大体 OK なようだったら完了とゆー事にして別途ソースをのっけておきます。
