継続が実装できた!!
おしゃぁぁぁ!!
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に落として・・・となっていく。ここからがすげー大変そうだ。