EoPL reading (79) 2.2 An Abstraction for Inductive Data Type
lisp と将棋エンジンに取り組んでいるヒトの記事を見た。具体的なアウトプットって良いなぁ。
Exercise 2.10
とりあえず以下をでっち上げてみました。
(add-load-path ".") (load "define-datatype") (define all-ids (lambda (exp) (cases expression exp (var-exp (id) (list id)) (lambda-exp (id body) (append (list id) (all-ids body))) (app-exp (rator rand) (append (all-ids rator) (all-ids rand))))))
で、順に試験を追加していきつつ、挫折。
(use gauche.test) (add-load-path ".") (load "define-datatype") (load "expression") (load "all-ids") (test-start "all-ids") (test-section "all-ids") (test* "all-ids (1)" '(w2 w1 w0 w3) (all-ids '(app-exp (lambda-exp w2 (app-exp (var-exp w1) (var-exp w0))) (var-exp w3)))) (test* "all-ids (2)" '(w0) (all-ids '(var-exp w0))) (test* "all-ids (3)" '(w2 w0) (all-ids '(lambda-exp w2 (var-exp w0)))) (test* "all-ids (4)" '(w0 w1) (all-ids '(app-exp (lambda-exp w0 (var-exp w0)) (var-exp w1)))) (test-end)
最後の試験は (w0 w0 w1) が戻る。戻りに重複があるかどうかを確認してないので当たり前の話。これは繰り返しで書かないとどうにもならんか。
で、試行錯誤の後に以下がでっち上がる。上記試験にはパス。勘違いの痕跡も含め。
(add-load-path ".") (load "define-datatype") (define all-ids (lambda (exp) (let f ((rslt '()) (exp exp)) (cases expression exp (var-exp (id) (if (memv id rslt) rslt (append rslt (list id)))) ;; (var-exp (id) (append rslt (list id))) ;; (var-exp (id) (list id)) (lambda-exp (id body) (f (append rslt (list id)) body)) (app-exp (rator rand) ;; (f (append rslt (f rslt rator)) rand)))))) (f (f rslt rator) rand))))))
で、以下の試験を書きました。
(use gauche.test) (add-load-path ".") (load "define-datatype") (load "expression") (load "fresh-id") (test-start "fresh-id") (test-section "fresh-id") (test* "fresh-id (1)" 'w4 (fresh-id (app-exp (lambda-exp 'w2 (app-exp (var-exp 'w1) (var-exp 'w0))) (var-exp 'w3)) "w")) (test-end)
試験パス、な土曜 1300 昼メシはこれから。