継続が実装できた!!

おしゃぁぁぁ!!

Unlambdaの方言で継続を実装しました。クロージャとか邪魔なので、Scheme組み込みを使います。

(define ((k x) y) x)
(define (((s x) y) z) ((x z) (y z)))
(define (i x) x)

(define (un-apply op arg)
  (eval `(,op ,arg)))

(define (un-eval stack pc program)
  (cond ((null? pc) `END)
        ((pair? pc)
         (let ((op (car pc))
               (arg (cadr pc)))
           (if (pair? op)
               (un-eval stack op (cons arg program))
               (un-eval (cons op stack) arg program))))
        (else
          (if (null? stack)
              (if (null? program)
                  pc
                  (un-eval (cons pc stack) (car program) (cdr program)))
              (un-eval (cdr stack) (un-apply (car stack) pc) program)))))

(define (main ex)
  (un-eval '() ex '()))

(main '((((s k) k) i) (i (i (i k)))))

スタック、レジスタ(プログラムカウンタ)、これから行うべきプログラム。コレを合わせると、継続という奴になる。

3つをプログラムの中に戻してやれば、計算機は何事も無かったかのように計算を続けることが出来る。

traceすると。

> (main '((((s k) k) i) (i (i (i k)))))
|(un-eval () ((((s k) k) i) (i (i (i k)))) ())
|(un-eval () (((s k) k) i) ((i (i (i k)))))
|(un-eval () ((s k) k) (i (i (i (i k)))))
|(un-eval () (s k) (k i (i (i (i k)))))
|(un-eval (s) k (k i (i (i (i k)))))
|(un-eval () #<procedure> (k i (i (i (i k)))))
|(un-eval (#<procedure>) k (i (i (i (i k)))))
|(un-eval () #<procedure> (i (i (i (i k)))))
|(un-eval (#<procedure>) i ((i (i (i k)))))
|(un-eval () #<procedure:i> ((i (i (i k)))))
|(un-eval (#<procedure:i>) (i (i (i k))) ())
|(un-eval (i #<procedure:i>) (i (i k)) ())
|(un-eval (i i #<procedure:i>) (i k) ())
|(un-eval (i i i #<procedure:i>) k ())
|(un-eval (i i #<procedure:i>) #<procedure:k> ())
|(un-eval (i #<procedure:i>) #<procedure:k> ())
|(un-eval (#<procedure:i>) #<procedure:k> ())
|(un-eval () #<procedure:k> ())
|#<procedure:k>

いえぃ。末尾再帰!!

今回はうまく行ったけど、

今回の場合はうまく行ったけど、真面目に継続渡しに変換しないとうまくいかないと思う。

継続化の手順を(途中まで)まとめておく。

まず、(apply (eval tree) (eval tree))の形を作る。

(define (un-eval tree)
  (if (pair? tree)
      (un-apply (un-eval (car tree)) (un-eval (cadr tree)))
      tree))

で、継続渡しに変換する。

(define (un-eval/cps tree cont)
  (if (pair? tree)
    (un-eval/cps (car tree) (lambda (x)
                                    (un-eval/cps (cadr tree) (lambda (y)
                                                               (cont (un-apply x y))))))
    (cont tree)))

その後、apply内もcontを使うようにして、後は最適化して・・・Cに落として・・・となっていく。ここからがすげー大変そうだ。

まとめ

処理系全体が継続渡しになってれば、末尾呼び出しの最適化が自然に導き出せる事がよくわかった。

しかし、僕のSchemeレベルではSchemeに継続を実装するのはまだまだ先だということも実感できた。

僕としては、継続というものが何であるかというのがはっきり掴めるようになっただけで、大収穫である。