SICP 読み (162) 4.1.3 評価器のデータ構造

SICP scheme

問題 4.13

方法としてどんなのがあるか、というと

  • カレントな環境からのみ結合を除去
  • トップレベルまで探索を行ない、最初に発見した束縛のみを除去
  • トップレベルまで探索を行ない、ある限りの束縛を除去

なんですが、どうするべきなのかなぁ。
遡りたくない、のは楽したいからなのか直感なのかは不明。正当化するにあたって説得力のある材料をきちんと展開できない気がします。スルーしようかな (を

材料

えーと、define がカレントな環境のみを相手にしてるのは何故だろう。上位レベルで束縛があってもカレントにカブせてしまう形になっている。ぶっちゃけ面倒だから、という事しか思いつかないあたりが微妙すぎ。
ただ、自分の責任の範疇ではないフレーム (しかもポジション的に上位) に対して手を加える事ができる、とゆーのは微妙に感じます。フィーリングでモノを言って申し訳ないんですが。

メモ

上記をビンゴとして考えてみる。まずフレームは以下の形式。

((a b c) (1 2 3))

これ、削除ってメンドいなぁ。b という変数を unbind! する場合、どうすれば良いか、というとこんな感じ??

(define (xxx vars vals var)
  (define (make-list a b)
    (if (null? a) 
	(cons b '())
	(append a (cons b '()))))
  (let f ((vars vars) (vals vals) (rvar '()) (rval '()))
    (cond ((null? vars) (cons rvar rval))
	  ((eq? var (car vars))
	   (f (cdr vars) (cdr vals) rvar rval))
	  (else
	   (f (cdr vars) (cdr vals) (make-list rvar (car vars))
	      (make-list rval (car vals)))))))

ただ、この手続きはリストを返すんだよねぇ。この戻りをフレームではなくて環境の car に設定すれば OK なのかなぁ。

(define (unbind! var env)
  (define (new-frame vars vals)
    (define (make-list a b)
      (if (null? a)
	  (cons b '())
	  (append a (list b))))
    (let new-frame-iter ((vars vars) (vals vals) (rvar '()) (rval '()))
      (cond ((null? vars) (cons rvar rval))
	    ((eq? var (car vars))
	     (new-frame-iter (cdr vars) (cdr vals) rvar rval))
	    (else
	     (new-frame-iter (cdr vars)
			     (cdr vals)
			     (make-list rvar (car vars))
			     (make-list rval (car vals)))))))
  (let ((f (first-frame env)))
    (set-car! env (new-frame (frame-variables f)
			     (frame-values f)))))

どうだろ。以下の試験にパスしてます。

#!/usr/bin/env gosh

(use test.unit)
(require "4.1.2")

(define-test-suite "4.1.2"

  ("4.13"
   ("unbind!"
    (let ((e (extend-environment '(a b c d) 
				 '(1 2 3 4) 
				 the-global-environment)))
      (unbind! 'b e)
      (assert-error (lambda () (lookup-variable-value 'b e)))
      (assert-equal '(a c d) (frame-variables (car e)))
      (assert-equal '(1 3 4) (frame-values (car e)))
      (define-variable! 'b 3 e)
      (assert-equal 3 (lookup-variable-value 'b e))
      (assert-equal '(b a c d) (frame-variables (car e)))
      (assert-equal '(3 1 3 4) (frame-values (car e)))
      )
    )
   )
 )

無論、一発で上の解にたどり着いた訳では全然なくっていくつかの試行錯誤を経ています。