非确定性程序设计语言

Question

我知道在Prolog里你可以做这样的事情

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

这将不会迭代列表中的每个元素；相反，它将分支到不同的“机器”(通过使用多个线程，在单个线程上进行回溯，创建并行宇宙或其他什么)，对每个可能的X值单独执行，从而使返回true!。

(我不知道它是如何做到的，但这对问题并不重要)

我的问题是：还有什么其他的非确定性编程语言？(非确定性)似乎是在一种具有不可变变量的语言中实现多线程的最简单和最合理的方法，但我以前从未见过这样做--，为什么这种技术不流行？。

Answer 1

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

为什么非决定论不更受欢迎？

非确定性是不受欢迎的，因为它使得对程序结果的推理变得更加困难，而真正的非确定性执行(相对于语义)很难实现。

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

• Dijkstra对受保护的命令的计算，他不想被实现
• 并发ML，其中通信可以不确定地同步。
• Gerard Holzmann的Promela语言，它是模型检查器SPIN的语言

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

当然，如果线程不同步，任何多线程语言的行为都是不确定的，但这正是很难推理的事情，也是为什么实现高效、正确的无锁数据结构如此困难的原因。

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

Answer 2

维基百科文章指出安姆是一种具有非确定性规划能力的方案导数.

据我所知，编程语言不这么做的主要原因是，在确定性机器上运行非确定性程序(就像所有现有计算机一样)本身就很昂贵。基本上，非确定性图灵机可以在多项式时间内求解复杂问题，而对于确定性图灵机则不知道多项式算法。换句话说，非确定性编程无法在现有计算机的上下文中捕捉到算法的本质。

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

顺便提一下，在确定性和非确定性图灵机之间，存在着“量子计算”模型。假设一个量子计算机存在，它不会做一个非确定性图灵机能做的所有事情，但它可以做的比一个确定性图灵机更多。有些人目前正在为量子计算机设计编程语言(假设量子计算机最终将被建造)。这些新语言中有一些是可以使用的。您可能会在这个维基百科页面上找到许多有用的链接。显然，无论函数式还是非函数式，设计一种量子编程语言并不容易，当然也不是“简单”的。

Answer 3

在Prolog中，您可以同时具有非确定性和并发性。非决定论是您在有关示例代码的问题中描述的。可以想象，Prolog子句中充满了隐式安姆语句。很少有人知道并发性也是由逻辑编程支持的。

历史告诉我们：

第一种并发逻辑编程语言是Clark和Gregory的关系语言，它是IC的一个分支.后来版本的并发逻辑编程包括Shapiro的并发Prolog和Ueda的守护角条款语言GHC。编程

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