KL1
与えられたリストのクイックソートを行うプログラム例を示す。part/4はリストをピボットより大きい数のリストと小さい数のリストの2つに分割する。二分割された各々のデータはそれぞれqsort/3でソートされる。
qsort/3を呼び出すことで順次part/4とqsort/3とのプロセスネットワークが作られ、それらの間で並行処理が行われる。
GHCで記述されたプログラムを効率よく並行・並列実行させるため、KL1では以下のプラグマが導入された。プログラムの正しさに影響を与えることなく負荷分散の仕方などを変えられるように設計されている。なお、プラグマはプログラムの正しさとは分離された効率のためだけの指定であり、これに従わない方が効率がいいと処理系が判断すると、必ずしも従わない場合もある。
ゴール分散プラグマは特定のゴール(プロセス)を実行するノードを指定する。ノードは個別のプロセッサ、あるいは負荷分散の対象となるプロセッサの集まりである。以下に、PEs 個のノードに対し N 個のspawnプロセスをサイクリックに割り当てる述語の例を示す。Prologと同様、英大文字や"_"で始まる項は変数を表す。%以降はコメントである。
ゴール優先度指定プラグマはゴール(プロセス)ごとの優先順位を指定する。ただし必ず優先順位を守ろうとすると効率的な実装が難しくなり、返って効率が落ちる可能性があるため、必ず守られるとは限らない。
節優先度指定プラグマはプログラムの構成要素である節(Clause)の優先順位である。節の優先順位の指定には、最初に優先したい節を先に書き、他の節との間に "alternatively." を書く。ゴール優先度指定プラグマと同様の理由で、節の優先順位も必ず守られるとは限らない。
Guarded Horn Clauses (GHC) は並行プログラミングのためのプログラミング言語で、論理変数を介して通信を行う複数の軽量プロセスのネットワークとしてプログラムを記述する。多くの並行プログラミング言語が逐次処理言語に並行実行の機能を追加したものなのに対して、GHCは並行実行が基本で、並行処理を素直に記述できる。
GHCではホーン節にガードを導入した以下のような規則(Clause)の集まりでプログラムを記述する。"|"はコミット演算子と呼ばれる。G はガード部、B はボディ部と呼ばれる。Head、G、Bはそれぞれ原子論理式である。ガード部の条件がない場合、ガード部とコミット演算子は省略できる。
HeadとG1, ..., Gnはプロセス書き換えのための条件、B1, ..., Bmは書き換え後のプロセスを表す。生成されたプロセスは全て並行に実行される。また、各プロセスごとの書き換え条件のチェックも複数の節で並行に実行してよく、コミット時にただ1つの節が選択される(コミッティッド・チョイス)。prologと異なりバックトラックの機能はない。
KL1のベースであるFlat GHCは、GHCのガード部を組み込み述語のみに制限したもので、ガードがアトミックに動作できるため、プログラムの長さは増加するが効率のよい処理系の実装が可能になる。