Lucid語言

Lucid是資料流程編程語言，設計用來實驗非馮 ・ 紐曼編程模型。伊是 William W . Wadge 和 Edward A . Ashcroft 佇一九七六年設計的，並來講一九八五年的冊《Lucid , the Dataflow Programming Language》。

pLucid 是 Lucid 的首一个直譯器。

模型

Lucid使用針對資料計算的需求趕動模型。逐个語句攏會當理解做一个方程，伊定義一个網路，即處理器佮𪜶之間的資料經過這流動的通信線路。逐个變數攏是值的一个無限流（stream）， 抑若逐个函式攏是一个過濾器抑是變換器。Lucid 上大的創新的所在，是會當進行流合成（composition）迵天代，這是通過「當前」值和算子 ` fby `（讀作 followed by）來類比表述的。

Lucid 是因為一種「歷史」（history）的代數，「 歷史」是資料項的無限列。佇咧操作上，「 歷史」會當被認為是一个變數的變更著的值的記錄，著「歷史」的運算操作比如講 ` first ` 和 ` next ` 會當綴其名所提示的彼款理解。Lucid 上頭先被構想做一个規矩的、數學上純粹的單賦值語言，按呢其實驗證將會去予人簡化。猶毋過，資料流程釋義佇咧 Lucid 的演變方向頂懸有真重要的影響。

鋩角

Lucid 對 ISWIM 繼承矣 ` where ` 子句作為家己的塊結構，對 POP 想二繼承了資料類型。佇咧 Lucid 中，逐个表達式中的變數，攏愛先咧表達式家己的 ` where ` 子句內底走揣對應的變數定義，包含猶未約束的變數的表達式，咧繼續進行（proceed）進前，愛等待到這个變數已經予人約束，等待對輸入中取得變數的值。一个表達式如 ` x + y `，伊閣倒轉來這个表達式的輸出進前，一直到共 ` x ` 和 ` y ` 二者攏成做約束的。按呢有一个重要結果，避免更新有關值的顯式的邏輯，致使了佮主流語言的先聲明才閣參照方式有大量的代碼簡單。

佇咧 Lucid 中逐个變數攏是值的流（stream）。 算子 ` fby `（followed by 的助憶碼）， 定義佇咧前一个表達式了後會出現啥。表達式 ` n=一 fby n + 一 ` 使用 ` fby ` 定義一个流 ` n `，佇這个實例中，這流產生序列 [一 , 二 , 三 , . . .]。佇咧流中的值，會當通過如下遮的算子來定址取用，假定 ` 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 零 , y 零 ) , f ( x 一 , y 一 ) , f ( x 二 , y 二 ) , . . .] `，佇後壁例中進行兩个流的合併佮串接時，因為佇條件表達式 ` if p then x else y fi ` 中需要通過 ` upon ` 著愛操作的流進行預處理。

資料煞（end of data）物件用預定義特殊識別碼 ` eod ` 表示，` iseod eod ` 共返回 ` " true " `，此外所有的對 ` eod ` 的運算操作攏產生 ` eod `。錯誤物件用預定義特殊識別碼 ` error ` 表示。` index ` 是預定義變數，伊彼是以 ` 零 ` 開始的自然數序列。此外預定義變數猶閣有 ` true=" true " `、` false=" false " ` 等。

例

序列的總和

` ` ` total where total=零fbytotal + x end ` ` `

累積徙振動平均

` ` ` running _ avg where sum=first( input )fbysum +next( input ) ; n=一fbyn + 一 ; running _ avg=sum / n ; end ` ` `

階乘

` ` ` fac where n=零fby( n + 一 ) ; fac=一fby( fac * ( n + 一 ) ) ; end ` ` `

斐波彼契數列

` ` ` fib where fib=零fby( 一fbyfib +nextfib ) ; end ` ` `

指數函式

指數函式的冪級數 $ e ^ { x }=一 + \ sum _ { n=一 } ^ { \ infty } { x ^ { n } \ over n ! }=一 + x + { x ^ { 二 } \ over 二 ! } + { x ^ { 三 } \ over 三 ! } + \ cdots $ 前十項：

` ` ` expsum'asa'nexti eq 十 where Xis currentx ; i=nextindex ; term=一fby( term / i ) * X ; expsum=零fbyexpsum + term ; end ` ` `

均方根

佇下跤均根程式當中的平方根計算使用矣巴比倫方法。

` ` ` sqroot ( avg ( square ( a ) ) ) where square ( x )=x * x ; avg ( y )=mean where n=一fbyn + 一 ; mean=firstyfbymean + d ; d=( next y-mean ) / ( n + 一 ) ; end; sqroot ( z )=approxasaerr < 空空空空一 where Zis currentz ; approx=Z / 二fby( approx + Z / approx ) / 二 ; err=abs ( square ( approx )-Z ) ; end; end ` ` `

素數

` ` ` prime where prime=二fby( nwheneverisprime ( n ) ) ; n=三fbyn + 二 ; isprime ( n )=not ( divs )asadivs or prime * prime > N where Nis currentn ; divs=N mod prime eq 零 ; end; end ` ` `

漢明數

計算升序的正規數的演算法經由戴克斯特拉會當時行，有關問題叫做「漢明問題」。 Dijkstra 計算遮的數的想法如下：

• 漢明數的序列開始於數 ` 一 `。
• 愛加入序列內底有啥物形式：` 二 h , 三 h , 五 h `，遮的 ` h ` 是序列已有的任意的漢明數。
• 所以，會當生做上頭仔干焦一个 ` 一 ` 的序列 ` H `，並且合併序列 ` 二 H , 三 H , 五 H `，並且以這樣推。

` ` ` hamming where h=一fbymerge ( merge ( 二 * h , 三 * h ) , 五 * h ) ; merge ( x , y )=ifxx <=yythenxxelseyyfi where xx=xuponxx <=yy ; yy=yuponyy <=xx ; end; end ` ` `

注意這个程式中合併函式中的 ` upon ` 條件會當起來到二个流當中有可能存在的仝款值在結果當中干焦出現一个的效果。

快速排序

下面程式實現了霍爾的快速排序演算法，將序列劃分做小於基準值（pivot）的元素佮無小於伊的元素的兩个子序列，然後遞迴的排序這兩粒子序列，閣將結果的兩个安順序的字序列共接起來。

` ` ` qsort ( a )=if'iseod(firsta )'thenaelsefollow ( qsort ( b 零 ) , qsort ( b 一 ) )fi where p=a <firsta ; b 零=awheneverp ; b 一=awhenevernot p ; follow ( x , y )=ifxdonethenyuponxdoneelsexfi where xdone=iseodx end end ` ` `

資料流程圖

` ` ` +--------> whenever-----> qsort---------+ |^ | | | | | not | | ^ | |---> first | | | | | | | V | | |---> less---+ | | | | | V V ---+--------> whenever-----> qsort-----> follow-----> if-then-else-----> | ^ ^ | | | +--------> next----> first------> iseod--------------+ | | | +------------------------------------------------------------+ ` ` `

外部連結

• pLucid
• Language overview
• Fluid Programming in Lucid
• Lucid page of HaskellWiki