有哪些函数式编程语言原生支持分治算法？

Question

非常抱歉我无法想出更清晰的标题来表达问题，但本质上是这样的：几乎所有函数式语言都有构造函数，可以通过尾递归处理变量列表，就像这个Erlang伪代码一样，它对数字列表求和：

sumup(0,A) -> A.
sumup(N,A) -> sumup(N) + A.

然而，函数式语言对我来说最大的吸引力之一是它们固有的并行性。尽管诸如对数字列表求和这样的问题显然非常易于并行化，并且几乎肯定可以通过分而治之最有效地处理，但我不知道是否有语言特性可以使这成为自然编程方式。实际上，除非语言具有允许基于函数传递的参数数量读取并根据索引检索参数的特性，否则我不知道怎么做。是否有任何函数式语言具有鼓励分而治之编程的特性？

- afeldspar

---

我不太确定你所说的“divide”是什么意思。如果你指的是将集合分区以进行递归计算（例如归并排序），那么任何函数式编程语言都可以做到。但是我想知道，如果你所说的“divide”是指将其划分为不同的执行路径（比如线程），那又会怎样呢？ - Alan

不仅仅是能够将集合进行递归计算的分区能力，而且要比尾递归更有效地实现这一点。 - afeldspar

Answer 1

是的：有能力在库中创建新的高阶函数来鼓励分治编程。

其中一个最重要的这样的函数，在列表上，是foldr，当应用于一个关联操作符时，原则上可以并行化，尽管实际上很少这样做。为什么?因为foldr是围绕顺序数据流设计的。

函数式语言的美妙之处在于，一旦认识到这个问题，我们就不必引入新的语言特性，而是通过更加智能地利用我们已经拥有的特性来解决问题。要了解如何操作，请查看Guy Steele's talk from August 2009，他解释了为什么foldr不是并行函数式编程的正确库函数，并提出了

• 一种新的编程风格
• 一种新的列表表示
• 库的新高阶函数

它们都是为支持分治编程而设计的。

我发现这个讲话令人兴奋的地方在于，支持分而治之编程“本地化”并不需要引入新的语言特性。利用我们已经拥有的基本元素来设计更好的库就足够了。

如果您可以访问ACM数字图书馆，您可以观看Guy的演讲视频Organizing Functional Code For Parallel Execution，或者如Ben Karel所指出的那样，您可以在Vimeo上观看由Malcom Wallace拍摄的视频。

- Norman Ramsey

---

Guy的演讲可在Vimeo上观看：http://www.vimeo.com/6624203。此外，Project Fortress团队还有其他幻灯片和论文在线，afeldspar可能会感兴趣：http://research.sun.com/projects/plrg/Publications/index.html。 - Ben Karel

那么这就是你从他的演讲中得到的内容吗？我认为他的演讲是关于我们目前拥有的语言级别特性不足以设计更好的库。每个人都有自己的想法，对吧？（警告：我真诚地相信，一个真正革命性的想法是几个人可以完全相反地解释的想法） - Pascal Cuoq

@Pascal：当然，他在推销Fortress，但我认为Guy的演讲完全是关于库的。 （想一想，这也是我看待Fortress的方式。）如果我们想在Haskell中使用这个模型，我们已经有了par，所以我们所要做的就是摆脱由我们的cons单元强加的限制！不需要伤害编译器，但我们必须重写所有的库... - Norman Ramsey

Answer 2

自动并行不像看起来那么简单。问题在于，如果分区是自动完成的，就有过度分区（太多分区）的风险，这会增加太多开销，或者分区不足，这将不能充分利用CPU中的所有核心。静态地（即在编译时）解决这个问题相当困难，这就是为什么通常将其留给开发人员注释何处进行并行化的原因。

例如：

Haskell具有 par combinator，它作为注释创建一个spark，即当CPU核心可用时，将计算转换为线程。 Data Parallel Haskell：定义了一种并行数组数据类型，以允许更隐式的并行化风格，但似乎要付出一些限制的代价，而且仍然是实验性代码。

（免责声明：我不是Haskell开发人员）

.NET中的任务并行库：可以自动并行化数据，或者您可以实现自己的Partitioner。您仍然需要了解并行化的工作原理，否则您会遇到过度或不足分区的问题。Reed Corpsey有一系列关于TPL和PLINQ的优秀文章。

DryadLINQ基于PLINQ构建，并添加了自动分布式计算。

这些都不是真正的本地语言，但它们与语言紧密集成。甚至还有一个F#的PLINQ集成模块。

- Mauricio Scheffer

Answer 3

看看曼蒂科，它的前身NESL和它的兄弟ZPL。所有这些都是至少部分功能语言，具有并行构造，可以一次操作数据结构的整个内容。

- Phil Miller

Answer 4

我对任何具有分治模式的语言都不熟悉。就像你所说的，很难想象如何指定这样的东西。

如果没有全新的符号表示法，我认为经典函数如partition是我们能做到的最好的。

- David Seiler

---

我该如何了解更多关于那个函数的信息？我一直在尝试研究它，但似乎无法缩小我的搜索范围。 - afeldspar

partition函数接受一个列表，并根据某个谓词将其分成两个子列表。如果您查找快速排序的函数式实现，您会发现它无处不在。 - David Seiler

Answer 5

在 Ruby 中，这种事情很容易指定。在这个例子中，我们将一个范围分成三组，并在每个组上调用 sum 方法。然后我们对得到的部分和求和。你可以很容易地扩展它以使其支持多线程。

(1..10).each_slice(3).map{ |x| x.inject :+ }.inject(:+)

这个例子与你的有些不同，但是展示了原则。

- Peter