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