NUS CS1101S：SICP JavaScript 描述：四、元语言抽象（3）-阿里云开发者社区

NUS CS1101S：SICP JavaScript 描述：四、元语言抽象（2）https://developer.aliyun.com/article/1427734

练习 4.25

假设我们向惰性求值器输入以下声明：

let count = 0;
function id(x) {
    count = count + 1;
    return x;
}

给出以下交互序列中的缺失值，并解释你的答案。

const w = id(id(10));

左求值输入：

count;

左求值值：

〈response〉

左求值输入：

w;

左求值值：

〈response〉

左求值输入：

count;

左求值值：

〈response〉

练习 4.26

函数evaluate在将函数表达式传递给apply之前使用actual_value而不是evaluate来求值函数表达式，以强制函数表达式的值。给出一个演示这种强制需求的示例。

练习 4.27

展示一个程序，你期望它在没有记忆的情况下运行得比有记忆的情况慢得多。另外，考虑以下交互，其中id函数的定义如练习 4.25 中所述，count从 0 开始：

function square(x) {
    return x * x;
}

左求值输入：

square(id(10));

左求值值：

〈response〉

左求值输入：

count;

左求值值：

〈response〉

给出求值器记忆和不记忆时的响应。

练习 4.28

改过自新的 C 程序员赛·D·费克特担心一些副作用可能永远不会发生，因为惰性求值器不会强制序列中的语句。由于序列中语句的值可能不会被使用（语句可能只是为了其效果而存在，例如赋值给变量或打印），因此可能没有后续使用这个值的情况（例如作为原始函数的参数），这将导致它被强制。因此，赛认为在求值序列时，我们必须强制序列中的所有语句。他建议修改 4.1.1 节中的evaluate_sequence，以使用actual_value而不是evaluate：

function eval_sequence(stmts, env) {
    if (is_empty_sequence(stmts)) {
        return undefined;
    } else if (is_last_statement(stmts)) {
        return actual_value(first_statement(stmts), env);
    } else {
        const first_stmt_value =
            actual_value(first_statement(stmts), env);
        if (is_return_value(first_stmt_value)) {
            return first_stmt_value;
        } else {
            return eval_sequence(rest_statements(stmts), env);
        }
    }
}

本·比特迪德尔认为赛伊是错误的。他向赛伊展示了练习 2.23 中描述的for_each函数，这给出了一个具有副作用的序列的重要示例：

function for_each(fun, items) {
    if (is_null(items)){
        return "done";
    } else {
        fun(head(items));
        for_each(fun, tail(items));
    }
}

他声称文本中的求值者（具有原始的eval_sequence）正确处理了这一点：

L-evaluate input:
for_each(display, list(57, 321, 88));
57
321
88
L-evaluate value:
"done"

解释为什么 Ben 对for_each的行为是正确的。
b. Cy 同意 Ben 关于for_each示例的观点，但说这不是他在提出对eval_sequence的更改时考虑的程序类型。他在惰性求值器中声明了以下两个函数：

function f1(x) {
    x = pair(x, list(2));
    return x;
}
function f2(x) {
    function f(e) { 
        e;
        return x;
    }
    return f(x = pair(x, list(2)));
}

原始eval_sequence的f1(1)和f2(1)的值是多少？Cy 对eval_sequence的建议更改后的值会是多少？
c. Cy 还指出，按照他的建议更改eval_sequence不会影响部分 a 中示例的行为。解释为什么这是真的。
d. 你认为序列在惰性求值器中应该如何处理？你喜欢 Cy 的方法，文本中的方法，还是其他方法？

练习 4.29

本节中采用的方法有些不愉快，因为它对 JavaScript 进行了不兼容的更改。实现惰性求值作为向上兼容的扩展可能更好，即普通 JavaScript 程序将像以前一样工作。我们可以通过在函数声明内部引入可选参数声明作为新的语法形式来实现这一点，以让用户控制参数是否延迟。顺便说一句，我们可能也可以让用户选择是否延迟记忆。例如，声明

function f(a, b, c, d) {
    parameters("strict", "lazy", "strict", "lazy_memo");
    ...
}

将f定义为一个四个参数的函数，其中在调用函数时会求值第一个和第三个参数，第二个参数会延迟，第四个参数既延迟又被记忆。您可以假设参数声明始终是函数声明体中的第一条语句，如果省略了参数声明，则所有参数都是严格的。因此，普通函数声明将产生与普通 JavaScript 相同的行为，而在每个复合函数的每个参数上添加"lazy_memo"声明将产生本节中定义的惰性求值器的行为。设计并实现所需的更改以产生 JavaScript 的这种扩展。parse函数将参数声明视为函数应用程序，因此您需要修改apply以分派到新的语法形式的实现。您还必须安排evaluate或apply确定何时延迟参数，并相应地强制或延迟参数，并且必须安排强制记忆或不适当。

4.2.3 流作为惰性列表

在 3.5.1 节中，我们展示了如何将流实现为延迟列表。我们使用 lambda 表达式构造了一个“承诺”来计算流的尾部，而不是在以后实际实现该承诺。我们被迫创建流作为一种新的数据对象，类似但不完全相同于列表，这要求我们重新实现许多用于流的普通列表操作（map，append等）。

使用惰性求值，流和列表可以是相同的，因此不需要单独的列表和流操作。我们需要做的就是安排pair是非严格的。实现这一点的一种方法是将惰性求值器扩展为允许非严格的原语，并将pair实现为其中之一。一个更简单的方法是回想一下（第 2.1.3 节）根本没有必要将pair实现为原语。相反，我们可以将对偶表示为函数：³⁶

function pair(x, y) {
    return m => m(x, y);
}
function head(z) {
    return z((p, q) => p);
}
function tail(z) {
    return z((p, q) => q);
}

根据这些基本操作，列表操作的标准定义将适用于无限列表（流）以及有限列表，并且流操作可以实现为列表操作。以下是一些示例：

function list_ref(items, n) {
    return n === 0
           ? head(items)
           : list_ref(tail(items), n - 1);
}
function map(fun, items) {
    return is_null(items)
           ? null
           : pair(fun(head(items)),
                  map(fun, tail(items)));
}
function scale_list(items, factor) {
    return map(x => x * factor, items);
}
function add_lists(list1, list2) {
    return is_null(list1)
           ? list2
           : is_null(list2)
           ? list1
           : pair(head(list1) + head(list2),
                  add_lists(tail(list1), tail(list2)));
}
const ones = pair(1, ones);
const integers = pair(1, add_lists(ones, integers));

左求值输入：

list_ref(integers, 17);

左求值值：

请注意，这些懒惰列表甚至比第 3 章的流更懒惰：列表的头部和尾部都被延迟。事实上，甚至访问懒惰对的head或tail也不需要强制列表元素的值。只有在真正需要时才会强制该值，例如用作原语的参数，或者作为答案打印时。

懒惰的对也有助于在第 3.5.4 节中出现的流的问题，我们发现，构建具有循环的系统的流模型可能需要我们在程序中添加额外的 lambda 表达式来延迟，除了构造流对所需的 lambda 表达式。通过惰性求值，所有函数的参数都被统一延迟。例如，我们可以按照我们在第 3.5.4 节最初打算的方式实现函数来集成列表和解决微分方程：

function integral(integrand, initial_value, dt) {
    const int = pair(initial_value,
                     add_lists(scale_list(integrand, dt),
                               int));
    return int;
}
function solve(f, y0, dt) {
    const y = integral(dy, y0, dt);
    const dy = map(f, y);
    return y;
}

