数据流程编程
![本页使用了标题或全文手工转换](http://upload.wikimedia.org/wikipedia/commons/thumb/c/cd/Zh_conversion_icon_m.svg/35px-Zh_conversion_icon_m.svg.png)
在程序设计中,数据流程编程是一种编程范型,它将程序建模为数据在运算(operation)之间流动的有向图,从而实现了数据流程原理和架构。数据流程编程语言,共享了纯函数式语言的某些特征,比如单赋值,并且开发它们的动因,通常是为了向更适合数值处理的语言,增加函数式编程概念。
历史
[编辑]先驱的数据流程语言是BLODI(BLOck DIagram),它是John Larry Kelly, Jr.、Carol Lochbaum和Victor A. Vyssotsky专门开发的,用于采样数据系统[1]。最初开发更常规的数据流程语言,是为了使并行编程更加容易。在1966年Bert Sutherland的博士论文《计算机过程的在线图形规定》中[2],Sutherland建立了第一个图形数据流程编程框架。
数据流程编程,是1960年代由Jack Dennis和他在MIT的研究生开创[3]。为了避免混淆于数据流程计算或数据流程架构[4],它基于了非确定型机器范型,一些作者使用术语“数据串流”(datastream)替代“数据流程”。
后续的数据流程语言,大多是在大型的超级计算机实验室中开发的。其中最流行的是1983年发行的SISAL,它是劳伦斯利弗莫尔国家实验室开发的。SISAL看起来很像大多数的语句驱动语言,但是变量必须是单赋值的。这允许编译器容易的识别输入和输出。SISAL已经发展出了很多分支,包括SAC,即单赋值C语言,它力求尽可能的接近流行的C编程语言。
在1980年代早期,美国海军开发了ACOS和SPGN(信号处理图式表示法)。它今天仍用于很多实战平台中[5]。更激进的概念是Prograph,在其中程序用屏幕上的图形来构造,而变量被完全替代为连接输入和输出的连线。
数据流程已被提议,用作规定分布式系统构件的全局行为的抽象方法:在现场分布式对象编程模型中,使用分布式数据流程来存储和沟通状态,因而它们扮演了类似于类Java编程语言中变量、字段和参数的角色。
特性
[编辑]传统上,程序被建模为,按照特定次序发生的一系列运算;这称为指令式编程,这种编程方式也叫做顺序式[6]、过程式[7]、控制流程[7](意指程序选择某个特定路径)。程序聚焦于命令,符合于冯·诺伊曼的顺序式编程愿景[6],而数据通常是“静止的”[7]。
与之相对,数据流程编程强调了数据的流动,并将程序建模为一系列的连接。显式的定义输入和输出的连接运算,它的功能类似于黑箱[7]。一个运算在它的所有输入成为有效时立即运行[8]。因此,数据流程语言是天然并行的,并可在大型的、去中心化的系统上运作[6][9][10]。
状态
[编辑]计算机编程的关键概念之一,是状态(state)的概念,它本质上是在系统中各种状况的快照(snapshot)。多数编程语言需要相当数量的状态信息,它们通常对编程者是隐蔽的,计算机自身经常完全不知道哪部份信息编码了持久状态。这是一个严重问题,因为在并行处理机器中,状态信息需要在多个处理器之间共享。多数语言强制编程者增加额外代码,来指示哪些数据和哪部份代码,对于状态而言是重要的。这种代码趋向于在性能方面是代价昂贵的,并且难于阅读和调试。
如果将顺序式程序想象为,在任务(运算)之间移动的一个单一工人,则数据流程程序,更像是在一个装配线上的一系列工人,每个人都在材料可获得的时候,作一份特定任务。因为运算只关心数据输入的可获得性,它们没有隐蔽的状态要追踪,都是同时“准备好的”。
体现
[编辑]数据流程程序,可以用不同方式来体现。一个传统程序,通常体现为一系列的正文指令,可以合理的描述一个串行系统,它在小型单一用途的,接收、处理并返回的工具之间,用管道连通数据。数据流程程序开始于一个输入,可能有命令行参数,并说明数据被怎样使用和修改。数据的流程是显式的,经常用连线或管道来说明。
在编码方面上,数据流程程序,可以被实现为一个散列表,具有以可唯一性识别的输入作为键(key),用它来查找转至指令的指针。当任何运算完成时,程序逐项扫描运算的一个列表,直到找到第一个全部输入都当前有效的运算,并运行它。当运算结束时,它典型的会输出数据,因而使得另一个运算变为有效。
对于并行运算,只有这个列表需要被共享;它是整个程序的状态。因此维护状态的任务,从编程者移交给了语言的运行时系统。在有着单一处理器核心的机器上,设计用于并行运算的实现,只会简单的产生开销,要完全去掉这种开销,可以使用一种不同的运行时系统。
语言
[编辑]数据流程编程语言包括:
- ASCET
- AviSynth,用于视频处理的脚本语言
- BMDFM,二进制模块数据流程机器
- CAL
- Cuneiform,函数式工作流程语言
- CMS管道
- Hume
- Id
- Joule
- Agilent VEE
- KNIME,一个免费和开源的数据分析、报表和集成平台
- LabVIEW[8]
- Linda
- Lucid[7]
- Lustre
- Max/MSP
- Microsoft可视编程语言
- Orange,一个开源的可视编程工具用于数据挖掘、统计数据分析和机器学习
- Oz
- Pipeline Pilot
- Prograph
- Pure Data
- Quartz Composer
- SAC,单赋值C语言
- SIGNAL,启用多时钟规定的面向数据流程的同步语言
- Simulink
- SISAL
- SystemVerilog,一种硬件描述语言
- Verilog,在2009年被吸收入SystemVerilog标准的硬件描述语言
- VHDL,一种硬件描述语言
- XEE (Starlight),XML工程环境
- XProc
应用编程接口
[编辑]- Apache Beam:Java/Scala SDK,统一的串流(和批量)处理,支持多种执行引擎(Apache Spark、Apache Flink、Google云平台等)。
- Apache Flink:Java/Scala库,允许串流(和批量)计算运行于分布式Apache Hadoop(或其他)集群之上。
- SystemC:C++库,主要用于硬件设计。
- TensorFlow:基于数据流程编程的一个机器学习库。
参见
[编辑]引用
[编辑]- ^ 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.
- ^ W.R. Sutherland. The On-line Graphical Specification of Computer Procedures. MIT. 1966.
- ^ VAL Overview
- ^ 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).
- ^ Underwater Acoustic Data Processing, Y.T. Chan
- ^ 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.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.0 8.1 Dataflow Programming Basics. Getting Started with NI Products. National Instruments Corporation. [15 August 2013]. (原始内容存档于2014-02-14).
- ^ Harter, Richard. Data Flow languages and programming - Part I. Richard Harter's World. [15 August 2013]. (原始内容存档于8 December 2015).
- ^ Why Dataflow Programming Languages are Ideal for Programming Parallel Hardware. Multicore Programming Fundamentals Whitepaper Series. National Instruments Corporation. [15 August 2013]. (原始内容存档于2018-12-21).
外部链接
[编辑]- Book: Dataflow and Reactive Programming Systems
- Basics of Dataflow Programming in F# and C# (页面存档备份,存于互联网档案馆)
- Dataflow Programming - Concept, Languages and Applications (页面存档备份,存于互联网档案馆)
- Static Scheduling of Synchronous Data Flow Programs for Digital Signal Processing (页面存档备份,存于互联网档案馆)
- Handling huge loads without adding complexity (页面存档备份,存于互联网档案馆) The basic concepts of dataflow programming, Dr. Dobb's, Sept. 2011
- 纯函数管道数据流 v3.0 (页面存档备份,存于互联网档案馆)
|
|