2006/12/22

フリップフロップのように動作する演算子、/regexp/../regexp/。 awkの似たような機能はずいぶん使ったのでこれが便利であることは分かってるが、 隠された状態が色々あって気持ち悪い。同様の機能を、状態をうまく閉じ込めて実現 するとどういったAPIになるだろうか、とつらつら考えていて、ジェネレータを 扱う関数群としてまとめられるんじゃなかろうか、と思った。

ここでのジェネレータは単なるthunk (引数無しの手続き) で良い。呼ばれるたびに次の データか、もしくはデータが無くなれば#<eof>を返すとする。無限にデータを生成 してもいい。標準入力関数のreadやread-charはそのままジェネレータとして使える。

そうすると、このジェネレータの出力に対してfold, map, for-each, take, drop など、ストリームやシーケンスと同型の関数群が定義できるだろう。例えば：

(define (generator-fold proc seed gen)
  (define (rec seed)
    (let1 elt (gen)
      (if (eof-object? elt) sedd (rec (proc seed)))))
  (rec seed))

(define (generator-take gen k)
  (define (rec k)
    (if (<= k 0)
      '()
      (let1 elt (gen)
        (if (eof-object? elt) '() (cons elt (rec (- k 1)))))))
  (rec k))

無限要素を許すこと、必要なだけ値を生成すること、等は遅延ストリームと よく似ているが、ジェネレータはリスタートが出来ない(途中状態をcall/ccで 捕まえておいてそこから再実行をかけることが出来ない)。ただ、それは 状態を保存しておかなくても良いことを意味し、効率は遅延ストリームよりも 良くなる。

ジェネレータを使うなら、フリップフロップ演算は一つのジェネレータからの データの流れをふたつのデータの流れに振り分ける弁みたいなものになるだろうか。

(define (generator-range gen begin? end? in-proc out-proc)
  (define (out e ins outs)
    (cond ((eof-object? e) (values (reverse ins) (reverse outs)))
          ((begin? e) (in (gen) (cons (in-proc e) ins) outs))
          (else (out (gen) ins (cons (out-proc e) outs)))))
  (define (in e ins outs)
    (cond ((eof-object? e) (values (reverse ins) (reverse outs)))
          ((end? e) (out (gen) (cons (in-proc e) ins) outs))
          (else (in (gen) (cons (in-proc e) ins) outs))))
  (out (gen) '() '()))

ジェネレータgenからの流れを、in-procかout-procへと振り分ける。一応、 関数的に、副作用を当てにするのではなく結果をリストでそれぞれ収集してみた。

gosh> (with-input-from-process "w3m -dump_source http://www.yahoo.com"
        (lambda ()
          (values-ref (generator-range read-line #/^<style/ #/<\/style>/
                                       identity identity)
                      0)))
("<style type=\"text/css\">" "a{color:#16387c;}"
 "a:link,a:visited{text-decoration:none;}" "a:hover{text-decoration:underline;}"
 "</style>" "<style type=\"text/css\" media=\"all\">"
 "#p{width:310px;}" "form{margin:0;}" "</style>")

こういうの、util.generatorとかしてモジュールにしとくと何か使えるだろうか。

Tag: Gauche