リンダ（調整言語）

リンダ
パラダイム	マルチパラダイム
家族	調整言語
デザイン：	デビッド・ゲレンター
開発者	サイエンティフィックコンピューティングアソシエイツ
初登場	1986年; 38年前
Webサイト	lindaspaces.com
影響を受けた
	ジャワ語

コンピュータサイエンスにおいて、Lindaは並列コンピューティング環境での通信を支援する調整モデルです。David Gelernterによって開発されたこのモデルは、 FortranやCなどの本格的な計算言語と一緒に使用することを目的としており、Lindaの役割は「計算アクティビティを作成し、それらの間の通信をサポートすること」です。^[3]^[4]^[5]

歴史

デイヴィッド・ゲレンターは1979年に博士課程の学生としてLindaの最初のバージョンを書き、ポルノ映画『ディープ・スロート』に出演したリンダ・ラヴレースにちなんで名付けた。当時、並列処理の主要言語はAdaだったが、ゲレンターはAdaを「洗練されておらず、扱いにくい」言語だと考えていた。^[6]

1986年に、ゲランターがエール大学の同僚ニコラス・カリエロ、 AT&Tベル研究所のスディール・アフージャとともにIEEEジャーナルに「リンダと友人たち」を発表し、広く公開されました。^[7]

1990年代初頭までに、Lindaは、ウォール街の証券会社やAT&T、ボーイング、ユナイテッドテクノロジーズなどの企業で、ビッグデータ分析をより効率的に行うために広く使用されるようになりました。Lindaをベースにした特殊な並列コンピューティングアプリケーションの作成を専門とする企業もあり、その最大の企業は、ニューヘイブンに拠点を置くScientific Computing Associatesで、同社は数人のイェール大学のコンピュータ科学者によって設立されました（ゲラーンターは時折彼らのコンサルタントを務めていましたが、そこで働いてはいませんでした）。^{[6] Lindaへの関心は1990年代半ばに低下しましたが、1990年代後半に}サンマイクロシステムズやIBMを含むいくつかの企業がJavaでLindaを実装したことで復活しました。^[3]

概要

モデル

Lindaモデルは、分散共有メモリを提供します。これはタプルスペースと呼ばれ、その基本的なアドレス指定可能な単位はタプル、つまり型付きデータオブジェクトの順序付けられたシーケンスであるためです。具体的には、Lindaでは、タプルは最大16個の型付きフィールドを括弧で囲んだシーケンスです。タプルスペースは、タプルを保存および取得するワーカーと呼ばれる「プロセスによって論理的に共有」されます。[ ^8]

オペレーション

Lindaの主な利点の1つは、タプルスペースにアクセスするためにワーカーがタプルに対して実行する操作が6つだけというシンプルな点です。^[9]

out: タプルをタプルスペースに入れる
in: タプルスペースから指定されたパターンに一致するタプルを取り出します（一致するものがない場合、操作はブロックされます）
rd: タプルスペースから指定されたパターンに一致するタプルをコピーします（一致するものがない場合、操作はブロックされます）
eval: タプルを評価するための新しいプロセスを作成します
inp: の非ブロッキングバージョンin（一致しない場合はエラーメッセージが返されます）
rdp: の非ブロッキングバージョンrd（一致しない場合はエラーメッセージが返されます）

比較

他の並列処理モデルと比較すると、Linda は、プロセス調整を計算とは別のアクティビティとして扱う点でより直交的であり、単一モデルでさまざまなレベルの同時実行 (ユニプロセッサ、マルチスレッドマルチプロセッサ、ネットワーク) を包含できる点でより汎用的です。直交性により、異なる言語やプラットフォームで計算するプロセスが同じプリミティブを使用して相互運用できます。汎用性により、マルチスレッド Linda システムを変更せずに複数のコンピュータに分散できます。

メッセージパッシングモデルでは、密結合したプロセスが何らかのシーケンスまたはプロトコルで互いにメッセージを送信する必要があるのに対し、Linda のプロセスは他のプロセスから分離されており、タプルスペースを介してのみ通信します。プロセスは、消費または生成されるタプルの種類を除いて、他のプロセスの概念を持つ必要はありません。マルチプロセッシングコミュニティからの Linda に対する批判は、メッセージパッシングインターフェイス(MPI) システムと比較して Linda システムの操作速度が遅いことに焦点を当てる傾向があります。^[要出典]正当性がないわけではありませんが、これらの主張は重要な種類の問題に対して大部分が反駁されました。^{[10] Linda モデルに対する詳細な批判は、Steven Ericsson-Zenith の著書}Process Interaction Models にも記載されています。^[11]

研究者らは、（オープン分散型）コンピュータシステム間のさまざまな種類の通信と調整をサポートし、モデルのさまざまな使用法から生じる特定の問題を解決するために、さらに多くのプリミティブを提案してきました。^{[引用が必要]}研究者らはまた、このモデルの仮想共有メモリを実装するさまざまな手段を試してきました。^{[引用が必要]}これらの研究者の多くは、オリジナルの Linda モデルに大幅な変更を提案し、Linda のようなシステムとして知られる一連のシステムを開発し、（オリジナルのバージョンとは異なり）直交技術として実装しました。その一例が、 Steven Ericsson-Zenith が設計した言語Easeです。

