如何同时进行Prolog？

Question

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

在我看来,Prolog可能是高度并发的,也许在尝试匹配规则时会立即尝试多种可能性.现代Prolog编译器/解释器本身是*并发的吗？哪个？默认情况下是并发吗？我需要以某种方式启用它吗？

*我对多线程,只是内在的并发性不感兴趣.

Answer 1

理论上看起来很有吸引力,但是有各种各样的问题使这种实施看起来不明智.

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

• 非关系语言元素(如cut操作符)只有在您可以依赖此类执行命令时才能被有意义地使用,即它们将在并行解释器中变得不可用,除非发明了非常复杂的依赖关系跟踪.

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

• Prolog通常用于高级,深度递归的问题,例如图遍历,定理证明等.现代机器上的并行化可以(理想地)实现n某些常量的加速n,但它不能将不可行的递归求解方法变为可行的一,因为这需要指数加速.相比之下,Fortran和C程序员通常解决的数值问题通常具有较高但非常有限的计算成本; 并行化的努力非常值得将10小时的工作转变为1小时的工作.相比之下,将一个可以看起来大约6个的程序转变为一个可以(平均而言)看起来向前移动的程序并不那么引人注目.

Answer 2

现代Prolog编译器/解释器本身是*并发的吗？哪个？默认情况下是并发吗？

并行逻辑编程是20世纪80年代日本第五代计算机程序的主要目标.预计Prolog变体将在大规模并行硬件上"轻松"并行化.这项工作很大程度上失败了,因为自动并发并不容易.今天,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的一个分支,它也在回溯中用于更接近函数式编程的东西.它仍然需要用户指导才能知道程序的哪些部分可以安全地同时运行.

Answer 3

Prolog中有两种并发概念.一个是多线程,另一个是暂停目标.我不确定你想知道什么.所以我将首先对多线程进行一些扩展:

今天广泛使用的Prolog系统可以区分它们是否是多线程的.在多线程Prolog系统中,您可以生成多个在同一知识库上并发运行的线程.这给咨询和动态谓词带来了一些问题,这些问题由这些Prolog系统解决.

您可以在此处找到多线程的Prolog系统列表:

操作系统和Web相关功能

多线程是各种并行化范例的先决条件.相应地,个体Prolog系统提供服务于某些范例的构造.典型的范例是线程池,例如在Web服务器中使用,或者为长期运行的GUI任务生成线程.

目前,线程库没有ISO标准,尽管有一个提议,每个Prolog系统通常都有丰富的库,提供线程同步,线程通信,线程调试和外部代码线程.Prolog系统中垃圾收集的某些进步是必要的,以允许具有潜在无限长运行线程的线程应用程序.

一些现有层甚至允许以Prolog系统独立方式的高级并行化范例.例如,Logtalk有一些映射到各种目标Prolog系统的结构.

现在让我们转向暂停的目标.从较旧的Prolog系统(自Prolog II,1982,实际上)我们知道freeze/2命令或阻塞指令.这些结构强制一个目标不被现有的子句扩展,而是放在一个睡眠列表上.目标可以后来被唤醒.由于目标的执行不是立竿见影的,而是只有在被唤醒时,暂停的目标有时被视为并发目标,但这种并行性形式的更好概念将是协同程序.

暂停目标对于实现约束求解系统很有用.在最简单的情况下,睡眠列表是一些变量属性.但约束求解系统的一种新方法是约束处理规则.在约束处理规则中,唤醒条件可以是暂停的目标对模式.可以在此处看到通过暂停目标或约束处理规则来解决约束的可用性:

Prolog系统概述

最好的祝福