Lucid_(编程语言)

**Lucid** 是資料流程編程語言，設計用來實驗非馮・紐曼編程模型。它是 William W. Wadge 和 Edward A. Ashcroft 在 1976 年設計的，並描述於 1985 年的書籍《Lucid, the Dataflow Programming Language》。

pLucid 是 Lucid 的首個直譯器。

## 模型

**Lucid** 使用針對資料計算的需求驅動模型。每個語句都可以理解為一個方程，它定義了一個網路，即處理器和它們之間的資料經此流動的通信線路。每個變數都是值的一個無限流（stream），而每個函式都是一個過濾器或變換器。Lucid 最大的創新之處，是能夠進行流合成（composition）的迭代，這是通過「當前」值和算子 `fby`（讀作 followed by）來類比表述的。

Lucid 基於了一種「歷史」（history）的代數，「歷史」是資料項的無限序列。在操作上，「歷史」可以被認為是一個變數的變更著的值的記錄，對「歷史」的運算操作比如 `first` 和 `next` 可以隨其名字所提示的那樣理解。Lucid 最初被構想為一個規矩的、數學上純粹的單賦值語言，如此其驗證將會被簡化。但是，資料流程釋義在 Lucid 的演變方向上有著重要的影響。

## 細節

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**
```

### 指數函式

指數函式的冪級數 $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**
```

### 均方根

在下面均方根程式中的平方根計算使用了巴比倫方法。

```
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`，並接著合併序列 `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 --------------+    |
   |                                                            |
   +------------------------------------------------------------+
```

## 參照

## 外部連結

* pLucid
* Language overview （頁面存檔備份，存於網際網路檔案館）
* Fluid Programming in Lucid （頁面存檔備份，存於網際網路檔案館）
* Lucid page of HaskellWiki （頁面存檔備份，存於網際網路檔案館）