查看“︁Lucid语言”︁的源代码

{{NoteTA
|G1 = IT
}}
{{Infobox programming language
|name = Lucid
|logo =
|paradigm = [[数据流程编程|数据流程]]
|year = {{Start date and age|1976}}
|designer = Edward A. Ashcroft<br>William W. Wadge
|developer =
|latest release version = 
|latest release date = 
|implementations = pLucid
|dialects = GIPSY, Granular Lucid
|influenced_by = [[ISWIM]]
|influenced = [[SISAL]], [[Pure Data]], [[Lustre (编程语言)|Lustre]]
}}
  	
'''Lucid'''是[[数据流程编程]]语言，设计用来实验非[[冯·诺伊曼结构|冯·诺伊曼]]编程模型。它是William W. Wadge和Edward A. Ashcroft在1976年设计的<ref>Edward A. Ashcroft, William W. Wadge. [http://wrap.warwick.ac.uk/59398/2/WRAP_Ashcroft_cs-rr-004.pdf Lucid—A Formal System for Writing and Proving Programs] {{Wayback|url=http://wrap.warwick.ac.uk/59398/2/WRAP_Ashcroft_cs-rr-004.pdf |date=20170923013633 }}. September 1976. SIAM Journal on Computing 5(3):336-354.DOI: 10.1137/0205029.<br />Edward A. Ashcroft, William W. Wadge. [https://cs.uwaterloo.ca/research/tr/1976/CS-76-22.pdf Lucid: Scope structures and defined functions] {{Wayback|url=https://cs.uwaterloo.ca/research/tr/1976/CS-76-22.pdf |date=20130303222849 }}. November 1976. TechnicalReport CS–76–22, Department of Computer Science, University of Waterloo. [https://www.cse.unsw.edu.au/~plaice/archive/WWW/1978/Waterloo-CS-78-01.pdf Published in 1978].</ref>，并描述于1985年的书籍《Lucid, the Dataflow Programming Language》<ref name="book"/>。

pLucid是Lucid的首个[[解释器]]。

==模型==
'''Lucid'''使用针对数据计算的需求驱动模型。每个语句都可以理解为一个方程，它定义了一个网络，即处理器和它们之间的数据经此流动的通信线路。每个[[变量 (程序设计)|变量]]都是值的一个无限[[串流|流]]（stream），而每个函数都是一个过滤器或变换器。Lucid最大的创新之处，是能够进行流合成（composition）的[[迭代]]，这是通过“当前”值和算子<code>fby</code>（读作followed by）来模拟表述的。

Lucid基于了一种“历史”（history）的[[代数]]，“历史”是数据项的无限序列。在操作上，“历史”可以被认为是一个变量的变更着的值的记录，对“历史”的运算操作比如<code>first</code>和<code>next</code>可以随其名字所提示的那样理解。Lucid最初被构想为一个规矩的、数学上纯粹的[[单赋值]]语言，如此其验证将会被简化<ref>Edward A. Ashcroft, William W. Wadge. [http://plaice.web.cse.unsw.edu.au/archive/WWW/1977/P-CACM77-Lucid.pdf LUCID, A Nonprocedural Language with Iteration]{{Dead link}}. July 1977. in Communications of the ACM 20(7):519-526.</ref>。但是，[[数据流程]]释义在Lucid的演变方向上有着重要的影响<ref>{{Cite web |url=https://hopl.info/showlanguage.prx?exp=960 |title=Online Historical Encyclopaedia of Programming Languages |accessdate=2020-05-02 |archive-date=2020-12-04 |archive-url=https://web.archive.org/web/20201204052051/https://hopl.info/showlanguage.prx?exp=960 |dead-url=no }}</ref>。

==细节==
Lucid从[[ISWIM]]继承了<code>where</code>子句作为自己的[[块结构]]，从[[POP-2]]继承了[[数据类型]]。在Lucid中，每个表达式中的[[变量 (程序设计)|变量]]，都要先在表达式自身的<code>where</code>子句中寻找对应的变量定义，包含仍未[[自由变量和约束变量|约束]]的变量的表达式，在继续进行（proceed）之前，要等待直到这个变量已经被约束，即等待从输入中获取变量的值。一个表达式如<code>x + y</code>，在返回这个表达式的输出之前，将等待直到<code>x</code>和<code>y</code>二者都成为约束的。这样有一个重要结果，避免了更新有关值的显式的逻辑，导致了相较于主流语言的先声明再引用方式有大量的代码简约。

在Lucid中每个变量都是值的[[串流|流]]（stream）。算子<code>fby</code>（followed by的[[助忆码]]），定义了在前一个表达式之后会出现什么。表达式<code>n = 1 fby n + 1</code>使用<code>fby</code>定义了一个流<code>n</code>，在这个实例中，这个流产生[[序列]]<tt>[1,2,3,...]</tt>。在流中的值，可以通过如下这些算子来寻址取用，假定<code>x</code>是用到的变量：

*<code>first x</code> - 取回在流<code>x</code>中的第一个值。每次求值这个表达式都得到同样这个值。
*<code>x</code> - 取回在流<code>x</code>中当前值。
*<code>next x</code> - 取回在流<code>x</code>中当前值的下一个值。
*<code>x asa p</code> - 如果<code>p</code>提供了一个<code>"true"</code>值，则立刻（as soon as）提供<code>x</code>，否则在下一个<code>x</code>和下一个<code>p</code>上继续进行此运算操作。每次求值这个表达式都得到同样这个值。可以想像为它根据控制流<code>p</code>，从流<code>x</code>选取出第一个已经符合条件的值。
*<code>x whenever p</code> - 如果<code>p</code>提供了一个<code>"true"</code>值，则提供<code>x</code>；接着在下一个<code>x</code>和下一个<code>p</code>上继续进行此运算操作。可以想像为它根据控制流<code>p</code>，从流<code>x</code>过滤出符合条件的所有值。它可以写为助记码<code>wvr</code>。
*<code>x upon p</code> - 提供<code>x</code>，如果<code>p</code>提供了一个<code>"true"</code>值，则在下一个<code>x</code>和下一个<code>p</code>上继续进行此运算操作，否则在这个<code>x</code>和下一个<code>p</code>上继续进行此运算操作。可以想像为它根据控制流<code>p</code>，在符合条件时放行流<code>x</code>的下一个值，在不符合条件时以重复当前值的方式滞留流<code>x</code>。
*<code>x attime i</code> - 将流<code>i</code>中的值作为流<code>p</code>中值的位次索引，依次从<code>i</code>取得索引选择流<code>x</code>中指定位次的值。可以想像为它根据索引流<code>i</code>，对流<code>x</code>进行了选取和重组。
*<code>X is current x</code> - 将流<code>x</code>的当前值保存在<code>X</code>变量中。每次求值<code>X</code>时都得到同样的这个值。典型用于嵌套的内层迭代，它不能直接使用<code>x</code>而导致这个流的当前值顺序前进的情况下，比如后面例子中的指数函数程序等。

计算是通过定义作用在数据的时变流上的过滤器或变换函数来完成的。涉及多个流的函数和运算操作采用逐点（pointwise）释义比如：<code>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>),...]</code>，在后面例子中进行二个流的归并和[[串接]]时，因而在[[条件表达式]]<code>if p then x else y fi</code>中需要通过<code>upon</code>对要操作的流进行预处理。

