問題4.11-4.12

環境をいじります。

4.11

フレームの表現形式を変更するみたいです。map使うだけです。
読み返して気づいたけどこのframeの手続きって各frameが必ず空でないから成り立つんですね。

(define (make-frame variables values)
  (map cons variables values))
(define (frame-variables frame) (map car frame))
(define (frame-values frame) (map cdr frame))
(define (add-binding-to-frame! var val frame)
  (set-cdr! frame (cons (cons var val) (cdr frame))))

add-binding-to-frame!がちょっと気持ち悪いですね。でも他に思いつかない。frameの先頭にダミーでもあれば気持ち悪くないんですが。
あと、効率的にはmake-frame,frame-variables,frame-valuesは以前の方がよいです(そんな大したものではないと思うけど)。前はmapなんてしなくてよかったので。
ということで前のに戻しておきます。

4.12

眺めてるとscanが抽象できるように思います。env-loopも、define-variable!は構造からthe-empty-environmentに行き着くことがないので、if以降はどの手続きでも同じ構造になり、これも抽象できそうです。
まずscanを見てみます。cond節のpredicateが全部一緒です。varを渡せば大丈夫そうです。
次にcondのbodyに注目します。上からbody1, body2, body3とします。else節のbody3は全部一緒なので問題ないです。
body1とbody2は一見ばらばらですが、全部一引数の手続きとして置き換えるとうまく抽象出来ます。ただし、body2では全部valsが使われていることに注意する必要があります。これはscanが再帰で呼び出される度に値が変わるので、scanの中で直接指示しなければなりません。
また、body1の引数としてenvとframeがあげられるのですが、frameは(first-frame env)で得ることができるので、scan内部に直接envを書いておいてもいいはずです。(つまり手続きの引数をscanの引数として渡す必要がないということです。)
scanのパラメータにbody1の手続き,body2の手続きを指定するf1,f2を追加します。これらは次のように置き換えます。

;;;lookup-variable-value
;body1
;f1=(lambda (x) (env-loop (enclosing-environment x)))で
;(env-loop (enclosing-environment env)) => (f1 env)

;body2
;f2=car
;(car vals) => (f2 vals)

;;;set-variable-value!
;body1
;lookup-variable-valueと同じ

;body2
;f2=(lambda (x) (set-car! x val))で
;(set-car! vals val) => (f2 vals)

;;;define-variable!
;body1
;f1=(lambda (x) (add-binding-to-frame! var val (first-frame x)))で
;(add-binding-to-frame! var val frame) => (f1 env)

;body2
;set-variable-value!と同じ

これで準備ができました。scanを抽象してみます。

(define (scan env var vars vals f1 f2)
  (cond ((null? vars) (f1 env))
        ((eq? var (car vars)) (f2 vals))
        (else (scan env var (cdr vars) (cdr vals) f1 f2))))

意味としては、このフレーム内でvarの束縛が見つからなかった場合(f1 env)(つまり環境をf1で操作)をする、見つかればvarに束縛されている値が先頭のリストvalsに対して(f2 vals)を行う、という感じです。
scanを抽象化できたので、env-loopの抽象の見通しもよくなりました。
env-loopのif以降を見ると、scanの適用以外の部分ではenvしか使っていないことが分かります。なので、env-loopには引数として、scanの引数(これは各手続きで指定する)と同じものをとることにするといいはずです。
次のようにできます。

(define (env-loop env var vars vals f1 f2)
  (if (eq? env the-empty-environment)
      (error "Unbound variable" var)
      (scan env var vars vals f1 f2)))

これでscanとenv-loopが抽象化できました。でもこれはscanを呼び出しているだけで、意味としてはenv-loop(環境を渡る)ではないように思います。なので名前を変えます。scan-frameみたいな感じでしょうか。scanはscan-frame-bodyにします。
ところで、scan-frame-bodyはenv,var,f1,f2がその内部で変更されることがありません。なのでscan-frameの内部手続きにしてこれらの引数を削ってしまいます。
また、scan-frameについても、envが渡ってるならvarsとvalsを引数として保持する必要はないので、これも削っちゃいます。

(define (scan-frame env var f1 f2)
  (define (scan-frame-body vars vals)
    (cond ((null? vars) (f1 env))
          ((eq? var (car vars)) (f2 vals))
          (else (scan-frame-body (cdr vars) (cdr vals)))))
  (if (eq? env the-empty-environment)
      (error "Unbound variable" var)
      (let ((frame (first-frame env)))
        (scan-frame-body (frame-variables frame) (frame-values frame)))))

これでやっと抽象できたので、各手続きを再定義したいと思います。

(define (lookup-variable-value var env)
  (define (env-loop env)
    (scan-frame env
                var
                (lambda (x) (env-loop (enclosing-environment x)))
                car))
  (env-loop env))

(define (set-variable-value! var val env)
  (define (env-loop env)
    (scan-frame env
                var
                (lambda (x) (env-loop (enclosing-environment x)))
                (lambda (x) (set-car! x val))))
  (env-loop env))

(define (define-variable! var val env)
  (scan-frame env
              var
              (lambda (x) (add-binding-to-frame! var val (first-frame x)))
              (lambda (x) (set-car! x val))))

ちゃんと動きます。

;;; M-Eval input:
(define x 3)
;;; M-Eval value:
ok

;;; M-Eval input:
(define lst '(1 2 3 4))
;;; M-Eval value:
ok

;;; M-Eval input:
(define (f n)
  (if (= n 0)
      0
      (+ n (f (- n 1)))))
;;; M-Eval value:
ok

;;; M-Eval input:
(f 10)
;;; M-Eval value:
55

ちょっとややこしい問題でした。あと抽象度高いから逆に分かりにくいような気もしないでもないです。
あと、マクロを使った方がもっとわかりやすく簡単に書けるんだろうなぁと思いました。やっぱりOn Lispほしいな。

4.12で疲れたので今日はここまで。