非确定性编程

维基百科,自由的百科全书
跳到导航 跳到搜索

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

概述[编辑]

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

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

引用[编辑]

  1. ^ Structure and Interpretation of Computer Programs. [2022-02-02]. (原始内容存档于2022-05-15). 
  2. ^ 存档副本 (PDF). [2022-02-02]. (原始内容 (PDF)存档于2016-03-04).