非確定性編程

非確定性編程，是一種編程范型，它可以在程序的特定點（叫做選擇點）上，指定各種可交替的程序流程。不像if…then語句，在這些交替者（alternative）的之間選擇的方法，不能直接由編程者來指定；程序必須通過應用到所有選擇點上的某種通用方法，在運行時間於這些交替者之間做出決定。編程者指定有限數目的交替者，而程序此後必須在它們之間做出選擇，（事實上「Choose」是非確定性算子的典型名字）。可以形成選擇點的一個層級，具有著高層選擇引出的包含其中低層選擇的諸分支。

概述

選擇的一種方法，體現為回溯系統（比如Amb，或Prolog中的合一），其中一些交替者可能「失敗」，導致程序回溯並嘗試其他交替者。如果所有交替者在一個特定選擇點上都失敗了，則整個分支失敗，程序將進一步回溯到一個更早的選擇。一種複雜的問題是，由於任何選擇都是試探性的而可以被重做，系統必須能夠通過撤銷執行一個最終失敗了的分支所導致的副作用，恢復早先的程序狀態。

選擇的另一種方法是強化學習，體現在系統如Alisp中。在這種系統中，不做回溯，系統跟蹤某種對成功的衡量，並學習在哪種條件下（可以影響選擇的內部程序狀態和環境輸入二者），哪種選擇經常導致成功。這些系統適合於應用到機器人和一些其他領域，其中回溯會涉及到，所嘗試撤銷的行動是在動態環境中進行的，而這將是困難或不實際的。