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