logo标签列表

函数式语言编译器相对于命令式语言编译器的优势

c#f#functional-programmingcompiler-theory
13
作为对这个问题的跟进 （F#内置不变性相对于C#的优势是什么？），我可以假设 F# 编译器能够进行某些优化，因为它处理的主要是不可变代码。我的意思是，即使开发人员编写了 "Functional C#" 代码，编译器也无法知道所有尝试编码的不可变性，因此不能进行相同的优化，对吗？
总的来说，一个函数式语言的编译器能否进行一些无法在命令式语言中实现的优化，即使使用了尽可能多的不可变性呢？
3
当您确定函数中没有副作用时，使用定理证明器将函数组合化简为数学上等价的优化版本就更加容易。当世界上的一切都在变化时，您不能过于激进地进行优化。如果不小心，可能会改变程序的含义。 - Mehrdad Afshari
我以为你在问用函数式语言和命令式语言编写编译器的优势。哈！ - Jared Updike
感谢大家提供的信息丰富的答案。 - Onorio Catenacci
6个回答
20
我能做出以下翻译：

我是否正确地认为，F#编译器可以通过处理大部分不可变代码来进行某些优化？

很遗憾，不是这样的。对于编译器编写者而言，“大部分不可变”和“不可变”之间存在巨大的差异。即使是保证不可变性也并不那么重要，主要的好处是可以编写非常激进的内联函数。

通常情况下，函数式语言的编译器能够进行哪些无法在命令式语言中实现的优化呢——即使是尽可能使用不可变性编写的命令式语言？

是的，但主要是能够更容易地在更多的地方应用经典的优化技术。例如，不可变性使得应用公共子表达式消除变得更加容易，因为不可变性可以保证您不会更改某些内存单元的内容。

另一方面，如果你的函数式语言不仅是不可变的，而且是纯的（没有像I/O这样的副作用），那么你就可以启用一类涉及将源级表达式重写为更高效表达式的优化。其中最重要且最有趣的是短路砍树，这是一种避免为中间结果分配内存空间的方法。一个很好的例子是流融合。

如果你正在编译一个静态类型的函数式语言以实现高性能，以下是一些重点：

  • 有效利用内存。尽可能使用“非装箱”值，避免分配和额外的间接引用到堆上。特别是流融合和其他消除分配技术非常有效，因为它们消除了分配。

  • 拥有超快速的分配器，并将堆耗尽检查分摊到多个分配中。

  • 有效地内联函数。特别是在模块边界内联小函数。

  • 有效地表示一级函数，通常通过闭包转换实现。高效处理部分应用函数。

  • 不要忽视经典的标量和循环优化。它们对像TIL和Objective Caml这样的编译器产生了巨大的影响。

如果你使用像Haskell或Clean这样的惰性函数语言，还有很多专门处理thunks的事情。

脚注：

  • 完全不可变性带来的一个有趣选项是更能执行非常细粒度的并行。这个故事的结局还没有被告知。

  • 为F#编写一个好的编译器比编写典型的编译器（如果有这样的东西）更难，因为F#受到严格限制：它必须很好地做函数式的事情，但它也必须在.NET框架内有效地工作，而该框架并不是为函数式语言而设计的。我们要感谢Don Syme及其团队在一个受到严格限制的问题上做出了如此出色的工作。

7

编号。

F#编译器不会尝试分析方法或lambda的引用透明性。.NET BCL根本没有为此设计。

F#语言规范确实保留了关键字“pure”，因此在vNext中可能可以手动标记方法为纯净，从而允许更积极地缩减lambda表达式的图形。

但是，如果您使用记录或代数类型，F#将创建默认比较和相等运算符，并提供复制语义。除了许多其他好处（模式匹配，封闭世界假设），这也减轻了重要负担！

5

是的，如果你不考虑F#，但考虑例如Haskell。没有副作用的事实确实为优化带来了很多可能性。

例如，在类似C语言中考虑：

int factorial(int n) {
    if (n <= 0) return 1;
    return n* factorial(n-1);
}

int factorialuser(int m) {
    return factorial(m) * factorial(m);
}

