過剰生産とその抑制

非常に単純な次のプログラムを用意する.

%  gencon.kl1
:- module main.

main:- true |
     generator(100,Stream), consumer(Stream).

generator(0,Stream) :- true | Stream = [].
generator(N,Stream) :- N =\= 0 |
     Stream = [N | NextStream],
     N1 := N - 1,
     generator(N1,NextStream).

consumer([]):- true | true.
consumer([N|Stream]):- integer(N) | consumer(Stream).

このプログラムは図 4.2 の通り整数列が次々に消費者に送られる.

  
図 4.2: 生産者-消費者問題プログラムの実行

前項で取り上げた LIFO スケジューリングを仮定し, プログラムを実行する.

無事動いたとしよう. プログラムを書き換えて生成データを増やす.

main :- true | generator(20000,Stream), consumer(Stream).

最大ヒープサイズ 30k ワードで実行するとメモリが足りなくなるのである. 何故であろうか ?

述語定義を眺めると述語 generator が 自分自身をサブゴールとしてリダクションするように記述されている. LIFO スケジューリングに従うと仮定すると, 述語 generator だけ が次々に走り, 長さ N のリストを生成して述語 generator の 実行が終了する. 次に述語 consumer の実行が開始することになる. 長さ 100 程度の リストを生産するのは問題なかったが, 長さ 20,000 のリストの生産を試みると 過剰生産でメモリが飽和してしまうことがあり得るのである.

さてどうするべきか. ひとつの解決方法として生産者プロセスと 消費者プロセスの間で同期をとる, 要求駆動的なプログラミングをする ことが考えられる.