データフロープログラミング

データフロープログラミング（英: dataflow programming）は、データフローの原理とアーキテクチャに準拠したプログラミングパラダイムであり、コンピュータプログラムをオペレーション間のデータフローの有向グラフとして模型化する。データフロー言語は、関数型言語の特徴を共有しており、より数値処理に適したものになっている。

概要

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

プログラミングにおける重要な概念として「状態」がある。状態とは基本的には、システムの各種条件（変数）の測定値のスナップショットである。多くのプログラミング言語は正しく動作させるために多数の状態情報を必要とするが、一般にプログラマからはそれら情報は隠蔽されている。実世界の例として、3方向の電灯スイッチがある。一般にスイッチを上にすれば電灯が点くが、3方向スイッチでは後ろの電灯が消えるかもしれない。結果は（おそらく視界からは見えない）他のスイッチの状態によって決まる。

実際、状態はコンピュータから見ても隠蔽されていることが多く、ある情報の断片が（一時的ですぐに捨てられる情報だとしても）状態を符号化したものかどうかはコンピュータの関知するところではない。並列処理マシンでは状態情報を複数のプロセッサ間で共有する必要があるため、これは重大な問題となる。どの状態が重要かを知らない場合、多くの言語ではコードやデータの重要性を示すために大量の特別なコードを追加する必要がある。

そのようなコードは性能も低下させ、デバッグも非常に難しくする。性能コストの大きいコードは単一プロセッサで動作させたときもある程度のコストがかかる。このような並列性の問題は、データ集約型で非OLTP型アプリケーションを Enterprise JavaBeans で組んだときの性能の低さの主な原因である。

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

処理・操作は入出力のある「ブラックボックス」であり、全てが明示的に定義される。その入力が全て妥当となったとたんに実行される。従来型のプログラムは一連の命令文で構成されているが、データフロープログラムは組み立てラインに労働者が並んでいるようなもので、各労働者は材料が到着したとたんに割り当てられた作業を開始する。データフロー言語が本質的に並列的であるというのはこのためである。各処理・操作には保持すべき隠蔽された状態を持たず、どの処理・操作も同時に実行可能である。

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

共有すべき並列処理はリストの検索部分だけであり、このリストがプログラム全体の状態を表している。従って、状態を管理する作業はプログラマの手を離れ、言語処理系がその役割をする。並列処理向けの処理系を単一プロセッサコアのマシン上で動作させるとオーバーヘッドが生じるが、これは異なる実装の処理系と置換することでオーバーヘッドのない実行が可能となる。

データフロープログラミングを効率的に実装することを指向したハードウェアアーキテクチャも各種存在する。Greg Papadopoulos はMITのタグ付きトークン・データフローアーキテクチャを設計した。

特徴

有向グラフ

データフロープログラミングは、{input} operator {output}を基本単位にする。outputは次のinputになる。operatorは有向グラフ形式で連結配置される。各ノードがoperatorで、矢印がinputとoutputのフローである。データフローには分流（diverge）と合流（converge）の概念がある。右図ではBのoutputは、C・D・Eへのinputに分流される。B・C・Dのoutputは、Eへのinputに合流される。

データフロープログラムは、起点オペレータへの外部からのデータ入力で開始される。右図ではAとGが起点になる。これはイベント駆動に似ている。データ入力ごとにスレッドが生成され、事実上のマルチスレッドで同時計算されつつ、特定の合流オペレータで同期が取られる。合流ではスレッドも一つに融合される。分流ではスレッドも別々に生成される。その同期にはプッシュ（push model）とプール（pull model）の二つがある。プッシュは、input値が全て揃うまで計算待機されるというバリア同期である。プールは、最初のinputが来てから一定時間経過すると未input値をdefault値にして強制計算outputするというタイマー同期である。

データフローの有向グラフ構築は、しばしばビジュアルプログラミングの対象にされる。

歴史

1961年にベル研究所で開発された制御回路設計プログラム「BLODI -BLOck DIagram-」は、フローチャート表示スクリーン上のオペレータブロックの視覚的配置を可能にしたデータフロープログラミングの元祖である。ジョン・ラリー・ケリーJrらが関与していた。

1966年にマサチューセッツ工科大学のバート・サザランド(アイバン・サザランドの兄) は『The On-line Graphical Specification of Computer Procedures』論文を発表して、Sketchpadとデータフローを融合したフレームワークを制作した。同時期のMITでデータフローの並行処理を提唱したジャック・デニスがデータフロープログラミングの最初の提唱者と見なされている。

60年代のデータフロープログラミングは、その並行計算性質からマルチプロセッサの大型コンピュータ施設向けになった。アメリカ国家安全保障局のPOGOL、アメリカ国防省のVHDL、アメリカ海軍のSPGNなどが有名である。60～70年代のデータフロープログラミングは、非ノイマン型コンピュータのモデルとして重視されていた。

70年代半ばのデータフロープログラミングはマイクロコンピュータ向けにもなり、1976年にLucidが公開された。1983年にローレンス・リバモア国立研究所で開発されたSISALは、束縛変数や暗黙並行計算仕様を備えて一つの標準形になり、SACなど数々の派生言語が登場している。

1983年のMacintoshで登場したProgprahは、GUI操作できるデータフローのビジュアルプログラミング言語であったが、シングルプロセッサ実行ゆえに1996年までは非並行計算仕様であった。Progprahは関数や変数の記述を、図形や線分の視覚マーク配置に置き換えた。Prographが示したプログラムレス理念は評価され、ホビーと実用を兼ねた数々のビジュアル言語がMacintoshとWindows環境で登場している。1986年のLabVIEWは非プログラマでも扱える言語として注目を集めた。これは実験機器のデータリンク設計用であったが汎用的にも使える。1991年のVEE は計測機器（デジタル電圧計、オシロスコープ、波形発生器など）のデータリンク設計用である。

言語と開発環境

• BioEra
• Cantata - 画像処理のためのデータフロー・ビジュアル言語
• CAL
• FlowDesigner
• ID
• KSKP - 大規模データの処理・分析環境。ビジュアルプログラミング言語で処理を構築できる。
• Lustre
• Mindscript - オープンソースの視覚化・ソフトウェア開発環境
• Max/Msp

• Lucid - 1976年
• VHDL - 1981年
• Lustre - 1983年
• SISAL- 1983年
• Prograph CPX - 1983年
• Verilog HDL - 1984年
• Linda - 1986年
• LabVIEW - 1986年
• SIGNAL- 1986年
• CMS Pipelines- 1986年
• Keysight VEE- 1991年
• Simulink - 1992年
• SAC- 1994年
• Pure Data - 1996年
• Joule- 1996年
• Orange - 1996年
• Pipeline Pilot - 1999年
• Hume- 2000年
• SystemVerilog - 2002年
• BMDFM- 2002年
• Quartz Composer - 2004年
• KNIME- 2006年
• Cuneiform- 2013年
• Scilla - 2018年

フレームワークとAPI

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

関連項目

• 関数型プログラミング
• 並行プログラミング
• ビジュアルプログラミング
• イベント駆動型プログラミング
• シグナルプログラミング
• フローベースプログラミング
• リアクティブプログラミング
• アクターモデル
• デジタル信号処理
• ストリーム処理
• パイプライン