Programming Languages: Application and Interpretation【譯17】【完】

校對: @lotuc

原文：PLAI 第二版

GitHub：PLAI-cn

GitBook：PLAI-cn

翻譯聲明見 Github 倉庫

17 其他調用語義

很久以前，我們討論過在執行函數調用時替換的問題。現在是時候考慮一些替代方案了。當時，我們只提出了一種方案；其實還有更多選擇。要理解這一點，請試著回答這個問題：

下列哪些是相同的？

我們將會發現，這段語法可以對應非常不同的運行時行為。比如我們提到過的區別：何時求值(current-seconds)導致的不同。另一個不同是，求值的次數有多少（也即f運行的次數）。還有一個不同，x的值是嚴格從調用者流向被調用者，還是甚至可能以相反的方向流動！

17.1 惰性調用

先來考慮參數何時規約為值。即，我們是將形參替換為實參的值呢，還是實參表達式本身？如果我們定義

(define (sq x) (* x x))

然後這樣調用

(sq (+ 2 3))

它是規約為

(* 5 5)

呢，還是

(* (+ 2 3) (+ 2 3))

？前者被稱為及早（eager）調用，後者則被稱為惰性（lazy）調用。【注釋】當然，我們不想回到使用替換模型定義解釋器，但將替換視為設計原則總是有用的。

有些人將前者稱為嚴格的（strict）。更加晦澀難解的術語將前者稱為調用次序求值（applicative-order evaluation），後者稱為正常次序求值（normal-order evaluation）。還有，前者稱為傳值調用（call-by-value），後者稱為傳名調用（call-by-name）或傳需求調用（call-by-need）。最後這兩個術語——傳名和傳需求——實際技術上有區別，我們將在後文討論。關於名字的介紹就到這裡。

17.1.1 惰性調用示例

惰性這一選擇有著輝煌的歷史（例如，純正的λ演算就用它），但是回歸編程實踐，考慮對於某些運算符，在函數調用時不對參數求值而等到需要用到參數值時才求值會出現什麼問題。例如，考慮定義

(define ones (cons 1 ones))

在標準Racket中，這顯然是有問題的：（左側的）ones還沒有完成定義，我們就（在右側）嘗試對它求值，所以這會導致錯誤。但是，如果我們直到真正需要時才對其求值，那麼這個定義就成立了。因為每次rest操作都會獲得另一個ones，我們得到了一個無窮鏈表。

我們略過了很多需要解釋的地方。cons的rest位置求值得到的是ones的副本呢，還是原表達式本身呢？換句話說，我們是簡單地創建了無限展開的鏈表，還是創建了實際上循環的鏈表？

這很大程度上取決於我們的語言是否帶有賦值。如果有賦值，那麼也許我們可以修改結果鏈表中的每個單元格，這意味著我們可以觀察上述兩個實現之間的區別：在展開版本中，修改一個first不會影響另一個，而在循環版本中，更改一個first會影響所有其他。因此，在有賦值的語言中，我們可能會傾向於惰性展開，而不是循環數據。

請記住這裡的討論。我們暫時還無法解決它；不妨再考察一下惰性求值，然後回到這個問題。

17.1.2 什麼是值？

回到之前的核心高階函數解釋器，我們記得有兩種類型的值：數和閉包。要支持惰性求值，我們要問，在函數調用中怎麼處理。究竟傳入什麼？

這似乎很明顯：在惰性調用語義中，我們需要傳入表達式。但細想就有問題了。表達式中包含標識符名稱，【注釋】而我們不希望它們被意外地綁定。

我們馬上會發現，這裡它們真的是標識符而不是變數，。

例如，假設我們有

(define (f x) (lambda (y) (+ x y)))

這樣調用它：

((f 3) (+ x 4))

思考題

這應該返回什麼？

顯然，應該得到錯誤，報告x沒有被綁定。

現在來逐步分析。第一步調用創建閉包，其中x綁定到3。如果接下來將y綁定到(+ x 4)，於是得到表達式(+ x (+ x 4))，而其環境中x是綁定的。因此我們得到答案10，而不是錯誤。

思考題

我們這裡有做什麼微妙的假設嗎？

是的，我們有：我們假定+調用時其會對各參數進行求值並都返回數。也許+也可以是惰性的；我們稍後研究這個問題。不管怎麼說，重點不變：如果我們不小心的話，這個錯誤的表達會得到某種合法的答案，而不是錯誤。

