可线索化算术表达式

可线索化算术表达式是一种算术表达式，在它的语法树表示中所有的叶节点都在左侧（或者右侧），我们称其为左展开（或右展开）可线索化算术表达式。可线索化算术表达式只有唯一的求值顺序。可线索化算术表达式在算术表达式几何里是居于核心的构造元素，它等同于几何路径。另外，在计算机系统的实践里，乘法累加单元（ multiplier-accumulator unit，MAC unit）也是被广泛采用的计算机制，有不少算法是在此基础上实现的。

可线索化表达式

柯里化与路径表示法

在函数式编程里，柯里化是一个基本的编程技巧，它把一个有多个参数的函数变成一串单参数的函数调用。我们对可线索化算术表达式可以应用这个技巧，由此得到如下的路径表示法。首先引入基本的操作数和操作子：

• 起始操作数: 语法树最左叶节点
• 加法操作子: [math]\displaystyle{ \oplus_y: x \mapsto x + y }[/math]
• 减法操作子: [math]\displaystyle{ \ominus_y: x \mapsto x - y }[/math]
• 乘法操作子: [math]\displaystyle{ \otimes_y: x \mapsto x \cdot e^y }[/math]
• 除法操作子: [math]\displaystyle{ \oslash_y: x \mapsto x \cdot e^{-y} }[/math]

例如 [math]\displaystyle{ (((((1 \times 2) \times 2) + 1) \times 3) + 6) }[/math] 可以被柯里化为 [math]\displaystyle{ \oplus_6(\otimes_{\ln 3}(\oplus_1(\otimes_{\ln 2}(\otimes_{\ln 2}(1))))) }[/math] 。

我们有一串操作子 [math]\displaystyle{ a_1, a_2, \cdots a_{n-1}, a_n }[/math]，我们引入如下路径表示法：[math]\displaystyle{ x a_1 a_2 \cdots a_{n-1} a_n := a\_n( a_{n-1}( \cdots a_2( a_1(x) ) \cdots ) ) }[/math]。

于是，上例可以用路径表示法表示为 [math]\displaystyle{ 1 \otimes_{\ln 2} \otimes_{\ln 2} \oplus_1 \otimes_{\ln 3} \oplus_6 }[/math]。

容易证明，一条路径内部的各个操作子是满足结合律的；同时，对于两条路径，可以引入路径的拼接操作，解释为路径对应函数的复合。此时，同样可证结合律。由此，我们可以知道，一个路径的集合只要运算封闭，就有可能构成一个群胚。