| title | author | year |
|---|---|---|
反应网编程 |
谢宇恒 |
2023 |
2021 年末，我偶然看到一篇 1990 年的论文 Interaction Nets， 作者是法国逻辑学家拉丰 Yves Lafont。 其中介绍了一种很新奇的计算模型， 以节点和边组成的图为数据， 视相邻节点之间的反应为计算。
节点之间的反应让人想到化学反应， 所以 Interaction 一词，我翻译为反应， 整个计算模型就称作反应网。
在这篇文章中，我顺着拉丰的论文中的例子，来讲解反应网的原理， 并且介绍我设计的，用来实践这个计算模型的程序语言。
如何用图来编码数据呢？
假设我们要编码最简单的数据 -- 自然数， 我们可以模仿上古结绳计数，用节点来记录个数。
0 (zero)-
1 (zero)-(add1)-
2 (zero)-(add1)-(add1)-
3 (zero)-(add1)-(add1)-(add1)-
代表 0 的节点 (zero)- 有一个接口，
代表 +1 的节点 -(add1)- 有两个接口，
将这些节点按照接口连接起来，就能编码自然数。
如何用图来表示作用于自然数的函数呢？
以加法为例，我们需要引入一个新的节点来代表加法， 并且定义这个节点与其他节点之间的反应规则。
用一个有三个接口的节点表示加法。
|
(add)
/ \
下面两个接口代表输入的 被加数 与 加数，
上面一个接口代表输出的 得数。
得数
|
(add)
/ \
被加数 加数
比如 0 + 1 可以表示如下：
|
(add)
/ \
(zero) (add1)
|
(zero)
2 + 2 可以表示如下：
|
(add)
/ \
(add1) (add1)
| |
(add1) (add1)
| |
(zero) (zero)
通过定义 (add) 与相邻节点之间的反应方式，就可以完成加法的操作。
当 (add) 的 被加数 接口与 (zero) 相连时，
删除 (zero) 与 (add)，
并将 (add) 的 得数 与 加数 直接相连。
得数 得数
| |
(add) => |
/ \ \
(zero) 加数 加数
当 (add) 的 被加数 接口与 (add1) 相连时，
将 (add1) 转移到 (add) 上方。
得数 得数
| |
(add) => (add1)
/ \ |
(add1) 被加数 (add)
| / \
前数 前数 被加数
按照这两个规则，表示 2 + 2 的图，将通过如下的反应而得到 4：
| | | |
(add) (add1) (add1) (add1)
/ \ | | |
(add1) (add1) (add) (add1) (add1)
| | => / \ => | => |
(add1) (add1) (add1) (add1) (add) (add1)
| | | | / \ |
(zero) (zero) (zero) (add1) (zero) (add1) (add1)
| | |
(zero) (add1) (zero)
|
(zero)
我们来设计一个程序语言，以实践上面所描述的计算模型。
在我们的语言中，每个节点都有固定数量的接口。
(zero) -- 有一个接口
(add1) -- 有两个接口
(add) -- 有三个接口
每个接口都有名字。
(zero)-value -- 0 这个值
(add1)-prev -- 前一个数
(add1)-value -- +1 所得的值
(add)-target -- 被加数
(add)-addend -- 加数
(add)-result -- 得数
接口分为两类，一类是输入接口，一类是输出接口。
(zero)-value -- 输出接口
(add1)-prev -- 输入接口
(add1)-value -- 输出接口
(add)-target -- 输入接口
(add)-addend -- 输入接口
(add)-result -- 输出接口
节点和节点之间可以通过接口相连。
比如代表数字 2 的图：
(zero)-(add1)-(add1)-
其接口具体的连接方式是：
(zero)-value-<>-prev-(add1)
(add1)-value-<>-prev-(add1)
(add1)-value-<>-
每个节点都有唯一一个主接口， 只有当两个节点的主接口相连， 才可以根据规则进行反应。
(zero)-value! -- 主接口
(add1)-prev
(add1)-value! -- 主接口
(add)-target! -- 主接口
(add)-addend
(add)-result
我们设计定义节点的语句如下：
- 以
define-node作为语句的开头，后面跟着节点的名字。 - 用
->来区分输入接口与输出接口。 - 主接口加
!后缀。
前文提到的节点定义如下：
(define-node zero value!)
(define-node add1 prev value!)
(define-node add target! addend result)
针对指定的两个节点，可以定义一条反应规则。
带着接口的英文名字，回顾看一下
(add1) 和 (add) 之间的反应规则：
result value
| |
(add) => (add1)
/ \ |
(add1) addend (add)
| / \
prev target addend
我们发现所谓反应，其实就是：
- 拆掉两个主接口之间的边。
- 拆掉规则所匹配到的两个节点，此时会暴露出来原本与这两个节点相连的接口。
- 将暴露出来的接口重新连接，在这个过程中可以引入新的节点。
我们设计定义规则的语句如下：
- 以
define-rule作为语句的开头，后面跟着两个节点的名字。 - 拆下来的接口连接线按顺序保存到栈中。
以 (add1) 与 (add) 之间的规则为例：
(define-rule (add (add1 prev) addend result)
(add1 (add prev addend) result))
(zero) 与 (add) 之间的规则较为特殊，
因为在重新连接所暴露出来的接口时，
没有引入新的节点。
(define-rule (add (zero) addend result)
(connect addend result))
综合上面所设计的语法关键词，完整的一段代码如下。
(define-node zero value!)
(define-node add1 prev value!)
(define-node add target! addend result)
(define-rule (add (zero) addend result)
(connect addend result))
(define-rule (add (add1 prev) addend result)
(add1 (add prev addend) result))
;; test
(define (two) (add1 (add1 (zero))))
(define (inspect-run wire)
(wire-print-net (run (wire-print-net wire))))
(inspect-run (add (two) (two)))
我们强调一下反应网的限制， 以及由于这些限制而得到的， 反应网作为计算模型的属性。
第一个限制是，对于两个节点，最多只能定义一条反应规则。
也就是说，当发现两个节点的主接口相连时， 要么找不到这两个节点所对应的规则，此时这两个节点不能反应； 要么只能找到唯一一条规则，这两个节点按照这条规则反应。
这个限制排除了，能找到两条规则，而需要做选择的情况。
第二个限制是，每个节点有且仅有一个主接口。
假设有两个节点的主接口相连了。 我们画一个圈把这两个节点还有主接口之间的边都圈起来。 由于这两个节点都只有一个主接口， 所以能跨过这个圈的都非主接口之间的边。 这些边是不能反应的。
\ | /
.-------------.
| \ | / |
| (.....) |
| | |
| (.....) |
| / | \ |
`-------------`
/ | \
所以即便这两个节点之间的一次反应可能引入新的节点， 以及新的可反应的边，但是所有新的可反应边都会在这个圈子之内， 反应过程中的拆除与重连都不会影响到图的其他部分。
也就是说，在反应网这个计算模型中， 反应都是相互独立的，先在这里反应，或者先在那里反应， 不会影响最终的计算结果。
如果忽略不同位置反应进行的先后， 那么在反应网中， 不光计算的结果是唯一的， 计算的过程也是唯一的！
在实现反应网时，如果计算机有多个内核， 我们可以开多个线程，共享同一段内存， 同时进行图中不同位置的反应， 这些线程之间也不会相互干扰。
每个节点有且仅有一个主接口， 这条限制，给计算模型带来了优越的属性， 但是它也使得我们在用这个计算模型编程时不那么方便了。
取两个自然数最大值的函数就是一个例子，
我们称代表这个函数的节点为 (nat-max)。
result
|
(nat-max)
/ \
first! second
定义如下：
(define-node nat-max first! second result)
(zero) 与 (zero) 的反应很简单：
result result
| |
(nat-max) => |
/ \ \
(zero) second second
定义如下：
(define-rule (nat-max (zero) second result)
(connect second result))
如果没有单主接口的限制，
对于 (add1) 与 (zero) 的反应，
我们完全可以想象下面的反应规则：
result result
| |
(nat-max) => (add1)
/ \ |
(add1) (add1) (nat-max)
| | / \
prev prev prev prev
但是，由于单主接口的限制， 我们不得不增加一个辅助节点以及相关的规则， 来明显地在两个可反应的边中做出选择。
我们称辅助节点为 (nat-max-add1)。
result
|
(nat-max-add1)
/ \
first second!
定义如下：
(define-node nat-max-add1 first second! result)
利用辅助节点定义 (add1) 和 (nat-max) 之间的规则：
result result
| |
(nat-max) => (nat-max-add1)
/ \ / \
(add1) second prev second
|
prev
定义如下：
(define-rule (nat-max (add1 prev) second result)
(nat-max-add1 prev second result))
(zero) 与 (nat-max-add1) 之间的规则：
result result
| |
(nat-max-add1) => (add1)
/ \ |
first (zero) first
定义如下：
(define-rule (nat-max-add1 (zero) first result)
(add1 first result))
(add1) 与 (nat-max-add1) 之间的规则：
result result
| |
(nat-max-add1) => (add1)
/ \ |
first (add1) (nat-max)
| / \
prev first prev
定义如下：
(define-rule (nat-max-add1 (add1 prev) first result)
(add1 (nat-max first prev) result))
(define-node nat-max first! second result)
(define-node nat-max-add1 first second! result)
(define-rule (nat-max (zero) second result)
(connect second result))
(define-rule (nat-max (add1 prev) second result)
(nat-max-add1 prev second result))
(define-rule (nat-max-add1 (zero) first result)
(add1 first result))
(define-rule (nat-max-add1 (add1 prev) first result)
(add1 (nat-max first prev) result))
(inspect-run (nat-max (one) (two)))
我们已经分析了代表加法的节点 (add)，
下面我们来分析代表乘法的节点 (mul)。
我们将会发现，为了定义 (mul) 与 (zero) 和 (add1) 之间的反应规则，
我们又要引入两个新的辅助节点：
(nat-erase)删除一个自然数。(nat-dup)复制一个自然数。
这两个节点与之前的所有节点都不一样， 之前的所有节点都有一个输出节点， 然而：
(nat-erase)有零个输出节点。(nat-dup)有两个输出节点。
这其实是我们使用栈来构造网的主要原因。
使用栈的好处之一是， 可以自然地处理零个返回值和多个返回值的节点， 而不必为它们设计新的特殊的语法。
决定使用栈来构造网之后，就进而决定使用纯粹的后缀表达式作为语法。 这样的另一个好处是，词之间复合具有结合性。 因此当我们想要把一串词中的一部分切分出来，定义成新的词时， 不用考虑那么多语法上相互影响的地方。
(define-node nat-erase target!)
(define-rule (nat-erase (zero)))
(define-rule (nat-erase (add1 prev)) (nat-erase prev))
(define-node nat-dup target! first second)
(define-rule (nat-dup (zero) first second)
(connect first (zero))
(connect second (zero)))
(define-rule (nat-dup (add1 prev) first second)
(let ([prev-first prev-second (nat-dup prev)])
(connect first (add1 prev-first))
(connect second (add1 prev-second))))
(define-node mul target! mulend result)
(define-rule (mul (zero) mulend result)
(nat-erase mulend)
(zero result))
(define-rule (mul (add1 prev) mulend result)
(let ([mulend-first mulend-second (nat-dup mulend)])
(add (mul mulend-second prev)
mulend-first
result)))
(inspect-run (mul (two) (two)))
下面我们在自然数这个最简单的数据之后， 介绍几乎是第二简单的数据 -- 链表。
并且实现一个 append 函数，来将两个链表连接起来。
链表的 (append)
与自然数的 (add) 非常相似。
差异是自然数的 (add1) 只是单纯地增加一个节点，
而链表的 (cons) 在增加一个节点的同时，
还连接到了一个额外的节点。
(define-node null value!)
(define-node cons head tail value!)
(define-node append target! rest result)
(define-rule (append (null) rest result)
(connect rest result))
(define-rule (append (cons head tail) rest result)
(cons head (append tail rest) result))
;; test
(define-node sole value!)
(inspect-run
(append
(cons (sole) (cons (sole) (cons (sole) (null))))
(cons (sole) (cons (sole) (cons (sole) (null))))))
想要用 (append) 将两个链表连接起来，
需要遍历 (append) 的 target，
一步一步构造一个新的链表连，
接到 (append) 的 rest 前面。
这样，运算所需要的步骤与前一个链表的长度成正比。 可不可以将前一个链表直接与后一个链表连接起来呢？ 这样应该只需要固定的几步就可以完成计算。
我们可以定义一个新的数据类型 -- 差异链表，
和一个新的节点 (diff)，
这个节点用来可以抓着一个链表的头和尾。
如果想要连接两个差异链表，
只要把第一个 (diff) 抓着的尾，
和第二个 (diff) 抓着的头相连即可。
注意，在常见的程序语言中， 经常用树状结构的表达式来作为数据， 从树的父节点可以找到子节点，但是反之不行。 而在反应网中，所有节点之间的关系是对称的。
(define-node diff front back value!)
(define-node diff-append target! rest result)
(define-node diff-open new-back target! old-back)
(define-rule (diff-append (diff front back) rest result)
(let ([new-back value (diff front)])
(connect value result)
(diff-open new-back rest back)))
(define-rule (diff-open (diff front back) new-back old-back)
(connect back new-back)
(connect front old-back))
;; test
(define (sole-diff-list)
(let* ([front front-op (wire-pair)]
[back value (diff front)])
(cons (sole) (cons (sole) back) front-op)
value))
(inspect-run
(diff-append
(sole-diff-list)
(sole-diff-list)))
反应网介绍完了。
下面我们回顾一下，再展望一下。
反应网这个计算模型确实有趣， 在其中任何一步计算都可以相互独立地进行， 因此非常适合并行计算。
用栈与后缀表达式来构造非线性的网， 我们就有了反应网的简洁语法。
其实对于反应网这样的，基于图论的计算模型来说，图本身才是语法。 但是图是非线性的，为了用线性的文本去描述图， 我们使用栈和后缀表达式来构造图。
这样，用于构造图的语言，其实就成了反应网这个语言下面一层的语言。
在纯粹的反应网中，数据只有点和边构成的图， 想要编码自然数都要用结绳计数， 在很多使用场景下，这显然是不实用的。
通过给这个语言加上 int 和 float 之类的基础数据类型， 我们就可以让整个语言变成一个实用的语言。
预知具体设计如何，且听下回分解。