5

当我的朋友在学校开始学习 Prolog 时，我取笑他学习了一种无用的语言。然而，他向我展示了一些我什至不知道可能的东西；我想知道这种技术是从哪里来的。

技术是这样的：

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

在这段代码中，isAMember(X, List)是一个函数，如果X是 in则返回 true List。然而，到目前为止X还没有被定义为一个变量——所以程序将产生一堆新线程，每个可能的值都为X真isAMember(X, List)，然后从那里继续。

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

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

4

4 回答 4

9

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

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

  • 线程（并发 Haskell）

  • 数据并行 Haskell

  • par与seq运营商“火花” 。

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

  • 最近的 ACM 研讨会 Haskell 会议记录（以及之前的 Haskell 研讨会）

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

于 2010-02-01T06:00:12.187 回答
3

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

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

于 2010-02-01T03:55:55.253 回答
0

isAMember(X, List)不会创建线程，序言逻辑只是严重依赖递归和回溯，除非您明确创建线程，否则它是非常程序化的。

在 的情况下isAMember(X, List)，您正在查看统一概念。该函数将与将该函数评估为真的所有值统一，在这种情况下，列表中包含的所有元素。并继续执行 X。

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

我敢说，如果你在逻辑上不小心，你很容易得到堆栈溢出。

于 2010-02-01T04:08:39.033 回答
0

老实说，您显示的内容似乎与列表理解没有什么不同，可能与 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 }

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

于 2010-02-02T14:42:08.090 回答