資料流程編程

程式設計中,資料流程編程是一種程式設計範式,它將程式建模為資料在運算(operation)之間流動的有向圖,從而實現了資料流程原理和架構。資料流程程式語言,共享了純函數式語言的某些特徵,比如單賦值,並且開發它們的動因,通常是為了向更適合數值處理的語言,增加函數式程式設計概念。

歷史

編輯

先驅的資料流程語言是BLODI(BLOck DIagram),它是John Larry Kelly, Jr.、Carol Lochbaum和Victor A. Vyssotsky英語Victor A. Vyssotsky專門開發的,用於採樣資料系統[1]。最初開發更常規的資料流程語言,是為了使並列編程更加容易。在1966年Bert Sutherland英語Bert Sutherland的博士論文《電腦過程的線上圖形規定》中[2],Sutherland建立了第一個圖形資料流程編程框架。

資料流程編程,是1960年代由Jack Dennis英語Jack Dennis和他在MIT的研究生開創[3]。為了避免混淆於資料流程計算或資料流程架構英語Dataflow architecture[4],它基於了非確定型機器範式,一些作者使用術語「資料串流」(datastream)替代「資料流程」。

後續的資料流程語言,大多是在大型的超級電腦實驗室中開發的。其中最流行的是1983年發行的SISAL,它是勞倫斯利弗莫爾國家實驗室開發的。SISAL看起來很像大多數的語句驅動語言,但是變數必須是單賦值的。這允許編譯器容易的辨識輸入和輸出。SISAL已經發展出了很多分支,包括SAC,即單賦值C語言,它力求儘可能的接近流行的C程式語言。

在1980年代早期,美國海軍開發了ACOS和SPGN(訊號處理圖式表示法)。它今天仍用於很多實戰平台中[5]。更激進的概念是Prograph英語Prograph,在其中程式用螢幕上的圖形來構造,而變數被完全替代為連接輸入和輸出的連線。

資料流程已被提議,用作規定分散式系統構件的全域行為的抽象方法:在現場分散式對象英語Live distributed object編程模型中,使用分散式資料流程英語Distributed data flow來儲存和溝通狀態,因而它們扮演了類似於類Java程式語言中變數、欄位和參數的角色。

特性

編輯

傳統上,程式被建模為,按照特定次序發生的一系列運算;這稱為指令式編程,這種編程方式也叫做順序式[6]程序式[7]控制流程[7](意指程式選擇某個特定路徑)。程式聚焦於命令,符合於馮·諾伊曼的順序式編程願景[6],而資料通常是「靜止的」[7]

與之相對,資料流程編程強調了資料的流動,並將程式建模為一系列的連接。顯式的定義輸入和輸出的連接運算,它的功能類似於黑箱[7]。一個運算在它的所有輸入成為有效時立即執行[8]。因此,資料流程語言是天然並列的,並可在大型的、去中心化的系統上運作[6][9][10]

狀態

編輯

電腦編程的關鍵概念之一,是狀態英語State (computer science)(state)的概念,它本質上是在系統中各種狀況的快照(snapshot)。多數程式語言需要相當數量的狀態資訊,它們通常對編程者是隱蔽的,電腦自身經常完全不知道哪部份資訊編碼了持久狀態。這是一個嚴重問題,因為在並列處理機器中,狀態資訊需要在多個處理器之間共享。多數語言強制編程者增加額外代碼,來指示哪些資料和哪部份代碼,對於狀態而言是重要的。這種代碼趨向於在效能方面是代價昂貴的,並且難於閱讀和除錯。

如果將順序式程式想像為,在任務(運算)之間移動的一個單一工人,則資料流程程式,更像是在一個裝配線上的一系列工人,每個人都在材料可獲得的時候,作一份特定任務。因為運算只關心資料輸入的可獲得性,它們沒有隱蔽的狀態要追蹤,都是同時「準備好的」。

體現

編輯

資料流程程式,可以用不同方式來體現。一個傳統程式,通常體現為一系列的正文指令,可以合理的描述一個串行系統,它在小型單一用途的,接收、處理並返回的工具之間,用管道連通資料。資料流程程式開始於一個輸入,可能有命令列參數,並說明資料被怎樣使用和修改。資料的流程是顯式的,經常用連線或管道來說明。

在編碼方面上,資料流程程式,可以被實現為一個雜湊表,具有以可唯一性辨識的輸入作為鍵(key),用它來尋找轉至指令的指標。當任何運算完成時,程式逐項掃描運算的一個列表,直到找到第一個全部輸入都當前有效的運算,並執行它。當運算結束時,它典型的會輸出資料,因而使得另一個運算變為有效。

對於並列運算,只有這個列表需要被共享;它是整個程式的狀態。因此維護狀態的任務,從編程者移交給了語言的執行時系統。在有著單一處理器核心的機器上,設計用於並列運算的實現,只會簡單的產生開銷,要完全去掉這種開銷,可以使用一種不同的執行時系統。

語言

編輯

資料流程程式語言包括:

應用編程介面

編輯

參見

編輯

參照

編輯
  1. ^ John L. Kelly Jr.; Carol Lochbaum; V. A. Vyssotsky. A block diagram compiler. Bell System Tech. J. 1961, 40 (3): 669–678. doi:10.1002/j.1538-7305.1961.tb03236.x. 
  2. ^ W.R. Sutherland. The On-line Graphical Specification of Computer Procedures. MIT. 1966. 
  3. ^ VAL Overview
  4. ^ Veen, Arthur H. Dataflow Machine Architecture. ACM Computing Surveys. December 1986, 18 (4): 365–396 [5 March 2019]. doi:10.1145/27633.28055. (原始內容存檔於2021-11-11). 
  5. ^ Underwater Acoustic Data Processing, Y.T. Chan
  6. ^ 6.0 6.1 6.2 Johnston, Wesley M.; J.R. Paul Hanna; Richard J. Millar. Advances in Dataflow Programming Languages (PDF). ACM Computing Surveys. March 2004, 36: 3 [15 August 2013]. doi:10.1145/1013208.1013209. (原始內容 (PDF)存檔於2018-05-16). 
  7. ^ 7.0 7.1 7.2 7.3 7.4 Wadge, William W.; Edward A. Ashcroft. Lucid, the Dataflow Programming Language illustrated. Academia Press. 1985: 7 [15 August 2013]. ISBN 9780127296500. 
  8. ^ 8.0 8.1 Dataflow Programming Basics. Getting Started with NI Products. National Instruments Corporation. [15 August 2013]. (原始內容存檔於2014-02-14). 
  9. ^ Harter, Richard. Data Flow languages and programming - Part I. Richard Harter's World. [15 August 2013]. (原始內容存檔於8 December 2015). 
  10. ^ Why Dataflow Programming Languages are Ideal for Programming Parallel Hardware. Multicore Programming Fundamentals Whitepaper Series. National Instruments Corporation. [15 August 2013]. (原始內容存檔於2018-12-21). 

外部連結

編輯