Prolog有多并发？

Question

我在网上找不到任何关于这个的信息... 我也是Prolog的新手...

在我看来，Prolog可能是高度并发的，也许在尝试匹配规则时会同时尝试多种可能性。 现代的Prolog编译器/解释器是否本质上是并发的？哪些是？默认情况下是否启用并发？我需要以某种方式启用它吗？

* 我对多线程不感兴趣，只对本质上的并发感兴趣。

- alejandro5042

Answer 1

不是所有现代Prolog编译器/解释器都内在地支持并发。哪些编译器支持并发？并发默认开启吗？

今天，Prolog编译器往往提供线程库，程序必须手动控制并发量。自动实现并发的尝试通常会失败，因为并发编程并不容易。在1980年代，日本的第五代计算机项目的主要目标是并行逻辑编程，人们预计Prolog变体将能够轻松地在大规模并行硬件上并行化。但由于自动并发并不容易，这个努力在很大程度上失败了。要理解为什么将Prolog进行并行化与其他语言一样困难，请考虑该语言提供的两种主要控制结构：合取（AND，串行执行）和析取（OR，带回溯的选择）。假设您有一个AND结构...

p(X) :- q(X), r(X).

如果您想要并行运行q(X)和r(X)，那么如果q部分统一了X（例如将其绑定到f(Y)），那会发生什么呢？r必须知道这个绑定，所以要么您必须进行通信，要么您必须等待两个并列子句完成；如果其中一个失败，则可能会浪费时间，除非您再次让它们进行同步通信。这会增加开销，并且很难做到正确。现在看看OR：

p(X) :- q(X).
p(X) :- r(X).

这里有一个有限的选择（当然，Prolog允许无限多的选择），所以您想要同时运行它们两个。但是，如果其中一个成功了怎么办？计算的另一部分必须被暂停并保存其状态。您会同时保存多少个状态？和处理器一样多似乎是合理的，但是那么您必须小心，不要让计算创建不适合内存的状态。这意味着您必须猜测计算的状态有多大，而Prolog隐藏了这些实现细节，例如处理器和内存； 它不像C语言。

换句话说，自动并行化很难。第五代计算机项目通过设计具有承诺选择的语言解决了其中的一些问题，即没有回溯的Prolog方言。在这样做时，他们彻底改变了语言。值得注意的是，并发语言Erlang是Prolog的一个分支，它也通过交换回溯来获得更接近函数式编程的东西。它仍然需要用户指导，以知道程序中哪些部分可以安全地并行运行。

- Fred Foo

---

是的，SICStus3和YAP可以适当编译（如果不利用并行或多核硬件，则存在一些开销）。 - David M W Powers

Answer 2

理论上看起来很有吸引力，但存在各种问题，使得这样的实现似乎不明智。

• 无论好坏，人们都习惯于将他们的程序视为从左到右和自上而下执行，即使在 Prolog 编程时也是如此。在标准的 Prolog 中，谓词子句的顺序以及子句内术语的顺序都具有语义意义。并行化它们会改变太多现有代码的行为以至于变得不流行。

• 非关系型的语言元素（例如 cut 操作符）只有在可以依赖这种执行顺序时才能有意义地使用，即在并行解释器中它们将变得无法使用，除非发明了非常复杂的依赖跟踪。

• 所有现有的并行化解决方案都会产生至少一些性能开销，用于线程间通信。

• Prolog 通常用于高级、深度递归的问题，例如图遍历、定理证明等。在现代计算机上进行并行化可以（理想情况下）实现某个常数 n 的加速，但它不能将一个不可行的递归解决方法转变为一个可行的方法，因为那将需要指数级加速。相比之下，Fortran 和 C 程序员通常解决的数字问题通常具有高但相当有限的计算成本。进行并行化以将一个耗时 10 小时的工作转变为一个耗时 1 小时的工作是值得的。相比之下，把一份程序从平均能看到 6 步延长到看到 6.5 步就不那么吸引人了。

- Kilian Foth

---

