概要

Schemeでジェネレーターを汎用的に作る方法のメモ。

http://qiita.com/items/e9181e827b1ca7f86e2d
を汎用的にするにはどうしたら良いか。

http://practical-scheme.net/wiliki/wiliki.cgi?Scheme:generatorとdoとwhile
の読んだけど、読んでるだけでは分からなかったので、書いてみた。

本文

問題意識

以前、順列を列挙するジェネレーターとして次のようなコードを書いた。

gen1.scm

(define (permutation-generator n)
  (define flag (make-vector n #t))
  (define return ())
  (define (loop i j perm)
    (cond ((= i n)
           (call/cc (lambda (cc)
                      (set! next-start cc) ;;残りの処理を継続として保存
                      (return perm)))) ;;途中脱出!
          ((< j n)
           (if (vector-ref flag j)
               (begin
                 (vector-set! flag j #f)
                 (loop (+ i 1) 0 (cons (+ 1 j) perm))
                 (vector-set! flag j #t)))
           (loop i (+ j 1) perm))))
  (define (next-start) (loop 0 0 ()))
  (define (generator)
    (call/cc
     (lambda (cc)
       (set! return cc)
       (next-start))))
  generator)

このloopの定義を変えれば、例えば組み合わせの列挙等、他の色々なジェネレーターが得られる。但し、このままだと、他のジェネレーターが手に入れるには、この関数全体を書き直さないといけない。それは宜しくないので何とか抽象化を施し、内部関数loopを外に出して、それを置き換えるだけで異なるジェネレーターが得られるようにしたい。

課題点

素朴に考えて、まずは次のような所に辿り着いた。

gen2.scm

(define (make-generator proc)
  (define return ())
  (define next ())
  (define (generator)
    (call/cc (lambda (cc)
           (set! return cc)
           (next))))
  generator)

ジェネレーターを作る関数なので、make-generatorという名前にする。
make-generatorは、実際に値を生成する手続きを受け取るために、仮引数procを持たせる。
さらに、クロージャーの中に、途中脱出時に戻るべき呼び出し元を保存するreturnと処理再開箇所を保存するnextを持つ。

ここまでは、前の汎用的でないpermutation-generatorと殆ど同じ考えなので問題無い。procがどうあるべきかを考える。procにやって欲しい事は何か。

計算の内部状態を保存しておいて欲しい。
適当なタイミングで返り値をreturnに投げて欲しい。
さらに、returnに返り値を投げる直前の継続をnextに保存して欲しい。

ここで、最初の2つは

内部状態の保存->クロージャーを使えば良い。
返り値をreturnに投げる->procにreturnを渡して、procは中でそれを呼べば良い。

と難しくない。が、最後の継続をnextに保存する部分が分からなくてハマったのだった。nextはprocとは関係ないクロージャーの中に居るオブジェクトなので、procの中からゴニョる事は出来ないのだ。だので、ここは少し工夫が必要だ。

解決策

gen3.scm

(define (make-generator proc)
  (define return ())
  (define (yield value)
    (call/cc (lambda (cc)
           (set! next cc)
           (return value))))
  (define (next) (proc yield))
  (define (generator)
    (call/cc (lambda (cc)
           (set! return cc)
           (next))))
  generator)

上のyieldのような関数を定義して、returnではなくてyieldをprocに渡してやれば良い。yieldは、まさにreturn直前の継続をnextに保存しつつ、returnに返り値を投げるという作業を行う。yieldは、nextと同じgeneratorの中に居るので、nextをゴニョる事が出来る。これを使うと、目出度く

gen4.scm

(define (permutation-generator n)
  (make-generator
   (lambda (yield)
     (define vec (make-vector n #t))
     (let loop ((i 0)
        (j 0)
        (ls ()))
       (cond ((= i n) (yield ls))
         ((< j n)
          (if (vector-ref vec j)
          (begin
            (vector-set! vec j #f)
            (loop (+ i 1) 0 (cons j ls))
            (vector-set! vec j #t)))
          (loop i (+ j 1) ls))
         ((= i 0) (yield 'end)))))))

;; テストコード
(let ((gen (permutation-generator 3)))
  (let loop ((perm (gen)))
    (cond ((eq? perm 'end) perm)
      (else
       (print perm)
       (loop (gen))))))

のような具体的な処理に依存しないジェネレーターを書ける。

振り返り

最初にprocのあるべき処理を考えた時には、nextはprocの中で弄れないから、procは値と一緒に継続も返して、make-generatorの中で継続を保存しつつ値を外に反すというような処理をしないといけないと思った。何か面倒臭いし綺麗じゃないし違う感じがして釈然としなかった。

yieldというクロージャーに包んで「nextに継続を保存する」という処理をprocに渡せば良いという解決策を理解した時、目からウロコだったので、メモ。