函数式编译器优于命令式语言编译器的优点

Question

作为对这个问题的跟进,F#内置不变性对C#有什么好处？--am我正确地假设F#编译器可以在知道它处理很大程度上不可变的代码时进行某些优化吗？我的意思是即使开发人员写了"Functional C#",编译器也不会知道开发人员试图编写的所有不可变性,因此它无法进行相同的优化,对吧？

通常情况下,函数式语言的编译器能够进行使用命令式语言无法实现的优化 - 即使是尽可能多的不可变写的语言编写的吗？

Answer 1

我是否正确假设F#编译器能够在知道它处理大部分不可变代码的情况下进行某些优化？

不幸的是.对于编译器编写者来说,"很大程度上不可变"和"不可变"之间存在巨大差异.即使是保证不变性也不是优化者那么重要; 它买的主要是你可以写一个非常积极的内联.

通常情况下,函数式语言的编译器能够进行使用命令式语言无法实现的优化 - 即使是尽可能多的不可变写的语言编写的吗？

是的,但这主要是能够在更多地方更轻松地应用经典优化的问题.例如,不变性使得应用公共子表达式消除变得更加容易,因为不变性可以保证某些存储器单元的内容不会被更改.

另一方面,如果您的函数式语言不仅仅是不可变的而且是纯粹的(没有像I/O这样的副作用),那么您可以启用一个新的优化类,其中包括将源级表达式重写为更高效的表达式.其中最重要和最有趣的一点是砍伐森林砍伐,这是一种避免为中间结果分配内存空间的方法.阅读的一个很好的例子是流融合.

如果您正在为高性能编译静态类型的函数式语言,以下是一些重点:

• 有效使用记忆.如果可以的话,使用"未装箱"的值,避免分配和额外的堆间接.特别是流融合和其他森林砍伐技术都非常有效,因为它们消除了分配.

• 拥有超快速分配器,并在多个分配上分摊堆耗尽检查.

• 内联函数有效.特别是跨模块边界的内联小功能.

• 通常通过闭包转换有效地表示第一类函数.有效处理部分应用的功能.

• 不要忽视经典的标量和循环优化.他们对TIL和Objective Caml等编译器产生了巨大的影响.

如果您使用像Haskell或Clean这样的惰性函数语言,那么还有很多专门用来处理thunk的东西.

脚注:

• 完全不变的一个有趣的选择是能够执行非常细粒度的并行性.这个故事的结尾尚未被告知.

• 为F#编写一个好的编译器比编写一个典型的编译器(如果有这样的东西)更难,因为F#受到如此严格的限制:它必须很好地完成功能,但它必须在.NET框架中有效工作,这是没有考虑到功能语言.我们应该向Don Syme和他的团队倾斜,因为他们在严重受限的问题上做得非常出色.

Answer 2

没有.

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

F#语言规范确实保留了关键字"pure",因此可以在vNext中手动将方法标记为纯,从而允许更加积极的lambda表达式图形缩减.

但是,如果使用记录或代数类型,F#将创建默认比较和相等运算符,并提供复制语义.在许多其他好处(模式匹配,封闭世界假设)中,这减轻了重大负担!

Answer 3

是的,如果你不考虑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(很棒!).

Answer 4

我基本上会说“不”。

从不变性或引用透明性中获得的主要“优化”优势是，当您看到类似...f(x)...f(x).... 但如果没有非常精确的信息，这样的分析很难完成，而且由于 F# 在 .Net 运行时上运行，而 .Net 无法将方法标记为纯方法（无效果），因此需要大量内置信息和分析来甚至尝试做任何这样的事情。

另一方面，在像 Haskell 这样的语言中（这主要意味着“Haskell”，因为很少有语言“像 Haskell”有人听说过或使用过:)）是惰性和纯粹的，分析更简单（一切都是纯粹，发疯）。

也就是说，这种“优化”通常会与系统的其他有用方面（性能可预测性、调试等）产生不良交互。

经常有这样的故事：“足够聪明的编译器可以完成 X 任务”，但我的观点是，“足够聪明的编译器”现在是、也永远是一个神话。如果你想要快速的代码，那就写快速的代码；编译器不会拯救你。如果您想要消除公共子表达式，请创建一个局部变量（自己做）。

这主要是我的观点，欢迎您投反对票或不同意（事实上，我听说“多核”被认为是潜在的“优化可能再次变得性感”的一个上升原因，这从表面上看似乎是合理的）。但是，如果您希望任何编译器执行任何重要的优化（源代码中的注释不支持），那么请准备好等待很长一段时间才能实现您的希望。

不要误会我的意思 - 不变性很好，并且可能会帮助您在许多情况下编写“快速”代码。但这并不是因为编译器对其进行了优化，而是因为代码易于编写、调试、正确化、并行化、分析并决定哪些是需要花时间处理的最重要的瓶颈（可能会可变地重写它们）。如果您想要高效的代码，请使用可让您快速开发、测试和分析的开发流程。