左求值输入：

list_ref(solve(x => x, 1, 0.001), 1000);

左求值值：

2.716924

练习 4.30

给出一些例子，说明第 3 章的流和本节中描述的“更懒惰”的惰性列表之间的区别。你如何利用这种额外的懒惰？

练习 4.31

Ben Bitdiddle 通过求值表达式来测试上述懒惰列表的实现

head(list("a", "b", "c"));

令他惊讶的是，这产生了一个错误。经过一番思考，他意识到从原始list函数获得的“列表”与新定义的pair、head和tail操作的列表是不同的。修改求值器，使得在驱动循环中键入原始list函数的应用程序将产生真正的惰性列表。

练习 4.32

修改求值器的驱动循环，以便懒惰的对和列表以某种合理的方式打印出来。（你打算如何处理无限列表？）你可能还需要修改懒惰对的表示，以便求值器能够识别它们以便打印它们。

4.3 非确定性计算

在本节中，我们通过将支持自动搜索的功能内置到求值器中，扩展 JavaScript 求值器以支持一种称为非确定性计算的编程范式。这对于语言的改变比第 4.2 节中引入的惰性求值更为深刻。

非确定性计算，如流处理，对于“生成和测试”应用程序非常有用。考虑从两个正整数列表开始，并找到一对整数，一个来自第一个列表，一个来自第二个列表，它们的和是素数的任务。我们在第 2.2.3 节中看到了如何处理这个问题，并在第 3.5.3 节中使用无限流。我们的方法是生成所有可能的对的序列，并过滤这些对以选择其和为素数的对。无论我们是否像在第 2 章中那样实际生成整个对序列，还是像在第 3 章中那样交替生成和过滤，对于计算组织的基本形象来说都是无关紧要的。

非确定性方法唤起了不同的形象。想象一下，我们简单地选择（以某种方式）从第一个列表中选择一个数字，从第二个列表中选择一个数字，并要求（使用某种机制）它们的和是素数。这由以下函数表示：

function prime_sum_pair(list1, list2) {
    const a = an_element_of(list1);
    const b = an_element_of(list2);
    require(is_prime(a + b));
    return list(a, b);
}

这个函数似乎只是重新陈述了问题，而不是指定了解决问题的方法。尽管如此，这是一个合法的非确定性程序。

关键思想在于非确定性语言中的组件可以有多个可能的值。例如，an_element_of可能返回给定列表的任何元素。我们的非确定性程序求值器将通过自动选择一个可能的值并跟踪选择来工作。如果后续要求不满足，求值器将尝试不同的选择，并将不断尝试新的选择，直到求值成功，或者直到我们用尽了选择。就像惰性求值器使程序员摆脱了值如何延迟和强制的细节一样，非确定性程序求值器将使程序员摆脱选择如何进行的细节。

对比非确定性求值和流处理所唤起的不同时间形象是有启发性的。流处理使用惰性求值来解耦可能答案流被组装的时间和实际流元素产生的时间。求值器支持这样一个错觉，即所有可能的答案都以一个无时间的序列摆在我们面前。而非确定性求值中，一个组件代表了一组可能世界的探索，每个世界由一组选择确定。一些可能的世界导致了死胡同，而另一些则有有用的值。非确定性程序求值器支持这样一个错觉，即时间分支，我们的程序有不同的可能执行历史。当我们遇到死胡同时，我们可以重新访问之前的选择点，并沿着不同的分支继续。

下面实现的非确定性程序求值器称为amb求值器，因为它基于一个称为amb的新的语法形式。我们可以在amb求值器驱动循环中键入prime_sum_pair的上述声明（以及is_prime、an_element_of和require的声明），并按如下方式运行该函数：

amb-求值输入：

prime_sum_pair(list(1, 3, 5, 8), list(20, 35, 110));

开始一个新问题

amb-求值值：

[3, [20, null]]

返回的值是在求值器重复选择每个列表中的元素，直到成功选择之后获得的。

第 4.3.1 节介绍了amb并解释了它如何通过求值器的自动搜索机制支持非确定性。第 4.3.2 节介绍了非确定性程序的示例，第 4.3.3 节详细介绍了如何通过修改普通 JavaScript 求值器来实现amb求值器。

4.3.1 搜索和`amb`

为了支持非确定性，我们引入了一个称为amb的新的语法形式。表达式amb(``e[1], e[2], ... , e[n]``)以“模棱两可”的方式返回n个表达式e[i]中的一个值。例如，表达式

list(amb(1, 2, 3), amb("a", "b"));

可以有六个可能的值：

list(1, "a") list(1, "b") list(2, "a")
list(2, "b") list(3, "a") list(3, "b")

一个带有单个选择的amb表达式会产生一个普通（单个）值。

没有选择的amb表达式——表达式amb()——是一个没有可接受值的表达式。在操作上，我们可以将amb()看作是一个导致计算“失败”的表达式：计算中止，不产生值。利用这个想法，我们可以表达一个特定的谓词表达式p必须为真的要求如下：

function require(p) {
    if (! p) {
        amb();
    } else {}
}

使用amb和require，我们可以实现上面使用的an_element_of函数：

function an_element_of(items) {
    require(! is_null(items));
    return amb(head(items), an_element_of(tail(items)));
}

如果列表为空，则an_element_of的应用将失败。否则，它会模棱两可地返回列表的第一个元素或从列表的其余部分中选择的一个元素。

我们还可以表示无限范围的选择。以下函数可能返回大于或等于给定n的任何整数：

function an_integer_starting_from(n) {
    return amb(n, an_integer_starting_from(n + 1));
}

这类似于第 3.5.2 节中描述的integers_starting_from流函数，但有一个重要的区别：流函数返回一个表示以n开头的所有整数序列的对象，而amb函数返回一个单个整数。

抽象地说，我们可以想象求值amb表达式会导致时间分成分支，其中计算在每个分支上继续，使用表达式的可能值之一。我们说amb代表一个非确定性选择点。如果我们有一台具有足够多动态分配的处理器的机器，我们可以以直接的方式实现搜索。执行将继续进行，就像在顺序机器中一样，直到遇到amb表达式。在这一点上，将分配更多的处理器，并初始化以继续选择所暗示的所有并行执行。每个处理器将按顺序进行，就好像它是唯一的选择，直到它通过遇到失败而终止，或者进一步细分，或者完成。⁴¹

另一方面，如果我们有一台只能执行一个进程（或几个并发进程）的机器，我们必须按顺序考虑各种选择。人们可以想象修改求值器，在遇到选择点时随机选择一个分支进行跟踪。然而，随机选择很容易导致失败的值。我们可以尝试一遍又一遍地运行求值器，做出随机选择，并希望找到一个非失败的值，但更好的方法是系统地搜索所有可能的执行路径。我们将在本节中开发和使用的amb求值器实现了以下系统搜索：当求值器遇到amb的应用时，它最初选择第一个备选方案。这个选择本身可能导致进一步的选择。求值器总是在每个选择点最初选择第一个备选方案。如果一个选择导致失败，那么求值器会自动地⁴² 回溯到最近的选择点，并尝试下一个备选方案。如果在任何选择点用完备选方案，求值器将回到上一个选择点并从那里继续。这个过程导致了一种被称为深度优先搜索或按时间顺序回溯的搜索策略。⁴³

驱动循环