リンダのアプローチはフローベースプログラミングのアプローチとも比較されている。^[12]

リンダ・カルキュラス

リンダ計算は上記のモデルを形式化したものであるが、以下ではoutとevalの両方の演算を包含している点が異なる。^[13] $\mathrm {outeval}$

構文

タプルの具体的な表現を抽象化します。タプルの集合があり、タプルに置換関数を適用して、項を変数に置き換えてタプルを生成することができると仮定します。たとえば、タプルがある場合、置換を適用すると次のようになります。 $t\in {\mathcal {T}}$ $\sigma$ $t=({\mathit {hello}},x)$ $\sigma =\{{\mathit {world}}/x\}$ $t$ $({\mathit {hello}},{\mathit {world}})$

Linda 計算プロセスは次の文法によって定義されます。

$P,Q::=t\;|\;\mathrm {outeval} (P).Q\;|\;\mathrm {rd} (t).P\;|\;\mathrm {in} (t).P\;|\;P+Q\;|\;\mathbf {rec} XP\;|\;X$

構文には、後述する Linda 操作、非決定論的選択、および再帰が含まれます。置換関数は、再帰的に処理するように拡張されます。

セマンティクス

タプル空間は、プロセスの多重集合として表現されます。は多重集合、は単一多重集合、は多重集合の和集合演算であるとして、と書きます。セマンティクスは、次のように多重集合上の縮約関係として定義されます。 $M\,|\,P$ $M\uplus \{P\}$ $M$ $\{P\}$ $\uplus$ $M\rightarrow M'$

