31

无副作用、引用透明的函数式编程的承诺之一是可以对此类代码进行广泛优化。引用维基百科：

在许多情况下，数据的不变性可以提高执行效率，因为它允许编译器在命令式语言中做出不安全的假设，从而增加内联扩展的机会。

我希望看到函数式语言编译器通过生成更好的优化代码来胜过命令式编译器的示例。

编辑：我试图给出一个特定的场景，但显然这不是一个好主意。所以我会尝试用不同的方式来解释它。

程序员将想法（算法）翻译成机器可以理解的语言。同时，翻译的最重要方面之一是人类也可以理解生成的代码。不幸的是，在许多情况下需要权衡取舍：简洁易读的代码会受到性能缓慢的影响，需要手动优化。这是容易出错、耗时的，并且会降低代码的可读性（甚至完全不可读）。

函数式语言的基础，例如不变性和引用透明性，允许编译器执行广泛的优化，这可以取代手动优化代码并使程序员从这种权衡中解脱出来。我正在寻找想法（算法）及其实现的示例，例如：

  1. （功能）实现接近原始想法并且易于理解，
  2. 它被语言的编译器广泛优化，并且
  3. 如果没有降低其简洁性和可读性的手动优化，很难（或不可能）用命令式语言编写类似高效的代码。

如果有点含糊，我深表歉意，但我希望这个想法很清楚。我不想对答案进行不必要的限制。如果有人知道如何更好地表达它，我愿意接受建议。

我的兴趣不仅仅是理论上的。我想用这样的例子（除其他外）来激励学生对函数式编程产生兴趣。

起初，我对评论中建议的几个例子并不满意。再三考虑，我收回我的反对意见，这些都是很好的例子。请随时将它们扩展为完整的答案，以便人们可以评论和投票。

（一类这样的例子很可能是并行化代码，它可以利用多个 CPU 内核。通常在函数式语言中，这可以很容易地完成，而不会牺牲代码的简单性（比如在 Haskell 中通过添加par或pseq在适当的地方）。我是也对此类示例感兴趣，但也对其他非平行示例感兴趣。）

4

4 回答 4

23

在某些情况下，相同的算法在纯上下文中会优化得更好。具体来说，流融合允许由一系列循环组成的算法，这些循环的形式可能多种多样：映射、过滤器、折叠、展开，组合成一个循环。

传统命令式设置中的等效优化，循环中的可变数据，必须实现完整的效果分析，这是没有人做的。

因此，至少对于作为序列上的变形和变态管道实现的算法类，您可以保证在命令式设置中不可能的优化结果。

于 2013-01-16T14:30:09.517 回答
8

Geoff Mainland、Simon Peyton Jones、Simon Marlow、Roman Leshchinskiy最近的一篇论文Haskell beats C using generalized stream fusion（提交给 ICFP 2013）描述了这样一个例子。摘要（有趣的部分以粗体显示）：

流融合 [6] 是一种强大的技术，用于将高级序列处理功能自动转换为有效的实现。它已在 Haskell 库中用于处理字节数组、Unicode 文本和未装箱的向量，效果非常好。然而，一些操作，如向量追加，在标准流融合框架中仍然不能很好地执行。其他的，例如使用现代 x86 芯片上可用的 SSE 和 AVX 指令的 SIMD 计算，似乎根本不适合该框架。

在本文中，我们介绍了广义流融合，它解决了这些问题。关键的见解是将多个流表示捆绑在一起，每个流表示都针对特定类别的流消费者进行了调整。我们还描述了一种适合使用 SSE 指令进行高效计算的流表示。vector我们的想法在 GHC 编译器和库 的修改版本中实现。基准测试表明，使用我们的编译器和库编写的高级 Haskell 代码可以生成比编译器和手动向量化 C 更快的代码。

于 2013-04-11T09:52:09.493 回答
3

这只是一个注释，而不是答案：gcc有一个pure属性表明它可以考虑纯度；明显的原因在此处的手册中进行了说明。

我认为“静态单一分配”强加了一种纯洁形式——请参阅http://lambda-the-ultimate.org/node/2860上的链接或维基百科文章。

于 2013-01-28T19:06:59.800 回答
0

通过假设各种构建步骤是参照透明的，使得和各种构建系统在大型项目中表现更好；因此，他们只需要重新运行输入发生变化的步骤。

对于中小型更改，这可能比从头开始构建要快得多。

于 2013-01-30T21:15:37.987 回答