amb求值器的驱动循环具有一些不寻常的特性。它读取一个程序，并打印第一个非失败执行的值，就像上面显示的prime_sum_pair示例一样。如果我们想要看到下一个成功执行的值，我们可以要求解释器回溯并尝试生成第二个非失败执行。这是通过输入retry来表示的。如果给出除retry之外的任何其他输入，解释器将开始一个新问题，丢弃上一个问题中未探索的备选方案。以下是一个示例交互：

amb-求值输入：

prime_sum_pair(list(1, 3, 5, 8), list(20, 35, 110));

开始一个新问题

amb-求值值：

[3, [20, null]]

amb-求值输入：

retry

amb-求值值：

[3, [110, null]]

amb-求值输入：

retry

amb-求值值：

[8, [35, null]]

amb-求值输入：

retry

没有更多的值

prime_sum_pair([1, [3, [5, [8, null]]]], [20, [35, [110, null]]])

amb-求值输入：

prime_sum_pair(list(19, 27, 30), list(11, 36, 58));

开始一个新问题

amb-求值值：

[30, [11, null]]

练习 4.33

编写一个名为an_integer_between的函数，该函数返回给定边界之间的整数。这可以用来实现一个函数，找到勾股数三元组，即在给定边界之间的整数三元组（i，j，k），使得i ≤ j和i² + j² = k²，如下所示：

function a_pythogorean_triple_between(low, high) {
    const i = an_integer_between(low, high);
    const j = an_integer_between(i, high);
    const k = an_integer_between(j, high);
    require(i * i + j * j === k * k);
    return list(i, j, k);
}

练习 4.34

练习 3.69 讨论了如何生成所有勾股数三元组的流，对要搜索的整数大小没有上限。解释为什么在练习 4.33 中的函数中简单地将an_integer_between替换为an_integer_starting_from不是生成任意勾股数三元组的充分方式。编写一个实际可以实现这一点的函数。（也就是说，编写一个函数，重复输入retry理论上最终会生成所有的勾股数三元组。）

练习 4.35

Ben Bitdiddle 声称生成勾股数的以下方法比练习 4.33 中的方法更有效。他正确吗？（提示：考虑必须探索的可能性数量。）

function a_pythagorean_triple_between(low, high) {
    const i = an_integer_between(low, high);
    const hsq = high * high;
    const j = an_integer_between(i, high);
    const ksq = i * i + j * j;
    require(hsq >= ksq);
    const k = math_sqrt(ksq);
    require(is_integer(k));
    return list(i, j, k);
}

4.3.2 非确定性程序的示例

第 4.3.3 节描述了amb求值器的实现。然而，我们首先给出一些它的使用示例。非确定性编程的优势在于我们可以抑制搜索是如何进行的细节，从而以更高的抽象级别表达我们的程序。

逻辑谜题

以下谜题（改编自 Dinesman 1968）是一个典型的简单逻辑谜题：

软件公司 Gargle 正在扩张，Alyssa、Ben、Cy、Lem 和 Louis 将搬进新大楼的一排五个私人办公室。Alyssa 不会搬进最后一个办公室。Ben 不会搬进第一个办公室。Cy 既不搬进第一个办公室，也不搬进最后一个办公室。Lem 搬进比 Ben 晚的一个办公室。Louis 的办公室不会在 Cy 的旁边。Cy 的办公室也不会在 Ben 的旁边。谁搬进哪个办公室？

我们可以通过列举所有可能性并施加给定的限制来直接确定谁搬进哪个办公室：⁴⁴

function office_move() {
    const alyssa = amb(1, 2, 3, 4, 5);
    const ben = amb(1, 2, 3, 4, 5);
    const cy = amb(1, 2, 3, 4, 5);
    const lem = amb(1, 2, 3, 4, 5);
    const louis = amb(1, 2, 3, 4, 5);
    require(distinct(list(alyssa, ben, cy, lem, louis)));
    require(alyssa !== 5);
    require(ben !== 1);
    require(cy !== 5);
    require(cy !== 1);
    require(lem > ben);
    require(math_abs(louis - cy) !== 1);
    require(math_abs(cy - ben) !== 1);
    return list(list("alyssa", alyssa),
                list("ben", ben),
                list("cy", cy),
                list("lem", lem),
                list("louis", louis));
}

求值表达式office_move()的结果是

list(list("alyssa", 3), list("ben", 2), list("cy", 4),
     list("lem", 5), list("louis", 1))

尽管这个简单的函数有效，但速度非常慢。练习 4.37 和 4.38 讨论了一些可能的改进。

练习 4.36

修改办公室搬迁函数，省略 Louis 的办公室不会在 Cy 的旁边的要求。对于这个修改后的谜题有多少解？

练习 4.37

办公室搬迁函数中限制的顺序是否影响答案？它是否影响找到答案的时间？如果你认为它很重要，通过重新排列限制从给定的函数中获得更快的程序。如果你认为它不重要，请阐述你的观点。

练习 4.38

在办公室搬迁问题中，人们搬进办公室的分配集合有多少个，在办公室分配必须不同的要求之前和之后？生成所有可能的人员到办公室的分配，然后依靠回溯来消除它们是非常低效的。例如，大多数限制只依赖于一个或两个人员-办公室名称，因此可以在为所有人员选择办公室之前施加。编写并演示一个更有效的非确定性函数，它基于生成仅仅是之前的限制已经排除的那些可能性来解决这个问题。

练习 4.39

编写一个普通的 JavaScript 程序来解决办公室搬迁谜题。

练习 4.40

解决以下“说谎者”谜题（改编自 Phillips 1934）：

Alyssa、Cy、Eva、Lem 和 Louis 在 SoSoService 商务午餐。他们的餐点一个接一个地到达，比他们下订单的时间晚了很多。为了取悦 Ben，他们决定每个人都说一句真话和一句假话关于他们的订单：

Alyssa：“Lem 的餐第二个到了。我的第三个到了。”

Cy：“我的先到了。Eva 的第二个到了。”

Eva：“我的第三个到了，可怜的 Cy 的最后一个到了。”

Lem：“我的第二个到了。Louis 的第四个到了。”

Louis：“我的第四个到了。Alyssa 的第一个到了。”

五个用餐者的真实用餐顺序是什么？

练习 4.41

使用amb求值器来解决以下谜题（改编自 Phillips 1961）：

Alyssa、Ben、Cy、Eva 和 Louis 分别选择 SICP JS 的不同章节，并解决该章节中的所有练习。Louis 解决了“函数”章节中的练习，Alyssa 解决了“数据”章节中的练习，Cy 解决了“状态”章节中的练习。他们决定相互检查对方的工作，Alyssa 自愿检查“元”章节中的练习。由 Ben 解决“寄存器机器”章节中的练习，并由 Louis 检查。检查“函数”章节中的练习的人解决了 Eva 检查的练习。谁检查“数据”章节中的练习？

尝试编写程序，使其运行效率高（参见练习 4.38）。还要确定如果我们不知道 Alyssa 检查“Meta”章节中的练习，有多少解决方案。

练习 4.42

练习 2.42 描述了在国际象棋棋盘上放置皇后，使得没有两个皇后互相攻击的“八皇后谜题”。编写一个非确定性程序来解决这个谜题。

解析自然语言

设计为接受自然语言作为输入的程序通常从尝试解析输入开始，即将输入与某种语法结构匹配。例如，我们可以尝试识别由冠词后跟名词后跟动词组成的简单句子，如“The cat eats”。为了完成这样的分析，我们必须能够识别单词的词性。我们可以从一些分类各种单词的列表开始：

