Program Composition Notation

Program Composition Notation

パラダイム	並行論理プログラミング
登場時期	1989年
設計者	K. Mani Chandy、Stephen Taylor 他
型付け	静的型付け、動的型付け
影響を受けた言語	Strand、PARLOG、Guarded Horn Clauses
影響を与えた言語	CC++

PCN (Program Composition Notation)はK. Mani ChandyとStephen TaylorがStrandの設計者であるIan Fosterの協力を受けて設計した、複数のプログラムを並列環境や分散環境で組み合わせるためのプログラミング言語である[1]。それまでの並行論理プログラミング言語の技術要素に、手続型言語の変数や{}をつかったブロック表現などを取り入れたプログラミング言語で、C言語やFortranのプログラムを呼び出すことができた。

概要

PCN (Program Composition Notation)は並行論理プログラミングでのガードや論理変数による通信と同期の仕組みをそのまま流用しながら、通常の手続型言語であるC言語などの要素を取り入れたプログラミング言語である。言語の基本的な部分はIan FosterやStephen Taylorが設計したStrandの影響を大きく受けているが、その構文はC言語風の{}によるブロック構造を持っている。C言語やFortranのプログラムとPCN自身のプログラムを組み合わせ、並列環境や分散環境で動くより大きなプログラムを構築するために設計された。PCNはアルゴンヌ国立研究所とカリフォルニア工科大学で開発され、UNIXワークステーションやBBN Butterflyなどの商用の並列コンピュータ上にインプリメントされた。

PCNの特徴は以下の通りである[2]。

• 値が変更可能な可変変数（Mutable Variable）と値が一度決まったらその後は変更できない定義変数（Definition Variable）の2種類の変数

それぞれ従来の手続型言語の変数と並行論理プログラミングでの論理変数とに相当する。定義変数は並行プロセス間の通信や同期に使われる。可変変数（Mutable Variable）は変数宣言が必要で、宣言されていないものは定義変数として扱われる。

• 逐次実行ブロック、並行実行ブロック、選択(choice)ブロックの3種類のブロック

それぞれ{; .., ... }、{|| .., ... }、{? ..-> .., ..-> .., ... }の形式で表現される。選択(choice)ブロックはエドガー・ダイクストラのガード付きコマンドと同様、ガードの条件を満たした文のみが実行される。

プログラム例

可変変数 m の内容がリスト x の要素であれば true(1) を、そうでなければ false(0) を返すプログラムの例を以下に示す。

member(x,m,r)
int m, r;
{? x ?= []             -> r:= false,
   x ?= [vlxs], v == m -> r:= true,
   x ?= [vlxs], v != m -> member(xs, m, r)
}

二分木（バイナリツリー）t の高さ z を求めるプログラムの例を以下に示す。ツリーの要素は {left, val, right} か空のタプルで表現されているものとする。各枝の深さは並行して計算され、定義変数 l と r によりheightの実行とｚの計算との同期が行われる。

height(t,z)
{? t ?= { }                -> z = 0,
   t ?= {left, val, right} -> {|| height(left, l), height(right, r),
                                 {? l >= r -> z = 1 + l,
                                    r >= l -> z = 1 + r
                                 }
        }
}

関連項目

• 並行論理プログラミング
• 並行プログラミング
• Strand

参考文献

1. Chandy,K.M. and S.Taylor, The Composition of Concurrent Programs,in Proceedings Supercomputing '89, Reno, Nevada, Nov.13-17, ACM. 1989.
2. Chandy, K. Mani and Taylor, Stephen, A Primer for Program Composition Notation. Technical Report. California Institute of Technology. 1990. [CaltechCSTR:1990.cs-tr-90-10]