EoPL reading (116) 2.3 Representation Strategies for Data Types

Exercise 2.24 のつづき

今日の晩メシ担当らしい。作成開始するまでの間で全体見つつ substitution を整理してみる。とりあえず最終的に作成する 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 (apply-subst s (car l)) rslt))
                              (cdr l))))))))

上記とすると empty-subst は error を呼び出してしまうと微妙?
# いいのかな ...
これデフォとしたら現状の extend-subst の実装はダウトだな。

(define extend-subst
  (lambda (i t s)
    (lambda (sym)
      (cases term t
	     (var-term 
	      (id)
	      (if (eqv? id i)
		  (var-term sym)
		  (apply-subst s i)))
	     (else
	      (apply-subst s i))))))

それ以前の問題として全然ダメって話もありますが ...
# 上記 subst-in-term も微妙にダウトか
# apply-subst じゃなくて subst-in-term を呼ばねぇとダメ

てーコトは extend-subst に渡される term は var-term キメって事にしよ。方向として微妙かもしれませんが、これで試験を書きなおしたのが以下。

あら?

これって全部置き換えられるな。上記実装をビンゴとすると subst-in-term 手続きで

           (var-term (id) (apply-subst s id))

apply-subst に渡している id は置き換え元の var-term な id という事は extend-subst が渡す手続きの引数になる。てーコトは

(define extend-subst
  (lambda (i t s)
    (lambda (sym)
      (cases term t
	     (var-term (id)
		       (if (eqv? sym i)
			   t

という事にすれば良いのか。問題文の意図が理解できてないのがバレバレですね。なんとなくまだ腑にオチてないのが sym と i が eqv? でない場合どうするか、という事。
この理解はダウトな気がしてきました。t が old で i が new って理解だと

(define extend-subst
  (lambda (i t s)
    (lambda (sym)
      (cases term t
	     (var-term (id)
		       (if (eqv? id sym)
			   (var-term i)
                           t))

みたいなカンジ? あ、違うや

		       (if (eqv? id sym)
			   (var-term i)
                           (var-term sym))

になるのか。試験が以下 (一部のみ)。

(test* "apply ex-subst (var)"
       '(var-term a)
       (apply-subst (extend-subst 'a '(var-term x) empty-subst)
		    'x))
(test* "apply ex-subst (var)"
       '(var-term y)
       (apply-subst (extend-subst 'a '(var-term x) empty-subst)
		    'y))

substitution なオブジェクトには置き換え対象の term と置換後の symbol が入ってて、渡された symbol と term の symbol が eqv? だったら置き換える、という理解。
とりあえずメシ作成に着手します。