如果使用Haskell编写相应的方法，当您调用factorialuser时，将不会有第二个对factorial的调用。可能C＃也可以做到这一点，但我怀疑当前的编译器即使是对于这样一个简单的示例也无法实现。随着事情变得更加复杂，C＃编译器很难优化到Haskell可以达到的水平。
请注意，F＃目前并不是真正的“纯”函数式语言，因此我引入了Haskell（它很棒！）。
2
尾递归优化很简单，由JIT编译器处理。它对Haskell或函数式语言并不关心。你能想出一个更好的例子吗？ - Hans Passant
5
我不是在谈论阶乘的优化，我是在谈论如何优化阶乘用户函数(factorial user)，使其只需调用一次阶乘函数(factorial)。如果我的重点是尾递归，那写出阶乘用户函数并讨论它有什么用呢？ - Aryabhatta
@Moron 虽然在这种情况下，习惯于命令式编程的人不会写出像这样的代码并调用两次阶乘(m)。他们只是在factorialuser()函数内将其分配给一个临时变量，然后对其进行平方运算。不过，我认同你的观点，在更广泛的上下文中应用。 - Trevor Tippins
@Trevor：没错，这只是一个例子而已。还有其他可能性，比如重新排序等等。甚至可能有机会进行运行时优化（比如备忘录化）。 - Aryabhatta
@nobugz：这里没有尾递归（正如Moron所说）。 - leppie
3

很遗憾，由于F#只是基本纯净的，因此并没有太多机会进行积极优化。事实上，有些地方F#比C#“悲观”，例如制作防御性结构体副本以防止可观察到的突变。但好的一面是，尽管如此，编译器总体表现良好，在大多数情况下提供与C#相当的性能，同时使程序更易于理解。

2

有时候，对于函数式语言的额外优化是可能的，但并不一定是因为不可变性。在内部，许多编译器会将代码转换成SSA（单静态赋值）形式，其中函数内的每个本地变量只能分配一次。这可以用于命令式和函数式语言。例如：

x := x + 1
y := x + 4

可以变成

x_1 := x_0 + 1
y := x_1 + 4

其中x_0和x_1是不同的变量名。这大大简化了许多转换操作，因为您可以将代码块移动到程序中的特定点而不必担心它们在该点具有的值是什么。但对于存储在内存中的值（即全局变量、堆值、数组等），这种方法不起作用。同样，这适用于函数式和命令式语言。

大多数函数式语言提供的一个好处是强类型系统。这使得编译器能够做出否则无法做出的假设。例如，如果您有两个不同类型的引用，编译器知道它们不能别名（指向同一物体）。这不是C编译器能够做出的假设。

根据标准，C编译器可以合法地做出这种假设。根据“严格别名规则”，不允许两个不同类型的指针指向同一地址。关于严格别名规则的讨论。 - user582350
2
我认为主要是'不行'。
从不可变性或引用透明度获得的主要'优化'优势，例如在看到代码时能够执行'公共子表达式消除'，如...f(x)...f(x)...。 但是，这种分析很难进行，没有非常精确的信息，因为F#运行在.Net运行时上，而.Net没有将方法标记为纯（无副作用）的方法，因此即使要尝试执行任何此类操作也需要大量内置信息和分析。
另一方面，在像Haskell这样的语言（这主要意味着'Haskell'，因为很少有人听说或使用其他类似于Haskell的语言 :))中，分析更简单（所有内容都是纯的）。
尽管如此，这样的“优化”通常会与系统的其他有用方面（性能可预测性，调试等）产生不良交互。
通常有关“足够聪明的编译器可以执行X”的故事，但我的观点是，“足够聪明的编译器”始终是一个神话。如果您想要快速的代码，请编写快速的代码；编译器不会拯救您。如果您想进行公共子表达式消除，请创建一个本地变量（自己做）。
这主要是我的意见，您可以投反对票或不同意（的确我听说过“多核心”被提出作为潜在的“优化可能再次变得性感”的原因，这在表面上听起来是有道理的）。但是，如果您对任何编译器执行任何非平凡优化（不受源代码注释支持）抱有希望，那么请准备等待很长时间才能实现您的希望。
不要误解 - 不可变性很好，并且在许多情况下有助于您编写'快速'代码。但并非因为编译器对其进行了优化 - 而是因为代码易于编写，调试，正确，并行化，分析并决定哪些是最重要的瓶颈需要花费时间（可能将它们改写成可变形式）。如果您想要高效的代码，请使用开发过程，可以让您快速开发，测试和分析。
谢谢Brian，这正是我所期望的解释。我一直以为由于更多的不可变性，编译器能够进行一些优化，在编译命令式代码时是不可能的。显然，我的假设是错误的。 - Onorio Catenacci
但这确实是一个优势。你可以懒惰地编写代码，就像知道编译器可以轻松进行这样的优化一样容易。在大多数情况下，我宁愿不自己编写常见的子表达式。 - Thomas Eding
我认为“编译器可以轻松完成的优化”和“你的编译器实际完成的优化”之间存在着一条宽如海洋的鸿沟。 - Brian
需要注意的是，在Haskell中，常见子表达式消除并不比其他语言更容易，因为仅仅消除常见子表达式可能会导致空间泄漏。检测CSE何时导致空间泄漏是困难的，而在非纯语言中确定函数是否为纯函数是简单的（计算纯/非纯的良好近似值是简单的）。 - Jules
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接