KL1とは？ わかりやすく解説

プログラミング言語

>>他のプログラミング言語

■カテゴリ / ■テンプレート

KL1 (Kernel Language One) は、Guarded Horn Clauses (GHC) を基に設計された言語で、並行・並列処理に向いた並行論理プログラミング言語である。第五世代コンピュータプロジェクトでハードウェアと応用ソフトウェアとの間をつなぐ共通核言語として近山 隆により設計され、並列マシンのオペレーティングシステムPIMOSやKL1を含む様々な言語処理系、各種応用プログラムの作成に利用された^[1]。 KL1 は第五世代コンピュータプロジェクトで並列マシン PIM 上の処理系として開発された。UNIX上での処理系として KLIC がある。

概要

KL1は、並行論理プログラミング言語であるGuarded Horn Clauses (GHC) のガード部を組み込み述語のみに制限したFlat GHCをもとに拡張を施した言語である。

論理的並行性の記述にはGHCの機能をそのまま使い、それを複数のマシンに分散する物理的並行性(並列性)やプロセスごとの優先順位などをそれに付加するプラグマとして追加することで、論理的並行性と物理的並行性を別々に指定可能にし、プログラムの正しさに影響を与えることなく負荷分散の仕方などを変えられるように設計された。逐次処理言語に並列処理機能を追加した多くの並列プログラミング言語が元の言語と全く異なった言語になってしまうのに対し、各種プラグマはプログラムの効率にのみ影響し、KL1はFlat GHCと同じ意味を持つ。そのためプログラムの解析・検証は単純なGHCのレベルで行うことができる。

また複数のプロセスの実行制御、資源管理、例外処理を行うため「荘園」と呼ばれる機能が追加された。

プログラム例

与えられたリストのクイックソートを行うプログラム例を示す。part/4はリストをピボットより大きい数のリストと小さい数のリストの2つに分割する。二分割された各々のデータはそれぞれqsort/3でソートされる。

:- module quicksort.
qsort([Pivot|Xs], Ys0, Ys2) :- part(Xs,Pivot, Small, Large),
                               qsort(Small, Ys0, [Pivot|Ys1]),
                               qsort(Large, Ys1, Ys2).
qsort([],         Ys0, Ys1) :- Ys0 = Ys1.

part([X|Xs],Pivot,Small,Large) :- Pivot< X | Large=[X|L1], part(Xs,Pivot,Small,L1).
part([X|Xs],Pivot,Small,Large) :- Pivot>=X | Small=[X|S1], part(Xs,Pivot,S1,Large).
part([],    _,    Small,Large) :-            Small=[], Large=[].

qsort/3を呼び出すことで順次part/4とqsort/3とのプロセスネットワークが作られ、それらの間で並行処理が行われる。

Guarded Horn Clauses

Guarded Horn Clauses (GHC) は並行プログラミングのためのプログラミング言語で、論理変数を介して通信を行う複数の軽量プロセスのネットワークとしてプログラムを記述する。多くの並行プログラミング言語が逐次処理言語に並行実行の機能を追加したものなのに対して、GHCは並行実行が基本で、並行処理を素直に記述できる。

GHCではホーン節にガードを導入した以下のような規則(Clause)の集まりでプログラムを記述する。"|"はコミット演算子と呼ばれる。G はガード部、B はボディ部と呼ばれる。Head、G、Bはそれぞれ原子論理式である。ガード部の条件がない場合、ガード部とコミット演算子は省略できる。

Head :- G1, ..., Gn| B1, ..., Bm.  (n,m≧0)

HeadとG₁, ..., G_nはプロセス書き換えのための条件、B₁, ..., B_mは書き換え後のプロセスを表す。生成されたプロセスは全て並行に実行される。また、各プロセスごとの書き換え条件のチェックも複数の節で並行に実行してよく、コミット時にただ1つの節が選択される(コミッティッド・チョイス)。prologと異なりバックトラックの機能はない。

KL1のベースであるFlat GHCは、GHCのガード部を組み込み述語のみに制限したもので、ガードがアトミックに動作できるため、プログラムの長さは増加するが効率のよい処理系の実装が可能になる。

プラグマ

