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? だったら置き換える、という理解。
とりあえずメシ作成に着手します。