+1 是为了给出一个深思熟虑的答案，强调标准 Prolog 实现在设计上不具有并发性（即固有的并行性）。你对这个问题的负面方面进行了充分的阐述，也许需要在另一方面寻求一些平衡，所以我也想试试。 - hardmath

是的，我很想听另一方的意见。我接受这个答案，但是说并行性太难是逃避责任的借口。不过，回答非常好。 - alejandro5042

不想显得对立，谢谢你的回答 :) - alejandro5042

第三点是主要问题 - 并行性的开销，就像任何语言一样。第1和第2点代表了不好的风格 - 纯逻辑程序不会有剪枝，并且不会依赖于从左到右自上而下的执行（我只写这种类型 - 但可能会添加绿色剪枝以提高效率）。第4点实际上是关于解决的问题 - 如果问题需要盲目搜索，则语言无关紧要，如果它是确定性的，则Prolog可以直接反映这一点（由程序员）或间接地（通过程序转换/编译）。 - David M W Powers

Answer 3

在Prolog中有两种并发的概念。一种与多线程相关，另一种与挂起目标相关。我不确定你想知道什么。所以我先稍微扩展一下关于多线程的内容：

现在广泛可用的Prolog系统可以区分它们是否支持多线程。在一个多线程的Prolog系统中，你可以创建多个线程并行地运行在同一个知识库上。这对于consult和dynamic谓词提出了一些问题，但这些问题已经被这些Prolog系统解决了。

你可以在这里找到支持多线程的Prolog系统的列表： 操作系统和Web相关功能 多线程是各种并行化范式的先决条件。相应地，各个Prolog系统提供了用于支持特定范式的构造。典型的范式包括线程池，例如在Web服务器中使用，或者为长时间运行的GUI任务创建一个线程。

目前还没有线程库的ISO标准，尽管已经有提案，并且每个Prolog系统通常都有丰富的库，提供线程同步、线程通信、线程调试和外部代码线程。在Prolog系统中取得垃圾回收的一定进展是必要的，以允许具有潜在无限长运行线程的线程化应用程序。

一些现有的层甚至允许在独立于Prolog系统的高级并行化范式中进行。例如，Logtalk具有一些构造，可以映射到各种目标Prolog系统。

现在让我们转向挂起的目标。从旧的Prolog系统（自Prolog II，1982年以来）我们就知道freeze/2命令或阻塞指令。这些构造强制一个目标不被现有子句扩展，而是放在睡眠列表上。该目标稍后可以被唤醒。由于目标的执行不是立即的，而只有在它被唤醒时才会执行，因此挂起的目标有时被视为并发目标，但对于这种形式的并行性来说，更好的概念应该是协程。

挂起目标对于实现约束求解系统非常有用。在最简单的情况下，睡眠列表是某个变量属性。但是，约束处理规则是约束求解系统的一种较新方法。在约束处理规则中，唤醒条件可以是挂起目标对模式。通过挂起目标或约束处理规则提供的约束求解的可用性可以在此处查看：

Prolog系统概述

此致

- user502187

---

这两种方式都不是OP所询问的 - 明确不是多线程，也不是通过暂停进行协同处理。有一些系统可以自动执行AND-或OR-并行操作，包括SICStus和YAP Prolog编译器中的选项。我已经广泛使用了SICStus OR-parallelism。 - David M W Powers

我指的是CHR，从这篇新论文中来看，我想应该没错。这篇论文的题目是《约束处理规则中的并行、并发和分布式：一份调查报告（草稿）》，作者是Thom Fruehwirth。链接为https://arxiv.org/abs/1703.10959。 - user502187

这个答案非常有用，突出了并行和并发之间的关键区别。顺便问一下，Tau Prolog 什么时候能够成为这样概述表格中的常见成员呢？ - Erik Kaplun

我除了不时在GitHub上提出问题之外，并没有参与任何TauProlog相关的事情。你也可以提出功能需求，他们会非常积极地响应。 - user502187

Answer 4