GHCで記述されたプログラムを効率よく並行・並列実行させるため、KL1では以下のプラグマが導入された。プログラムの正しさに影響を与えることなく負荷分散の仕方などを変えられるように設計されている。なお、プラグマはプログラムの正しさとは分離された効率のためだけの指定であり、これに従わない方が効率がいいと処理系が判断すると、必ずしも従わない場合もある。

* ゴール分散プラグマ　　　　　Goal@node(Node)
* ゴール優先度指定プラグマ　　Goal@priority(Priority)
* 節優先度指定プラグマ　　　　alternatively.

ゴール分散プラグマは特定のゴール(プロセス)を実行するノードを指定する。ノードは個別のプロセッサ、あるいは負荷分散の対象となるプロセッサの集まりである。以下に、PEs 個のノードに対し N 個のspawnプロセスをサイクリックに割り当てる述語の例を示す。Prologと同様、英大文字や"_"で始まる項は変数を表す。%以降はコメントである。

:- module cyclic.
:- public distribute/1.
distribute(N):- true |
                current_node(_,PEs),  %ノードの総数PEsを取得
                fork(N,PEs,0).        %N個のプロセスをPEs個のノードで起動

fork(0,PEs,PE):- true | true.
otherwise.
fork(N,PEs,PE):- PeNo:=PE mod PEs |
                spawn@node(PeNo),     %PeNoのノードでspawnプロセスを起動
                NextPE:=PE+1,
                N1:=N-1,
                fork(N1,PEs,NextPE).

ゴール優先度指定プラグマはゴール(プロセス)ごとの優先順位を指定する。ただし必ず優先順位を守ろうとすると効率的な実装が難しくなり、返って効率が落ちる可能性があるため、必ず守られるとは限らない。

節優先度指定プラグマはプログラムの構成要素である節(Clause)の優先順位である。節の優先順位の指定には、最初に優先したい節を先に書き、他の節との間に "alternatively." を書く。ゴール優先度指定プラグマと同様の理由で、節の優先順位も必ず守られるとは限らない。

荘園

荘園は一種のメタコール機能で、起動した複数のプロセスの実行制御、資源管理、例外処理を行う。荘園自身をネストすることもできる。荘園は外部からの制御ストリームによって起動/停止 /再起動/実行放棄や使用可能な計算機資源の制御を行い、結果を報告ストリームに返す。荘園は以下のような組み込み述語を呼び出すことで生成される。Goalは実行すべきゴール(プロセス)、Tagはネストした荘園を識別するフラグである。

execute(Goal, ControlStream, ResultStream, Tag)

この機能は、オペレーティングシステムなどのシステムプログラミングのために使われ、またオペレーティングシステム自身のデバッグのための仮想マシン環境としても使用された^[1]。

関連項目

• 並行論理プログラミング
• 論理プログラミング
• 並行プログラミング
• Prolog
• Guarded Horn Clauses

参考文献

• Ueda, K. Guarded Horn Clauses. ICOT Technical Report TR-103, ICOT, Tokyo. 1985.
• Ueda, K. Guarded Horn Clauses.(pdf) Doctoral Thesis. Information Engineering Course, University of Tokyo, 1986 2010-01-20 閲覧
• 近山 隆, KL1入門. 1991. 2010-01-20 閲覧
• 近山 隆, オペレーティングシステムPIMOSと核言語KL1.(pdf) 1992. 2010-01-20 閲覧
• 近山 隆, 他, KLIC ユーザーズ マニュアル.(pdf) 1997. 2010-01-20 閲覧
• 上田 和紀, 並行論理プログラミング言語　GHC/KL1.(pdf) 2000. 2010-01-20 閲覧
• 斉藤 賢爾, Overlay GHC.(pdf) 2008. 2014-07-05 閲覧
• 古川 康一,溝口 文雄(編) 並列論理型言語GHCとその応用 (知識情報処理シリーズ) 共立出版 1987, ISBN 978-4320022669

1. ^ ^{a b} 近山 隆, オペレーティングシステムPIMOSと核言語KL1

外部リンク

• 並列論理型言語KL1の処理系KLICのページ
• KLIC 講習会テキスト KL1 言語編
• KLIC 講習会テキスト KLIC システム編