Lucid (编程语言)
Lucid是数据流程编程语言,设计用来实验非冯·诺伊曼编程模型。它是William W. Wadge和Edward A. Ashcroft在1976年设计的[1],并描述于1985年的书籍《Lucid, the Dataflow Programming Language》[2]。
数据流程 | |
設計者 | Edward A. Ashcroft William W. Wadge |
1976年 | |
主要實作產品 | |
pLucid | |
衍生副語言 | |
GIPSY, Granular Lucid | |
啟發語言 | |
ISWIM | |
影響語言 | |
SISAL, Pure Data, Lustre |
pLucid是Lucid的首个解释器。
模型
Lucid使用针对数据计算的需求驱动模型。每个语句都可以理解为一个方程,它定义了一个网络,即处理器和它们之间的数据经此流动的通信线路。每个变量都是值的一个无限流(stream),而每个函数都是一个过滤器或变换器。Lucid最大的创新之处在于,能够进行流合成(composition)的迭代,是通过“当前”值和算子fby
(读作followed by)来模拟表述的。
Lucid基于了一种“历史”(history)的代数,“历史”是数据项的无限序列。在操作上,“历史”可以被认为是一个变量的变更着的值的记录,对“历史”的运算操作比如first
和next
可以随其名字所提示的那样理解。Lucid最初被构想为一个规矩的、数学上纯粹的单赋值语言,如此验证将会被简化[3]。但是,数据流程释义在Lucid的演变方向上有着重要的影响[4]。
细节
Lucid从ISWIM继承了where
子句作为自己的块结构,从POP-2继承了数据类型。在Lucid中,每个表达式中的变量,都要先在表达式自身的where
子句中寻找对应的变量定义,包含仍未约束的变量的表达式,在继续进行(proceed)之前,要等待直到这个变量已经被约束,即等待从输入中获取变量的值。一个表达式如x + y
,在返回这个表达式的输出之前,将等待直到x
和y
二者都成为约束的。这样有一个重要结果,避免了更新有关值的显式的逻辑,导致了相较于主流语言的先声明再引用方式有大量的代码简约。
在Lucid中每个变量都是值的流(stream)。算子fby
(followed by的助忆码),定义了在前一个表达式之后会出现什么。表达式n = 1 fby n + 1
使用fby
定义了一个流n
,在这个实例中,这个流产生序列[1,2,3,...]。在流中的值,可以通过如下这些算子来寻址取用,假定x
是用到的变量:
first x
- 取回在流x
中的第一个值。每次求值这个表达式都得到同样这个值。x
- 取回在流x
中当前值。next x
- 取回在流x
中当前值的下一个值。x asa p
- 如果p
提供了一个"true"
值,则立刻(as soon as)提供x
,否则在下一个x
和下一个p
上继续进行此运算操作。每次求值这个表达式都得到同样这个值。可以想像为它根据控制流p
,从流x
选取出第一个已经符合条件的值。x whenever p
- 如果p
提供了一个"true"
值,则提供x
;接着在下一个x
和下一个p
上继续进行此运算操作。可以想像为它根据控制流p
,从流x
过滤出符合条件的所有值。它可以写为助记码wvr
。x upon p
- 提供x
,如果p
提供了一个"true"
值,则在下一个x
和下一个p
上继续进行此运算操作,否则在这个x
和下一个p
上继续进行此运算操作。可以想像为它根据控制流p
,在符合条件时放行流x
的下一个值,在不符合条件时以重复当前值的方式滞留流x
。x attime i
- 将流i
中的值作为流p
中值的位次索引,依次从i
取得索引选择流x
中指定位次的值。可以想像为它根据索引流i
,对流x
进行了选取和重组。X is current x
- 将流x
的当前值保存在X
变量中。每次求值X
时都得到同样的这个值。典型用于嵌套的内层迭代,它不能直接使用x
而导致这个流的当前值顺序前进的情况下,比如后面例子中的指数函数程序等。
计算是通过定义作用在数据的时变流上的过滤器或变换函数来完成的。涉及多个流的函数和运算操作采用逐点(pointwise)释义比如:f(x,y) = [f(x0,y0),f(x1,y1),f(x2,y2),...]
,在后面例子中进行二个流的归并和串接时,因而在条件表达式if p then x else y fi
中需要通过upon
对要操作的流进行预处理。
数据结束(end of data)对象用预定义特殊标识符eod
表示,iseod eod
将返回"true"
,此外所有的对eod
的运算操作都产生eod
。错误对象用预定义特殊标识符error
表示。index
是预定义变量,它是以0
开始的自然数序列。此外预定义变量还有true = "true"
、false = "false"
等。
例子
序列的总和
total where total = 0 fby total + x end
累积移动平均
running_avg where sum = first(input) fby sum + next(input); n = 1 fby n + 1; running_avg = sum / n; end
阶乘
fac where n = 0 fby (n + 1); fac = 1 fby ( fac * (n + 1) ); end
斐波那契数列
fib where fib = 0 fby ( 1 fby fib + next fib ); end
指数函数
expsum asa next i eq 10 where X is current x; i = next index; term = 1 fby (term / i) * X; expsum = 0 fby expsum + term; end
均方根
sqroot(avg(square(a))) where square(x) = x*x; avg(y) = mean where n = 1 fby n+1; mean = first y fby mean + d; d = (next y - mean)/(n+1); end; sqroot(z) = approx asa err < 0.0001 where Z is current z; approx = Z/2 fby (approx + Z/approx)/2; err = abs(square(approx)-Z); end; end
素数
prime where prime = 2 fby (n whenever isprime(n)); n = 3 fby n+2; isprime(n) = not(divs) asa divs or prime*prime > N where N is current n; divs = N mod prime eq 0; end; end
漢明數
计算升序的正规数的算法经由戴克斯特拉得以流行,这个问题叫做“汉明问题”。Dijkstra计算这些数的想法如下:
- 汉明数的序列开始于数1。
- 要加入序列中的数有下述形式:2h,3h,5h,这里的h是序列已有的任意的汉明数。
- 因此,序列H可以生成自输出数1,并接着归并序列2H,3H,5H。
h where h = 1 fby merge(merge(2 * h, 3 * h), 5 * h); merge(x,y) = if xx <= yy then xx else yy fi where xx = x upon xx <= yy; yy = y upon yy <= xx; end; end
注意这个程序中归并函数中的upon
条件能够起到二个流中可能存在的相同值在结果中只出现一个的效果。
数据流程图
快速排序
下面程序实现了霍尔的快速排序算法,将序列划分为小于基准值(pivot)的元素和不小于它的元素的两个子序列,然后递归的排序这两个子序列,再将结果的两个排好序的子序列串接起来。
qsort(a) = if iseod(first a) then a else follow(qsort(b0), qsort(b1)) fi where p = a < first a; b0 = a whenever p; b1 = a whenever not p; follow(x,y) = if xdone then y upon xdone else x fi where xdone = iseod x end end
数据流程图
+--------> whenever -----> qsort ---------+ | ^ | | | | | not | | ^ | |---> first | | | | | | | V | | |---> less ---+ | | | | | V V ---+--------> whenever -----> qsort -----> follow -----> if-then-else -----> | ^ ^ | | | +--------> next ----> first ------> iseod --------------+ | | | +------------------------------------------------------------+
引用
- Edward A. Ashcroft, William W. Wadge. Lucid—A Formal System for Writing and Proving Programs 页面存档备份,存于. September 1976. SIAM Journal on Computing 5(3):336-354.DOI: 10.1137/0205029.
Edward A. Ashcroft, William W. Wadge. Lucid: Scope structures and defined functions 页面存档备份,存于. November 1976. TechnicalReport CS–76–22, Department of Computer Science, University of Waterloo. Published in 1978. - Wadge, William W.; Ashcroft, Edward A. (PDF). Academic Press. 1985 [28 April 2020]. ISBN 0-12-729650-6. (原始内容存档 (PDF)于2020-03-27).
- Edward A. Ashcroft, William W. Wadge. LUCID, A Nonprocedural Language with Iteration. July 1977. in Communications of the ACM 20(7):519-526.
- . [2020-05-02]. (原始内容存档于2020-12-04).