数据结束（end of data）对象用预定义特殊标识符<code>eod</code>表示，<code>iseod eod</code>将返回<code>"true"</code>，此外所有的对<code>eod</code>的运算操作都产生<code>eod</code>。错误对象用预定义特殊标识符<code>error</code>表示。<code>index</code>是预定义变量，它是以<code>0</code>开始的[[自然数]]序列。此外预定义变量还有<code>true = "true"</code>、<code>false = "false"</code>等。

==例子==

===序列的[[总和]]===
<syntaxhighlight lang="sql">
total
where
    total = 0 fby total + x
end
</syntaxhighlight>

===[[移动平均#累积移动平均|累积移动平均]]===
<syntaxhighlight lang="sql">
running_avg
where 
    sum = first(input) fby sum + next(input);
    n = 1 fby n + 1;
    running_avg = sum / n;
end
</syntaxhighlight>

===[[阶乘]]===
<syntaxhighlight lang="sql">
fac
where
    n = 0 fby (n + 1);
    fac = 1 fby (fac * (n + 1));
end
</syntaxhighlight>

===[[斐波那契数列]]===
<syntaxhighlight lang="sql">
fib
where
    fib = 0 fby (1 fby fib + next fib);
end
</syntaxhighlight>

===指数函数===
[[指数函数]]的[[幂级数]]<math display="inline">e^x = 1+ \sum_{n = 1}^{\infty} {x^n \over n!} = 1 + x + {x^2 \over 2!} + {x^3 \over 3!} + \cdots</math>的前10项：
<syntaxhighlight lang="sql">
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
</syntaxhighlight>

===均方根===
在下面[[均方根]]程序中的[[平方根]]计算使用了{{en-link|计算平方根的方法|Methods_of_computing_square_roots#Babylonian_method|巴比伦方法}}。
<syntaxhighlight lang="sql">
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
</syntaxhighlight>

===[[素数]]===
<syntaxhighlight lang="sql">
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
</syntaxhighlight>

====[[数据流程图]]====
:[[File:Prime numbers sequence dataflow diagram (Lucid).png|left|thumb|579x579px|注释：程序代码在图示基本原理上进行了代码优化。]]
{{-}}

===漢明數===
计算升序的[[正规数 (整数)|正规数]]的算法经由[[艾兹赫尔·戴克斯特拉|戴克斯特拉]]得以流行，有关问题叫做“[[理查德·衛斯里·漢明|汉明]]问题”。Dijkstra计算这些数的想法如下：
* 汉明数的序列开始于数<code>1</code>。
* 要加入序列中的数有下述形式：<code>2h,3h,5h</code>，这里的<code>h</code>是序列已有的任意的汉明数。
* 因此，可以生成最初只有一个<code>1</code>的序列<code>H</code>，并接着{{en-link|归并算法|Merge algorithm|归并}}序列<code>2H,3H,5H</code>，并以此类推。

<syntaxhighlight lang="sql">
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
</syntaxhighlight>

注意这个程序中归并函数中的<code>upon</code>条件能够起到二个流中可能存在的相同值在结果中只出现一个的效果。

====数据流程图====
:[[File:Hamming problem dataflow diagram (Lucid).png|left|Hamming problem dataflow diagram]]
{{-}}

===快速排序===
下面程序实现了[[東尼·霍爾|霍尔]]的[[快速排序]]算法，将序列[[分治法|划分]]为小于基准值（pivot）的元素和不小于它的元素的两个子序列，然后[[递归]]的排序这两个子序列，再将结果的两个排好序的子序列[[串接]]起来。

<syntaxhighlight lang="sql">
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
</syntaxhighlight>

====数据流程图====
    +--------> whenever -----> qsort ---------+
    |             ^                           |
    |             |                           |
    |            not                          |
    |             ^                           |
    |---> first   |                           |
    |       |     |                           |
    |       V     |                           |
    |---> less ---+                           |
    |             |                           |
    |             V                           V
 ---+--------> whenever -----> qsort -----> follow -----> if-then-else ----->
    |                                                       ^    ^
    |                                                       |    |
    +--------> next ----> first ------> iseod --------------+    |
    |                                                            |
    +------------------------------------------------------------+

==引用==
{{reflist|refs=
<ref name="book">{{Cite book
| first1 = William W.
| last1 = Wadge
| first2 = Edward A.
| last2 = Ashcroft
| date = 1985
| title = Lucid, the Dataflow Programming Language
| publisher = Academic Press
| isbn = 0-12-729650-6
| url = http://worrydream.com/refs/Wadge%20-%20Lucid,%20the%20Dataflow%20Programming%20Language.pdf
| accessdate = 28 April 2020
| archive-date = 2020-03-27
| archive-url = https://web.archive.org/web/20200327175245/http://worrydream.com/refs/Wadge%20-%20Lucid,%20the%20Dataflow%20Programming%20Language.pdf
| dead-url = no
}}</ref>
|2}}

==外部链接==
*[https://github.com/mwmarkland/plucid pLucid] {{Wayback|url=https://github.com/mwmarkland/plucid |date=20230217223415 }}
*[http://c2.com/cgi/wiki?LucidLanguage Language overview] {{Wayback|url=http://c2.com/cgi/wiki?LucidLanguage |date=20160709140453 }} 
*[http://www.haskell.org/haskellwiki/Lucid Lucid page of HaskellWiki] {{Wayback|url=http://www.haskell.org/haskellwiki/Lucid |date=20140704054239 }}

{{程序设计语言}}

[[Category:学术的编程语言]]
[[Category:并发编程语言]]
[[Category:函数式编程语言]]