非确定性编程语言

Question

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

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

This won't iterate over every element in List;相反，它会分支到不同的“机器”（通过使用多个线程、在单个线程上回溯、创建并行宇宙或其他什么），对每个可能的值进行单独的执行X 导致 someOtherFunction(X, List) 返回 true！
（我不知道它是如何做到这一点的，但这对问题来说并不重要）

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

Answer 1

Prolog 实际上是确定性的——计算的顺序是规定的，而顺序很重要。

为什么非决定论没有更流行？

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

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

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

• 并发 ML，在哪些通信可以非确定性同步

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

SPIN 实际上使用了不确定性，并在可能的情况下探索整个状态空间。

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

顺便说一句，如果您希望实现并行性，则可以通过 Haskell 等纯函数式语言中的简单 map 函数来实现相同的效果。 Google MapReduce 基于函数式语言是有原因的。

Answer 2

维基百科文章指向Amb 这是一个具有非确定性编程能力的方案衍生。

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

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

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

Answer 3

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

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

^†_{ALT 构造通常使用 PRI ALT 实现，因此，如果您需要公平地显式编码，则必须公平地进行编码。公平。}

---

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

只要通信的顺序不会导致死锁，这可以通过应用来完成如果采用 CSP 技术，那么完成工作的精确顺序应该比您是否及时获得所需的结果更重要。

可以说，这种缺乏决定论是阻碍奥卡姆和翻译机被采用的一个主要因素军事项目中的系统，当时由 Ada 主导，准确地知道什么CPU 在每个时钟周期所做的工作被认为对于证明系统正确至关重要。如果没有这种限制，Occam 及其运行的 Transputer 系统（当时唯一经过正式验证的 IEEE 浮点实现的 CPU）将非常适合需要在小型计算机中提供高级处理功能的硬实时军事系统。空间。

Answer 4

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

历史记载：

第一个并发逻辑编程语言是关系型语言
Clark 和 Gregory 的语言，它是 IC-Prolog 的一个分支。
并发逻辑编程的更高版本包括夏皮罗的
并发 Prolog 和 Ueda 的 Guarded Horn Clause 语言 GHC。
https://en.wikipedia.org/wiki/Concurrent_logic_programming

但今天我们可能会选择深入逻辑编程。 这里是一个通过线程实现 findall 的示例。还可以对其进行修改以在集合上执行各种任务，甚至可以生成面向分布式人工智能的代理网络。

Answer 5

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

Answer 6

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

Answer 7

Java 2K

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

Answer 8