非确定性编程

非确定性编程，是一种编程范型，它可以在程序的特定点（叫做选择点）上，指定各种可交替的程序流程。不像if…then语句，在这些交替者（alternative）的之间选择的方法，不能直接由编程者来指定；程序必须通过应用到所有选择点上的某种通用方法，在运行时间于这些交替者之间做出决定。编程者指定有限数目的交替者（英语：Alternation (formal language theory)），而程序此后必须在它们之间做出选择，（事实上“Choose”是非确定性算子的典型名字）。可以形成选择点的一个层级，具有着高层选择引出的包含其中低层选择的诸分支。

概述

选择的一种方法，体现为回溯系统（比如Amb^[1]，或Prolog中的合一），其中一些交替者可能“失败”，导致程序回溯并尝试其他交替者。如果所有交替者在一个特定选择点上都失败了，则整个分支失败，程序将进一步回溯到一个更早的选择。一种复杂的问题是，由于任何选择都是试探性的而可以被重做，系统必须能够通过撤销执行一个最终失败了的分支所导致的副作用，恢复早先的程序状态。

选择的另一种方法是强化学习，体现在系统如Alisp中^[2]。在这种系统中，不做回溯，系统跟踪某种对成功的衡量，并学习在哪种条件下（可以影响选择的内部程序状态和环境输入二者），哪种选择经常导致成功。这些系统适合于应用到机器人和一些其他领域，其中回溯会涉及到，所尝试撤销的行动是在动态环境中进行的，而这将是困难或不实际的。