問題4-11〜13

SICP

｢4.1.3 評価器のデータ構造｣では評価器の内部的なロジック、特に環境を操作するための定義の詳細について述べられています。｢3.2 評価の環境モデル｣を読み返しながら、本文で描かれているコードを解読していきました。
問題4-11。フレームの表現方法を変更します。本文では、束縛名のリストと束縛値のリストの対で表現されていましたが、この問題では、各束縛の対を作って、その対のリストがフレームであるようなデータ構造で表現します。フレームの中身を操作するインターフェイスは変更せず、その内部ロジックだけを変更することにします。

(define (make-frame variables values)
  (if (null? variables)
      '()
      (cons (cons (car variables) (car values))
            (make-frame (cdr variables) (cdr values)))))

(define (frame-variables frame)
  (map car frame))

(define (frame-values frame)
  (map cdr frame))

(define (add-binding-to-frame! var val frame)
  (cons frame (cons var val)))

束縛名のリストを取得する手続きframe-variablesは、それぞれの束縛の対からcarで束縛名を取得し、そのリストを作成します。束縛値のリストを取得する手続きframe-valuesについても同様です。frameに新しい束縛を追加する場合は、ただ単に、frameに束縛名と束縛値の対をconsしてやればよさそうです。
問題4-12。set-variable-value!/define-variable!/lookup-variable-valueの中に存在している似たようなロジックとして、渡された環境の中から指定された束縛を探していくscanという手続きがあります。また、scanの呼び出し方も、first-frameの束縛データを渡しているという点で似ています。これらの点を抽象的に表現する手続きをbinds-controllerとして、その手続きに、操作対象となっている環境(env)、検索対象となる束縛名(var)、渡された環境そのものが存在しなかった場合のアクション(null-env-proc)、環境の中に渡された束縛名がなかった場合のアクション(unmatched-proc)、渡された束縛名を発見した場合のアクション(found-proc)を、引数として渡すことにします。

(define (binds-controller env var null-env-proc unmatched-proc found-proc)
  (define (scan vars vals)
    (cond ((null? vars)
           (unmatched-proc env))
          ((eq? var (car vars))
           (found-proc vals))
          (else (scan (cdr vars) (cdr vals)))))
  (if (eq? env the-empty-environment)
      (null-env-proc)
      (let ((frame (first-frame env)))
        (scan (frame-variables frame)
              (frame-values frame)))))

(define (lookup-variable-value var env)
  (binds-controller env
                    var
                    (lambda () (error "Unbound variable" var))
                    (lambda ()
                      (lookup-variable-value var (enclosing-environment env)))
                    (lambda (vals)
                      (car vals))))

(define (set-variable-value! var val env)
  (binds-controller env
                    var
                    (lambda () (error "Unbound variable -- SET!" var))
                    (lambda ()
                      (set-variable-value! var val (enclosing-environment env)))
                    (lambda (vals)
                      (set-car! vals val))))

(define (define-variable! var val env)
  (binds-controller env
                    var
                    (lambda () ())
                    (lambda ()
                      (add-binding-to-frame! var val (first-frame env)))
                    (lambda (vals)
                      (set-car! vals val))))

これで動くかどうかは、後ほど検証してみたいと思っています。
問題4-13。一度定義した束縛を除去するためのunbind!を作成します。環境を渡り歩きながら、最初に発見した場所で、その束縛を除去するという仕様にします。

(define (unbind! var env)
  (binds-controller env
                    var
                    (lambda () (error "Unbound variable -- UNBIND!" var))
                    (lambda ()
                      (unbind! var (enclosing-environment env)))
                    (lambda (vals)
                      (set-car! env (replace-var! (first-frame env) var)))))

replace-var!は、渡されたフレームを、同じく渡されたvarという束縛を除外したフレームに置き換えます。ここは、frameのデータ構造によって、操作方法が変わってきますが、本文に掲載されていたデータ構造の場合は、以下のようになるかと思います。

(define (replace-var! frame var)
  (define (remake-frame new-frame vars vals)
    (cond ((null? vars) '())
          ((eq? var (car vars))
           (remake-frame new-frame 
                         (cdr vars) 
                         (cdr vals)))
          (else (remake-frame (add-binding-to-frame! (car vars)
                                                     (car vals)
                                                     new-frame)
                              (cdr vars)
                              (cdr vals)))))
  (remake-frame (make-frame '() '())
                (frame-variables frame)
                (frame-values frame)))

かなり汚いコードになってしまいました。正しく動くかどうかは未検証ですので、これも今後の課題としていきたいと思います。