23

我知道在 Prolog 你可以做类似的事情

someFunction(List) :- 
    someOtherFunction(X, List)
    doSomethingWith(X)
    % and so on

这不会遍历 List 中的每个元素；相反，它将分支到不同的“机器” （通过使用多个线程，在单个线程上回溯，创建并行宇宙或你有什么），并为每个可能的 X 值单独执行导致someOtherFunction(X, List)返回 true！
（我不知道它是如何做到的，但这对问题并不重要）

我的问题是： 还有哪些其他非确定性编程语言？ 似乎非确定性是在具有不可变变量的语言中实现多线程的最简单和最合乎逻辑的方法，但我以前从未见过这样做 -为什么这种技术不更受欢迎？

4

8 回答 8

21

Prolog 实际上是确定性的——评估的顺序是规定的，顺序很重要。

为什么非确定性不更受欢迎？

非确定性是不受欢迎的，因为它使您更难推理程序的结果，并且真正的非确定性执行（与语义相反）难以实现。

我知道的唯一非确定性语言是

  • Dijkstra 的受保护命令演算，他希望永远不会实施

  • 并发 ML，其中通信可能以非确定性方式同步

  • Gerard Holzmann 的 Promela 语言，这是模型检查器 SPIN 的语言

SPIN 确实使用了不确定性，并尽可能探索整个状态空间。

当然，如果线程不同步，任何多线程语言的行为都是不确定的，但这正是难以解释的事情——以及为什么很难实现高效、正确的无锁数据结构。

map顺便说一句，如果您希望实现并行性，您可以通过使用像 Haskell 这样的纯函数式语言的简单函数来实现相同的目标。Google MapReduce 基于函数式语言是有原因的。

于 2010-02-02T15:55:08.610 回答
5

Wikipedia 文章指向Amb，它是具有非确定性编程能力的 Scheme 衍生物。

据我了解，编程语言不这样做的主要原因是因为在确定性机器（就像所有现有计算机一样）上运行非确定性程序本质上是昂贵的。基本上，非确定性图灵机可以在多项式时间内解决复杂问题，而确定性图灵机的多项式算法尚不为人所知。换句话说，非确定性编程无法在现有计算机的上下文中捕捉算法的本质。

同样的问题也会影响 Prolog。任何高效的，或者至少不是非常低效的 Prolog 应用程序都必须使用“cut”运算符来避免探索指数数量的路径。该运算符只有在程序员对 Prolog 解释器如何以确定性和非常程序化的方式探索可能的路径有良好的头脑时才起作用。非常程序化的东西不能与函数式编程很好地混合，因为后者主要是一种根本不按程序思考的努力。

作为旁注，在确定性和非确定性图灵机之间，存在“量子计算”模型。假设量子计算机存在，它不会做非确定性图灵机能做的所有事情，但它比确定性图灵机能做的更多。有人目前正​​在为量子计算机设计编程语言（假设最终将建造一台量子计算机）。其中一些新语言是功能性的。您可以在此Wikipedia 页面上找到许多有用的链接。显然，设计一种量子编程语言，无论是否具有功能性，并使用它，并不容易，当然也不“简单”。

于 2010-02-02T16:37:38.460 回答
5

非确定性语言的一个例子是Occam，它基于CSP理论。PAR和结构的组合ALT可以在多处理器系统中产生不确定的行为，实现细粒度并行程序。

当使用软通道时，即同一处理器上的进程之间的通道，实现ALT将使行为接近确定性†，但是一旦您开始使用硬通道（物理的处理器外通信链接），任何确定性的幻觉都会消失。预计不同的远程处理器不会以任何方式同步，它们甚至可能没有相同的内核或时钟速度。

†该ALT结构通常使用 a 来实现PRI ALT，因此如果您需要它是公平的，则必须明确地公平编码。

在推理和证明程序正确时，非确定性被视为劣势，但在许多方面，一旦你接受了它，你就摆脱了确定性对推理施加的许多限制。

只要通信的顺序不会导致死锁（这可以通过应用 CSP 技术来完成），那么完成事情的精确顺序应该比您是否及时获得想要的结果重要得多。

可以说，这种缺乏确定性是阻止在当时由Ada主导的军事项目中采用 Occam 和Transputer系统的一个主要因素，在该项目中，准确地知道 CPU 在每个时钟周期做什么被认为是证明系统正确。如果没有这个限制，Occam 和运行它的 Transputer 系统（当时唯一具有正式证明的 IEEE 浮点实现的 CPU）将非常适合需要高水平处理功能的硬实时军事系统。空间。

于 2011-11-09T18:52:24.580 回答
4

在 Prolog 中，您可以同时具有非确定性和并发性。非确定性是您在有关示例代码的问题中所描述的。你可以想象一个 Prolog 子句充满了隐含的amb语句。鲜为人知的是，逻辑编程也支持并发。

历史说：

第一个并发逻辑编程语言是克拉克和格雷戈里的关系语言，它是 IC-Prolog 的一个分支。更高版本的并发逻辑编程包括 Shapiro 的 Concurrent Prolog 和 Ueda 的 Guarded Horn Clause 语言 GHC。 https://en.wikipedia.org/wiki/Concurrent_logic_programming

但是今天我们可能只是在逻辑编程中进行操作。这是一个通过线程实现 findall 的示例。这也可以修改为在集合上执行各种任务，甚至可以生成面向分布式人工智能的代理网络。

于 2016-07-01T19:53:38.197 回答
1

我相信 Haskell 有能力构建和非确定性机器。Haskell 起初看起来对于实际使用来说过于困难和抽象，但它实际上非常强大。

于 2010-02-02T15:57:48.867 回答
1

Java 2K

注意：在您单击链接并感到失望之前：这是一种深奥的语言，与并行性无关。

于 2010-02-02T16:18:43.443 回答
1

有一种用于非确定性问题的编程语言，称为“控制网络编程”。如果您想了解更多信息，请访问http://controlnetworkprogramming.com。该站点仍在进行中，但您可以阅读有关它的一些信息。

于 2010-09-30T13:55:55.260 回答
1

IBM Research 正在开发的Sly编程语言试图将多线程执行中固有的非确定性包含在某些类型算法的执行中。不过，看起来这是一项正在进行中的工作。

于 2014-03-02T05:00:49.070 回答