EoPL reading (118) 2.3 Representation Strategies for Data Types

scheme EoPL

理解が微妙なまま進める、というのも手を動かし辛い。とりあえず昨晩のソレをビンゴと見てつき進むしかないな。

Exercise 2.24 のつづき

で、以下のがヒリ出てきた。なんか不調だ。

(add-load-path ".")

(load "term")

(define-datatype subst subst?
  (empty-subst-rec)
  (extended-subst-rec
   (i symbol?)
   (t term?)
   (s subst?)))

(define empty-subst
  (lambda ()
    (empty-subst-rec)))

(define extend-subst
  (lambda (i t s)
    (extended-subst-rec i t s)))

(define apply-subst
  (lambda (s i)
    (cases subst s
	   (empty-subst-rec 
	    ()
	    (eopl:error 'apply-subst
			"No binding for " sym))
	   (extended-subst-rec
	    (item term substitution)
	    (if (eqv? item i)
		term
		(var-term i))))))

試験が以下。昨晩の試験と微妙に違う。

(use gauche.test)

(add-load-path ".")
(load "substitution")

(test-start "substitution")
(test-section "empty-subst")
(test* "apply empty-subst"
       *test-error*
       (apply-subst empty-subst 'a))

(test-section "apply-subst")
(test* "apply ex-subst (var)"
       '(var-term a)
       (apply-subst (extend-subst 'x '(var-term a) empty-subst)
		    'x))
(test* "apply ex-subst (var)"
       '(var-term y)
       (apply-subst (extend-subst 'x '(var-term a) empty-subst)
		    'y))
(test* "apply ex-subst (var)"
       '(app-term (var-exp +) (var-exp x) (constant-exp 1))
       (apply-subst (extend-subst 'x '(app-term (var-exp +) (var-exp x) (constant-exp 1)) empty-subst)
		    'x))

(test-section "extend-subst")

(test-end)

異なる点は

  • empty-subst の手続きを呼び出さなくてはならない
  • 基本的に var-term しか渡されない

という事。微妙さ満点なんですが、以下の subst-in-term を実装して試験書いてみる。

(define subst-in-term
  (lambda (s t)
    (cases term t
           (constant-term (datum) datum)
           (var-term (id) (apply-subst s id))
           (app-term (terms)
                     (let f ((rslt '()) (l terms))
                       (if (null? l)
                           rslt
                           (f (append (list (subst-in-term s (car l)) rslt))
                              (cdr l))))))))

以下の試験を書いて微妙にハマる。上記実装は相当ダウト。

(test-section "subst-in-term")
(let ((s (extend-subst 'x '(var-term a) (empty-subst))))
  (test* "not subst"
	 '(constant-term 1)
	 (subst-in-term s '(constant-term 1)))
  (test* "subst"
	 '(var-term a)
	 (subst-in-term s '(var-term x)))
  (test* "not subst"
	 '(var-term y)
	 (subst-in-term s '(var-term y)))
  (test* "not subst"
	 '(app-term ((constant-term 1) (constant-term 2)))
	 (subst-in-term s '(app-term ((constant-term 1) (constant-term 2)))))
  (test* "subst"
	 '(app-term ((var-term a) (var-term y) (constant-term 1)))
	 (subst-in-term s '(app-term ((var-term x) (var-term y) (constant-term 1)))))
  )

バグってたのは以下

  • constant-term の時に datum のみ戻すのはダメで (constant-term datum) を戻す
  • app-term の処理で最終的に戻すのは rslt ではなくて (append (list 'app-term) (list rslt)) を戻す
  • l が null? でない場合、car 要素を subst-in-term した戻りは末端に append
    • しかも append の括弧が上記実装では微妙

で最終的に以下。

(define subst-in-term
  (lambda (s t)
    (cases term t
           (constant-term (datum) (constant-term datum))
           (var-term (id) (apply-subst s id))
           (app-term (terms)
                     (let f ((rslt '()) (l terms))
                       (if (null? l)
                           (append (list 'app-term) (list rslt))
                           (f (append rslt (list (subst-in-term s (car l))))
                              (cdr l))))))))

これ、次の問題込みで検討した方が良さげ。しかも EoPL 一旦休憩して SICP の図形言語方面に去ったりなんかしようと思ってます。