継続とか全然理解してなかった
(個人用のメモ。gauche前提の話)
本当は探索用の手続きだったけれど、本質とは関係ないのでもっと単純な例で書くことにする。
以下のようなコードがあるとする。
(define (rec n) (let loop ((i 0)) (unless (> i n) (print i) (loop (+ i 1))))) (rec 4) ;; ; => 0 ;; 1 ;; 2 ;; 3 ;; 4 ;; #<undef>
1..4までの間の数を表示するだけのコード。これを以下のように変更したい。
- print以外の他の処理を行えるようにしたい。
- (元の手続きは時間のかかる処理なので)解がひとつ求まったら途中で計算を打ちきりたい
- (他の解も知りたいので)打ち切った計算を途中から再開させたい
継続使えば簡単にできるだろうと思ったけど、そうでも無かった。
初めに書いたコード
(define (rec n) (let/cc break (let loop ((i 0)) (cond ((> i n) (values #f (lambda () #f))) (else (let/cc cont (break i cont)) (loop (+ i 1))))))) ;; (define-values (i cont) (rec 3)) (print i) (cont) (print i) (cont) (print i) (cont) (print i) (cont) (print i) (cont) ;; gosh> 0 ;; 1 ;; 2 ;; 3 ;; #f ;; #t
脱出用の継続と再開用の継続を作って、解が求まる度に多値で返すというもの。*1
これでうまく動くかと思ってたけれど。トップレベル以外の場所で返ってきた継続を評価しようとするとうまく動かない。
(define-values (i cont) (rec 3)) (dotimes (i 3) (cont)) (print i) ;; gosh> 1 ;; #t
元々の手続きrecの呼び出しはトップレベルで行われている。返ってきた継続の残りもトップレベルのものを指す。
なので、dotimesの中のcontも一回しか呼ばれない
考えてみると、まー当然のことでcall/ccをこのように使えない。
在れば、call-with-composable-continuationを使うと大丈夫。(gaucheには無い)
部分継続を使う
最初に書いたコードは以下。
(use gauche.partcont :prefix pc:) (define cont #f) (define (rec n :optional (fn print)) (pc:reset (let loop ((i 0)) (unless (> i n) (pc:shift k (set! cont k) (cut set! fn <>)) (fn* i) (loop (+ i 1))))))
事前にoptional引数で各解に行う処理を変更できる。
そして、pc:shiftが返した手続きを利用することで各解に行う処理を後で変更できる。
利用例
;; (define fn-edit! (rec 3)) (cont) (cont) (cont) ;; gosh> 0 ;; 1 ;; 2 ;; #t ;;; 他のprint以外の処理を行いたい (define fn-edit! (rec 3 (compose print (cut * 2 <>)))) (cont) (cont) (cont) ;; ;; gosh> 0 ;; 2 ;; 4 ;; #t ;;; 各解に対する処理を途中で変更したい (define fn-edit! (rec 5)) (cont) (cont) (cont) (fn-edit! (compose print (lambda (x) (* x x x)))) (dotimes (i 3) (cont)) ;; gosh> 0 ;; 1 ;; 2 ;; 27 ;; 64 ;; 125 ;; #t
contというグローバル変数に依存しているのが嫌。contを内部に入れる。
(use gauche.partcont :prefix pc:) (define (rec n) (letrec ((cont (lambda () (pc:reset (let loop ((i 0)) (unless (> i n) (pc:shift k (set! cont k) i) (loop (+ i 1))) #f))))) (lambda () (cont)))) ;; (define rec-itr (rec 3)) (dotimes (i 5) (print (rec-itr))) ;; gosh> 0 ;; 1 ;; 2 ;; 3 ;; #f ;; #t
補足
contを手続きにしているのと、以下のようにlambdaで包んでいる箇所があるのには理由がある。
- cont手続きにしないと呼び出せない。
- (lambda () (cont))ではなく単にcontにしてしまうと、最初の実行時にcontの振る舞いが決定されてしまうため。
面倒なのでマクロにした。
計算に時間のかかる処理を途中で打ち切る。ただし、打ちきった計算を再開することができる。
このような処理を書くとき継続のこととか考えたくない。
適切な形式に変換してくれるマクロが書けそうなので書いてみる。
(use gauche.partcont :prefix pc:) (define-syntax as-itr (syntax-rules () [(_ (rec arg ...)) ;; (define (rec fn arg ...)) (letrec ((cont (lambda () (pc:reset (rec (lambda (i) (pc:shift k (set! cont k) i)) arg ...) #f)))) (lambda () (cont)))])) ;; (define (rec fn n) (let loop ((i 0)) (unless (> i n) (fn i) (loop (+ i 1))))) (define rec-itr (as-itr (rec 5))) (dotimes (i 5) (print (rec-itr))) ;; gosh> 0 ;; 1 ;; 2 ;; 3 ;; 4 ;; #t
as-itrというマクロを作った。as-itrに渡す手続きrecの取る引数の数が1つ増えている。
recはfnという各要素か処理をする手続きを受け取って各要素にその手続きを適用するような手続き。
for-eachとかも渡せる。
(define for-each-itr (as-itr (for-each (iota 10)))) (dotimes (i 3) (print (for-each-itr))) ;; gosh> 0 ;; 1 ;; 2 ;; #t
と、ここでgaucheのマニュアルに載っているinvという手続きそのものだということに気づいた。
ここ
(use gauche.partcont :prefix pc:) (define (inv walker) (lambda (coll) (define (continue) (pc:reset (walker (lambda (e) (pc:shift k (set! continue k) e)) coll) (eof-object))) (lambda () (continue)))) ;; (define (rec fn n) (let loop ((i 0)) (unless (> i n) (fn i) (loop (+ i 1))))) (define rec-itr ((inv rec) 5)) (dotimes (i 5) (print (rec-itr))) ;; gosh> 0 ;; 1 ;; 2 ;; 3 ;; 4 ;; #t
