fbpx
维基百科

Lucid语言

六月 20, 2023

Lucid是数据流程编程语言，设计用来实验非冯·诺伊曼编程模型。它是William W. Wadge和Edward A. Ashcroft在1976年设计的[1]，并描述于1985年的书籍《Lucid, the Dataflow Programming Language》[2]。

Lucid
编程范型数据流程
設計者Edward A. Ashcroft
William W. Wadge
发行时间1976年，​46年前​（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

指数函数

指数函数的幂级数 的前10项： 

 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

均方根

在下面均方根程序中的平方根计算使用了巴比伦方法（英语：Methods_of_computing_square_roots#Babylonian_method）。 

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是序列已有的任意的汉明数。
  • 因此，可以生成最初只有一个1的序列H，并接着归并（英语：Merge algorithm）序列2H,3H,5H，并以此类推。
hamming 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 --------------+ | | | +------------------------------------------------------------+

引用

  1. ^ 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.
  2. ^ Wadge, William W.; Ashcroft, Edward A. Lucid, the Dataflow Programming Language (PDF). Academic Press. 1985 [28 April 2020]. ISBN 0-12-729650-6. （原始内容 (PDF)于2020-03-27）. 
  3. ^ Edward A. Ashcroft, William W. Wadge. LUCID, A Nonprocedural Language with Iteration. July 1977. in Communications of the ACM 20(7):519-526.
  4. ^ Online Historical Encyclopaedia of Programming Languages. [2020-05-02]. （原始内容于2020-12-04）. 

外部链接

六月 20, 2023
lucid语言, lucid是数据流程编程语言, 设计用来实验非冯, 诺伊曼编程模型, 它是william, wadge和edward, ashcroft在1976年设计的, 并描述于1985年的书籍, lucid, dataflow, programming, language, lucid编程范型数据流程設計者edward, ashcroftwilliam, wadge发行时间1976年, 46年前, 1976, 主要實作產品plucid衍生副語言gipsy, granular, lucid啟發語言iswim影. Lucid是数据流程编程语言 设计用来实验非冯 诺伊曼编程模型 它是William W Wadge和Edward A Ashcroft在1976年设计的 1 并描述于1985年的书籍 Lucid the Dataflow Programming Language 2 Lucid编程范型数据流程設計者Edward A AshcroftWilliam W Wadge发行时间1976年 46年前 1976 主要實作產品pLucid衍生副語言GIPSY Granular Lucid啟發語言ISWIM影響語言SISAL Pure Data LustrepLucid是Lucid的首个解释器 目录 1 模型 2 细节 3 例子 3 1 序列的总和 3 2 累积移动平均 3 3 阶乘 3 4 斐波那契数列 3 5 指数函数 3 6 均方根 3 7 素数 3 7 1 数据流程图 3 8 漢明數 3 8 1 数据流程图 3 9 快速排序 3 9 1 数据流程图 4 引用 5 外部链接模型 编辑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 x sub 0 sub y sub 0 sub f x sub 1 sub y sub 1 sub f x sub 2 sub y sub 2 sub 在后面例子中进行二个流的归并和串接时 因而在条件表达式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 指数函数 编辑 指数函数的幂级数e x 1 n 1 x n n 1 x x 2 2 x 3 3 displaystyle e x 1 sum n 1 infty x n over n 1 x x 2 over 2 x 3 over 3 cdots 的前10项 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 均方根 编辑 在下面均方根程序中的平方根计算使用了巴比伦方法 英语 Methods of computing square roots Babylonian method 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 lt 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 gt N where N is current n divs N mod prime eq 0 end end 数据流程图 编辑 注释 程序代码在图示基本原理上进行了代码优化 漢明數 编辑 计算升序的正规数的算法经由戴克斯特拉得以流行 有关问题叫做 汉明问题 Dijkstra计算这些数的想法如下 汉明数的序列开始于数1 要加入序列中的数有下述形式 2h 3h 5h 这里的h是序列已有的任意的汉明数 因此 可以生成最初只有一个1的序列H 并接着归并 英语 Merge algorithm 序列2H 3H 5H 并以此类推 hamming where h 1 fby merge merge 2 h 3 h 5 h merge x y if xx lt yy then xx else yy fi where xx x upon xx lt yy yy y upon yy lt xx end end 注意这个程序中归并函数中的upon条件能够起到二个流中可能存在的相同值在结果中只出现一个的效果 数据流程图 编辑 快速排序 编辑 下面程序实现了霍尔的快速排序算法 将序列划分为小于基准值 pivot 的元素和不小于它的元素的两个子序列 然后递归的排序这两个子序列 再将结果的两个排好序的子序列串接起来 qsort a if iseod first a then a else follow qsort b0 qsort b1 fi where p a lt 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 数据流程图 编辑 gt whenever gt qsort not gt first V gt less V V gt whenever gt qsort gt follow gt if then else gt gt next gt first gt 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 Lucid the Dataflow Programming Language 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 Online Historical Encyclopaedia of Programming Languages 2020 05 02 原始内容存档于2020 12 04 外部链接 编辑pLucid 页面存档备份 存于互联网档案馆 Language overview 页面存档备份 存于互联网档案馆 Fluid Programming in Lucid 页面存档备份 存于互联网档案馆 Lucid page of HaskellWiki 页面存档备份 存于互联网档案馆 取自 https zh wikipedia org w index php title Lucid语言 amp oldid 77659109, 维基百科，wiki，书籍，书籍，图书馆，

文章

，阅读，下载，免费，免费下载，mp3，视频，mp4，3gp， jpg，jpeg，gif，png，图片，音乐，歌曲，电影，书籍，游戏，游戏。