const nouns = list("noun", "student", "professor", "cat", "class");
const verbs = list("verb", "studies", "lectures", "eats", "sleeps");
const articles = list("article", "the", "a");

我们还需要一个语法，即一组描述语法元素如何由更简单的元素组成的规则。一个非常简单的语法可能规定一个句子总是由两部分组成——一个名词短语后跟一个动词——而一个名词短语由一个冠词后跟一个名词组成。有了这个语法，句子“The cat eats”被解析如下：

list("sentence",
     list("noun-phrase", list("article", "the"), list("noun", "cat"),
     list("verb", "eats"))

我们可以用一个简单的程序生成这样的解析，该程序为每个语法规则分别定义了函数。为了解析一个句子，我们识别它的两个组成部分，并返回带有符号sentence的这两个元素的列表：

function parse_sentence() {
    return list("sentence",
                parse_noun_phrase(),
                parse_word(verbs));
}

类似地，名词短语通过找到一个冠词后跟一个名词来解析：

function parse_noun_phrase() {
    return list("noun-phrase",
                parse_word(articles),
                parse_word(nouns));
}

在最低级别，解析归结为反复检查下一个尚未解析的单词是否属于所需词性的单词列表。为了实现这一点，我们维护一个全局变量not_yet_parsed，它是尚未解析的输入。每次检查一个单词时，我们要求not_yet_parsed必须非空，并且它应该以指定列表中的一个单词开头。如果是这样，我们就从not_yet_parsed中删除该单词，并返回该单词以及它的词性（该词性位于列表的开头）：

function parse_word(word_list) {
    require(! is_null(not_yet_parsed));
    require(! is_null(member(head(not_yet_parsed), tail(word_list))));
    const found_word = head(not_yet_parsed);
    not_yet_parsed = tail(not_yet_parsed);
    return list(head(word_list), found_word);
}

要开始解析，我们所需要做的就是将not_yet_parsed设置为整个输入，尝试解析一个句子，并检查是否有剩余的内容：

let not_yet_parsed = null;
function parse_input(input) {
    not_yet_parsed = input;
    const sent = parse_sentence();
    require(is_null(not_yet_parsed));
    return sent;
}

现在我们可以尝试解析器，并验证它是否适用于我们的简单测试句子：

amb-求值输入：

parse_input(list("the",  "cat",  "eats"));

开始一个新问题

amb-求值值：

list("sentence",
      list("noun-phrase", list("article", "the"), list("noun", "cat")),
      list("verb", "eats"))

amb求值器在这里很有用，因为使用require来表达解析约束非常方便。然而，当我们考虑更复杂的语法，其中有关于单元如何分解的选择时，自动搜索和回溯确实很有回报。

让我们在我们的语法中添加一个介词列表：

const prepositions = list("prep", "for", "to", "in", "by", "with");

并定义介词短语（例如，“为猫”）为介词后跟一个名词短语：

function parse_prepositional_phrase() {
    return list("prep-phrase",
                parse_word(prepositions),
                parse_noun_phrase());
}

现在我们可以定义一个句子为一个名词短语后跟一个动词短语，其中动词短语可以是一个动词，也可以是一个由介词短语扩展的动词短语：

function parse_sentence() {
    return list("sentence",
                parse_noun_phrase(),
                parse_verb_phrase());
}
function parse_verb_phrase() {
    function maybe_extend(verb_phrase) {
        return amb(verb_phrase,
                   maybe_extend(list("verb-phrase",
                                     verb_phrase,
                                     parse_prepositional_phrase())));
    }
    return maybe_extend(parse_word(verbs));
}

顺便说一下，我们还可以详细说明名词短语的定义，以允许“a cat in the class”这样的内容。我们过去称之为名词短语的东西，现在称之为简单名词短语，名词短语现在可以是一个简单名词短语，也可以是由介词短语扩展的名词短语：

function parse_simple_noun_phrase() {
    return list("simple-noun-phrase",
                parse_word(articles),
                parse_word(nouns));
}
function parse_noun_phrase() {
    function maybe_extend(noun_phrase) {
        return amb(noun_phrase,
                   maybe_extend(list("noun-phrase",
                                     noun_phrase,
                                     parse_prepositional_phrase())));
    }
    return maybe_extend(parse_simple_noun_phrase());
}

我们的新语法让我们能够解析更复杂的句子。例如

parse_input(list("the", "student", "with", "the", "cat",
                 "sleeps", "in", "the", "class"));

产生

list("sentence",
     list("noun-phrase",
          list("simple-noun-phrase",
               list("article", "the"), list("noun", "student")),
          list("prep-phrase", list("prep", "with"),
               list("simple-noun-phrase",
                    list("article", "the"),
                    list("noun", "cat")))),
     list("verb-phrase",
          list("verb", "sleeps"),
          list("prep-phrase", list("prep", "in"),
               list("simple-noun-phrase",
                    list("article", "the"),
                    list("noun", "class")))))

注意，给定的输入可能有多个合法的解析。在句子“The professor lectures to the student with the cat.”中，可能是教授正在和猫一起讲课，也可能是学生有这只猫。我们的非确定性程序找到了这两种可能性：

parse_input(list("the", "professor", "lectures",
                 "to", "the", "student", "with", "the", "cat"));

产生

list("sentence",
     list("simple-noun-phrase",
          list("article", "the"), list("noun", "professor")),
     list("verb-phrase",
          list("verb-phrase",
               list("verb", "lectures"),
               list("prep-phrase", list("prep", "to"),
                    list("simple-noun-phrase",
                    list("article", "the"),
                    list("noun", "student")))),
          list("prep-phrase", list("prep", "with"),
               list("simple-noun-phrase",
                    list("article", "the"),
                    list("noun", "cat")))))

要求求值器重试会产生

list("sentence",
     list("simple-noun-phrase",
          list("article", "the"), list("noun", "professor")),
     list("verb-phrase",
          list("verb", "lectures"),
          list("prep-phrase", list("prep", "to"),
               list("noun-phrase",
                    list("simple-noun-phrase",
                         list("article", "the"),
                         list("noun", "student")),
                    list("prep-phrase", list("prep", "with"),
                         list("simple-noun-phrase",
                         list("article", "the"),
                         list("noun", "cat")))))))

练习 4.43

使用上面给出的语法，以下句子可以有五种不同的解析方式：“The professor lectures to the student in the class with the cat.” 给出这五种解析并解释它们之间的意义差异。

练习 4.44

第 4.1 和 4.2 节的求值器不确定参数表达式的求值顺序。我们将看到amb求值器会从左到右对它们进行求值。解释为什么如果参数表达式以其他顺序进行求值，我们的解析程序将无法工作。

练习 4.45

Louis Reasoner 建议，由于动词短语要么是一个动词，要么是一个动词短语后跟一个介词短语，因此将函数parse_verb_phrase声明为以下方式（名词短语也是如此）会更加直接：

function parse_verb_phrase() {
    return amb(parse_word(verbs),
               list("verb-phrase",
                   parse_verb_phrase(),
                   parse_prepositional_phrase()));
}

这样行得通吗？如果我们交换amb中表达式的顺序，程序的行为会改变吗？

练习 4.46

扩展上面给出的语法以处理更复杂的句子。例如，您可以扩展名词短语和动词短语以包括形容词和副词，或者您可以处理并列句。

练习 4.47

Alyssa P. Hacker 对生成有趣的句子更感兴趣，而不是解析它们。她认为，通过简单地更改函数parse_word，使其忽略“输入句子”，而总是成功并生成一个合适的单词，我们可以使用我们为解析构建的程序来进行生成。实现 Alyssa 的想法，并展示生成的前六个或更多句子。

4.3.3 实现`amb`求值器

普通 JavaScript 程序的求值可能返回一个值，可能永远不会终止，也可能会发出错误。在非确定性 JavaScript 中，程序的求值可能会导致发现死胡同，此时求值必须回溯到先前的选择点。这种额外情况使得非确定性 JavaScript 的解释变得复杂。

我们将通过修改第 4.1.7 节的分析求值器来构建非确定性 JavaScript 的amb求值器。与分析求值器一样，组件的求值是通过调用分析该组件的执行函数来完成的。普通 JavaScript 的解释和非确定性 JavaScript 的解释之间的区别将完全体现在执行函数中。

执行函数和延续

请记住，普通求值器的执行函数接受一个参数：执行环境。相比之下，amb求值器中的执行函数接受三个参数：环境和两个称为延续函数的函数。组件的求值将通过调用这两个延续函数之一来完成：如果求值得到一个值，将调用成功延续并传递该值；如果求值导致发现死胡同，则调用失败延续。构造和调用适当的延续是非确定性求值器实现回溯的机制。

成功延续的工作是接收一个值并继续计算。除了该值之外，成功延续还传递另一个失败延续，如果使用该值导致死胡同，随后将调用该失败延续。

失败延续的工作是尝试非确定性过程的另一个分支。非确定性语言的本质在于组件可以代表在选择之间进行选择。这样的组件的求值必须继续进行所指示的备选选择之一，即使事先不知道哪些选择将导致可接受的结果。为了处理这个问题，求值器选择其中一个备选方案，并将该值传递给成功延续。除了该值之外，求值器还构造并传递一个失败延续，以便稍后调用以选择不同的备选方案。

在求值过程中触发失败（即调用失败延续）当用户程序明确拒绝当前攻击线路时（例如，调用require可能导致执行amb()，一个总是失败的表达式-见第 4.3.1 节）。此时手头的失败延续将导致最近的选择点选择另一个替代方案。如果在该选择点没有更多的替代方案需要考虑，将触发较早选择点的失败，依此类推。失败延续还会在驱动循环响应retry请求时调用，以找到程序的另一个值。

此外，如果在选择的过程中发生了副作用操作（例如对变量的赋值），当过程找到死胡同时，可能需要在进行新的选择之前撤消副作用。这是通过使副作用操作产生一个失败延续来实现的，该失败延续撤消副作用并传播失败。

总之，失败延续是由构建的

amb表达式-提供一种机制，如果amb表达式的当前选择导致死胡同，则进行替代选择。
顶层驱动程序-提供一种机制，在选择耗尽时报告失败；
分配-拦截失败并在回溯期间撤消分配。

只有在遇到死胡同时才会启动失败。这发生在

如果用户程序执行amb()；
如果用户在顶层驱动程序处键入retry。

在处理失败时也称为失败延续：

当由分配创建的失败延续完成撤消副作用时，它调用它拦截的失败延续，以将失败传播回导致此分配的选择点或顶层。
当amb的失败延续用尽选择时，它调用最初给amb的失败延续，以将失败传播回先前的选择点或顶层。

求值器的结构

amb求值器的语法和数据表示函数，以及基本的analyze函数，与第 4.1.7 节的求值器相同，只是我们需要额外的语法函数来识别amb语法形式：

function is_amb(component) {
    return is_tagged_list(component, "application") &&
           is_name(function_expression(component)) &&
           symbol_of_name(function_expression(component)) === "amb";
}
function amb_choices(component) {
    return arg_expressions(component);
}

我们继续使用第 4.1.2 节的解析函数，该函数不支持amb作为语法形式，而是将amb(``...``)视为函数应用。函数is_amb确保每当名称amb出现为应用的函数表达式时，求值器将“应用”视为不确定性选择点。

我们还必须在analyze的分发中添加一个子句，以识别这样的表达式并生成适当的执行函数：

...
: is_amb(component)
? analyze_amb(component)
: is_application(component)
...

顶层函数ambeval（类似于第 4.1.7 节中给出的evaluate版本）分析给定的组件，并将生成的执行函数应用于给定的环境，以及两个给定的延续：

function ambeval(component, env, succeed, fail) {
    return analyze(component)(env, succeed, fail);
}

成功延续是一个带有两个参数的函数：刚刚获得的值和另一个失败延续，如果该值导致后续失败，则使用该失败延续。失败延续是一个没有参数的函数。因此，执行函数的一般形式是

(env, succeed, fail) => {
    // succeed is (value, fail) => ...
    // fail is () => ...
    ...
}

例如，执行

ambeval(component,
        the_global_environment,
        (value, fail) => value,
        () => "failed");

将尝试求值给定的组件，并将返回组件的值（如果求值成功）或字符串"failed"（如果求值失败）。下面显示的驱动循环中对ambeval的调用使用了更复杂的延续函数，这些函数继续循环并支持retry请求。

amb求值器的大部分复杂性都来自于在执行函数相互调用时传递延续的机制。在阅读以下代码时，您应该将每个执行函数与第 4.1.7 节中给出的普通求值器的相应函数进行比较。

简单表达式

最简单类型表达式的执行函数基本上与普通求值器的执行函数相同，除了需要管理延续。执行函数只是成功地返回表达式的值，并传递给它们的失败延续。

function analyze_literal(component) {
    return (env, succeed, fail) =>
             succeed(literal_value(component), fail);
}
function analyze_name(component) {
    return (env, succeed, fail) =>
             succeed(lookup_symbol_value(symbol_of_name(component),
                                         env),
                    fail);
}
function analyze_lambda_expression(component) {
    const params = lambda_parameter_symbols(component);
    const bfun = analyze(lambda_body(component));
    return (env, succeed, fail) =>
             succeed(make_function(params, bfun, env),
                     fail);
}

请注意，查找名称总是“成功”的。如果lookup_symbol_value未能找到名称，它会像往常一样发出错误信号。这样的“失败”表示程序错误 - 引用未绑定的名称；这不是表明我们应该尝试另一个非确定性选择，而不是当前正在尝试的选择。

条件和序列

条件也以与普通求值器相似的方式处理。由analyze_conditional生成的执行函数调用谓词执行函数pfun，并使用一个成功延续来检查谓词值是否为真，并继续执行条件的结果或替代方案。如果pfun的执行失败，将调用条件表达式的原始失败延续。

function analyze_conditional(component) {
    const pfun = analyze(conditional_predicate(component));
    const cfun = analyze(conditional_consequent(component));
    const afun = analyze(conditional_alternative(component));
    return (env, succeed, fail) =>
             pfun(env,
                  // success continuation for evaluating the predicate
                  // to obtain pred_value (pred_value, fail2) =>
                    is_truthy(pred_value)
                    ? cfun(env, succeed, fail2)
                    : afun(env, succeed, fail2),
                  // failure continuation for evaluating the predicate
                  fail);
}

序列也以与以前的求值器相同的方式处理，除了在子函数sequentially中进行的操作，这些操作对于传递延续是必需的。即，为了依次执行a和b，我们使用一个成功延续调用a，该成功延续调用b。

function analyze_sequence(stmts) {
    function sequentially(a, b) {
        return (env, succeed, fail) =>
                 a(env,
                   // success continuation for calling a
                   (a_value, fail2) =>
                     is_return_value(a_value)
                     ? succeed(a_value, fail2)
                     : b(env, succeed, fail2),
                   // failure continuation for calling
                   a fail);
    }
    function loop(first_fun, rest_funs) {
        return is_null(rest_funs)
               ? first_fun
               : loop(sequentially(first_fun, head(rest_funs)),
                      tail(rest_funs));
    }
    const funs = map(analyze, stmts);
    return is_null(funs)
           ? env => undefined
           : loop(head(funs), tail(funs));
}

声明和赋值

声明是另一种情况，我们必须费力地管理延续，因为必须在实际声明新名称之前求值声明值表达式。为了实现这一点，使用环境、成功延续和失败延续调用声明值执行函数vfun。如果vfun的执行成功，获得了声明名称的值val，则声明名称并传播成功：

function analyze_declaration(component) {
    const symbol = declaration_symbol(component);
    const vfun = analyze(declaration_value_expression(component));
    return (env, succeed, fail) =>
             vfun(env,
                  (val, fail2) => {
                      assign_symbol_value(symbol, val, env);
                      return succeed(undefined, fail2);
                  },
                  fail);
}

赋值更有趣。这是我们真正使用延续的第一个地方，而不仅仅是传递它们。赋值的执行函数开始时与声明的执行函数类似。它首先尝试获取要分配给名称的新值。如果vfun的求值失败，赋值也失败。

然而，如果vfun成功，并且我们继续进行赋值，我们必须考虑这一计算分支可能以后会失败的可能性，这将需要我们回溯到赋值之外。因此，我们必须安排在回溯过程中撤消赋值。

这是通过给vfun一个成功继续（在下面标有注释1）来实现的，该成功继续在分配新值给变量并从分配中继续之前保存变量的旧值。与分配值一起传递的失败继续（在下面标有注释2）在继续失败之前恢复变量的旧值。也就是说，成功的分配提供了一个失败继续，该失败继续将拦截后续的失败；否则会调用fail2的任何失败都会调用此函数，以在实际调用fail2之前撤消分配。

function analyze_assignment(component) {
    const symbol = assignment_symbol(component);
    const vfun = analyze(assignment_value_expression(component));
    return (env, succeed, fail) =>
             vfun(env,
                  (val, fail2) => { // 1
                      const old_value = lookup_symbol_value(symbol,
                                                            env);
                      assign_symbol_value(symbol, val, env);
                      return succeed(val,
                                     () => { // 2
                                         assign_symbol_value(symbol,
                                                             old_value,
                                                             env);
                                         return fail2();
                                     });
                  },
                  fail);
}

返回语句和块

分析返回语句很简单。返回表达式被分析以产生执行函数。返回语句的执行函数调用具有成功继续的执行函数，该成功继续将返回值包装在返回值对象中并将其传递给原始成功继续。

function analyze_return_statement(component) {
    const rfun = analyze(return_expression(component));
    return (env, succeed, fail) =>
             rfun(env,
                  (val, fail2) =>
                    succeed(make_return_value(val), fail2),
                  fail);
}

块的执行函数在扩展环境上调用主体的执行函数，而不更改成功或失败继续。

function analyze_block(component) {
    const body = block_body(component);
    const locals = scan_out_declarations(body);
    const unassigneds = list_of_unassigned(locals);
    const bfun = analyze(body);
    return (env, succeed, fail) =>
             bfun(extend_environment(locals, unassigneds, env),
                  succeed,
                  fail);
}

函数应用

应用的执行函数中除了管理继续的技术复杂性外，没有新的想法。这种复杂性出现在analyze_ application中，因为我们在求值参数表达式时需要跟踪成功和失败继续。我们使用一个函数get_args来求值参数表达式的列表，而不是像普通求值器中那样简单地使用map。

function analyze_application(component) {
    const ffun = analyze(function_expression(component));
    const afuns = map(analyze, arg_expressions(component));
    return (env, succeed, fail) =>
             ffun(env,
                  (fun, fail2) =>
                    get_args(afuns,
                             env,
                             (args, fail3) =>
                               execute_application(fun,
                                                   args,
                                                   succeed,
                                                   fail3),
                             fail2),
                  fail);
}

在get_args中，注意如何通过使用一个递归调用get_args的成功继续来遍历afun执行函数列表并构造args的结果列表。每个对get_args的递归调用都有一个成功继续，其值是使用pair将新获得的参数添加到累积参数列表中得到的新列表：

function get_args(afuns, env, succeed, fail) {
    return is_null(afuns)
           ? succeed(null, fail)
           : head(afuns)(env,
                         // success continuation for this afun
                         (arg, fail2) =>
                           get_args(tail(afuns),
                                    env,
                                    // success continuation for
                                    // recursive call to get_args
                                    (args, fail3) =>
                                      succeed(pair(arg, args),
                                              fail3),
                                    fail2),
                         fail);
}

实际的函数应用是由execute_application执行的，与普通求值器一样，只是需要管理继续。

function execute_application(fun, args, succeed, fail) {
    return is_primitive_function(fun)
           ? succeed(apply_primitive_function(fun, args),
                     fail)
           : is_compound_function(fun)
           ? function_body(fun)(
                 extend_environment(function_parameters(fun),
                                    args,
                                    function_environment(fun)),
                 (body_result, fail2) =>
                   succeed(is_return_value(body_result)
                           ? return_value_content(body_result)
                           : undefined,
                           fail2),
                 fail)
           : error(fun, "unknown function type - execute_application");
}

求值`amb`表达式

amb语法形式是非确定性语言中的关键元素。在这里，我们看到了解释过程的本质以及跟踪继续的原因。amb的执行函数定义了一个循环try_next，该循环循环执行amb表达式的所有可能值的执行函数。每个执行函数都使用一个失败继续进行调用，该失败继续将尝试下一个值。当没有更多的替代方案可尝试时，整个amb表达式失败。

function analyze_amb(component) {
    const cfuns = map(analyze, amb_choices(component));
    return (env, succeed, fail) => {
               function try_next(choices) {
                   return is_null(choices)
                          ? fail()
                          : head(choices)(env,
                                          succeed,
                                          () =>
                                            try_next(tail(choices)));
               }
               return try_next(cfuns);
           };
}

驱动循环

由于允许用户重试求值程序的机制，amb求值器的驱动循环非常复杂。驱动程序使用一个名为internal_loop的函数，该函数以retry函数作为参数。意图是调用retry应该继续尝试非确定性求值中的下一个未尝试的替代方案。函数internal_loop要么在用户在驱动循环中键入retry时调用retry，要么通过调用ambeval开始新的求值。

对于对ambeval的此调用的失败继续通知用户没有更多的值，并重新调用驱动循环。

对于对ambeval的调用，成功的延续更加微妙。我们打印获得的值，然后使用retry函数重新调用内部循环，该函数将能够尝试下一个替代方案。这个next_alternative函数是传递给成功延续的第二个参数。通常，我们认为这第二个参数是一个失败延续，如果当前的求值分支后来失败了，就会使用它。然而，在这种情况下，我们已经完成了一个成功的求值，因此我们可以调用“失败”替代分支，以搜索额外的成功求值。

const input_prompt = "amb-求值输入：";
const output_prompt = "amb-求值值：";
function driver_loop(env) {
    function internal_loop(retry) {
        const input = user_read(input_prompt);
        if (is_null(input)) {
            display("evaluator terminated");
        } else if (input === "retry") {
            return retry();
        } else {
            display("Starting a new problem");
            const program = parse(input);
            const locals = scan_out_declarations(program);
            const unassigneds = list_of_unassigned(locals);
            const program_env = extend_environment(
                                     locals, unassigneds, env);
            return ambeval(
                       program,
                       program_env,
                       // ambeval success
                       (val, next_alternative) => {
                           user_print(output_prompt, val);
                           return internal_loop(next_alternative);
                       },
                       // ambeval failure
                       () => {
                           display("There are no more values of");
                           display(input);
                           return driver_loop(program_env);
                       });
        }
    }
    return internal_loop(() => {
                             display("There is no current problem");
                             return driver_loop(env);
                         });
}

对internal_loop的初始调用使用retry函数，该函数抱怨当前没有问题并重新启动驱动循环。如果用户在没有进行求值时输入retry，则会发生这种行为。

我们像往常一样启动驱动循环，通过设置全局环境并将其作为第一次迭代的封闭环境传递给driver_loop。

const the_global_environment = setup_environment();
driver_loop(the_global_environment);

练习 4.48

实现一个新的语法形式ramb，它类似于amb，但是以随机顺序搜索替代，而不是从左到右。展示这如何帮助艾丽莎在练习 4.47 中的问题。

练习 4.49

更改赋值的实现，使其在失败时不会被撤消。例如，我们可以从列表中选择两个不同的元素，并计算成功选择所需的尝试次数如下：

let count = 0;
let x = an_element_of("a", "b", "c");
let y = an_element_of("a", "b", "c"); count = count + 1;
require(x !== y); list(x, y, count);

开始新问题：

amb-求值值：

["a", ["b", [2, null]]]

amb-求值输入：

retry

amb-求值值：

["a", ["c", [3, null]]]

如果我们使用了赋值的原始含义而不是永久赋值，将显示哪些值？

练习 4.50

我们将可怕地滥用条件语句的语法，通过实现以下形式的结构：

if (evaluation_succeeds_take) { statement } else { alternative }

该结构允许用户捕获语句的失败。它像往常一样求值语句，如果求值成功，则像往常一样返回。但是，如果求值失败，将求值给定的替代语句，如下例所示：

amb-求值输入：

if (evaluation_succeeds_take) {
    const x = an_element_of(list(1, 3, 5));
    require(is_even(x));
    x;
} else {
    "all odd";
}

开始一个新问题

amb-求值值：

"all odd"

amb-求值输入：

if (evaluation_succeeds_take) {
    const x = an_element_of(list(1, 3, 5, 8));
    require(is_even(x));
    x;
} else {
    "all odd";
}

开始一个新问题

amb-求值值：

`8`

通过扩展amb求值器来实现此结构。提示：函数is_amb显示了如何滥用现有的 JavaScript 语法以实现新的语法形式。

练习 4.51

使用练习 4.49 中描述的新类型的赋值和结构

if (evaluation_succeeds_take) { ... } else { ... }

就像在练习 4.50 中一样，求值的结果将是什么

let pairs = null;
if (evaluation_succeeds_take) {
    const p = prime_sum_pair(list(1, 3, 5, 8), list(20, 35, 110));
    pairs = pair(p, pairs); // using permanent assignment
    amb();
} else {
    pairs;
}

练习 4.52

如果我们没有意识到require可以作为一个普通函数来实现，该函数使用amb，由用户作为非确定性程序的一部分来定义，我们将不得不将其实现为一个语法形式。这将需要语法函数

function is_require(component) {
    return is_tagged_list(component, "require");
}
function require_predicate(component) { return head(tail(component)); }

以及在analyze的调度中的新子句

: is_require(component)
? analyze_require(component)

以及处理require表达式的analyze_require函数。完成analyze_require的以下定义。

function analyze_require(component) {
    const pfun = analyze(require_predicate(component));
    return (env, succeed, fail) =>
            pfun(env,
                 (pred_value, fail2) =>
                   〈??〉
                   ? 〈??〉
                   : succeed("ok", fail2),
                 fail);
}

4.4 逻辑编程

在第 1 章中，我们强调计算机科学涉及命令式（如何）知识，而数学涉及声明式（什么是）知识。事实上，编程语言要求程序员以一种形式表达知识，该形式指示解决特定问题的逐步方法。另一方面，高级语言作为语言实现的一部分，提供了大量的方法论知识，使用户不必关心特定计算的进展细节。

大多数编程语言，包括 JavaScript，都是围绕计算数学函数的值而组织的。面向表达式的语言（如 Lisp、C、Python 和 JavaScript）利用了一个“双关语”，即描述函数值的表达式也可以被解释为计算该值的手段。因此，大多数编程语言都倾向于单向计算（具有明确定义的输入和输出的计算）。然而，也有根本不同的编程语言放松了这种偏见。我们在 3.3.5 节中看到了一个这样的例子，其中计算的对象是算术约束。在约束系统中，计算的方向和顺序没有那么明确定义；因此，在进行计算时，系统必须提供比普通算术计算更详细的“如何”知识。然而，这并不意味着用户完全摆脱了提供命令性知识的责任。有许多约束网络实现了相同的约束集，用户必须从数学上等价的网络集合中选择一个合适的网络来指定特定的计算。

第 4.3 节的非确定性程序求值器也摆脱了编程是关于构建计算单向函数的观点。在非确定性语言中，表达式可以有多个值，因此计算处理的是关系而不是单值函数。逻辑编程通过将编程的关系视野与一种称为统一的强大的符号模式匹配相结合来扩展这一思想。

这种方法在起作用时可以是编写程序的一种非常强大的方式。部分原因在于一个“是什么”事实可以用来解决许多不同的问题，这些问题可能有不同的“如何”组成部分。例如，考虑append操作，它接受两个列表作为参数，并将它们的元素组合成一个单一的列表。在 JavaScript 等过程式语言中，我们可以根据基本的列表构造函数pair来定义append，就像我们在 2.2.1 节中所做的那样。

function append(x, y) {
    return is_null(x)
           ? y
           : pair(head(x), append(tail(x), y));
}

这个函数可以被看作是将以下两条规则翻译成 JavaScript，第一条规则涵盖了第一个列表为空的情况，第二条规则处理了非空列表的情况，即两个部分的pair：

对于任何列表y，空列表和y append形成y。
对于任何u、v、y和z，如果pair(u, v)和y append形成pair(u, z)，那么v和y append形成z。

使用append函数，我们可以回答诸如

找到list("a", "b")和list("c", "d")的append。

但是，同样的两条规则也足以回答以下类型的问题，而函数无法回答：

找到一个列表y，它与list("a", "b")一起append以产生

list("a", "b", "c", "d").

找到所有x和y，它们append形成list("a", "b", "c", "d")。

在逻辑编程语言中，程序员通过陈述上述关于append的两条规则来编写append“函数”。解释器会自动提供“如何”知识，以便使用这一对规则来回答关于append的所有三种类型的问题。

当代逻辑编程语言（包括我们在这里实现的语言）存在重大缺陷，因为它们的一般“如何”方法可能会导致它们陷入虚假的无限循环或其他不良行为。逻辑编程是计算机科学中的一个活跃研究领域。

在本章的前面，我们探讨了实现解释器的技术，并描述了对于类似 JavaScript 的语言（实际上，对于任何传统语言）的解释器所必不可少的元素。现在我们将应用这些想法来讨论逻辑编程语言的解释器。我们将这种语言称为查询语言，因为它非常适用于通过用语言表达的查询或问题来从数据库中检索信息。尽管查询语言与 JavaScript 非常不同，但我们将发现用相同的一般框架来描述语言是方便的：作为原始元素的集合，以及使我们能够将简单元素组合成更复杂元素的组合手段和使我们能够将复杂元素视为单个概念单位的抽象手段。逻辑编程语言的解释器比像 JavaScript 这样的语言的解释器复杂得多。尽管如此，我们将看到我们的查询语言解释器包含了在第 4.1 节的解释器中找到的许多相同元素。特别是，将有一个“求值”部分，根据类型对表达式进行分类，以及一个“应用”部分，实现语言的抽象机制（JavaScript 的情况下是函数，逻辑编程的情况下是规则）。此外，实现中的一个核心作用是由框架数据结构发挥的，它确定了符号和它们关联值之间的对应关系。我们查询语言实现的另一个有趣方面是我们大量使用了流，这在第 3 章中介绍过。

4.4.1 推理信息检索

逻辑编程在提供接口以用于信息检索的数据库方面表现出色。我们将在本章实现的查询语言旨在以这种方式使用。

为了说明查询系统的功能，我们将展示如何使用它来管理波士顿地区蓬勃发展的高科技公司 Gargle 的人员记录数据库。该语言提供了对人员信息的模式导向访问，并且还可以利用一般规则进行逻辑推断。

一个样本数据库

Gargle 的人员数据库包含有关公司人员的断言。以下是有关 Ben Bitdiddle 的信息，他是公司的计算机专家：

address(list("Bitdiddle", "Ben"),
        list("Slumerville", list("Ridge", "Road"), 10))
job(list("Bitdiddle", "Ben"), list("computer", "wizard"))
salary(list("Bitdiddle", "Ben"), 122000)

断言看起来就像 JavaScript 中的函数应用，但实际上它们代表了数据库中的信息。第一个符号——这里是address、job和salary——描述了各自断言中包含的信息种类，而“参数”是列表或原始值，如字符串和数字。第一个符号不需要像 JavaScript 中的常量或变量那样被声明；它们的范围是全局的。

作为公司的专家，Ben 负责公司的计算机部门，并监督两名程序员和一名技术员。以下是关于他们的信息：

address(list("Hacker", "Alyssa", "P"),
        list("Cambridge", list("Mass", "Ave"), 78))
job(list("Hacker", "Alyssa", "P"), list("computer", "programmer"))
salary(list("Hacker", "Alyssa", "P"), 81000)
supervisor(list("Hacker", "Alyssa", "P"), list("Bitdiddle", "Ben"))
address(list("Fect", "Cy", "D"),
        list("Cambridge", list("Ames", "Street"), 3))
job(list("Fect", "Cy", "D"), list("computer", "programmer"))
salary(list("Fect", "Cy", "D"), 70000)
supervisor(list("Fect", "Cy", "D"), list("Bitdiddle", "Ben"))
address(list("Tweakit", "Lem", "E"),
        list("Boston", list("Bay", "State", "Road"), 22))
job(list("Tweakit", "Lem", "E"), list("computer", "technician"))
salary(list("Tweakit", "Lem", "E"), 51000)
supervisor(list("Tweakit", "Lem", "E"), list("Bitdiddle", "Ben"))

还有一名程序员实习生，由 Alyssa 监督：

address(list("Reasoner", "Louis"),
        list("Slumerville", list("Pine", "Tree", "Road"), 80))
job(list("Reasoner", "Louis"),
        list("computer", "programmer", "trainee"))
salary(list("Reasoner", "Louis"), 62000)
supervisor(list("Reasoner", "Louis"), list("Hacker", "Alyssa", "P"))

所有这些人都在计算机部门，这可以从他们的工作描述中的第一个项目为“计算机”这个词来看出。

Ben 是一名高级雇员。他的主管是公司的大佬本人：

supervisor(list("Bitdiddle", "Ben"), list("Warbucks", "Oliver"))
address(list("Warbucks", "Oliver"),
        list("Swellesley", list("Top", "Heap", "Road")))
job(list("Warbucks", "Oliver"), list("administration", "big", "wheel"))
salary(list("Warbucks", "Oliver"), 314159)

除了由 Ben 监督的计算机部门，公司还有一个会计部门，由一名总会计和他的助手组成：

address(list("Scrooge", "Eben"),
        list("Weston", list("Shady", "Lane"), 10))
job(list("Scrooge", "Eben"), list("accounting", "chief", "accountant"))
salary(list("Scrooge", "Eben"), 141421)
supervisor(list("Scrooge", "Eben"), list("Warbucks", "Oliver"))
address(list("Cratchit", "Robert"),
        list("Allston", list("N", "Harvard", "Street"), 16))
job(list("Cratchit", "Robert"), list("accounting", "scrivener"))
salary(list("Cratchit", "Robert"), 26100)
supervisor(list("Cratchit", "Robert"), list("Scrooge", "Eben"))

公司的大佬还有一名行政助理：

address(list("Aull", "DeWitt"),
        list("Slumerville", list("Onion", "Square"), 5))
job(list("Aull", "DeWitt"), list("administration", "assistant"))
salary(list("Aull", "DeWitt"), 42195)
supervisor(list("Aull", "DeWitt"), list("Warbucks", "Oliver"))

数据库还包含有关持有其他种类工作的人可以做哪种工作的断言。例如，计算机专家可以做计算机程序员和计算机技术员的工作：

can_do_job(list("computer", "wizard"),
           list("computer", "programmer"))
can_do_job(list("computer", "wizard"),
           list("computer", "technician"))

计算机程序员可以代替实习生：

can_do_job(list("computer", "programmer"),
           list("computer", "programmer", "trainee"))

此外，众所周知，

can_do_job(list("administration", "assistant"),
           list("administration", "big", "wheel"))

NUS CS1101S：SICP JavaScript 描述：四、元语言抽象（4）https://developer.aliyun.com/article/1427737

NUS CS1101S：SICP JavaScript 描述：四、元语言抽象（3）

NUS CS1101S：SICP JavaScript 描述：四、元语言抽象（2）https://developer.aliyun.com/article/1427734

练习 4.25

练习 4.26

练习 4.27

练习 4.28

练习 4.29

4.2.3 流作为惰性列表

练习 4.30

练习 4.31

练习 4.32

4.3 非确定性计算

4.3.1 搜索和amb

驱动循环

练习 4.33

练习 4.34

练习 4.35

4.3.2 非确定性程序的示例

逻辑谜题

练习 4.36

练习 4.37

练习 4.38

练习 4.39

练习 4.40

练习 4.41

练习 4.42

解析自然语言

练习 4.43

练习 4.44

练习 4.45

练习 4.46

练习 4.47

4.3.3 实现amb求值器

执行函数和延续

求值器的结构

简单表达式

条件和序列

声明和赋值

返回语句和块

函数应用

求值**amb**表达式

驱动循环

练习 4.48

练习 4.49

练习 4.50

练习 4.51

练习 4.52

4.4 逻辑编程

4.4.1 推理信息检索

一个样本数据库

热门文章

最新文章

相关课程

相关电子书

相关实验场景

4.3.1 搜索和`amb`

4.3.3 实现`amb`求值器

求值`amb`表达式