2.1.2 要求駆動とサーバプロセス

ある与えられた数よりも小さいフィボナッチ数が何個あるかを求めるプログラムを 組んでみよう. もし, 与えられた数までのフィッボナッチ数を生成するプロセスが既に あったとしたら, 今までのデータ駆動という考え方に基づけば, それとカウンタプロセス(入力ストリームを持ち, そこに何個の入力 が流れてきたかをカウントすることを基本動作とするプロセス)をストリームで結ぶ, というのが方針の一つとして立つ. これに基づいたプログラムが次のものである.

        go(Target,Answer) :- true|
            fibonacci(0,1,Stream,Target),
            consume(Stream,0,Answer).
        
        fibonacci(N1,N2,Stream,Target) :- N2 >= Target |
            Stream = [].
        fibonacci(N1,N2,Stream,Target) :- N2 < Target |
            Stream = [N2|StreamN],
            N3 := N1 + N2,
            fibonacci(N2,N3,StreamN,Target).
        
        consume([],Count,Answer) :- true |
            Answer = Count.
        consume([X|StreamN],Count,Answer) :- true |
            CountN := Count + 1,
            consume(StreamN,CountN,Answer).

カウンタプロセスを実現するのが述語consume/3である. 第1引数が入力ストリームであり, カウント結果は第3引数の変数に具体化される. ストリームを介してカウンタプロセスがデータ駆動的に動くのが分かる. ところで, ここでKL1のゴール実行順序に関する仕様を思い出すと, KL1では同一の優先度を持つゴール間の実行順序は特に規定していなかった. すると, このプログラムの場合, フィボナッチプロセスが カウンタプロセスより早く動く可能性がある. そうすると, フィボナッチプロセスが ``Target'' までのフィボナッチ数を生成して 終了してから初めてカウンタプロセスが動き出す, つまり, ``Target'' が大きい値だった場合は そのフィボナッチプロセスが大量のメモリを消費してしまう, という可能性がある. このフィボナッチプロセスとカウンタプロセスの間で同期を取ってない点で, 上のプログラムには欠陥がある.

そこで, このプログラムを要求駆動的 に書き換え, プロセス間で同期を取るよ うにする. つまり, カウンタプロセスからの要求がある度にフィボナッチ プロセスが一つだけフィボナッチ数を生成してカウンタプロセスに渡すようにする. KL1実行機構を思い出せば, 要求がくるのを待 つようなフィボナッチプロセスはすぐに書けるだろう. カウンタプロセスは単なるカウントだけではなく, フィボナッチプロセスにフィボナッチ数生成を要求し, ``Target'' よ り小さいかどうかのチェックをする働きをする. プログラムを次に示す.

        go(Target,Answer) :- true|
            fibonacci_lazy(0,1,Stream),
            consume(Stream,Target,Answer).
        
        fibonacci_lazy(_,_,[]) :- true | true.
        fibonacci_lazy(N1,N2,[Box|Stream]) :- true |
            N3 := N1 + N2,
            Box = N3,
            fibonacci_lazy(N2,N3,Stream).
        
        consume(Stream,Target,Answer) :-
            NewStream = [Box|Stream],
            consume(Box,Target,0,NewStream,Answer).

        consume(Box,Target,Count,Stream,Answer) :- Target =< Box |
            Stream = [],
            Answer = Count.
        consume(Box,Target,Count,Stream,Answer) :- Target > Box |
            NewCount := Count + 1,
            Stream = [NewBox|NewStream],
            consume(NewBox,Target,NewCount,NewStream,Answer).

ストリームの流れが逆であることに注意されたい. fibonacci_lazy/3は, 第 3 引数のストリームから結果を与える変数 ``Box''が到着したら, その 変数にフィボナッチ数を入れ (``Box'' にフィボナッチ数を具体化し) 次の結果を与える変数の到着を待つ. この例題では変数 ``Box'' の 到着, 即ち第 3 引数がリストセルにユニファイされることがフィボナッチ数 の計算要求を意味する. 逆に言えばこのストリームが閉じられることがプロセ スの終了を意味する. すなわち fibonacci_lazy/3 は要求駆動的に フィボナッチ数の計算を行なう述語であり, また答えの容器の到着を待つとい う意味でデータ駆動でもある. 一方 consume/5 によって実現されるカウンタプロセスは, 第2節の第 2 ボディ ゴールで ``Stream = [NewBox|NewStream]'' つまりストリーム に変数 ``NewBox'' を流している. これがフィボナッチプロセスに `次のフィボナッチ数を生成して ``NewBox''に入れろ' と要求を 出していることになるのである. そしてその要求の結果がそこに入れられる(具体化されてくる)のを ガードで待っている. 尚, プログラムの都合上, consume/3の第 1 ボディゴールで最初の要求を出し ている.

未完成メッセージの技法を使って書くことも出来る. この方式の方が 意味を表現し易く, 特にメッセージ駆動と呼ぶことがある. 次がメッセージ駆動的に書き直したプログラムである.

        go(Target,Answer) :- true|
            fibonacci_lazy(0,1,Stream),
            consume(Stream,Target,0,Answer).
        
        fibonacci_lazy(N1,N2,[]) :- true | true.
        fibonacci_lazy(N1,N2,[make(X)|Stream]) :- true|
            X = N2,
            N3 := N1 + N2,
            fibonacci_lazy(N2,N3,Stream).
        
        consume(Stream,Target,Count,Answer) :- true | 
            Stream = [make(X)|StreamN],
            consume(StreamN,Target,Count,Answer,X).
        
        consume(Stream,Target,Count,Answer,X) :- Target =< X |
            Stream = [],
            Answer = Count.
        consume(Stream,Target,Count,Answer,X) :- Target >  X |
            CountN := Count + 1,
            consume(Stream,Target,CountN,Answer).

consume/4とconsume/5の二つの述語でカウンタプロセスが実現される. カウンタプロセスは `次のフィボナッチ数を生成して ``X'' に入れろ' という要求メッセージである ''make(X)'' という未完成メッセージを ストリーム流す. そして, ``X'' がフィボナッチプロセスによってフィボナッチ数に 具体化されるのを待ち, カウントしたのち, 次の要求を出す. ``X'' に具体化される値が ``Target'' 以上に なったら, ストリームを閉じ, 答えを ``Answer'' に具体化して, 消 滅する.

フィボナッチプロセスは, 要求を受けて計算を行ない結果を要求者に返す, という 点でサーバと見ることも出来る. このサーバもKL1プロセスの重要なプロセス の一つである.