可线索化算术表达式是一种算术表达式,在它的语法树表示中所有的叶节点都在左侧(或者右侧),我们称其为左展开(或右展开)可线索化算术表达式。可线索化算术表达式只有唯一的求值顺序。可线索化算术表达式在算术表达式几何里是居于核心的构造元素,它等同于几何路径。另外,在计算机系统的实践里,乘法累加单元( 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]。
容易证明,一条路径内部的各个操作子是满足结合律的;同时,对于两条路径,可以引入路径的拼接操作,解释为路径对应函数的复合。此时,同样可证结合律。由此,我们可以知道,一个路径的集合只要运算封闭,就有可能构成一个群胚。
交错式算术表达式
如果一个可线索化算术表达式里加法性的操作子(加法和减法)与乘法性的操作子(乘法和除法)是交错出现的,我们称其为交错式算术表达式。因为加零和乘一没有作用,我们可以把任意一个可线索化算术表达式规范化为交错式算术表达式。由于它整齐划一的特点,我们可以方便的讨论一些性质,比如一个扰动如何沿着交错式传递。