如果您認為這問題只關於錯誤的程序，因此可以專門處理（例如，先掃描程序源尋找自由標識符），下面是同一個f的另一個的用法：

(let ([x 5]) ((f 3) x))

思考題

這應該返回什麼？

正常來說這應該求得(+ 3 5)的結果（即8）。但是，如果我們在算術表達式中替換x，我們會得到(+ 3 3)。

在這個例子中。後面這個例子包含了解決方案的關鍵，只有當我們用到環境時，問題才會出現；反之如果我們使用替換，一遇到let就替換函數調用中的x，結果就符合期望。事實上，請注意，這個觀點對前一個例子也適用：如果我們使用替換，那麼x的出現就導致錯誤。簡而言之，我們必須確保基於環境的實現和基於替換的實現行為一致。聽起來熟悉不！

換種說法，解決方案是將參數表達式與其環境捆綁在一起：即創建閉包。此閉包沒有參數，所以它實際上是thunk（譯註，無參數的lambda）。【注釋】我們可以使用已有的函數來表示這裡的thunk，但是直覺告訴我們，更好的做法是為邏輯上不同的目的使用不同的數據表示：closV表示用戶創建的閉包，用另一種東西表示內部創建的閉包。事實上，正如我們將看到的那樣，將它們分開是明智的做法，因為有一個地方我們需要能將它們區分開來。

事實上，這表明函數有兩個用途：用值替換名稱，推遲替換。let只有前一個功能而沒有後一個；thunk只有後一個功能而沒有前一個。前文已經明確，前者本身是很有價值的；本節表明後者也是如此。

總結來說，現在我們新的值的集合是：

(define-type Value [numV (n : number)] [closV (arg : symbol) (body : ExprC) (env : Env)] [suspendV (body : ExprC) (env : Env)])

前兩個變體完全不變；第三個是新的，正如我們所討論的，它實際上是一個無參數的子程序，正如其類型所表明的那樣。

17.1.3 什麼導致求值？

回頭來討論算術表達式。對(+ 1 2)求值時，惰性調用的解釋器可以返回好幾種東西，包括(suspendV (+ 1 2) mt-env)。【注釋】這樣，掛起的計算可以級聯起來，在極限情況下，任何程序都會立即返回「答案」：表示掛起（suspension）計算的thunk。

這裡放上mt-env（譯註，空白環境）是合理的，因為就算(+ 1 2)表達式存在於非空的環境中，它其中也不包含自有標識符，因此不需要任何環境的綁定。

顯然，必須有什麼東西用來強制解除掛起。（當然，解除掛起的意思是，在存儲下來的環境中對主體求值。）這種解除表達式掛起狀態的位置稱為嚴格點（strictness point）。最明顯的嚴格點是互動式環境的列印，因為如果用戶使用交互環境顯然是希望看到答案。我們用strict子程序表示解除掛起：

(define (strict [v : Value]) : Value (type-case Value v [numV (n) v] [closV (a b e) v] [suspendV (b e) (strict (interp b e))]))

這裡返回的Value保證不是suspendV。我們可以假設列印程序會對被求值的表達式調用strict，以獲得要列印的值。

思考題

如果使用閉包來表示掛起的計算，後果是啥？

上面strict的定義依賴於區分延遲計算——是內部構建的閉包——與用戶定義閉包的能力。如果我們將兩者混為一談，那麼這裡就不得不去猜測如何處理零參數閉包。如果沒有進一步處理它們，我們可能會錯誤地得到報錯（例如，+可能會得到thunk而不是其中的數值）。如果進一步處理，我們可能會意外地過早調用用戶定義的thunk。總之，對於thunk我們需要一個標誌，告訴我們它們是內部的還是用戶定義的。為了清晰起見，我們的解釋器使用獨立的變體。

接下來討論strict和解釋器之間的互動。不幸的是，按我們原來的定義，這將導致無限循環。解釋加法將創建創建該計算的掛起，strict會試圖解除這個掛起，解除的方式是讓解釋器去解釋加法，而這又……顯然，我們不能簡單的讓每個表達式都掛起其計算；相反，我們只掛起函數調用。這不會使語言變得荒謬，又足以讓我們擁有惰性求值的強大力量。

