next up previous
Next: 7 Tail-recursiveインタプリタ Up: ソフトウェア特論 講義資料 Scheme言語とインタプリタ Previous: 5 Schemeインタプリタ


6 クロージャの実現

上のSchemeインタプリタでは,lambdaで表された 式を評価するとCommonLispのクロージャを返すという形で 作られていました. ここでは,そのクロージャをLispに組み込みのものを使うのではなく, 作ってみようということを考えます. そこで,クロージャを表現するために,次のような構造体を 定義します. 要素paramsはクロージャへの引数,codeはクロージャの本体 envはこのクロージャを作った時点の環境のための領域です.

(defstruct closure params code env)
レキシカルクロージャというのは,この関数の定義を作った時点のレキシカル スコープをもつ変数の環境を保存するためのものです.そのため, interp-specialformは以下のようになります. lambdaの処理は構造体のクロージャを返すことになります.

(defun interp-specialform (name params env)
  (case
   name
   (quote (car params))
   (begin (if (null params) nil
            (car (last
                  (mapcar
                   #'(lambda (v) (interp v env))
                   params)))))
   (set! (set-var! (car params)
                   (interp (cadr params) env)
                   env))
   (if  (if (interp (car params) env)
            (interp (cadr params) env)
          (interp (caddr params) env)))
   (lambda
       (make-closure :params (car params)
        :code (cons 'begin (cdr params))
        :env env))))
これに伴って,手続きを評価する interp-call の中での処理は,この構造体データであるクロージャが 与えられた場合には,Lispのapplyでは処理できないので, そのクロージャの中にある環境を考慮してそのクロージャの 中の手続きコードをinterpするという形になります.

(defun interp-call (call env)
  (let ((proc (interp (car call) env))
        (args (mapcar
               #'(lambda (v) (interp v env))
               (cdr call))))
    (if
        (closure-p proc)
        (interp (closure-code proc)
                (extend-env 
                 (closure-params proc)
                 args
                 (closure-env proc)))
      (apply proc args))))
という具合いの記述になります. つまり,interp-call に渡されるフォーム(call)が,lambdaフォームで作られ たクロージャに引数を適用する形である場合には,そのクロージャの中に保存 されている環境(closure-env)に,そのクロージャへ渡された実引数argsとク ロージャの中に宣言されている引数(closure-params)とのバインディングを追 加した環境を作り,その環境の中でクロージャの中にある関数定義をinterpす るという形になります. そのフォーム(call)がクロージャを呼び出す場合でなく,car, cdr のように, init-scheme-interpreter の中で前もって定義されている手続きの場合には, CommonLisp の関数定義をそのまま使っているので,CommonLisp の apply を 使って評価するということになります. 実行例は以下のようになります.

<cl> (scheme-interpreter)
==> (define (fact n)
       (if (< n 2) 1 (* (fact (- n 1)) n)))
FACT 

==> fact
#s(CLOSURE :PARAMS (N)
      :CODE (BEGIN (IF (< N 2) 1
                       (* (FACT (- N 1)) N)))
      :ENV NIL) 
==> (fact 5)
120 

==> (define (table f start end)
       (if (<= start end)
           (begin (write (list start (f start)))
                  (newline) 
                  (table f (+ start 1) end))))
TABLE 

==> table
#s(CLOSURE
     :PARAMS (F START END)
     :CODE (BEGIN
            (IF (<= START END)
                (BEGIN (WRITE (LIST START (F START)))
                       (NEWLINE)
                       (TABLE F (+ START 1) END))))
     :ENV NIL) 

==> (table fact 1 5)
(1 1)
(2 2)
(3 6)
(4 24)
(5 120)
NIL 

==> (table (lambda (x) (* x x x)) 5 10)
(5 125)
(6 216)
(7 343)
(8 512)
(9 729)
(10 1000)
NIL
関数定義 fact の実体がクロージャを示す構造体になっています.:params ス ロットは fact 関数の引数で,:code は Scheme での定義であり,begin フォー ムとなっています.:env は fact の定義を行なった環境にレキシカル変数が ないために nil になっています.

==> (define a 10)
A 
==> (let ((a 1)) (let ((b (+ a 3))) (list a b)))
(1 4) 
==> a
10


generated through LaTeX2HTML. M.Inaba 平成18年5月6日