lifeLOG + REPOsitory: フィルタプログラムとは

前回書いた「かけら」をもっと Scheme/Lisp らしくすることを考える前に、題材になっているフィルタとはどんなプログラムなのかを復習しておこう。

Unix とフィルタ

以下の一文はフィルタと呼ばれる一群のプログラムの特徴をうまく表現している。

(「UNIXプログラミング環境」p.155 より)
UNIX には，"何か入力を読み込み，それに単純な変形を加え，何らかの出力を書き出す" という仕事をするプログラムが多数存在する．例をあげると，入力の一部分を選び出す grep や tail，入力をソートする sort，入力のなかのワード数を数える wc がある．このようなプログラムを総称してフィルタと読んでいる．

また、フィルタは単独で使われるだけでなく、複数を組み合わせることでより複雑な処理を実現することもできる。

(「UNIXプログラミング環境」p.199 より)
わずか 1 つのフィルタを適用してやることで抱えた問題が氷解することもあるが，複数のフィルタを結合して 1 本のパイプラインにすることは、問題を解決可能な小問題に分解するのに役立つ．このようなツールの利用法こそは UNIX プログラミング環境の核心であるといわれることが多い．

Unix のシェルが備えているパイプやリダイレクトは、フィルタを組み合わせるための仕組みだ。

設計パターン

パイプやリダイレクトのような仕組みでつなげられるようにするには、それぞれのフィルタプログラムが共通する設計を持っていなければならない。それが以下の 3 つだ(厳密には最初の 2 つで十分)。

共通の入力方式
共通の出力方式
上記入出力とは独立したメッセージ出力方式

Unix (とそれに良く似たプログラミング環境)では、上記の 3 つは、それぞれ標準入力、標準出力、そして標準エラー出力と呼ばれている。

簡単に言えば、フィルタプログラムとは、標準入力からデータを読み込み、適切な処理をした後、標準出力に結果を出力し、処理中に必要があれば(警告メッセージの表示など)標準エラー出力に書き出すようなもののことだ。

実装パターン

フィルタを実装するために汎用パターンは以下のようになる。

(汎用方式)
すべての入力を読み込む;
入力に対して処理を行う;
結果を出力する;

この場合、一般には、入力、処理、出力のそれぞれの段階でループが必要で、データを蓄えておく領域も入力と出力にそれぞれ必要になる。はっきり言えば、この方式は効率が良くない。

処理の単位が文字(バイト)ごとだとわかっていれば、以下のように入力、処理、出力を共通のループに押し込む方式が使える。

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

こうすればループの回数は減るし、必要な記憶領域も小さくなる。

この変種として、文字ではなく行を処理の単位にする方式もある。

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

実際には、ほとんどの場合、処理(と出力)の部分は以下のようにパターンとの照合でガードされている。

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

ここまで来ると、フィルタを記述するのに必要なのは、処理が必要か否かをガードするパターンとパターンに応じた処理の記述(アクション)だけだということがわかる。残りの部分はフィルタの種類によらず共通なのだ。文字や行のような処理の単位も区切りを指定することで柔軟に変えることができる。AWK はこの発想を実現するために作られたプログラミング言語だ。

Scheme/Lisp らしく書くには

Ruby や Python なら、先の「行指向パターンマッチ方式」を素直にほぼそのままの形で実装できる。一方、Scheme/Lisp ではデータの基本構造はリストで、繰り返し処理は再帰で実現する。リストと再帰で「行指向パターンマッチ方式」を実現するのは難しい。その代わりと言っては何だが、最初に挙げた「汎用方式」をすっきりと実現できる。すなわち、以下のようにする。