EoPL reading (115) 2.3 Representation Strategies for Data Types

Exercise 2.24

現実トウヒで以下なプロトタイプを作ってみた。
まず試験。

(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-term a)
       (apply-subst (extend-subst 'x '(var-term x) empty-subst)
		    'a)
       )

(test-section "extend-subst")

(test-end)

で、実装。

(add-load-path ".")

(load "term")

(define empty-subst
  (lambda ()
    (lambda (sym)
      (eopl:error 'empty-subst
		  "No binding for " sym))))

(define apply-subst
  (lambda (s i)
    (s i)))

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

これ、app-term が渡されたら微妙。これは procedural な実装なんですが、現時点にて

(apply (extend-subst x (var-term x) (empty-subst)) 'a)

みたいな形にしか対応してません。実装によると

(apply (extend-subst y (var-term y) (extend-subst x (var-term x) (empty-subst)))
       'a)

とかって (var-term a) が戻ってくる?
# あまり上記な形って無いのかどうか微妙

もう少し

検討予定ですが、まだ割り込み多い。