SICP 4.1.3 Evaluator Data Structures - プログラミング再入門

ノート

前節ではスタブで誤摩化していた部分の実装の続き。定義された手続き、変数、環境など。

Testing of predicates

内部で評価する際に使うtrue?とfalse?の定義。

Representing procedures

手続きを実行する部分は4.1.4まで先送り。
ここでは手続きの内部表現はprocedureと言うタグ、パラメータリスト、本体、環境のリストで表現する。

Operations on Environments

ここで『環境』とは一連のフレームの事。フレームには変数とオブジェクトの対が保存されている。

ここでset-car!とset-cdr!が登場するので、racketモードは使えない。試行錯誤の結果、r5rsモードで適当なerror関数、true/falseを定義して、global-envを作ってあげれば動作した。

#lang r5rs
(define error #f)
(call-with-current-continuation (lambda (k)
              (set! error
                (lambda error-arguments
                  (display ">>>> ERROR ")
                  (newline)
                  (k error-arguments)))
              'done))
(define true #t)
(define false #f)
(define global-env (extend-environment '(true false) '(#t #f) the-empty-environment))

動作確認

> (eval '(define a 1) global-env)
'ok
> (eval 'a global-env)
1
>

Exercise 4.11

applyからextend-environmentを呼ぶ時には仮引数のリスト＋実引数のリスト＋ベースの環境と言う引数になり、これを返るのは得策ではないので、make-framesでペアを作る事にする。
単なるペアではmutable/immutableのデータの扱いが面倒なので、Racketモードに戻してペアをハッシュとして保存する事にする。こうするとset!とかset-car!/set-cdr!を使わずにRacketモードで妙なerror関数とか定義せずに済む。

#lang racket
(require racket/dict)

中略

(define (make-frame variables values)
  (let ((hash (make-hash)))
    (for-each (lambda (a b) (dict-set! hash a b)) variables values)
    hash))

(define (add-binding-to-frame! var val frame)
  (dict-set! frame var val))

(define (lookup-variable-value var env)
  (define (env-loop env)
    (if (eq? env the-empty-environment)
        (error "Unbound variable" var)
        (dict-ref (first-frame env) var (lambda () (env-loop (enclosing-environment env))))))
  (env-loop env))

(define (set-variable-value! var val env)
  (define (env-loop env)
    (if (eq? env the-empty-environment)
        (error "Unbound variable -- SET!" var)
        (let ((frame (first-frame env)))
          (if (dict-ref frame var #f)
              (dict-set! frame var val)
              (env-loop (enclosing-environment env))))))
  (env-loop env))

(define (define-variable! var val env)
  (dict-set! (first-frame env) var val))

簡単に動作確認

> (define global-env (extend-environment '(true false) '(#t #f) the-empty-environment))
> (eval '(define a 1) global-env)
'ok
> (eval 'a global-env)
1
>

Exercise 4.12

scanとenv-loopをそれぞれ括り出す事が出来る。

(define (scan var vars vals)
  (cond ((null? vars) #f)
        ((eq? var (car vars)) vals)
        (else (scan var (cdr vars) (cdr vals)))))

(define (find-variable var env)
  (if (eq? env the-empty-environment)
      (error "Unbound variable" var)
      (let ((frame (first-frame env)))
        (cond ((scan var
                     (frame-variables frame)
                     (frame-values frame)) => (lambda (vals) vals))
              (else (find-variable var (enclosing-environment env)))))))

これを使って書き換える。

(define (lookup-variable-value var env)
  (car (find-variable var env)))

(define (set-variable-value! var val env)
  (set-car! (find-variable var env) val))

(define (define-variable! var val env)
  (let ((frame (first-frame env)))
    (cond ((scan var
                 (frame-variables frame)
                 (frame-values frame)) => (lambda (vals) (set-car! vals val)))
          (else (add-binding-to-frame! var val frame)))))

動作確認

> (define global-env (extend-environment '(true false) '(#t #f) the-empty-environment))
> (eval '(define a 1) global-env)
'ok
> (eval 'a global-env)
1
> (eval '(set! a 2) global-env)
'ok
> (eval 'a global-env)
2
>

Exercise 4.13

最新のフレームにある変数だけを削除するものとする。
Schemeモードは何かと不便なのでExercise 4.11の実装上で行う事にする。テキストのコード上で実装するよりも遥かに楽に出来るが、問題の本質はそこじゃないだろうと言う事で。

(define (eval exp env)
  (cond ((self-evaluating? exp) exp)
        ((variable? exp) (lookup-variable-value exp env))
        ((quoted? exp) (text-of-quotation exp))
        ((assignment? exp) (eval-assignment exp env))
        ((definition? exp) (eval-definition exp env))
        ((unbound? exp) (remove-binding exp env))
以下省略

(define (unbound? exp) (tagged-list? exp 'make-unbound!))
(define (symbol-to-unbound exp) (cadr exp))
(define (remove-binding exp env)
  (dict-remove! (first-frame env) (symbol-to-unbound exp)))

簡単に動作確認。

> (define global-env (extend-environment '(true false) '(#t #f) the-empty-environment))
> (eval '(define a 1) global-env)
'ok
> (eval 'a global-env)
1
> (eval '(make-unbound! a) global-env)
> (eval 'a global-env)
. . Unbound variable a
> global-env
'(#hash((true . #t) (false . #f)))
>