EoPL reading (117) 2.3 Representation Strategies for Data Types

Exercise 2.24 のつづき

直前エントリにて

substitution なオブジェクトには置き換え対象の term と置換後の symbol が入ってて、渡された symbol と term の symbol が eqv? だったら置き換える、という理解。

と思ったんですが、逆かな、って思いはじめてます。
例えば x を (+ q 1) とかに置き換える、というケースには対応できない。ので substitution なオブジェクトには置き換え後の term と置き換え対象の symbol が入ってて、手続きに渡された sym と symbol が eqv? だったら term を戻す、という方向で。
上記な条件の else だと (var-term sym) を戻せば良いはず。割り込み入ったんで、その後実装を検討して別途追記予定ッス。

着手

色々割り込み処理。# 買い物に行ったり云々
で、試験を以下に変更。

(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))

extend-subst の実装が以下。

(define extend-subst
  (lambda (i t s)
    (lambda (sym)
      (cases term t
	     (var-term (id)
		       (if (eqv? i sym)
			   t
			   (var-term sym)))
	     (else
	      (eopl:error 'extend-subst
			  "not var-term " t))))))

当たり前ですが試験にパスしてます。あ、これ駄目だな。t の値で条件判定はしちゃいかん。cases な判定は不要か。

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

手続き定義が凄く simple になりました。
# var-term しか相手にしないので当たり前ですが

以下な試験を追加してパス。

(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))

なんとなくこっちの方が substitution 的に良いカンジです。これを基に abstract syntax tree な実装を検討してみます。