${\begin{array}{lrcll}{\text{(outeval)}}&M\,|\,\mathrm {outeval} (P).Q&\rightarrow &M\,|\,P\,|\,Q&\\{\text{(read)}}&M\,|\,\mathrm {rd} (t).P\,|\,t'&\rightarrow &M\,|\,P\sigma \,|\,t'&{\text{if exists }}\sigma {\text{ such that }}t\sigma =t'\\{\text{(input)}}&M\,|\,\mathrm {in} (t).P\,|\,t'&\rightarrow &M\,|\,P\sigma &{\text{if exists }}\sigma {\text{ such that }}t\sigma =t'\\{\text{(left choice)}}&M\,|\,P+Q&\rightarrow &M\,|\,P&\\{\text{(right choice)}}&M\,|\,P+Q&\rightarrow &M\,|\,Q&\\{\text{(recursion)}}&M\,|\,\mathbf {rec} X.P&\rightarrow &M\,|\,P\{\mathbf {rec} X.P/X\}&\\\end{array}}$

(input) はタプルスペースからタプルを消費しますが、(read) は読み取りのみを行うことに注意してください。結果として得られる操作セマンティクスは同期的です。 $t'$

実装

Linda はもともとCとFortranで実装されていましたが、その後、次のような多くのプログラミング言語で実装されました。

C : C-Linda、TCP-Linda、LinuxTuples
C++ : CppLinda、Boreas
C# : pSpaces
エルラン：エルリンダ
行く：pSpaces
Java : JavaSpaces、jRESP、TSpaces、LightTS、LIME、pSpaces
JavaScript : pSpaces
リスプ
Lua : LuaTS Lua レーン
プロローグ: SICStus プロローグリンダ
Python : PyLinda について
ルビー：リンダ
Swift : pSpaces

注目すべき Linda の実装には次のようなものがあります。

C-Linda または TCP-Linda - Martin Schultz が設立した Scientific Computing Associates による、スーパーコンピュータおよびクラスターシステム向けの仮想共有メモリの最も初期の商用かつ広範な実装。
JavaSpaces - 分散コンピューティングの普及に貢献した Java ベースのタプルスペース実装。
TSpaces - IBM の Java ベースのタプルスペースプラットフォーム。^{[過度の重み? –議論]}

参照

参考文献

^ Ciancarini, Paolo. 「講義3: 調整言語」(PDF)。ボローニャ大学。 2022年1月9日閲覧。
^ 「David Gelernter、BA & MA '76」。Yale Scientific。2011年2月14日。 2022年1月8日閲覧。
^ ab Wells, George (2005 年 7 月)。「コーディネーション言語: Linda による未来への回帰」(PDF)。カンファレンス: ソフトウェアエンティティのコーディネーションと適応技術に関する第 2 回国際ワークショップ。ローズ大学。2009 年 12 月 19 日時点のオリジナル(PDF)からアーカイブ。
^ Gelernter, David; Carriero, Nicholas (1992 年 2 月). 「コーディネーション言語とその重要性」(PDF) . Communications of the ACM . 35 (2): 97–107. doi :10.1145/129630.129635. S2CID 7748555.
^ Carriero, Nicholas; Gelernter, David (1985-01-01). 「S/Net の Linda カーネル (拡張要約)」。第10回 ACM オペレーティングシステム原則シンポジウム議事録 - SOSP '85。SOSP '85。ニューヨーク、ニューヨーク、米国: ACM。pp. 160–。doi : 10.1145 /323647.323643。ISBN 978-0897911740. S2CID 6922183。
^ ab Markoff, John (1992年1月19日). 「David Gelernter's Romance With Linda」. The New York Times . 2019年12月30日時点のオリジナルよりアーカイブ。 2022年1月8日閲覧。
^ アフジャ、スディール;カリエロ、ニコラス。 David Gelernter (1986 年 8 月)、「Linda and Friends」、Computer、19b (8)、IEEE: 26–34、doi :10.1109/mc.1986.1663305、S2CID 5155678
^ John H. Reynolds (2002 年 12 月)。「Linda が眠っている理髪師を起こす」( PDF)。冬季シミュレーション会議の議事録。第 2 巻。カリフォルニア州サンディエゴ: IEEE。pp. 1804–1808。doi : 10.1109 /WSC.2002.1166471。ISBN 0-7803-7614-5. S2CID 62584541 . 2022年1月8日閲覧。
^ 関正俊 (2017年2月). 『dRubyブック: Rubyによる分散並列コンピューティング (第0.1版)』. Pragmatic Programmers . 2022年1月9日閲覧。
^ Carriero; et al. (1994 年 4 月 1 日). 「メッセージパッシングシステムに代わる Linda の代替手段」(PDF) . Parallel Computing . 2 (4): 633–655. doi :10.1016/0167-8191(94)90032-9.
^ Ericsson-Zenith (1992).プロセス相互作用モデル. パリ大学.
^ J. Paul Rodker Morrison (2004年7月2日). 「Coordination Language」. 2023年9月28日時点のオリジナルよりアーカイブ。2022年1月9日閲覧。
^ Cridlig, Régis; Goubault , Eric (1993). 「Linda ベースの言語の意味論と分析」。Lecture Notes in Computer Science、vol 724。Springer、ベルリン、ハイデルベルク。doi :10.1007/ 3-540-57264-3_30。ISBN 978-3-540-57264-0。

[lecture-1] Ciancarini, Paolo. 「講義3: 調整言語」(PDF)。ボローニャ大学。 2022年1月9日閲覧。

[scientific-2] 「David Gelernter、BA & MA '76」。Yale Scientific。2011年2月14日。 2022年1月8日閲覧。

[wells-3] Wells, George (2005 年 7 月)。「コーディネーション言語: Linda による未来への回帰」(PDF)。カンファレンス: ソフトウェアエンティティのコーディネーションと適応技術に関する第 2 回国際ワークショップ。ローズ大学。2009 年 12 月 19 日時点のオリジナル(PDF)からアーカイブ。

[coordination-4] Gelernter, David; Carriero, Nicholas (1992 年 2 月). 「コーディネーション言語とその重要性」(PDF) . Communications of the ACM . 35 (2): 97–107. doi :10.1145/129630.129635. S2CID 7748555.

[5] Carriero, Nicholas; Gelernter, David (1985-01-01). 「S/Net の Linda カーネル (拡張要約)」。第10回 ACM オペレーティングシステム原則シンポジウム議事録 - SOSP '85。SOSP '85。ニューヨーク、ニューヨーク、米国: ACM。pp. 160–。doi : 10.1145 /323647.323643。ISBN 978-0897911740. S2CID 6922183。

[nyt-6] Markoff, John (1992年1月19日). 「David Gelernter's Romance With Linda」. The New York Times . 2019年12月30日時点のオリジナルよりアーカイブ。 2022年1月8日閲覧。

[:0-7] アフジャ、スディール;カリエロ、ニコラス。 David Gelernter (1986 年 8 月)、「Linda and Friends」、Computer、19b (8)、IEEE: 26–34、doi :10.1109/mc.1986.1663305、S2CID 5155678

[barber-8] John H. Reynolds (2002 年 12 月)。「Linda が眠っている理髪師を起こす」( PDF)。冬季シミュレーション会議の議事録。第 2 巻。カリフォルニア州サンディエゴ: IEEE。pp. 1804–1808。doi : 10.1109 /WSC.2002.1166471。ISBN 0-7803-7614-5. S2CID 62584541 . 2022年1月8日閲覧。

[9] 関正俊 (2017年2月). 『dRubyブック: Rubyによる分散並列コンピューティング (第0.1版)』. Pragmatic Programmers . 2022年1月9日閲覧。

[mpi-10] Carriero; et al. (1994 年 4 月 1 日). 「メッセージパッシングシステムに代わる Linda の代替手段」(PDF) . Parallel Computing . 2 (4): 633–655. doi :10.1016/0167-8191(94)90032-9.

[process-11] Ericsson-Zenith (1992).プロセス相互作用モデル. パリ大学.

[12] J. Paul Rodker Morrison (2004年7月2日). 「Coordination Language」. 2023年9月28日時点のオリジナルよりアーカイブ。2022年1月9日閲覧。

[13] ^ Cridlig, Régis; Goubault , Eric (1993). 「Linda ベースの言語の意味論と分析」。Lecture Notes in Computer Science、vol 724。Springer、ベルリン、ハイデルベルク。doi :10.1007/ 3-540-57264-3_30。ISBN 978-3-540-57264-0。