17.1.4 解釋器

照例，我們將分步定義解釋器。

<lazy-interp> ::= (define (interp [expr : ExprC] [env : Env]) : Value (type-case ExprC expr <lazy-numC-case> <lazy-idC-case> <lazy-plusC/multC-case> <lazy-appC-case> <lazy-lamC-case>))

數很容易：它們已經是值了，所以沒必要掛起它們：

<lazy-numC-case> ::= [numC (n) (numV n)]

閉包同樣保持不變：

<lazy-lamC-case> ::= [lamC (a b) (closV a b env)]

標識符應該返回它們所綁定的內容：

<lazy-idC-case> ::= [idC (n) (lookup n env)]

算術表達式的參數通常被定義為嚴格點，不然的話我們會不得不在其他地方自行實現算術運算：

<lazy-plusC/multC-case> ::= [plusC (l r) (num+ (strict (interp l env)) (strict (interp r env)))] [multC (l r) (num* (strict (interp l env)) (strict (interp r env)))]

最後我們要處理函數調用。在這裡，我們不再對參數求值，而是將其掛起。然而，函數位置必須是嚴格點，否則我們不知道要調用什麼函數，也就不知道如何繼續計算：

<lazy-appC-case> ::= [appC (f a) (local ([define f-value (strict (interp f env))]) (interp (closV-body f-value) (extend-env (bind (closV-arg f-value) (suspendV a env)) (closV-env f-value))))]

這就行了！添加一種新的結果類型、插入一些strict、並在函數調用參數位置用suspendV替換interp，我們就將及早調用解釋器轉換成了惰性調用了。然而，這個小小的變化對我們編寫的程序有著巨大的影響！要更全面地了解這種影響，請學習Haskell或Racket中的#lang lazy語言。

練習

如果我們把標識符子句替換為(strict (lookup n env))（即對查找標識符的結果調用strict），會對語言產生什麼影響？請考慮更豐富的語言的情況，比如包含數據結構的情況。

練習

編寫一些程序，它們在惰性求值下會給出和及早求值不同的結果（在兩種情況下，同樣的程序給出不同的結果）。請給出有意義的差異，一個返回suspendV而另一個返回實際計算結果這種不算。比如說，一個會終止而另一個不會，或者一個會產生錯誤而另一個不會？

練習

調整兩個解釋器，讓它們記錄求得答案的步數。對於在兩種求值策略下產生相同答案的程序，一個策略是否總是比另一個需要更多步驟？

17.1.5 惰性和賦值

惰性求值的優點之一是它會延遲執行。通常這是好事：它使我們能夠構建無限的數據結構，還能避免不必要的計算。不幸的是，它也改變了計算髮生的時間，尤其是表達式求值的相對時間，這將取決於何時遇到嚴格點。結果是，程序員基本無法預測計算的順序。當表達式執行賦值操作時，這顯然是個問題，因為這種情形下預測程序計算結果非常困難（相對及早求值來說）。

這導致了，所有惰性語言的核心中都不支持賦值。在Haskell中，賦值和其他狀態操作都是通過諸如monad（單子）和arrow（箭頭）等多種機制引入的，這些機制實質上賦予我們（嚴格）順序化代碼的能力；這種順序性對於能夠預測執行順序以及操作結果至關重要。如果程序結構良好，這些依賴關係的數量應該很小；此外，Haskell類型系統試圖在類型本身中反映這些操作，因此程序員可以更輕鬆地推理其效果。

17.1.6 緩存計算結果

從已經得出的惰性計算必須不包含賦值這個結論，我們可以觀察到一個喜人的結果（能不能稱其為副作用呢？）：給定固定的環境，同一表達式總會產生相同的答案。其結果是，當表達式第一次被嚴格求值時，運行時系統可以緩存其值，並在隨後計算它時返回這個緩存值。當然，這種緩存（這是記憶化(memoization)的一種形式）只有當表達式每次返回相同的值時才成立，這正是我們所假設的。實際上，編譯器和運行時系統可以積極地在程序的不同部分中使用相同的表達式，並且如果其環境的相關部分相同，則合併求值。每當被需要時都對掛起的計算進行求值的策略稱為傳名調用；將結果緩存起來，則稱為傳需求調用。

17.2 響應式調用

