17 其他调用语义

很久以前，我们讨论过在执行函数调用时替换的问题。现在是时候考虑一些替代方案了。当时，我们只提出了一种方案；其实还有更多选择。要理解这一点，请试着回答这个问题：

下列哪些是相同的？

• (f x (current-seconds))
• (f x (current-seconds))
• (f x (current-seconds))
• (f x (current-seconds))

我们将会发现，这段语法可以对应非常不同的运行时行为。比如我们提到过的区别：何时求值(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 -> unit
closeTk : unit -> unit

destroy : 'a Widget.widget -> unit
update : unit -> unit

pack : ... -> 'd Widget.widget list -> unit
grid : ... -> '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)