对于每个命令式函数，是否存在具有相同性能甚至指令的函数对应项？

Question

目前，我还没有了解到一种函数式语言可以达到与C/C++相同的性能。而且我了解到，一些更喜欢函数式编程而不是命令式编程的语言，例如 Scala 和 Rust，使用命令式方式来实现其库函数以提高效率。

那么我的问题是，在当今执行命令式指令的计算机上，这是编译器或函数式编程本身的限制吗？对于每一个没有副作用的命令式函数，无论是在没有 GC 的语言中，如 C/C++/Rust/汇编，还是在有 GC 的语言中，如 Java，在 Haskell、Scala 等中是否有一个纯函数对应的函数。可以编译为在时间和空间上以相同的性能运行（不仅仅是渐近而是完全相同），甚至可以使用相同的指令，使用最佳的函数编译器，该编译器利用所有现代甚至未被发现的优化技术，例如尾递归、惰性、静态分析、形式验证等等我不知道的？

我知道 λ-可计算和图灵可计算之间的等价性，但我无法在网上找到这个问题的答案。如果有，请分享编译器示例或证明。如果不是，请解释原因并举出反例。或者这是一个重要的开放性问题？

---

根据建议进行补充编辑 安德烈·鲍尔:

更具体地说，这里有两个例子让我们思考这个问题。

例如，尾递归和累加器可以提高某些递归函数的性能，使其与使用命令式实现相同 for. 。在某些情况下，他们甚至可能有相同的说明。

另一个例子是关于 Haskell 中的惰性。惰性可以帮助避免不必要的数据结构复制并提高性能。然而，懒惰会留下包装、封闭等。在运行时，仍然无法使程序像没有这样的东西的命令式实现一样快。所以我想知道是否可以在编译期间运行时之前静态删除这些东西。

根据建议进行补充编辑 尼鲁:

这个问题也可以这样表述：是否有一种语言既支持纯函数式编程又支持命令式编程，并配有优化的编译器，其中命令式实现的每个没有副作用的函数都可以替换为纯函数式实现的函数，不影响性能，甚至可以编译为相同的函数指示？

Answer 1

1. 性能不是语言的属性，而是语言中特定程序的属性。有些语言可能在某些方面非常快，而在另一些方面却很慢。

   例如，Chez-Scheme 有时可以找到与 C 相当的性能，并不是因为该语言更高效，而是因为程序员在 C 中经常使用的防御性做法在 schema 中不太必要。

   同样，有时 Haskell 可以实现非常高效的并行性或并发性，不是因为它比 C 更快，而是因为该语言的不变性保证允许程序员避免诸如锁和其他同步技术之类的事情。

   而且，性能因实施而异。我可以手写一个 C 解释器，但速度肯定不会很快。C 不快，GCC 和 Clang 快。

2. 什么被认为是“功能性”语言？每种实用的函数式语言都有一些用于可变状态的工具：OCaml、Haskell、Scala、Lisp、Scheme 等尾递归给出的东西大致相当于 for 循环内的突变。但是，当这还不够时，函数式语言可以让程序员访问可变状态。就 Haskell 而言，这是由类型系统控制的，因此永远不会 隐式可变状态, ，但是 Haskell 中非常允许甚至鼓励突变。看看任何 Haskell 代码，你都会看到 IO monad 无处不在。同样，ML 语言区分类型 T 和 ref T, ，因此您可以通过类型判断变量是否可变。

3. 由于赖斯定理，不存在“最佳”编译器。所有编译器，无论是命令式编译器还是函数式编译器，都是“尽力而为”：使用保守的近似值来优化代码。

   如果我们有一个最佳的编译器，答案就是每个程序总是使用尽可能最有效的指令运行，并且用什么语言编写问题并不重要。计算问题的最佳指令序列不依赖于源语言。但是如果我们有这个，那么这个编译器会将每个非停止程序编译为 while(0), ，这意味着我们可以检测非暂停程序，这是不可能的。

4. 对于图灵机和 lambda 演算，我认为为图灵机实现 lambda 演算解释器是相当简单的 渐近地 相当于通用图灵机。人们所说的“函数式语言很慢”并不是指大 O 复杂性。通常他们谈论的是恒定的开销，这是非常不同的。我们没有很好的方法来对此进行数学建模，因此我们通常最终只是使用实验来测量精确的性能。