來考慮這個表達式(current-seconds)。求值時，它返回一個表示當前時間的數。例如，

> (current-seconds)1353030630

但即使我們盯著執行過程，當看見這個數時它就已經過時了！它表示函數調用發生的時間，而不會一直保持為當前時間。

17.2.1 動機樣例：計時器

假設我們要實現一個計時器，記錄經過的時間。理想情況下，我們會這樣寫：

(let ([start (current-seconds)]) (- (current-seconds) start))

在JavaScript中就是：

d = new Date();start = d.getTime();current = d.getTime();elapsed = current - start;

在大多數機器上，此Racket表達式，或JavaScript中elapsed的值將被求得為0，或著某個非常小的數字。這是因為這些程序代表了經過時間的一次度量：即第二次調用獲取當前時間子程序時的時間。這樣我們拿到一個瞬間的時間片，而不是實際的計時器。

在大多數語言中，要構建真正的計時器，我們必須創建某種計時器對象的實例，然後設置回調。每當時鐘滴答時，計時器對象——代表操作系統——都會調用回調函數。然後回調負責更新系統其餘部分的值，我們期望它能全局一致地完成這個任務。但是，回調函數無法通過返回值來實現這點，因為它會返回到操作系統，而操作系統無法感知到、也不關心我們的應用程序；因此，回調只能通過賦值來執行其行為。例如在JavaScript中：

var timerID = null;var elapsedTime = 0;function doEverySecond() { elapsedTime += 1; document.getElementById(curTime).innerHTML = elapsedTime; }function startTimer() { timerId = setInterval(doEverySecond, 1000); }

假設這裡的HTML頁面id為curTime，並且onload或其他回調會調用startTimer。

要避免這種義大利面風格的代碼，一種替代方案是應用程序反覆向操作系統輪詢當前時間。然而：

• 過於頻繁地調用會浪費資源，而調用過於不頻繁則會導致錯誤的值。不過，要以恰當的頻率進行調用，我們需要先有一個計時器信號！
• 儘管可以為諸如定時器之類的常規事件創建這樣的輪詢循環，但對於諸如用戶輸入等不可預知的行為（其頻率通常不能被預測）的來說，這是不可能的。
• 除此之外，編寫這樣的循環會污染程序的結構，迫使開發人員承擔額外的負擔。

基於回調的方案體現了控制反轉（inversion of control）的思想。現在，操作系統負責調用（從而進入）應用程序，而不是應用程序調用操作系統（所提供的功能）。本應深度嵌套於顯示錶達式的內部的響應行為現在被置於頂層，其他計算將由其值驅動。這麼做的根本原因在於，對外部世界的控制權不再程序手中，因此應該由外部刺激決定程序何時運行以及如何運行，而非內部的程序表達式。

17.2.2 回調的類型是四字母單詞

這種模式的特徵（可以這麼說）體現在類型中。由於操作系統對程序的值不可知，所以回調通常沒有返回類型，或者只返回通用的狀態指示值，而不是特定於應用程序的值。因此，在靜態類型語言中，它們的類型通常是四個字母的單詞。 例如，下面是Java中某GUI庫的片段：

interface ChangeListener extends EventListener { void stateChanged(ChangeEvent e) { ... } }interface ActionListener extends EventListener { void actionPerformed(ActionEvent e) { ... } }interface MouseListener extends EventListener { void mouseClicked(MouseEvent e) { ... } void mouseEntered(MouseEvent e) { ... } }

OCaml中是這樣：

mainLoop : unit -> unitcloseTk : unit -> unitdestroy : a Widget.widget -> unitupdate : unit -> unitpack : ... -> d Widget.widget list -> unitgrid : ... -> b Widget.widget list -> unit

在Haskell中，這四個字母中包含一個額外的空格：

select :: Selecting w => Event w (IO ())mouse :: Reactive w => Event w (EventMouse -> IO ())keyboard :: Reactive w => Event w (EventKey -> IO ())resize :: Reactive w => Event w (IO ())focus :: Reactive w => Event w (Bool -> IO ())activate :: Reactive w => Event w (Bool -> IO ())

諸如此類。在所有這些情況下，類似「void」類型的存在清楚地表明這些函數不會返回任何有意義的值，所以它們唯一的目的必須是修改貯存或者具有其他副作用。這也意味著複雜的組合手段（例如表達式的嵌套）是不可能的：void類型語句唯一的組合操作是順序執行。因此這些類型表明我們將被迫放棄編寫嵌套表達式。

