[ 目次, 前節, 次節, 索引 ]

述語のテスト

(define (true? x)
  (not (eq? x false)))


(define (false? x)
  (eq? x false))

手続きの表現

   合成手続きはパラメタ, 手続き本体および環境から, 構成子 make-procedureを使って構成する:

(define (make-procedure parameters body env)
  (list 'procedure parameters body env))


(define (compound-procedure? p)
  (tagged-list? p 'procedure))


(define (procedure-parameters p) (cadr p))


(define (procedure-body p) (caddr p))


(define (procedure-environment p) (cadddr p))

環境に対する操作

   これらの演算を実装するため, 環境をフレームのリストとして表現する. ある環境の外側の環境はリストのcdrである. 空の環境は単に空リストである.

(define (enclosing-environment env) (cdr env))


(define (first-frame env) (car env))


(define the-empty-environment '())

(define (make-frame variables values)
  (cons variables values))


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


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


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

   変数を値に対応づける新しいフレームで環境を拡張するには, 変数のリストと値のリストからなるフレームを作り, これを環境に接続する. 変数の個数が値の個数に一致しなければ, エラーとする.

(define (extend-environment vars vals base-env)
  (if (= (length vars) (length vals))
      (cons (make-frame vars vals) base-env)
      (if (< (length vars) (length vals))
          (error "Too many arguments supplied" vars vals)
          (error "Too few arguments supplied" vars vals))))

   環境の中で変数を探すには, 最初のフレームで変数のリストを走査する. 探している変数が見つかれば, 値のリストの対応する要素を返す. 現在のフレームに変数が見つからなければ, 外側の環境を探し, これを続ける. 空の環境に達したら, 「未束縛変数」エラーを出す.

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

   指定された環境の中で, 変数を新しい値に設定するには, lookup-variable-valueのように変数を走査し, それが見つかれば対応する値を変更する.

(define (set-variable-value! var val env)
  (define (env-loop env)
    (define (scan vars vals)
      (cond ((null? vars)
             (env-loop (enclosing-environment env)))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) (cdr vals)))))
    (if (eq? env the-empty-environment)
        (error "Unbound variable -- SET!" var)
        (let ((frame (first-frame env)))
          (scan (frame-variables frame)
                (frame-values frame)))))
  (env-loop env))

   変数を定義するには, 最初のフレームで変数の束縛を探し, (set-variable-value!のように)それが存在すれば束縛を変更する. 束縛がなければ, 最初のフレームに接続する.

(define (define-variable! var val env)
  (let ((frame (first-frame env)))
    (define (scan vars vals)
      (cond ((null? vars)
             (add-binding-to-frame! var val frame))
            ((eq? var (car vars))
             (set-car! vals val))
            (else (scan (cdr vars) (cdr vals)))))
    (scan (frame-variables frame)
          (frame-values frame))))

   ここに記述した方法は環境を表現する多くの可能なやり方の一つに過ぎない. 評価器の他の部分を表現の詳細な決定から孤立させるためデータ抽象を使ったので, 環境の表現は, そうしたければ変更出来る. (問題4.11参照) 製品品質のLispシステムでは, 評価器の環境演算の速度---特に変数探索---がシステムの性能に大きく影響する. ここに述べた表現は考え方は単純だが, 効率的でなく, 普通には製品システムとしては使われないであろう.15

問題 4.11

フレームをリストの対で表現する代りに, 各束縛が名前-値の対であるような束縛のリストでフレームを表現することが出来る. この表現を使うように環境演算を書き直せ.

問題 4.12

手続きset-variable-value!, define-variable!およびlookup-variable-valueは, 環境構造を渡り歩く, より抽象的な手続きを使って表すことが出来る. 共通パターンを取り込む抽象を定義し, その抽象を使って三つの手続きを再定義せよ.

問題 4.13

Schemeでは, defineにより, 変数の新しい束縛を作り出すことが出来る. しかし束縛を除去する方法は用意していない. unbind!式を評価した環境から与えられた記号の束縛を除去する特殊形式unbind! を, 評価器に実装せよ. この問題は完全な仕様にはなっていない. 例えば環境の最初のフレームからだけ結合を除去するのか. 仕様を完成し, 自分の選択を正当化せよ.

14 フレームは次のプログラムではデータ抽象ではない: set-variable-value!とdefine-variable!はフレームの値を直接修正するためset-car!を使う. このフレーム手続きの目的は, 環境操作の手続きを読み易くするためである.

15 (問題4.11の変形もそうだが)この表現の欠点は, 与えられた変数の束縛を見つけるために, 評価器は多くのフレームを探さなければならないことである. (この方法を 深い束縛(deep binding)という.) この非効率欠点を避ける一つの方法は, 5.5.6節で議論する, 文面アドレス(lexical addressing)という戦略を使うことである.

[ 目次, 前節, 次節, 索引 ]