CAL アクター言語

CAL（Cal Actor Language）は、データオブジェクト（トークン）の入力ストリームを出力ストリームに変換するステートフルオペレータである（データフロー）アクターを記述するための高水準プログラミング言語^{[1]です。CALは、シングルコアプロセッサ、}マルチコアプロセッサ、プログラマブルハードウェアなど、さまざまなターゲットプラットフォームにコンパイルされています。ビデオと処理、圧縮と暗号化など、いくつかのアプリケーション分野で使用されています。MPEG Reconfigurable Video Coding（RVC）^[2]ワーキンググループは、標準化活動の一環としてCALを採用しました。

CAL アクター言語は、2001 年にカリフォルニア大学バークレー校のPtolemy II プロジェクトの一環として開発されました。CAL は、マルチメディア処理、制御システム、ネットワーク処理など、 さまざまなアプリケーション ドメイン向けのデータフロー言語です。

データフローを選択するもう 1 つの一般的な理由は、目標が効率的な並列実装であるためです。これは、シーケンシャル プログラミング言語では実現が困難または不可能です。シーケンシャル言語は一般に並列化が難しいことで有名であるため、効率的な並列実装には通常、ユーザーからの十分なガイダンスが必要です。CAL データフロー プログラムは、必要なだけ並列処理を指定できるシンプルでわかりやすく強力な抽象化を提供し、ツールが計算の同時構造を活用する高度な実装を作成できるようにします。

データフローでプログラミングする場合、プログラマーは通常、一般的な順次プログラムとは異なる、計算システムの並行記述を構築します。データフロー プログラマーは、アルゴリズムのステップごとの実行に関心を持つのではなく、アクターと呼ばれる非同期通信エンティティのシステムを構築します。プログラミング作業の多くは、問題をアクターに適切に分解し、それらのアクター間で適切な通信パターンを設計することに向けられます。

アクターは、発火と呼ばれる一連のステップで計算を実行します。各ステップでは、次の処理が行われます。

• 1. アクターは入力ポートからトークンを消費する可能性がある。
• 2. 内部状態を変更する可能性がある。
• 3. 出力ポートでトークンを生成する場合があります。

したがって、アクターを記述するには、外部とのインターフェイス、ポート、内部状態の構造、実行できるステップ、これらのステップで実行される内容 (トークンの生成と消費、およびアクター状態の更新)、アクターが次に実行するステップの選択方法などについて記述する必要があります。このセクションでは、これらの問題に対処する CAL 言語の構成要素のいくつかについて説明します。アクションは、アクターが実行するステップ中に発生する事柄を記述します。実際、ステップはアクションの実行で構成されていると言っても過言ではありません。アクターがステップを実行すると、入力トークンを消費し、出力トークンを生成する場合があることを思い出してください。

したがって、入力パターンは次のようになります。

• これらは、アクションが実行（発動）されたときに消費されるトークンの数（ポートごと）を定義します。
• これらは、アクションの実行によって消費されるトークンがアクション内で参照される変数シンボルを宣言します。
• これらは、アクションの発動条件、つまりアクションが発動するために満たさなければならない条件を定義します。

アクションの出力側はもう少し単純で、出力式は、アクションが実行されるたびに各出力ポートで生成される出力トークンの数と値を定義するだけです。アクションが入力ポートと同じ数の入力パターン、または出力ポートと同じ数の出力式を提供する場合は、入力パターンまたは出力式が適用されるポートの明示的な命名を省略できます。このような場合、パターンまたは式は、ポート宣言に対して位置によって一致します。

アクターについて考える方法の 1 つは、データ ストリームの演算子として考えることです。つまり、トークンのシーケンスが入力ポートに入力され、トークンのシーケンスが出力ポートから出力されます。アクターの操作について説明するときは、ストリームの演算子として考えると役立つことがよくあります。アクターにはパラメーターがあります。パラメーターは、アクターの実行中に定数として機能し、アクターがアクター ネットワークの一部としてインスタンス化されるときに具体的な値が与えられます。アクター パラメーターの主な目的は、プログラマーが大量のコードを重複させることなく、関連するアクターのファミリーを指定できるようにすることです。

非決定論的アクターとは、同じ入力シーケンスに対して、複数の実行と複数の可能な出力を許可するアクターです。非決定論は、適切に使用すれば非常に強力になりますが、非常に厄介なエラーの原因にもなります。特に懸念されるのは、非決定論がアクターに不注意に導入される可能性があることです。つまり、作成者はアクターが決定論的ではないにもかかわらず、決定論的であると考えてしまうのです。CAL 言語の主要な設計目標の 1 つは、非決定論的アクターを記述できるようにすると同時に、ツールが非決定論の可能性のある原因を特定できるようにして、ユーザーに警告できるようにすることでした。

