非確定性編程

非確定性編程,是一種編程范型,它可以在程序的特定點(叫做選擇點)上,指定各種可交替的程序流程。不像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).