任何人都可以编写一个程序将总和（1 到 n）更改为 n*（n+1）/2 自动吗？

Question

与记录总和：

let rec sum a=if a==0 then 0 else a+sum(a-1)

如果编译器使用尾递归优化，它可能会创建一个变量“sum”来迭代（当我使用“ocamlc -dlambda”时，递归仍然存在。当我使用“ocamlc -dinstr”得到汇编代码时，我现在看不懂）

但是在《Design Concepts of programming languages》一书287页，可以把函数改成这个（关键行）：n*(n+1)/2

“你应该说服自己，这个最不固定的点 函数是返回求和过程的计算 csum，如果其参数是“

”中的非负整数，则返回 n*(n+1)/2

我无法理解，prog 不是 Gauss！我认为它不能将“rec sum”更改为 n*(n+1)/2 automatic！只有人才能做到，对吗？

所以这本书写在这里是什么意思？有人知道吗？谢谢！

Answer 1

我相信你的书只是提出了关于纯函数等价性的一个小观点。尽管如此，优化掉只包含仿射运算的循环还是相对容易的。

纯函数等价

我没读过那本书，但从你引用的段落来看，我认为这本书只是提出了一个关于纯函数的观点。由于

sum

是一个纯函数，即一个没有副作用的函数，那么在某种意义上，

let rec sum n =
    if n = 0 then 0
    else n + sum (n - 1)

相当于

let sum n =
    n * (n + 1) / 2

但是这里的“等效”当然忽略了时间和空间的复杂性，除非编译器对常用函数进行某种硬编码来优化，否则如果它像那样优化

sum

我会感到非常惊讶。

另请注意，以上两个函数仅在仅在非负参数上调用时才等效。如果

n

为负数，递归版本将无限循环（并引发堆栈溢出）；直接公式版本将始终返回一个结果，尽管如果

n

为负，该结果将是无意义的。

只包含仿射操作的优化循环

尽管如此，编写一个可以执行此类优化的编译器并不完全是科幻小说。在此答案的末尾，您会找到指向您可能感兴趣的两篇博文的链接。在此答案中，我将总结如何将这些博文中描述的方法应用于您的问题。

首先让我们将函数

sum

重写为伪代码中的循环：

function sum(n):
    s := 0
    i := 1
    repeat n:
        s += i
        i += 1
    return s

这种重写类似于将

sum

转化为尾递归函数时发生的情况。

现在，如果你考虑向量

v = [s, i, 1]

，那么仿射运算

s += i

和

i += 1

可以描述为将

v

乘以矩阵：

s += i
[[ 1, 0, 0 ],    # matrix Msi
 [ 1, 1, 0 ],
 [ 0, 0, 1 ]]

i += 1
[[ 1, 0, 0 ],    # matrix Mi1
 [ 0, 1, 0 ],
 [ 0, 1, 1 ]]

s += i, i += 1
[[ 1, 0, 0 ],    # M = Msi * Mi1
 [ 1, 1, 0 ],
 [ 0, 1, 1 ]]

此仿射操作包含在“重复

n

”循环中。所以我们必须将

v

乘以这个矩阵

M

，

n

次。但是矩阵乘法是结合的；所以不是用矩阵

n

做

M

乘法，我们可以将矩阵

M

提高到它的

n

次方，然后将

v

乘以得到的矩阵

M**n

。

事实证明：

[[1, 0, 0],                [[          1, 0, 0],
 [1, 1, 0],  to the nth =   [          n, 1, 0],
 [0, 1, 1]]                 [n*(n - 1)/2, n, 1]]

代表仿射运算：

s = s + n * i + n * (n - 1) / 2
i = i + n

从

s, i = 0, 1

开始，这给了我们预期的

s = n * (n+1) / 2

。

更多阅读：

• 利用矩阵的快速提升来编写简单编程语言的非常快速的解释器；
• 通过快速矩阵求幂的自动算法优化.

Answer 2

是的，这是 Stef 出色回答中展示的已知转换。我想给它添加更多注释：

OCaml 进行尾递归优化¹，其中函数调用被消除并变成循环，但它没有进行这种封闭形式的转换，这是它自己的事情。不过，今天可以在 LLVM² 中进行转换！

虽然您提到您无法阅读 OCaml 生成的assembly³，但我认为您仍然可以进行足够的解释以看到优化的实际效果⁴.

unsigned recsum(unsigned n) {
  return n ? n + recsum(n - 1) : 0;
}

循环和递归函数通常用以

j

开头的指令表示，以某种方式使用它们跳转到它们上面的代码，您会注意到 gcc 发出了

jmp

到较早的标签以供参考，但是 clang （LLVM）根本不会发出任何此类指令。

当您编写 OCaml 时，您必须在需要时手动进行此类封闭式优化。没有多少编译器能像 LLVM 那样走得那么远，这样做的回报会递减，而且每次新添加的分析都会影响编译时间。

---

^{1你假设求和函数是尾递归的是不正确的，因为这里尾部位置的函数是}

(+)

let rec sum a =
 if a = 0 then 0 else a + sum (a - 1)

^{2github.com/llvm/llvm-project
3 注意 -dinstr 转储字节码指令，您想使用}

ocamlopt

和

objdump

进行汇编
^{4https://clang.godbolt.org/z/rcc6jcG9T}