lifeLOG + REPOsitory: Gauche でフィルタを書く

前回、Lisp で以下のような「行指向パターンマッチ方式」でフィルタを書くのは難しい、と書いた。

(行指向パターンマッチ方式)
while (入力がある) {
    一行読み込む;
    if (あるパターンに一致する) {
        一行分のデータに対して処理を行う;
        結果を出力する;
    } else if (別のパターンに一致する {
        別の処理を行う;
        結果を出力する;
    } ...
}

その代わりにリストを利用した「丸ごと読み込んで、全部処理して、まとめて書き出す」方式ならすっきりと書ける、と。

後者は確かにその通り。「プログラミングGauche」のコラム『「Lisp 脳」の謎に迫る - Scheme プログラマの発想』を読んでも、入力をリストにして、リストの各要素を処理して、結果をリストにする、というのは Lisp らしい書き方なんだとわかる。

けれど、前者は間違いだった。Scheme でも大して難しくはないと気付いた。

while ループは条件分岐と goto で書き直せる

説明を単純にするためにパターンマッチのない「行指向方式」に戻ろう。

(行指向方式)
while (入力がある) {
    一行読み込む;
    一行分のデータに対して処理を行う;
    結果を出力する;
}

これは、以下のように書き直すことができる。

(行指向方式 #2)
Loop:
    if (入力がない) goto Exit;
    一行読み込む;
    一行分のデータに対して処理を行う;
    結果を出力する;
    goto: Loop;
Exit:

こうなれば、Scheme でも容易に実現できることがわかる。なぜなら、Scheme では、

(「プログラミングGauche」p.6 より)

手続き呼び出しは継続を伴った引数つき goto である

からだ。また、(もう少しわかりやすく)こうも書いてある。

(「プログラミングGauche」p.57 より)
処理の一番最後に再帰呼び出しをして、その結果がそのまま現在の処理の結果として返されるパターンを末尾再帰と呼びます[...snip...]

Scheme では、上記のとおり、最後に呼び出した手続きの戻り値に何も行わない場合、最後の呼び出しは通常の手続き呼び出しではなくジャンプとして扱われることになっています

末尾再帰を goto 代わりに使う

手続き呼び出しが goto なのだとわかれば、上述の「行指向方式 #2」はこう書くことができる。

 1: (define (apply-filter proc port)
 2:   (let ((line (read-line port)))
 3:     (if (not (eof-object? line))
 4:       [begin
 5:         (proc line)
 6:         (apply-filter proc port)])))

3 行目がループの脱出条件の判定に、6 行目の再帰呼び出しがループの先頭に戻る goto に相当する。proc に標準入力ポート、proc にデータを処理する手続きを指定して、apply-filter を呼び出せばフィルタプログラムができあがる。

以下は、これを利用して書いた wc っぽいフィルタだ。単語数の出力が wc と同じにならないことがあるのは単語の区切りとして空白文字しか想定していないためだ。

「BEGIN」と「END」というコメントは AWK をちょっと思い出して書いてみた。たぶん、AWK でこれと同じものを書くとすると、やはり BEGIN でグローバル変数を用意し、END で結果を出力する、というようになると思う。

「まとめて」と「少しずつ」の違い

「正規表現を使った処理を scheme (Gauche) で書いてみる」で示したものは、読み込み、処理、結果出力の 3 つの段階をそれぞれ「まとめて」実行する方式だ。一方、↑で示した wc モドキでは、3 つの段階を「少しずつ」行い、全体をループするようになっている。

データ量が小さいときには、両者の方式の実行に差を見つけることは難しいだろう。実際のところ、いまどきの Mac や PC ならどちらの方式で書いてあろうが、たいていの入力に対して一瞬で完了するはず。ただ、データ量がぐっと大きくなるとその差が顕在化するはず。

極端なことを言えば、入力ファイルが GB 単位の大きさになると「まとめて」方式は(いまどきのパソコンでも)かなり苦しくなる。すべてを一度にメモリに読み込む必要があるからだ。32 ビットモードなプラットフォームなら読み込みの段階で実行時エラーになるかもしれない。一方「少しずつ」方式では、データ量が大きくなっても実行時に必要なメモリは一定の範囲に収まる。もちろん実行時間はデータ量に見合うだけのものが必要になるが、データが読み込めないというような事態にはならないはず。ま、もっとも、GB 単位のデータ(それもテキスト)を処理するなんてことは、かなり特殊な状況で、普通の人は一生、経験することはないかもしれない。

実のところフィルタにもいろいろあって、「まとめて」方式では実現できても「少しずつ方式」では実現できなかったり、難しかったりするものもある。たとえば、sort は「まとめて」なら実装しやすくて、「少しずつ」だと困難な(というか外部にデータを書き出さない限りできないよね？)フィルタだ。tr や grep は、まさに「行指向パターンマッチ方式」に適した例だし、wc や uniq あたりは実装に工夫(状態の保持にグローバルなデータ構造を使うとか)が必要になる例だろう。