在80年代和90年代，人们非常希望将并行性嵌入到编程语言中（从而使其“固有”地具备并行性），特别是在第五代计算机项目的背景下。甚至研究了特殊的硬件结构来实现“并行推理机”（PIM）（类似于“函数式编程”阵营中LISP机器的特殊硬件）。由于现成CPU的不断改进，硬件方面的努力被放弃，由于编译器复杂度过高、难以实现高级功能且可能缺乏回报，软件方面的努力也被放弃：在语言层面上看起来透明和优雅可利用的并行性通常意味着昂贵的进程间通信和事务锁定“底层”处理。

关于这个问题的一个好文章是

"《并发逻辑编程语言的退化》"

作者是Evan Tick，1994年3月。出现在“逻辑编程杂志，十周年特刊，1995年”。链接的Postscript文件是完整的，不像您在Elsevier得到的PDF文件。

作者说：

过去几年（即1990-94年），并发逻辑编程及其发展有两种主要观点。大多数逻辑编程文献将并发逻辑编程语言视为逻辑程序的派生或变体，即主要区别在于广泛使用“不关心”非确定性而不是“不知道”（回溯）非确定性。因此名称为committed choice或CC语言。第二个观点是，并发逻辑程序是并发反应程序，类似于其他“传统”的并发语言，例如具有显式消息传递的C语言，因为过程是通过数据流进行通信以逐步生成答案的进程。一个愤世嫉俗者可能会说，前一种观点具有更多的学术丰富性，而后一种观点具有更多的实际公共关系价值。

本文是并发逻辑编程语言实现技术的调查，因此这两个观点的完全披露并不特别相关。相反，对基本语言语义的快速概述以及它们与家族内各种语言的基本编程范例的关系就足够了。不会尝试涵盖许多可行的编程范例，也不会涵盖语义细微差别或家族历史。（...）

我想在本文中要表达的主要观点是，并发逻辑编程语言自它们约十年前诞生以来一直在退化，因为以下原因：

1. 系统设计师和编译器编写者只能在强大而高效的实现中提供某些有限的功能。这推动市场接受这些受限制的语言作为非正式意义上的事实标准。

2. 程序员意识到，某些更具表现力的语言特性对于编写应用程序并不是至关重要的，并且不要求将它们包含在内。

因此，我在本文中的立场将是第三个观点：最初富有的语言逐渐失去了它们的“锐气”，变得更加实用，实现速度更快。这种演化历史始于Concurrent Prolog（深层保护，原子一致性；只读注释变量用于同步），经过一系列缩减（例如：GHC（输入匹配同步），Parlog（安全），FCP（平面），Fleng（无保护），Janus（受限通信），Strand（分配而不是输出一致性）） ，现在以PCN结束（平面保护，非原子赋值输入匹配同步和明确定义的可变变量）。本文将定义这和其他术语。

这种观点可能会使一些读者不满意，因为它预设了性能是语言市场的主要驱动力；而且，并发逻辑程序相对于逻辑程序的主要“附加值”是利用并行性自然获得速度的能力。当然，语言的反应性质也增加了价值；例如，在构建复杂的面向对象应用程序时。因此，人们可以认为，当以反应能力为代价换取速度时，所见证的退化是一件坏事。

- David Tonhofer

Answer 5

通过快速的谷歌搜索，似乎并发逻辑编程范式只是一些研究语言的基础，并且不再被积极开发。我看到有人声称在Mozart/Oz系统中很容易实现并发逻辑。

- han

Answer 6

ECLiPSe-CLP是一种“与Prolog基本兼容”的语言，支持OR并行性，尽管“由于其他优先事项，目前不积极维护此功能”。

[1,2]记录了ECLiPSe-CLP中的OR-(和AND-)并行性。

然而，我曾经尝试过使用ECLiPSe-CLP存储库中的代码来使其工作，但是我没有成功。

• [1] http://eclipseclp.org/reports/book.ps.gz
• [2] http://eclipseclp.org/doc/bips/kernel/compiler/parallel-1.html

- chs