非确定性编程语言

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

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

这不会迭代List中的每个元素; 相反,它将分支到不同的"机器" (通过使用多个线程,在单个线程上回溯,创建并行Universe或者你是什么),并为每个可能的X值执行单独的执行,导致someOtherFunction(X, List)返回true!
(我不知道它是如何做到的,但这对问题并不重要)

我的问题是: 还有哪些其他非决定性编程语言？ 似乎非确定性是在具有不可变变量的语言中实现多线程的简单化和最合乎逻辑的方式,但我以前从未见过这样做 - 为什么这种技术不再流行？

Prolog实际上是确定性的 - 评估的顺序是规定的,秩序很重要.

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

非确定性是不受欢迎的,因为它使你更难以推理你的程序的结果,真正的非确定性执行(与语义相反)很难实现.

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

Dijkstra的守卫命令演算,他希望永远不会实施

并发ML,其中通信可以不确定地同步

Gerard Holzmann的Promela语言,它是模型检查器SPIN的语言

SPIN确实使用了非确定性,并在可能的情况下探索整个状态空间.

当然还有任何多线程语言非确定性的行为,如果线程不同步,但也正是这种东西是很难的原因有关,以及为什么它是如此难以实施有效的,正确的无锁的数据结构.

顺便说一句,如果您希望实现并行性,您可以通过mapHaskell等纯函数语言中的简单函数来实现相同的功能.Google MapReduce基于函数式语言是有原因的.

在维基百科的文章点大使这是一个计划衍生能力的非确定性编程.

据我所知,编程语言不这样做的主要原因是因为在确定性机器上运行非确定性程序(与所有现有计算机一样)本质上是昂贵的.基本上,非确定性图灵机可以在多项式时间内解决复杂问题,对于该问题,没有用于确定性图灵机的多项式算法.换句话说,非确定性编程无法在现有计算机的上下文中捕获算法的本质.

同样的问题会影响Prolog.任何有效的,或至少效率不高的Prolog应用程序都必须使用"cut"运算符来避免探索指数数量的路径.只要程序员对Prolog解释器如何以确定性和非常程序化的方式探索可能的路径有良好的心理观点,该算子才有效.非常程序化的东西与功能编程不能很好地混合,因为后者主要是根本不考虑程序性的努力.

作为旁注,在确定性和非确定性图灵机之间,存在"量子计算"模型.假设一个量子计算机存在,它并不能完成非确定性图灵机可以做的所有事情,但它可以做的不仅仅是确定性的图灵机.目前有人正在为量子计算机设计编程语言(假设最终将构建量子计算机).其中一些新语言功能齐全.您可以在此维基百科页面上找到许多有用的链接.显然,设计量子编程语言,无论是否有效,并使用它,都不容易,当然也不是"简单".

一种非确定性语言的示例是基于CSP理论的Occam。和构造的组合会在多处理器系统中引起不确定的行为，从而实现细粒度的并行程序。PARALT

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

^† _{的ALT结构通常与实施PRI ALT，所以你必须在公正明确的代码，如果你需要它是公平的。}

在推理和证明程序正确时，非确定性被视为不利条件，但是一旦您接受了非确定性，就可以从许多方面摆脱确定性对推理施加的许多约束。

只要通信的排序不会导致死锁（可以通过应用CSP技术来完成），那么完成操作的确切顺序就比确定是否及时获得所需结果要重要得多。

这可以说是这种缺乏确定性的这是一个主要因素，防止通过奥卡姆和晶片机在军事项目系统，通过主导阿达当时，那里知道正是一个CPU在做什么，在每一个时钟周期被认为是必要的证明一系统正确。如果没有这种限制，Occam及其运行的Transputer系统（当时唯一的CPU经过正式验证的IEEE浮点实现）将非常适合需要小规模高处理功能的硬实时军事系统空间。