當然，通過我們之前對Web編程的討論，讀者應該已經熟悉這個問題。無狀態的伺服器和單線程的客戶端程序都會出現這個問題。伺服器上，我們至少還能使用continuation解決這個問題。但是，不是所有的語言都支持continuation，且實現continuation也會很繁瑣。此外，設置合適的continuation作為回調來傳遞可能會非常棘手。因此，我們將探索另一種解決方案。

17.2.3 替代方案：響應式語言

考慮DrRacket中的FrTime（發音為「Father Time」）語言。【注釋】如果我們在交互窗口中運行下面的表達式，我們仍然得到0或者非常小的正數：

(let ([start (current-seconds)]) (- (current-seconds) start))

在DrRacket v5.3中，必須從「語言/Language」菜單中選擇該語言；只寫#lang frtime不會提供想要的交互窗口行為。

事實上，我們可以嘗試其他幾種表達式，看上去FrTime似乎與傳統的Racket完全一樣。

但是，它還綁定了額外一些標識符。例如，有一個值綁定到seconds。如果我們將其輸入交互窗口的提示符，結果非常有意思！首先我們看到1353030630，然後一秒後1353030631，再一秒1353030632，諸如此類。這種值被稱為行為（behavior）：隨時間變化的值。但是我們沒有編寫任何回調或其他代碼將其值保持為當前時間。

行為可以用於計算。 例如可以這麼寫(- seconds seconds)，並且它總是計算為0。請在交互提示符中嘗試更多表達式：

(add1 seconds)(modulo seconds 10)(build-list (modulo seconds 10) identity)(build-list (add1 (modulo seconds 10)) identity)

正如你所看到的，行為是「粘性的」：如果任何子表達式是行為，包含它的表達式也是。

基於這裡的求值模型，每當seconds更新，整個應用程序重新求值：因此，即使我們寫了看似簡單的表達式，不包含任何明確的循環控制，程序仍然會「循環」。最早我們探索的調用語義，其中參數被求值一次，然後惰性求值那裡的調用語義中，參數可能被求值零次，現在這個調用語義會根據需要對參數以及與它們對應的整個函數進行多次求值。因此，表達式「內部」的響應式值不再需要被帶到「外部」；相反，它們可以內嵌在表達式中，為程序員提供更自然的表達方式。這種求值方式被稱為數據流（dataflow）或函數響應式（functional reactive）編程。

歷史上，數據流一般指的是具有一階函數的語言，而函數響應式語言還支持高階函數。

FrTime實現了我們所說的透明響應式，即程序員可以在程序求值的任意位置插入響應行為，而無需對其上下文進行任何語法修改。這麼做的優點是，現有程序中很易於加入響應式，但這也使求值模型更加複雜，成本預估更為困難。在其他語言中，程序員需要通過適當的原語明確地引入行為，不那麼方便，但可預測性更強。FrTime的姊妹語言Flapjax是JavaScript的擴展，同時支持這兩種模式。

參見Flapjax網站。

17.2.4 實現透明響應式

要使現有語言實現透明響應式，我們必須（自然地）改變函數調用的語義。分兩步來做。首先將響應式函數調用改寫成更複雜的形式，然後我們將展示這種更複雜的形式支持響應式更新。

17.2.4.1 數據流圖的構建

很容易用語法糖來解釋將函數調用變成響應性的本質。假設我們已經定義了新的構造器behavior。該構造器的接收一個表示每當參數更新時所需要進行的計算的thunk以及所有表達式所依賴的值為參數。那麼(f x y)這樣的表達式就展開為

(if (or (behavior? x) (behavior? y)) (behavior (λ () (f (current-value x) (current-value y))) x y) (f x y))

其中我們假設，如果輸入是常數而非行為，那麼current-value的行為就是恆等函數。

來看一下使用上述定義的兩個例子。考慮兩個參數都不是行為的簡單情況，例如(+ 3 4)。 去語法糖得到

(if (or (behavior? 3) (behavior? 4)) (behavior (λ () (+ (current-value 3) (current-value 4))) 3 4) (+ 3 4))

