NUS CS1101S：SICP JavaScript 描述：四、元语言抽象（3）https://developer.aliyun.com/article/1427735
简单查询
查询语言允许用户通过对系统提示的查询来从数据库中检索信息。例如，要找到所有计算机程序员，可以说
查询输入：
job($x, list("computer", "programmer"))
系统将响应以下项目：
查询结果：
job(list("Hacker", "Alyssa", "P"), list("computer", "programmer")) job(list("Fect", "Cy", "D"), list("computer", "programmer"))
输入查询指定我们正在寻找与数据中的某个模式匹配的条目。在这个例子中，模式指定job作为我们正在寻找的信息类型。第一项可以是任何东西，第二项是字面上的列表list("computer", "programmer")。匹配断言中可以作为第一项的“任何东西”由模式变量$x指定。作为模式变量，我们使用以美元符号开头的 JavaScript 名称。我们将在下面看到为什么指定模式变量的名称比只在模式中放入一个符号（比如$）来代表“任何东西”更有用。系统通过显示所有与指定模式匹配的数据中的条目来响应简单查询。
模式可以有多个变量。例如，查询
address($x, $y)
将列出所有员工的地址。
模式可以没有变量，这种情况下查询只是确定该模式是否是数据中的一个条目。如果是，将会有一个匹配；如果不是，将没有匹配。
相同的模式变量可以在查询中出现多次，指定相同的“任何东西”必须出现在每个位置。这就是为什么变量有名称。例如，
supervisor($x, $x)
查找所有监督自己的人（尽管在我们的样本数据库中没有这样的断言）。
查询
job($x, list("computer", $type))
匹配所有工作条目，其第二项是一个第一项为"computer"的两元素列表：
job(list("Bitdiddle", "Ben"), list("computer", "wizard")) job(list("Hacker", "Alyssa", "P"), list("computer", "programmer")) job(list("Fect", "Cy", "D"), list("computer", "programmer")) job(list("Tweakit", "Lem", "E"), list("computer", "technician"))
这个模式不匹配
job(list("Reasoner", "Louis"), list("computer", "programmer", "trainee"))
因为断言中的第二项是一个三元素列表，而模式的第二项指定应该有两个元素。如果我们想要更改模式，使得第二项可以是以"computer"开头的任何列表，我们可以指定
job($x, pair("computer", $type))
例如，
pair("computer", $type)
匹配数据
list("computer", "programmer", "trainee")
以$type为list("programmer", "trainee")。它也匹配数据
list("computer", "programmer")
以$type为list("programmer")，并匹配数据
list("computer")
以$type为空列表，null。
我们可以描述查询语言对简单查询的处理如下：
- 系统找到查询模式中变量的所有赋值，这些赋值满足该模式——也就是说，所有变量的值集合，使得如果模式变量被实例化为（替换为）这些值，结果就在数据中。
- 系统通过列出满足查询模式的变量赋值来响应查询。
注意，如果模式没有变量，查询将简化为确定该模式是否在数据中。如果是，空赋值将满足该模式。
练习 4.53
给出从数据库中检索以下信息的简单查询：
- a. 由 Ben Bitdiddle 监督的所有人；
- b. 会计部门所有人的姓名和工作；
- c. 居住在 Slumerville 的所有人的姓名和地址。
复合查询
简单查询形成了查询语言的原始操作。为了形成复合操作，查询语言提供了组合的手段。查询语言成为逻辑编程语言的一个原因是，组合的手段反映了形成逻辑表达式时使用的组合手段：and，or和not。
我们可以使用and如下来找到所有计算机程序员的地址：
and(job($person, list("computer", "programmer")), address($person, $where))
结果输出为
and(job(list("Hacker", "Alyssa", "P"), list("computer", "programmer")), address(list("Hacker", "Alyssa", "P"), list("Cambridge", list("Mass", "Ave"), 78))) and(job(list("Fect", "Cy", "D"), list("computer", "programmer")), address(list("Fect", "Cy", "D"), list("Cambridge", list("Ames", "Street"), 3)))
一般来说，
and(query[1], query[2], ..., query[n])
由同时满足query[1]，...，query[n]的模式变量的值集合来满足模式。
对于简单查询，系统通过找到满足查询的模式变量的所有赋值，然后显示具有这些值的查询的实例化来处理复合查询。
构建复合查询的另一种方法是通过or。例如，
or(supervisor($x, list("Bitdiddle", "Ben")), supervisor($x, list("Hacker", "Alyssa", "P")))
将找到所有由 Ben Bitdiddle 或 Alyssa P. Hacker 监督的员工：
or(supervisor(list("Hacker", "Alyssa", "P"), list("Bitdiddle", "Ben")), supervisor(list("Hacker", "Alyssa", "P"), list("Hacker", "Alyssa", "P"))) or(supervisor(list("Fect", "Cy", "D"), list("Bitdiddle", "Ben")), supervisor(list("Fect", "Cy", "D"), list("Hacker", "Alyssa", "P"))) or(supervisor(list("Tweakit", "Lem", "E"), list("Bitdiddle", "Ben")), supervisor(list("Tweakit", "Lem", "E"), list("Hacker", "Alyssa", "P"))) or(supervisor(list("Reasoner", "Louis"), list("Bitdiddle", "Ben")), supervisor(list("Reasoner", "Louis"), list("Hacker", "Alyssa", "P")))
一般来说，
or(query[1], query[2], ..., query[n])
由满足至少一个query[1] ... query[n]的模式变量的值集合满足。
复合查询也可以用not形成。例如，
and(supervisor($x, list("Bitdiddle", "Ben")), not(job($x, list("computer", "programmer"))))
找到所有由 Ben Bitdiddle 监督的不是计算机程序员的人。一般来说，
not(query[1])
由不满足query[1]的模式变量的所有赋值满足。⁵⁷
最终的组合形式以javascript_predicate开头，包含一个 JavaScript 谓词。一般来说，
javascript_predicate(predicate)
将满足predicate中实例化的predicate为真的模式变量的赋值。例如，要找到所有工资大于 5 万美元的人，我们可以写⁵⁸
and(salary($person, $amount), javascript_predicate($amount > 50000))
练习 4.54
制定检索以下信息的复合查询：
- a. 所有由 Ben Bitdiddle 监督的人的姓名，以及他们的地址；
- b. 所有工资低于 Ben Bitdiddle 的人，以及他们的工资和 Ben Bitdiddle 的工资；
- c. 所有由不在计算机部门的人监督的人，以及主管的姓名和工作。
规则
除了原始查询和复合查询，查询语言还提供了抽象查询的手段。这些由规则给出。规则
rule(lives_near($person_1, $person_2), and(address($person_1, pair($town, $rest_1)), address($person_2, pair($town, $rest_2)), not(same($person_1, $person_2))))
指定如果两个人住在同一个城镇，那么他们住在附近。最后的not子句防止规则说所有人都住在自己附近。same关系由一个非常简单的规则定义：⁵⁹
rule(same($x, $x))
以下规则声明，如果一个人监督一个人，而这个人又是一个主管，那么这个人在组织中是一个“轮子”：
rule(wheel($person), and(supervisor($middle_manager, $person), supervisor($x, $middle_manager)))
规则的一般形式是
rule(conclusion, body)
其中conclusion是一个模式，body是任何查询。⁶⁰我们可以认为规则代表一个大（甚至无限）的断言集，即满足规则体的变量赋值的规则结论的所有实例化。当我们描述简单查询（模式）时，我们说变量的赋值满足模式，如果实例化的模式在数据库中。但是模式不一定要作为断言明确地在数据库中。它可以是由规则暗示的隐式断言。例如，查询
lives_near($x, list("Bitdiddle", "Ben"))
导致
lives_near(list("Reasoner", "Louis"), list("Bitdiddle", "Ben")) lives_near(list("Aull", "DeWitt"), list("Bitdiddle", "Ben"))
要找到所有住在 Ben Bitdiddle 附近的计算机程序员，我们可以问
and(job($x, list("computer", "programmer")), lives_near($x, list("Bitdiddle", "Ben")))
与复合函数一样，规则可以作为其他规则的一部分（就像我们上面看到的lives_near规则），甚至可以递归地定义。例如，规则
rule(outranked_by($staff_person, $boss), or(supervisor($staff_person, $boss), and(supervisor($staff_person, $middle_manager), outranked_by($middle_manager, $boss))))
说一个员工在组织中被老板超越，如果老板是这个人的主管，或者（递归地）如果这个人的主管被老板超越。
练习 4.55
定义一个规则，规定如果人 1 和人 2 做同样的工作，或者做人 1 的工作的人也可以做人 2 的工作，那么人 1 可以取代人 2，前提是人 1 和人 2 不是同一个人。使用你的规则，给出以下查询：
- a. 所有可以取代 Cy D. Fect 的人；
- b. 所有可以取代收入比他们高的人的人，以及两个人的工资。
练习 4.56
定义一个规则，如果一个人在部门中工作但没有一个在部门中工作的主管，那么这个人在部门中是一个“大人物”。
练习 4.57
Ben Bitdiddle 错过了太多次会议。担心他忘记会议的习惯可能会让他失去工作，Ben 决定采取一些行动。他通过断言将公司的所有周会议添加到 Gargle 数据库中，如下所示：
meeting("accounting", list("Monday", "9am")) meeting("administration", list("Monday", "10am")) meeting("computer", list("Wednesday", "3pm")) meeting("administration", list("Friday", "1pm"))
上述每个断言都是整个部门的会议。Ben 还为跨越所有部门的全公司会议添加了一个条目。公司的所有员工都参加这次会议。
meeting("whole-company", list("Wednesday", "4pm"))
- a. 在星期五早上，Ben 想要查询当天发生的所有会议。他应该使用什么查询？
- b. Alyssa P. Hacker 并不感到满意。她认为，通过指定她的名字来询问她的会议将会更有用。因此，她设计了一个规则，规定一个人的会议包括所有“整公司”会议以及该人所在部门的所有会议。填写 Alyssa 的规则的主体。
rule(meeting_time($person, $day_and_time), rule-body)
- c. Alyssa 在周三早上到达工作岗位，想知道当天她需要参加哪些会议。在定义了上述规则之后，她应该提出什么查询来找出这一点？
练习 4.58
通过给出查询
lives_near($person, list("Hacker", "Alyssa", "P"))
Alyssa P. Hacker 能够找到住在她附近的人，可以和他们一起上班。另一方面，当她尝试通过查询找到所有住在附近的人的对时
lives_near($person_1, $person_2)
她注意到每对住在附近的人都被列出了两次；例如，
lives_near(list("Hacker", "Alyssa", "P"), list("Fect", "Cy", "D")) lives_near(list("Fect", "Cy", "D"), list("Hacker", "Alyssa", "P"))
为什么会发生这种情况？有没有办法找到住在附近的人的名单，其中每对只出现一次？请解释。
逻辑作为程序
我们可以将规则视为一种逻辑蕴涵：如果对模式变量的值的分配满足主体，那么它满足结论。因此，我们可以认为查询语言具有根据规则执行逻辑推导的能力。例如，考虑第 4.4 节开头描述的append操作。正如我们所说的，append可以由以下两个规则来描述：
- 对于任何列表
y，空列表和y append成y。 - 对于任何
u、v、y和z，如果v和y append成z，则pair(u, v)和y append成pair(u, z)。
为了在我们的查询语言中表达这一点，我们为一个关系定义了两个规则
append_to_form(x, y, z)
我们可以将其解释为“x和y append成z”：
rule(append_to_form(null, $y, $y)) rule(append_to_form(pair($u, $v), $y, pair($u, $z)), append_to_form($v, $y, $z))
第一个规则没有主体，这意味着结论对于任何$y的值都成立。请注意第二个规则如何利用pair来命名列表的头部和尾部。
在给定这两个规则的情况下，我们可以制定计算两个列表的append的查询：
查询输入：
append_to_form(list("a", "b"), list("c", "d"), $z)
查询结果：
append_to_form(list("a", "b"), list("c", "d"), list("a", "b", "c", "d"))
更令人惊讶的是，我们可以使用相同的规则来询问“哪个列表append到list("a", "b")会产生list("a", "b", "c", "d")？” 这样做如下：
查询输入：
append_to_form(list("a", "b"), $y, list("a", "b", "c", "d"))
查询结果：
append_to_form(list("a", "b"), list("c", "d"), list("a", "b", "c", "d"))
我们可以要求所有append成list("a", "b", "c", "d")的列表对：
查询输入：
append_to_form($x, $y, list("a", "b", "c", "d"))
查询结果：
append_to_form(null, list("a", "b", "c", "d"), list("a", "b", "c", "d")) append_to_form(list("a"), list("b", "c", "d"), list("a", "b", "c", "d")) append_to_form(list("a", "b"), list("c", "d"), list("a", "b", "c", "d")) append_to_form(list("a", "b", "c"), list("d"), list("a", "b", "c", "d")) append_to_form(list("a", "b", "c", "d"), null, list("a", "b", "c", "d"))
查询系统似乎在使用规则推断上述查询的答案时表现出相当多的智能。实际上，正如我们将在下一节中看到的那样，系统正在遵循一个明确定义的算法来解开规则。不幸的是，尽管系统在append情况下的工作令人印象深刻，但一般方法可能会在更复杂的情况下崩溃，正如我们将在第 4.4.3 节中看到的那样。
练习 4.59
以下规则实现了一个next_to_in关系，找到列表的相邻元素：
rule(next_to_in($x, $y, pair($x, pair($y, $u)))) rule(next_to_in($x, $y, pair($v, $z)), next_to_in($x, $y, $z))
对以下查询的响应将是什么？
next_to_in($x, $y, list(1, list(2, 3), 4)) next_to_in($x, 1, list(2, 1, 3, 1))
练习 4.60
定义规则来实现练习 2.17 的last_pair操作，该操作返回包含非空列表的最后一个元素的列表。在以下查询中检查您的规则：
- last_pair(list(3), $x)
- last_pair(list(1, 2, 3), $x)
- last_pair(list(2, $x), list(3))
您的规则在诸如last_pair($x, list(3))的查询上是否正确工作？
练习 4.61
以下数据库（参见创世记 4）追溯了亚当的后裔的家谱，经由该隐：
son("Adam", "Cain") son("Cain", "Enoch") son("Enoch", "Irad") son("Irad", "Mehujael") son("Mehujael", "Methushael") son("Methushael", "Lamech") wife("Lamech", "Ada") son("Ada", "Jabal") son("Ada", "Jubal")
制定规则，例如“如果S是F的儿子，F是G的儿子，那么S是G的孙子”，以及“如果W是M的妻子，S是W的儿子，那么S是M的儿子”（这在圣经时代比今天更真实），这将使查询系统能够找到该隐的孙子；拉麦的儿子；麦土撒的孙子。（参见练习 4.67，了解推断更复杂关系的一些规则。）
4.4.2 查询系统的工作原理
在第 4.4.4 节中，我们将介绍查询解释器的一组函数实现。在本节中，我们将概述解释器的一般结构，独立于低级实现细节。在描述解释器的实现之后，我们将能够理解查询语言的逻辑操作与数学逻辑操作的一些微妙差异以及一些限制。
显然，查询求值器必须执行某种搜索，以便将查询与数据库中的事实和规则匹配。一种方法是将查询系统实现为一个非确定性程序，使用第 4.3 节的amb求值器（参见练习 4.75）。另一种可能性是使用流来管理搜索。我们的实现遵循第二种方法。
查询系统围绕两个中心操作组织，称为模式匹配和统一。我们首先描述模式匹配，并解释这个操作，以及信息的组织方式，以流的形式的帧，使我们能够实现简单和复合查询。接下来我们讨论统一，这是模式匹配的一般化，需要实现规则。最后，我们展示整个查询解释器如何通过一个函数组合在一起，类似于第 4.1 节中描述的解释器对表达式进行分类的方式。
模式匹配
模式匹配器是一个测试某个数据是否符合指定模式的程序。例如，数据list(list("a", "b"), "c", list("a", "b"))与模式list($x, "c", $x)匹配，其中模式变量$x绑定到list("a", "b")。相同的数据列表与模式list($x, $y, $z)匹配，其中$x和$z都绑定到list("a", "b")，$y绑定到"c"。它还与模式list(list($x, $y), "c", list($x, $y))匹配，其中$x绑定到"a"，$y绑定到"b"。但是，它不与模式list($x, "a", $y)匹配，因为该模式指定了第二个元素为字符串"a"的列表。
查询系统使用的模式匹配器将模式、数据和指定各种模式变量绑定的帧作为输入。它检查数据是否与模式匹配，并且与帧中已有的绑定一致。如果是，它返回给定的帧，其中可能包含由匹配确定的任何绑定。否则，它指示匹配失败。
使用模式list($x, $y, $x)来匹配list("a", "b", "a")，给定一个空帧，例如，将返回一个指定$x绑定为"a"和$y绑定为"b"的帧。尝试使用相同的模式、相同的数据和指定$y绑定为"a"的帧进行匹配将失败。尝试使用相同的模式、相同的数据和一个帧，其中$y绑定为"b"和$x未绑定，将返回给定的帧，增加了$x绑定为"a"。
模式匹配器是处理不涉及规则的简单查询所需的全部机制。例如，处理查询
job($x, list("computer", "programmer"))
我们扫描数据库中的所有断言，并选择与最初空帧相匹配的断言。对于我们找到的每个匹配，我们使用匹配返回的帧来实例化具有$x值的模式。
帧流
通过使用流，模式对帧的测试是有组织的。给定一个单个帧，匹配过程逐个运行数据库条目。对于每个数据库条目，匹配器生成一个特殊符号，指示匹配失败，或者是帧的扩展。所有数据库条目的结果被收集到一个流中，通过过滤器传递以清除失败。结果是所有通过与数据库中某个断言的匹配扩展给定帧的所有帧的流。⁶¹
在我们的系统中，查询接受帧的输入流，并对流中的每个帧执行上述匹配操作，如图 4.5 所示。也就是说，对于输入流中的每个帧，查询生成一个新的流，其中包含通过与数据库中的断言匹配的该帧的所有扩展。然后将所有这些流组合成一个巨大的流，其中包含输入流中每个帧的所有可能扩展。这个流是查询的输出。
图 4.5 查询处理帧流。
为了回答一个简单的查询，我们使用一个输入流，其中包含一个单个的空帧的查询。生成的输出流包含对空帧的所有扩展（即，对我们查询的所有答案）。然后使用这些帧的流来生成原始查询模式的副本流，其中变量由每个帧中的值实例化，这是最终打印的流。
复合查询
当我们处理复合查询时，流式帧实现的真正优雅之处就显而易见了。复合查询的处理利用了我们的匹配器要求匹配与指定帧一致的能力。例如，处理两个查询的and，如
and(can_do_job($x, list("computer", "programmer", "trainee")), job($person, $x))
（非正式地，“找到所有能够做计算机程序员实习生工作的人”），我们首先找到所有与模式匹配的条目
can_do_job($x, list("computer", "programmer", "trainee"))
这产生了一系列帧，每个帧都包含$x的绑定。然后对于流中的每个帧，我们找到所有与之匹配的条目
job($person, $x)
以与$x的给定绑定一致的方式。每个这样的匹配都将产生一个包含$x和$person绑定的帧。两个查询的and可以被视为两个组成查询的串联组合，如图 4.6 所示。通过第一个查询过滤的帧将通过第二个查询进行进一步的过滤和扩展。
图 4.6 两个查询的and组合是通过对帧流进行串联操作而产生的。
图 4.7 显示了计算两个查询的or的类似方法，作为两个组成查询的并联组合。输入的帧流分别由每个查询单独扩展。然后合并两个结果流以产生最终的输出流。
图 4.7 两个查询的or组合是通过并行操作帧流并合并结果来产生的。
即使从这个高层描述中，处理复合查询的过程可能会很慢。例如，由于查询可能会为每个输入帧产生多个输出帧，并且and中的每个查询都从前一个查询中获取其输入帧，因此and查询在最坏的情况下可能需要执行指数数量的匹配（参见练习 4.73）。⁶² 尽管处理简单查询的系统非常实用，但处理复杂查询非常困难。⁶³
从帧流的观点来看，某些查询的not作为一个过滤器，删除所有可以满足查询的帧。例如，给定模式
not(job($x, list("computer", "programmer")))
我们尝试，对于输入流中的每个帧，产生满足job($x, list("computer", "programmer"))的扩展帧。我们从输入流中删除所有存在这样的扩展的帧。结果是一个仅由那些绑定$x不满足job($x, list("computer", "programmer"))的帧组成的流。例如，在处理查询时
and(supervisor($x, $y), not(job($x, list("computer", "programmer"))))
第一个子句将生成具有$x和$y绑定的帧。然后，not子句将通过删除所有绑定$x满足$x是计算机程序员的限制的帧来过滤这些帧。⁶⁴
javascript_predicate语法形式被实现为帧流上的类似过滤器。我们使用流中的每个帧来实例化模式中的任何变量，然后应用 JavaScript 谓词。我们从输入流中删除所有谓词失败的帧。
统一
为了处理查询语言中的规则，我们必须能够找到结论与给定查询模式匹配的规则。规则结论类似于断言，只是它们可以包含变量，因此我们需要一种称为统一的模式匹配的泛化，其中“模式”和“数据”都可以包含变量。
统一器接受两个包含常量和变量的模式，并确定是否可能为变量分配值，使得两个模式相等。如果可以，它返回一个包含这些绑定的帧。例如，统一list($x, "a", $y)和list($y, $z, "a")将指定一个帧，其中$x，$y和$z都必须绑定到"a"。另一方面，统一list($x, $y, "a")和list($x, "b", $y)将失败，因为没有值可以使两个模式相等。 （为了使模式的第二个元素相等，$y必须是"b"；然而，为了使第三个元素相等，$y必须是"a"。）查询系统中使用的统一器，就像模式匹配器一样，接受一个帧作为输入，并执行与该帧一致的统一。
统一算法是查询系统中最技术上困难的部分。对于复杂的模式，执行统一可能需要推理。要统一
list($x, $x)
和
list(list("a", $y, "c"), list("a", "b", $z))
例如，算法必须推断出$x应该是list("a", "b", "c")，$y应该是"b"，$z应该是"c"。我们可以将这个过程看作是在模式组件之间解方程组。一般来说，这些是同时方程，可能需要大量的操作来解决。⁶⁵ 例如，统一list($x, $x)和list(list("a", $y, "c"), list("a", "b", $z))可以被认为是指定同时方程
$x = list("a", $y, "c")
$x = list("a", "b", $z)
这些方程意味着
list("a", $y, "c") = list("a", "b", $z)
这反过来意味着
"a" = "a", $y = "b", "c" = $z
因此
$x = list(“a”, “b”, “c”)
在成功的模式匹配中，所有模式变量都被绑定，它们被绑定的值只包含常量。到目前为止，我们所见到的所有统一的例子也是如此。然而，一般来说，成功的统一可能并不完全确定变量的值；一些变量可能保持未绑定，而其他变量可能绑定到包含变量的值。
考虑list($x, "a")和list(list("b", $y), $z)的统一。我们可以推断$x=list("b", $y)和"a"=$z，但我们无法进一步解决$x或$y。统一不会失败，因为通过为$x和$y分配值，可以使这两个模式相等。由于这种匹配无论如何都不会限制$y可以取的值，所以不会将$y的绑定放入结果帧中。但是，这种匹配确实限制了$x的值。无论$y有什么值，$x必须是list("b", $y)。因此，将$x绑定到模式list("b", $y)放入帧中。如果以后确定了$y的值并将其添加到帧中（通过需要与此帧一致的模式匹配或统一），则先前绑定的$x将引用此值。
应用规则
统一是查询系统的组成部分，用于从规则中进行推理。要了解如何实现这一点，可以考虑处理涉及应用规则的查询，例如
lives_near($x, list("Hacker", "Alyssa", "P"))
为了处理这个查询，我们首先使用上面描述的普通模式匹配函数来查看数据库中是否有任何与这个模式匹配的断言。（在这种情况下不会有任何匹配，因为我们的数据库中没有关于谁住在附近的直接断言。）下一步是尝试将查询模式与每条规则的结论统一。我们发现模式与规则的结论统一。
rule(lives_near($person_1, $person_2), and(address($person_1, pair($town, $rest_1)), address($person_2, list($town, $rest_2)), not(same($person_1, $person_2))))
导致一个指定$x应该绑定到（具有与）$person_1相同的值，并且$person_2绑定到list("Hacker", "Alyssa", "P")的帧。现在，相对于这个帧，我们求值规则体给出的复合查询。成功的匹配将通过为$person_1提供绑定来扩展此帧，因此也会提供$x的值，我们可以用它来实例化原始查询模式。
一般来说，查询求值器在尝试在指定了一些模式变量绑定的帧中建立查询模式时，使用以下方法应用规则：
- 将查询与规则的结论统一，如果成功，形成原始帧的扩展。
- 相对于扩展帧，求值规则体形成的查询。
注意这与 JavaScript 中evaluate/apply求值器中应用函数的方法有多么相似：
- 将函数的参数绑定到其参数以形成扩展原始函数环境的帧。
- 相对于扩展环境，求值函数体形成的表达式。
这两个求值器之间的相似之处应该不足为奇。正如函数定义是 JavaScript 中的抽象手段一样，规则定义是查询语言中的抽象手段。在每种情况下，我们通过创建适当的绑定来解开抽象，并相对于这些绑定来求值规则或函数体。
简单查询
我们在本节前面看到了如何在没有规则的情况下求值简单查询。现在我们已经看到了如何应用规则，我们可以描述如何通过使用规则和断言来求值简单查询。
给定查询模式和帧流，我们为输入流中的每个帧生成两个流：
- 通过将模式与数据库中的所有断言进行匹配获得的扩展帧的流（使用模式匹配器），
- 通过应用所有可能的规则（使用统一器）获得的扩展帧的流。
将这两个流附加起来，产生的流包含了满足原始帧一致的给定模式的所有方式。这些流（每个输入流中的每个帧一个）现在都被组合成一个大流，因此包含了原始输入流中的任何帧扩展以产生与给定模式匹配的所有方式。
查询求值器和驱动循环
尽管底层匹配操作复杂，但系统的组织方式与任何语言的求值器类似。协调匹配操作的函数称为evaluate_query，它的作用类似于 JavaScript 的evaluate函数。函数evaluate_query的输入是一个查询和一个帧流。它的输出是一个帧流，对应于成功匹配查询模式的情况，这些帧扩展了输入流中的某个帧，如图 4.5 所示。与evaluate类似，evaluate_query对不同类型的表达式（查询）进行分类，并为每个类型的表达式调用适当的函数。对于每种句法形式（and、or、not和javascript_predicate）以及简单查询，都有一个函数。
驱动循环类似于本章其他求值器中的driver_loop函数，它读取用户键入的查询。对于每个查询，它调用evaluate_query，并提供查询和由单个空帧组成的流。这将产生所有可能匹配的流（所有可能的扩展到空帧的情况）。对于结果流中的每个帧，它使用帧中找到的变量的值来实例化原始查询。然后打印这些实例化的查询流。
驱动程序还检查特殊命令assert，该命令表示输入不是查询，而是要添加到数据库的断言或规则。例如，
assert(job(list("Bitdiddle", "Ben"), list("computer", "wizard"))) assert(rule(wheel($person), and(supervisor($middle_manager, $person), supervisor($x, $middle_manager))))
4.4.3 逻辑编程是数理逻辑吗？
查询语言中使用的组合方式乍看起来与数理逻辑中的“与”、“或”和“非”操作相同，事实上，查询语言规则的应用是通过一种合法的推理方法完成的。尽管如此，将查询语言与数理逻辑等同起来并不是真正有效的，因为查询语言提供了一个控制结构，以过程化方式解释逻辑语句。我们经常可以利用这种控制结构。例如，要找到所有程序员的主管，我们可以用两种逻辑上等价的形式来制定查询：
and(job($x, list("computer", "programmer")), supervisor($x, $y))
或
and(supervisor($x, $y), job($x, list("computer", "programmer")))
如果一个公司的主管比程序员多得多，最好使用第一种形式而不是第二种形式，因为数据库必须为第一个and子句产生的每个中间结果（帧）扫描。
逻辑编程的目的是为程序员提供将计算问题分解为两个独立问题的技术：“要计算什么”和“如何计算”。这是通过选择数理逻辑陈述的子集来实现的，该子集足够强大，可以描述任何想要计算的内容，但又足够弱，可以有可控的过程性解释。这里的意图是，一种逻辑编程语言中指定的程序应该是一个可以由计算机执行的有效程序。控制（“如何”计算）是通过使用语言的求值顺序来实现的。我们应该能够安排子句的顺序和每个子句内部子目标的顺序，以便以被认为是有效和高效的顺序进行计算。同时，我们应该能够将计算结果（“要计算什么”）视为逻辑法则的简单结果。
我们的查询语言可以被视为数学逻辑的一个过程可解释子集。一个断言代表一个简单的事实（一个原子命题）。规则代表规则结论成立的推论。规则有一个自然的过程解释：要建立规则的结论，要建立规则的主体。因此，规则指定了计算。然而，因为规则也可以被看作是数学逻辑的陈述，我们可以通过断言，即通过完全在数学逻辑中工作，来证明逻辑程序所完成的任何“推理”都是可以被证明的。⁷⁰
无限循环
逻辑程序的过程性解释的一个结果是，可以构建解决某些问题的无望低效程序。当系统陷入无限循环时，效率低下的极端情况发生。举个简单的例子，假设我们正在建立一个包括著名婚姻的数据库，包括
assert(married("Minnie", "Mickey"))
如果我们现在问
married("Mickey", $who)
我们将得不到任何回应，因为系统不知道如果A与B结婚，那么B也与A结婚。因此，我们断言规则
assert(rule(married($x, $y), married($y, $x)))
再次查询
married("Mickey", $who)
不幸的是，这将使系统陷入无限循环，如下所示：
- 系统发现
married规则适用；也就是说，规则结论married($x, $y)与查询模式married("Mickey", $who)统一，产生一个帧，其中$x绑定为"Mickey"，$y绑定为$who。因此，解释器继续在这个帧中求值规则主体married($y, $x)，实际上是处理查询married($who, "Mickey")。 - 一个答案，
married("Minnie", "Mickey")，直接出现在数据库中作为一个断言。 married规则也适用，因此解释器再次求值规则主体，这次等同于married("Mickey", $who)。
系统现在陷入了无限循环。实际上，系统是否会在陷入循环之前找到简单的答案married("Minnie", "Mickey")取决于关于系统检查数据库中项目顺序的实现细节。这是可以发生的循环的一种非常简单的例子。相关规则的集合可能导致更难以预料的循环，并且循环的出现可能取决于and中子句的顺序（参见练习 4.62）或关于系统处理查询的顺序的低级细节。⁷¹
not的问题
查询系统中的另一个怪癖涉及not。给定第 4.4.1 节的数据库，考虑以下两个查询：
and(supervisor($x, $y), not(job($x, list("computer", "programmer")))) and(not(job($x, list("computer", "programmer"))), supervisor($x, $y))
这两个查询不会产生相同的结果。第一个查询首先查找与supervisor($x, $y)匹配的数据库中的所有条目，然后通过删除满足job($x, list("computer", "programmer"))的值的结果帧来过滤结果。第二个查询首先通过过滤传入的帧来删除可以满足job($x, list("computer", "programmer"))的帧。由于唯一的传入帧是空的，它检查满足job($x, list("computer", "programmer"))的模式的数据库。由于通常存在这种形式的条目，not子句会过滤掉空帧并返回一个空的帧流。因此，整个复合查询返回一个空的帧流。
问题在于我们的not实现实际上是作为变量值的过滤器。如果在处理not子句时，一些变量保持未绑定（如上面的示例中的$x），系统将产生意外的结果。类似的问题也会出现在使用javascript_predicate时——如果其中一些变量未绑定，JavaScript 谓词将无法工作。参见练习 4.74。
查询语言的not与数学逻辑中的not有一种更为严重的不同之处。在逻辑中，我们解释语句“not P”表示P不是真的。然而，在查询系统中，“not P”表示P不能从数据库中的知识中推导出来。例如，给定第 4.4.1 节的人事数据，系统会愉快地推断出各种not语句，比如本·比迪德尔不是棒球迷，外面不下雨，2+2 不等于 4。换句话说，逻辑编程语言中的not反映了所谓的封闭世界假设，即所有相关信息都已包含在数据库中。
练习 4.62
路易斯·里森纳错误地从数据库中删除了outranked_by规则（第 4.4.1 节）。当他意识到这一点时，他迅速重新安装了它。不幸的是，他对规则进行了轻微更改，并将其输入为
rule(outranked_by($staff_person, $boss), or(supervisor($staff_person, $boss), and(outranked_by($middle_manager, $boss), supervisor($staff_person, $middle_manager))))
就在路易斯将这些信息输入系统后，德维特·奥尔过来询问谁的地位高于本·比迪德尔。他发出了查询
outanked_by(list("Bitdiddle", "Ben"), $who)
回答后，系统陷入无限循环。解释原因。
练习 4.63
赛伊·D·费克特期待着有一天能在组织中崛起，他提出了一个查询，以找到所有的车轮（使用第 4.4.1 节的wheel规则）：
wheel($who)
令他惊讶的是，系统的回应是
查询结果：
wheel(list("Warbucks", "Oliver")) wheel(list("Bitdiddle", "Ben")) wheel(list("Warbucks", "Oliver")) wheel(list("Warbucks", "Oliver")) wheel(list("Warbucks", "Oliver"))
为什么奥利弗·沃巴克斯被列出了四次？
练习 4.64
本一直在将查询系统概括为提供有关公司的统计信息。例如，要找到所有计算机程序员的总薪水，可以说
sum($amount, and(job($x, list("computer", "programmer")), salary($x, $amount)))
一般来说，本的新系统允许形式的表达
accumulation_function(variable, query-pattern)
其中accumulation_function可以是sum、average或maximum之类的东西。本推断实现这应该很容易。他只需将查询模式提供给evaluate_query。这将产生一系列框架。然后，他将通过一个映射函数将这个流传递给累积函数，从而提取流中每个框架的指定变量的值，并将结果流传递给累积函数。就在本完成实现并准备尝试时，赛伊路过，仍在思考练习 4.63 中wheel查询结果。当赛伊向本展示系统的回应时，本叹息道：“哦，不，我的简单累积方案行不通！”
本刚刚意识到了什么？概述他可以用来挽救情况的方法。
练习 4.65
设计一种方法，在查询系统中安装一个循环检测器，以避免文本和练习 4.62 中所示的简单循环。一般的想法是，系统应该维护其当前推断链的某种历史，并且不应该开始处理它已经在处理的查询。描述这个历史中包含的信息（模式和框架），以及应该如何进行检查。（在你研究第 4.4.4 节中的查询系统实现的细节之后，你可能想修改系统以包括你的循环检测器。）
练习 4.66
定义规则来实现练习 2.18 的reverse操作，该操作以相反的顺序返回包含与给定列表相同元素的列表。（提示：使用append_to_form。）你的规则能回答查询reverse(list(1, 2, 3), $x)和查询reverse($x, list(1, 2, 3))吗？
练习 4.67
让我们修改练习 4.61 的数据库和规则，将great添加到孙子关系中。这应该使系统能够推断出伊拉德是亚当的曾孙，或者贾伯尔和尤巴尔是亚当的曾曾曾曾曾孙。
- a.更改数据库中的断言，使得只有一种关系信息，即
related。第一项描述了关系。因此，不是son("Adam", "Cain")，而是related("son", "Adam", "Cain")。例如，表示关于 Irad 的事实为
related(list(“great”, “grandson”), “Adam”, “Irad”) - b.编写规则，确定列表是否以单词
"grandson"结尾。 - c.使用这个来表达一个允许推导关系的规则
list(pair(“great”, $rel), $x, $y)
其中$rel是以"grandson"结尾的列表。 - d.检查你的规则在查询
related(list("great", "grandson"), $g, $ggs)和related($relationship, "Adam", "Irad")上的表现。
4.4.4 实现查询系统
4.4.2 节描述了查询系统的工作原理。现在我们通过提供系统的完整实现来填写细节。
4.4.4.1 驱动循环
查询系统的驱动循环反复读取输入表达式。如果表达式是要添加到数据库中的规则或断言，那么信息就会被添加。否则，假定表达式是一个查询。驱动程序将此查询传递给evaluate_query，并与一个由单个空帧组成的初始帧流一起传递。求值的结果是通过满足在数据库中找到的变量值来生成的帧流。这些帧用于形成一个新的流，其中包含原始查询的副本，其中变量被帧流提供的值实例化，最终的流被显示：
const input_prompt = "Query input:"; const output_prompt = "Query results:"; function query_driver_loop() { const input = user_read(input_prompt) + ";"; if (is_null(input)) { display("evaluator terminated"); } else { const expression = parse(input); const query = convert_to_query_syntax(expression); if (is_assertion(query)) { add_rule_or_assertion(assertion_body(query)); display("Assertion added to data base."); } else { display(output_prompt); display_stream( stream_map( frame => unparse(instantiate_expression(expression, frame)), evaluate_query(query, singleton_stream(null)))); } return query_driver_loop(); } }
在这里，与本章中的其他求值器一样，我们使用parse将作为字符串给出的查询语言的组件转换为 JavaScript 语法表示。（我们在输入表达式字符串后附加了一个分号，因为parse期望一个语句。）然后我们进一步将语法表示转换为适合查询系统的概念级别，使用convert_to_query_syntax，它在 4.4.4.7 节中声明，以及谓词is_assertion和选择器assertion_body。函数add_rule_or_assertion在 4.4.4.5 节中声明。查询求值产生的帧用于实例化语法表示，结果被解析成字符串进行显示。函数instantiate_expression和unparse在 4.4.4.7 节中声明。
4.4.4.2 求值器
evaluate_query函数由query_driver_loop调用，是查询系统的基本求值器。它以查询和帧流作为输入，并返回扩展帧的流。它通过使用get和put进行数据导向分派来识别句法形式，就像我们在第 2 章中实现通用操作一样。任何未被识别为句法形式的查询都被假定为简单查询，由simple_query处理。
function evaluate_query(query, frame_stream) { const qfun = get(type(query), "evaluate_query"); return is_undefined(qfun) ? simple_query(query, frame_stream) : qfun(contents(query), frame_stream); }
函数type和contents在 4.4.4.7 节中定义，实现了句法形式的抽象语法。
简单查询
simple_query函数处理简单查询。它以简单查询（模式）和帧流作为参数，并返回通过扩展每个帧的所有数据库匹配项形成的流。
function simple_query(query_pattern, frame_stream) { return stream_flatmap( frame => stream_append_delayed( find_assertions(query_pattern, frame), () => apply_rules(query_pattern, frame)), frame_stream); }
对于输入流中的每个框架，我们使用find_assertions（第 4.4.4.3 节）来匹配数据库中所有断言与模式，产生一个扩展框架的流，并使用apply_rules（第 4.4.4.4 节）来应用所有可能的规则，产生另一个扩展框架的流。这两个流被合并（使用stream_append_delayed，第 4.4.4.6 节）以生成给定模式可以满足的所有方式的流，与原始框架一致（参见练习 4.68）。输入框架的流使用stream_flatmap（第 4.4.4.6 节）组合，形成一个大的流，列出原始输入流中任何框架可以扩展以与给定模式匹配的所有方式。
复合查询
我们处理and查询，如图 4.6 所示，使用conjoin函数，它以连接词和框架流作为输入，并返回扩展框架的流。首先，conjoin处理框架流以找到满足连接词中第一个查询的所有可能框架扩展的流。然后，使用这个新的框架流，它递归地将conjoin应用于其余的查询。
function conjoin(conjuncts, frame_stream) { return is_empty_conjunction(conjuncts) ? frame_stream : conjoin(rest_conjuncts(conjuncts), evaluate_query(first_conjunct(conjuncts), frame_stream)); }
陈述
put("and", "evaluate_query", conjoin);
设置evaluate_query以在遇到and时分派到conjoin。
我们类似地处理or查询，如图 4.7 所示。or的各个分离词的输出流分别计算，并使用第 4.4.4.6 节中的interleave_delayed函数合并。（参见练习 4.68 和 4.69。）
function disjoin(disjuncts, frame_stream) { return is_empty_disjunction(disjuncts) ? null : interleave_delayed( evaluate_query(first_disjunct(disjuncts), frame_stream), () => disjoin(rest_disjuncts(disjuncts), frame_stream)); } put("or", "evaluate_query", disjoin);
在第 4.4.4.7 节中给出了表示连接词和分离词的谓词和选择器。
NUS CS1101S：SICP JavaScript 描述：四、元语言抽象（5）https://developer.aliyun.com/article/1427738
