next up previous
Next: 8 Continuation(継続) Up: ソフトウェア特論 講義資料 Scheme言語とインタプリタ Previous: 6 クロージャの実現


7 Tail-recursiveインタプリタ

Schemeの特徴は線形再帰型の手続きのものは内部ですべて繰り返し処理として 取り扱い,単純な再帰によるメモリ空間の爆発を押え,効率のよい手続きを実 行することが可能になっています.そのため,繰り返し文などの特別な構文は スペシャルフォームとして用意してはありません. interpの中で再帰呼び出しを行なっているところを 行なわないようにするためには,繰り返しを行なってinterpの引数x を使い回すということが必要となります. interpを再帰的に行なっているところは,
  1. beginの処理のところで引数を順に評価しているところ.
  2. ifの処理のところで条件部,then部,else部のところ
  3. closureの処理のところ
  4. マクロ処理のところ
でした. そこで,これらのところでinterpを再帰ではなく,go loopで 変更できるかどうか考えてinterpを定義すると,以下のように なります.

(defun interp (x &optional env)
  (prog
   nil
   :loop
   (cond
    ((symbolp x) (return (get-var x env)))
    ((atom x) (return x))
    ((scheme-macro (car x))
     (setf x (scheme-macro-expand x)) (go :loop))
    ((member (car x) '(quote set! lambda))
     (return (interp-specialform
             (car x) (cdr x) env)))
    ((eq (car x) 'begin)
     (setq x (cdr x))
     (do ((l x (cdr l)))
         ((null (cdr l)) (setq x (car l)))
          (interp (car l) env))
     (go :loop))
    ((eq (car x) 'if)
     (setq x (cdr x))
     (setq x (if (interp (car x) env)
                (cadr x)
               (caddr x)))
     (go :loop))
    (t
     (let ((proc (interp (car x) env))
           (args (mapcar #'(lambda (v) (interp v env))
                         (cdr x))))
       (if (closure-p proc)
           (progn
             (setq x (closure-code proc))
             (setq env (extend-env (closure-params proc)
                                   args
                                   (closure-env proc)))
             (go :loop))
         (return (apply proc args))))))))
そこで,前に定義していたinterpとの処理時間の差を調べてみます. 時間を調べるためにはScheme-interpreterに時間を 調べる手続きを組み込むという方法も可能ですが, 処理時間をはかるためのベンチマーク用に使えるfib関数の定義とその実行形 式を与えてbeginで複合文かしたものをinterp手続きに渡し, それをLispのtime手続きに渡すという手法を使ってみます. 繰り返し処理をしない前のinterpでは,


<cl> (time
       (interp
        '(begin
           (define (fib n)
             (if (< n 2)
                 1
               (+ (fib (- n 1)) (fib (- n 2)))))
           (fib 12))))

cpu time (non-gc) 21900 msec user, 1049 msec system
cpu time (gc)     2716 msec user, 34 msec system
cpu time (total)  24616 msec user, 1083 msec system
real time  27210 msec

233
となります. 繰り返し処理に変更すると,

cpu time (non-gc) 21283 msec user, 783 msec system
cpu time (gc)     583 msec user, 17 msec system
cpu time (total)  21866 msec user, 800 msec system
real time  23520 msec
となりました. これよりいくらか効果があることがわかります.

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