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(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"`等。

## 例子

### 序列的總和

```sql
total
where
    total = 0 fby total + x
end
```

### 累積移動平均

```sql
running_avg
where 
    sum = first(input) fby sum + next(input);
    n = 1 fby n + 1;
    running_avg = sum / n;
end
```

### 階乘

```sql
fac
where
    n = 0 fby (n + 1);
    fac = 1 fby (fac * (n + 1));
end
```

### 斐波那契數列

```sql
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項：

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

### 均方根

在下面均方根程序中的平方根計算使用了計算平方根的方法。

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

### 素數

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

#### 數據流程圖

<image>

### 漢明數

計算升序的正規數的算法經由戴克斯特拉得以流行，有關問題叫做「漢明問題」。Dijkstra計算這些數的想法如下：

- 漢明數的序列開始於數`1`。
- 要加入序列中的數有下述形式：`2h,3h,5h`，這裡的`h`是序列已有的任意的漢明數。
- 因此，可以生成最初只有一個`1`的序列`H`，並接著歸併演算法序列`2H,3H,5H`，並以此類推。

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

注意這個程序中歸併函數中的`upon`條件能夠起到二個流中可能存在的相同值在結果中只出現一個的效果。

#### 數據流程圖

<image>

### 快速排序

下面程序實現了霍爾的快速排序算法，將序列劃分為小於基準值（pivot）的元素和不小於它的元素的兩個子序列，然後遞歸的排序這兩個子序列，再將結果的兩個排好序的子序列串接起來。

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

#### 數據流程圖

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

## 外部連結

- pLucid
- Language overview
- Lucid page of HaskellWiki

## 基本資料

- 日語原文：Lucid
- 編程范型：數據流程
- 發行時間：1976年
- 設計者：Edward A. Ashcroft、William W. Wadge
- 軟體實現：pLucid
- dialects：GIPSY, Granular Lucid
- 受影響於：ISWIM
- 施影響於：SISAL, Pure Data, Lustre