NDMerge のような非決定論的アクターの主な結果は、実際の実行中に、その出力が入力のタイミングに依存する可能性があることです。両方の入力キューが空で、NDMerge が入力を待機している場合、次のトークンが到着する入力は、出力の次にコピーされるものになる可能性があります。その結果、アクター ネットワーク内のアクティビティのスケジュール、またはNDMergeのようなアクターに入力するアクターの相対速度が、システムの出力に影響を与える可能性があります。これは、場合によっては望ましいこともあれば、そうでないこともあります。いずれにせよ、これは知っておく必要がある特性です。

アクターがトークンの到着の正確なタイミングに依存するような非決定性について考える 1 つの方法は、そのようなアクターが非決定性であるように見えるのは、ストリームの演算子として見たときだけであるということです。これは、その見方では実行の時間的特性が抽象化され、アクションが実行される順序を決定するために使用される情報が意図的に削除されるためです。CAL 言語の観点からは、これは完全に正確ではありませんが、それでも、トークンのタイミングとアクターの実装についてすべてわかっていたとしても、決定性ではない非決定性アクターを簡単に記述できます。たとえば、次のようになります。

アクションのガード句には、アクションが実行可能となるためにすべてが真である必要のあるいくつかの式が含まれます。最初のアクションが実行可能となるには、入力トークンが 0 以上である必要があり、その場合、出力Pに送信されます。そうでない場合、そのアクションは実行できません。逆に、2 番目のアクションが実行可能となるには、トークンが 0 未満である必要があり、その場合、出力 N に送信されます。このアクターの実行は次のようになります。アクターがゼロ トークンに遭遇すると、そのアクションのいずれも実行できないため、アクターは問題に遭遇する可能性があります。

何らかの入力で終了するアクターを記述することは違法ではありません。実際、一部のシステムではそのようなアクターをいくつか持つことが重要になる場合があります。しかし、これは注意が必要な落とし穴です。第二に、ガード条件は網羅的であるだけでなく、互いに独立しています。

最後に、ガード条件は、実際にトークンを消費することなく、入ってくるトークンを「覗く」ことができることに注意してください。ガードが偽であったり、アクションが他の理由で実行されなかったり、トークンが別のアクションによって消費されなかったりすると、トークンはそのままの場所に残り、次の実行に利用できるようになります。(または、SplitDeadの前のゼロ トークンの場合のように、アクターが死亡しているために削除されないため、トークンは永久にそこに残ります。)

以下の Select アクターは、ガードされたアクションの使用例の 1 つです。2つのストリーム (A 入力ポートと B 入力ポートに到着するストリーム) をマージするという点で、 NDMergeアクターに似ています。ただし、 S入力ポート に到着するトークンの (ブール) 値に従ってマージが行われます。

これまでのすべてのアクターでは、アクションの発動によって、同じアクターのその後のアクションの発動が影響を受けることはありませんでした。状態変数を使用すると、アクションの発動によって、同じアクターの同じアクションまたは別のアクションの後続の発動のための情報が残されます。このアクターの記述方法では、次の入力トークンの選択と、トークンの出力への実際のコピーは、1 つのアトミック ステップです。

Select とIterSelect はほぼ同等ですが、完全に同等というわけではありません。まず、IterSelect は同じ数のトークンを処理するために 2 倍のステップを実行します。次に、一致するデータ トークンがAまたはBで使用できるかどうかに関係なく、実際には S 入力トークンを読み取り、消費します。

前のセクションのIterSelectアクターは、状態を使用してアクションの選択を制御する方法を示しました。これは実際には非常に一般的なことであり、CAL 言語では、スケジュールの形式でこの目的のための特別な構文を提供しています。概念的には、スケジュールは状態変数を使用する特定のパターンをコード化したものと考えることができます。表現力の点で言語に何かを追加するものではありません。スケジュールを使用する理由は 2 つあります。

1. これらは通常、状態変数や多くのガードと割り当てを使用するよりも使いやすく、エラーも起こりにくくなります。
2. ツールはスケジュールにエンコードされた情報をより簡単に使用できるため、アクター内の規則性を認識して、より効率的なコードを作成したり、実装や設計に役立つその他の分析を実行したりできます。