由於3和4都是數而非行為，這就規約為(+ 3 4)，正是我們想要的。這反映了一個重要的原則：當沒有行為出現時，程序的行為完全等同於與非響應式語言版本。

如果計算(+ 1 seconds)，展開為

(if (or (behavior? 1) (behavior? seconds)) (behavior (λ () (+ (current-value 1) (current-value seconds))) 1 seconds) (+ 1 seconds))

由於seconds是行為，這規約為

(behavior (λ () (+ (current-value 1) (current-value seconds))) 1 seconds)

如果其他表達式依賴於此，現在它們都會看到其參數也是行為，於是該屬性如我們之前所論證的那樣是「粘性的」。

練習

上述去語法糖是否依賴於及早求值？如果有的話，是以什麼方式？

17.2.4.2 數據流圖的更新

當然，僅僅構建行為值是不夠的。這裡關鍵的附加信息位於behavior的參數中。語言會過濾掉那些本身是行為的參數（例如前述的seconds），並將新行為註冊為依賴於現有行為的行為。這個註冊過程創建了行為表達式的依賴關係圖，稱為數據流圖(dataflow graph)（因為它反映了數據流動所需的路徑）。

如果程序求值得到的不是行為，那麼就是是答案，並且不會創建圖表。但是，如果存在行為依賴，那麼求值不會產生傳統的答案，而會產生行為值，並且會記錄其依賴。（實踐中，有必要記錄下哪些內建行為實際地被用到，以避免對程序中沒有引用到的內建行為進行求值）。總之，程序執行會生成數據流圖。因此，我們需要的不是新的、專門的語言求值器；而是要將圖構建語義嵌入到傳統求值器中。

現在可以運行數據流傳播演算法了。每當某個內建行為發生變化時，該演算法會調用其存儲的thunk，獲取新值，存儲之，然後發信號給依賴於它的所有行為。例如，如果seconds更新，它會通知對應表達式(+ 1 seconds)的行為。後者於是對其thunk求值，即(λ () (+ (current-value 1) (current-value seconds)))。這會對seconds的最新值加1，將其作為該行為的的新值——正如我們所期望的那樣。

17.2.4.3 求值順序

上面對圖更新的討論過於簡單了。考慮以下程序：

(> (add1 seconds) seconds)

這個程序里有一個內建行為，seconds，構造了兩個新行為：分別是(add1 seconds)和整個表達式。

我們期望這個表達永遠計算為真。但是，當seconds更新時，取決於處理更新的順序，可能會在更新(add1 seconds)之前更新整個表達式。假設seconds的舊值是100，所以新值是101。但是，(add1 seconds)的節點仍然存儲了其舊值（因為它尚未更新），所以它的值還是(add1 100)即101。這意味著>會比較101與1（譯註，此處應為101），得到假，於是這個表達式返回了其靜態描述不可能產生的值。這種情況被稱為毛刺（glitch）。

避免上面例子所描述的毛刺的方案很簡單（而且可以證明這麼做足夠了）。就是對節點拓撲排序。每個節點只在它所依賴的節點更新後才被處理，因此不存在查看過時或不一致的值的危險。

在圖中出現循環時問題變得難了。在這種情況下，我們需要特殊的遞歸運算元來為循環行為提供初始值。這樣做就打破了循環依賴關係，將求值簡化為已定義的過程。

關於數據流語言的求值還有很多可以討論的內容，例如條件的處理、還有離散和流式（stream-like）行為對偶的概念。 我希望你會去閱讀響應式語言的文獻，以便更多地了解這些主題。

練習

之前我們提到過一個Haskell庫。不過，公平地說，我們展示的響應式解決方案是用Haskell來闡述的，因為惰性求值更容易支持這種求值形式。

用惰性求值實現響應式。

17.3 回溯調用

同一個調用可能發生多次的另一個原因是，它是搜索樹的一部分。這類語言的調用語義試圖去滿足搜索；如果成功，則返回成功的信息，但如果失敗，則會重試調用以期成功。當然，這假定程序按照所寫的邏輯中，嘗試給定的那些選擇最終會搜索成功。因此，具有回溯調用語義的語言的核心操作是邏輯析取（disjunction，或）。出於各種原因，此類語言還支持邏輯合取（conjunction，與），其中一個原因是，實現邏輯非會有問題，所以通常的布爾代數規則並不適用。

