函数式语言中的多线程？ （序言）

Question

当我的朋友在学校开始学习 Prolog 时，我嘲笑他学习了一门无用的语言。然而，他向我展示了一些我从来不知道可能发生的东西；我想知道这个技术从何而来。

技术是这样的：

permutation(List) :-
    isAMember(X, List),
    deleteFirstElement(X, List, Substring),
    % and so on

在此代码中，isAMember(X, List) 是一个函数，如果 X 位于 List 中，则返回 true。但是，到目前为止，X 尚未定义为变量 - 因此程序将生成一堆新线程，每个线程对应 X 的每个可能值使 isAMember(X, List) true， 并从那里继续。

这使我们能够以我能想象到的最简单、最优雅的方式创建多线程算法。

所以我的问题是：这是 Prolog 特有的，还是所有逻辑和/或函数语言的功能？ 另外，我在哪里可以学习更多像这样的令人惊叹的多线程技术 - 这肯定是未来的编程。

Answer 1

Prolog 的子集称为“Datalog”，仅限于纯逻辑特征（无“剪切”），原则上，证明搜索可以并行完成。但是，您必须小心，因为完整 Prolog 的语义对结果生成的顺序非常敏感，并且一些真正的 Prolog 程序依赖于此。

Haskell 和 Clean 等纯函数语言的情况要好一些——并行计算子表达式总是安全的——但性能方面存在许多挑战。如果您执行极端并行性（每个子表达式），则由于所有开销，您不会获得任何性能提升。目前有前途的方法似乎是

• 线程（并发Haskell）

• 数据并行Haskell

• “Sparks”与par 和 seq 运算符。

并行函数已经存在了近 30 年，人们仍在努力使其表现良好。如果您想了解更多信息，请尝试

• ACM Haskell 研讨会的最新记录（以及在此之前的 Haskell 研讨会）

• Arvind 在麻省理工学院的工作，他是该领域的伟大先驱（请参阅他与 R. Nikhil 合着的关于 pH 并行编程的书）

Answer 2

如果我没记错我的 Prolog，那么您并没有创建线程，而是使用回溯和统一依次尝试 X 的每个可能的实例。这是相当连续的。

编辑：显然有一些实验性的并行序言，例如 Reform Prolog。然而，据我所知，这并不是 Prolog 实现中的规范。

Answer 3

isAMember(X, List) 不会创建线程，prolog 逻辑仅严重依赖于递归和回溯，并且非常程序化，除非您显式创建线程。

就 isAMember(X, List) 而言，您正在查看统一概念。该函数将与将该函数计算为 true 的所有值（在本例中为列表中包含的所有元素）统一。并继续使用 X 执行。

一旦执行到达叶子，它将回溯到最早可能的“仍然无法统一”的调用（或者切点，我认为，不记得正确的术语），说 isAMember(X, List)，将把 X 统一到下一个候选者，并恢复执行。

我敢说，如果你的逻辑不小心，你很容易就会出现堆栈溢出。

Answer 4

老实说，您所展示的内容似乎与列表理解没有任何不同，可能与 foreach 结合使用：

foreach {x | x in List}
    deleteFirstElement(x, List, Substring) 
    // not sure what deleteFirstElement does, so...

正如您提到的 isAMember 可以是任何东西，列表理解也可以更复杂

foreach {x | x in List if x % 2 == 0} // ie, even elements of List

沿着同样的路线，您可以做同样的事情没有列表理解的东西

new_list = old_list.every { x | x % 2 == 0 }

可以很容易地分解成线程。