各状態遷移は、元の状態、アクション タグのリスト、次の状態の 3 つの部分で構成されます。注目すべき点の 1 つは、アクションの数が増えたことです。元の 3 つではなく、スケジュール付きの新しいバージョンではアクションが 4 つになりました。その理由は、アクションが後続の状態を直接割り当てることができなくなったためです。元のバージョンでは、トークンの値に応じて read 状態に値 1 または 2 が割り当てられていました。スケジュール付きのバージョンでは、その状態の変更はステート マシンの構造に暗黙的に含まれており、どのアクションが実行されるかどうかに応じて変更が行われます。したがって、トークンの値を確認する条件は、アクションの本体内から、readTおよびreadFタグが付けられた 2 つのアクションのガードに移動しました。

入力ポートの 1 つにのみ入力がある限り、すべてが明確です。ただし、NDMerge と同様に、両方の入力ポートで入力が利用可能になると、2 つのアクションのいずれかが実行される可能性があり、アクター仕様には、どちらか一方を選択するように誘導するものは何もありません。

これまでの言語構造では、これを実現することはできませんでした。スケジュールは言語の既存の要素 (状態変数、ガード、割り当て) に縮小できるため、構文上の糖衣と見なすことができますが、この状況では、実際のところ、真の拡張、つまりアクションの優先順位が必要です。基本的な考え方は、アクションをその発動優先順位に関して関連付ける不等式をいくつか追加することです。

スケジュールの場合と同様に、アクション タグを使用して、後で参照するアクションを識別します (今回は優先度の不等式内)。優先度ブロックには、そのような不等式が 1 つだけ含まれており、アクション タグが付けられた config が、タグが付けられた process に関連し、前者が後者よりも優先されます。もちろん、このバージョンでもタイミングに大きく依存します。この場合、それが問題になる必要はなく、実際、このアクターが機能を実行するにはおそらくそれが要件です。ただし、一般に、優先度 (特に前の例のように使用される場合) は、正しい結果を得るために十分に理解しておく必要があることを理解することが重要です。特に、ネットワーク内の通信のタイミングに関する情報があいまいな場合は、それらを強力な実装指示として考えるのが最適です。

前の章では、トークンの入力と出力、アクション、アクション選択の制御など、アクター固有の概念に関連する CAL の構成要素に主に焦点を当てました。このセクションでは、CAL のより「平凡な」部分、つまりデータ オブジェクトを操作し、(シーケンシャルな) アルゴリズムを表現するために使用されるステートメントと式について説明します。言語のこの部分は、多くの手続き型プログラミング言語 ( C、Pascal、Java、Adaなど) に見られるものと似ているため、CAL で少し異なる可能性のある領域に焦点を当てます。

C などの言語とは異なり、CAL ではステートメントと式が明確に区別されています。ステートメントと式の役割、意味はそれぞれ異なり、互換的に使用することはできません。CAL の式は、値を計算することだけを目的とするコードです。式には値がある、または式が値に評価されるとも言います。ほとんどの式では、式が評価される値は、式が評価される時点での 1 つ以上の変数の値によって決まります。変数の値は時間の経過とともに変化する可能性があるため、同じ式でも、異なる時点で評価されると値が異なることがあります。

おそらく最も基本的な式は定数です。基本的な式のもう 1 つのグループは変数参照です。構文的には、変数は文字と数字のシーケンスです。式の重要な特性の 1 つは、変数を変更しないことが保証されていることです (副作用がないとも言えます)。したがって、式内で同じ変数を複数回参照すると、常に同じ結果になります。

CAL は、式を構築するために単項演算子と二項演算子の 2 種類の演算子を提供します。CAL の単項演算子は常にプレフィックス演算子です。つまり、単一のオペランドの前に現れます。二項演算子は、2 つのオペランドの間に現れます。

ある意味では、CAL のステートメントは式の正反対です。つまり、「戻り値」はありませんが、変数の値を変更できます。実際、変数の値を変更することがステートメントの目的です。ステートメントは厳密に順番に実行され、特に指定がない限り、ステートメントの実行はプログラム テキストに出現する順序で進行します。つまり、ステートメントによって生成された変数の変更は、後続のステートメントの実行に影響を与える可能性があります。

他のほとんどのプログラミング言語と同様に、プログラム内のステートメントが実行される順序を制御する構造があります。このループの ' foreachキーワードの直後の部分は、リスト内包表記のジェネレーターとよく似ています。

• 入力パターン: 変数の宣言
• ガード: 有効化条件の指定
• 出力式: 出力トークンの計算
• 本文: アクターの状態の変更