17.3.1 通過搜索獲得滿足

使用二值目標描述回溯搜索問題比較簡單。即使只是尋找滿足命題公式的布爾變數的值，從性能的角度來也是非常有挑戰性的，並且這在各種現實世界問題中非常重要。【注釋1】然而，我們只討論這個問題的簡化版本，只使用布爾常量而非變數，這樣我們只需要確定公式的真實性就可以了。不那麼有趣，但它會有助於我們理解一般的、實際上有趣的情況。【注釋2】

參見「SAT求解器」的眾多用途。

對於這種特殊情況，制定真值表就可以了，但對一般情況這不起作用。

假設我們的輸入是包含析取、合取和表示真假的常量的公式。目標是判定公式本身求值為真還是假。我們希望盡量減少計算量，當發現答案——無論哪一個——我們都希望儘快將其返回到依賴於它的上下文。例如，如果在計算某個合取過程中發現某個項為假，我們希望整個（合取）項立即得假——條件表達式求值中的短路求值概念。而且，我們也希望這種做法能泛化到調用堆棧中：如果子表達式求得真或假，並且這可以決定包含表達式的值了，那麼它也應該快速地「通知所在堆棧」。

因此，一般來說，每個計算都應該再帶兩個容器參數：一個用來報告當前項為真（如果發現是真），另一個報告當前項為假（如果發現是假）。為了避免未決函數調用等問題的複雜性，我們還將限定兩個參數的值都為continuation，這樣該值能儘快地回到正確的上下文中，而不用對中間那些不會影響到結果的部分進行求值。

這些continuation目前沒有太多有意思的值可以傳遞：給它的唯一參數也是我們能獲取到的唯一信息（一比特的信息，代表真或假）。因為默認情況下continuation需要有一參數，我們將提供一個符號表示知道的內容。

最容易的值是真和假本身。之前說過，所有表達式都會讀入兩個continuation，稱為成功和失敗continuation，如果式子具有明確的值，則調用其中一個。因此，真值調用成功continuation，而假值調用失敗的那個：

(define (truth t1 t2) (t1 yes))(define (falsity t1 t2) (t2 no))

現在我們來討論析取。為了簡單起見，我們將討論其雙目版本。和所有計算一樣，兩個回溯搜索的析取必須接受成功和失敗continuation。

<try-or-bt> ::= (define (try-or t1 t2) (lambda (success failure) <try-or-bt-body>))

從概念上講，最簡單的方式是創建兩個局部continuation，稱之為pass和fail，並傳遞給t1求值。如果t1（或者遞歸地，它的某個子計算）成功，控制將返回到創建pass的上下文；如果失敗，則返回到fail。

如果控制返回到pass，我們就知道第一個子表達式成功了。但是因為對於析取，這就夠了，所以我們現在可以將控制交給continuation success。因此任何對pass的調用都應該立即觸發success。

反之，假設t1失敗。那我們應該試試t2。因此fail應被定義在序列操作中，接下來要嘗試t2；如果t1成功，控制將不會以這種方式返回。接下來嘗試t2時，不必擔心pass和fail：在t1失敗後，整個析取的成功和失敗等同於t2（尾位置的一種形式）的成功和失敗，因此它的成功和失敗continuation與整個表達式的相同。於是，我們獲得：

<try-or-bt-body> ::= (success (let/cc pass (begin (let/cc fail (t1 pass fail)) (t2 success failure))))

因此，如果t1成功，則控制返回到創建pass的上下文，即調用success。如果t1成功（譯註，應為失敗），則控制返回到創建fail的continuation，也就是序列中的下一個語句，t2。

根據對稱推理，我們可以得到對偶的try-and程序：

(define (try-and t1 t2) (lambda (success failure) (failure (let/cc fail (begin (let/cc pass (t1 pass fail)) (t2 success failure))))))

為了方便測試，我們可以編寫封裝函數，將這些基於continuation的回復轉換為簡單的值：

(define (run t) (let/cc escape (t (lambda (v) (escape yes)) (lambda (v) (escape no)))))

然後以此創建測試案例，從

(test (run (try-or falsity falsity)) no)

到

(test (run (try-or (try-and (try-or falsity truth) (try-or truth falsity)) (try-and truth (try-and falsity truth)))) yes)

推薦閱讀：