プロセス・ネットワークの基本の一つは木構造である.
前章では次のようなプログラムが出てきた. この中にも木構造が存在する.
queer_sum(N,Sum) :-
naturals(N,Naturals), dispatch(Naturals,Odd,Even),
square(Even,Squares), cube(Odd,Cubes),
merge(Squares,Cubes,Both), sum(Both,Sum).
これは `Nより小さい偶数の平方とNより小さい奇数の立方の総和を求める' という問題を解くプログラムであった. 自然数を偶数と奇数に分ける, すなわち入力を分割する(述語dispatch/3によ って実現される)ディスパッチャプロセス, 入力の平方を作って出力する(述語square/2によって実現される)フィルタプロセス, 入力の立方を作って出力する(述語cube/2によって実現される)フィルタプロセス, そして(述語merge/3によって実現される)マージャプロセス, といったプロセ スがこのプログラム中に現れている.
このプログラムは, (naturals/2によって実現される)自然数生成プロセスから(square/2, cube/2 によって実現される)フィルタプロセスまでの, 入力を分割していく木構造, それらフィルタプロセスから(sum/2によって実現される)総和計算プロセスま での, マージャプロセスを使って部分解を集めて全体の解を 作り出す木構造, この二つの木構造プロセス・ネットワークを実現する. このような木構造を持ったものがプロセス・ネットワークの基本の一つである.
前章の復習も兼ねて, 上のプログラム中の各プロセスを実現する述語 についてみていこう.
まず, ディスパッチャプロセスを実現する述語dispatch/3である.
dispatch([],Odd,Even) :- Odd=[], Even=[].
dispatch([One|Rest],Odd,Even) :- One mod 2 =:= 0 |
Odd=[One|OddTail], dispatch(Rest,OddTail,Even).
dispatch([One|Rest],Odd,Even) :- One mod 2 =\= 0 |
Even=[One|EvenTail], dispatch(Rest,Odd,EvenTail).
第1引数が入力ストリーム, 第2及び第3引数が出力ストリームである. 入力ストリームから流れてきた入力が ある条件を満たしたら出力ストリームのどちらかにそれを流す, その条件と出力ストリームの組ごとに節が用意されている. 第1節は, 入力ストリームが閉じられたら出力ストリームを全て閉じて (再帰的に自らを呼ばないことで)自ら消滅するために用意されている. この第1節は後述するようにプログラムの終了判定にとって重要である.
次にフィルタプロセスを実現する述語square/2,cube/2である.
square([],Out) :- Out=[].
square([One|Rest],Out) :-
Square:=One*One, Out=[Square|OutTail], square(Rest,OutTail).
cube([],Out) :- Out=[].
cube([One|Rest],Out) :-
Cube:=One*One*One, Out=[Cube|OutTail], cube(Rest,OutTail).
第1引数が入力ストリーム, 第2引数が出力ストリームである. 入力ストリームに流れてきた入力に処理を施し(ここでは平方や立方をとり) その結果を出力ストリームに流している. 入力によって施す処理を変えたい時にはディスパッチャと同様に節を幾つか用 意してやれば良い. 第1節は, ディスパッチャの第1節と同様に, 入力ストリームが閉じられたら出力ストリームを全て閉じて 自ら消滅するために用意されている.
フィルタプロセスを幾つか直列につなげばパイプライン・プロセス・ネットワークが
出来る. 入力Nに対して
を求めるパイプラインは, 次のような述語
で実現できる。
pipe(In,Out) :- true | square(In,Mid), cube(Mid,Out).
そして, マージャプロセスを実現する述語merge/3である.
merge([],In2,Out) :- Out=In2.
merge(In1,[],Out) :- Out=In1.
merge([Msg|In1],In2,Out) :- Out=[Msg|OutTail], merge(In1,In2,OutTail).
merge(In1,[Msg|In2],Out) :- Out=[Msg|OutTail], merge(In1,In2,OutTail).
入力ストリームである第2引数と第3引数のどちらかに入力が流れてきたら, それをそのまま出力ストリームに流す, ということをしているのが第3節, 及び第4節である. 第1節, 第2節は, 入力ストリームのどちらかが閉じられ たら, もう一方を出力ストリームに直結し, 自ら消滅するために用意されている.
2本の入力ストリームに同時に入力が流れてきた場合の非決定性(どちらが先 に出力ストリームに流されるかは決められていないこと)はマージャの問題点 ではなく, KL1の特質であることは前章で述べた. マージャには入力ストリームの本数の問題があるが, これについては後に 詳しく述べる。
プログラムが大規模になってくると全体を一つのフラットな木構造にする ことは難しくなる. そのような場合にはネストした木構造にするのが良い.
探索問題では, 問題を部分問題に分割し, 各部分問題を各プロセスに解 かせ, その部分問題の解を回収して全体の解を得るという分割統治法がよく 用いられるが, この木構造プロセス・ネットワークはその解法によくマッチす る. 探索問題の多くはこの木構造を基本としたプロセス・ネットワークで解ける.
ところで, 上述のsuqare/2, cube/2などの述語によって実現されるプロセスは, 第1引数の入力ストリームに入力が流れてきた時になって始めて動き出す. 流れてくる前は中断している. つまりこれらのプロセスはプロセス・ネットワークの中でデータ駆動的に 動いている. しかし, このデータ駆動だけで全てがうまくいくわけではない.