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

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

过滤器

not语法形式由第 4.4.2 节中概述的方法处理。我们尝试扩展输入流中的每个框架以满足被否定的查询，并且只有在不能扩展时才将给定框架包含在输出流中。

function negate(exps, frame_stream) {
    return stream_flatmap(
               frame =>
                 is_null(evaluate_query(negated_query(exps),
                                        singleton_stream(frame)))
                 ? singleton_stream(frame)
                 : null, frame_stream);
}
put("not", "evaluate_query", negate);

javascript_predicate语法形式类似于not的过滤器。流中的每个框架用于实例化谓词中的变量，实例化的谓词被求值，谓词求值为false的框架被过滤出输入流。使用evaluate（第 4.1 节）从the_global_environment求值实例化的谓词，因此可以处理任何 JavaScript 表达式，只要在求值之前实例化所有模式变量。

function javascript_predicate(exps, frame_stream) {
    return stream_flatmap(
               frame =>
                 evaluate(instantiate_expression(
                              javascript_predicate_expression(exps),
                              frame),
                          the_global_environment)
                 ? singleton_stream(frame)
                 : null,
               frame_stream);
}
put("javascript_predicate", "evaluate_query", javascript_predicate);

always_true语法形式提供了一个始终满足的查询。它忽略其内容（通常为空），并简单地通过输入流中的所有框架。rule_body选择器（第 4.4.4.7 节）使用always_true为没有定义体的规则提供体（即，始终满足的规则）。

function always_true(ignore, frame_stream) {
    return frame_stream;
}
put("always_true", "evaluate_query", always_true);

定义not和javascript_predicate的选择器在第 4.4.4.7 节中给出。

4.4.4.3 通过模式匹配查找断言

函数find_assertions由simple_query（第 4.4.4.2 节）调用，以模式和框架作为输入。它返回一个框架流，每个框架都通过给定模式的数据库匹配扩展给定框架。它使用fetch_assertions（第 4.4.4.5 节）获取数据库中所有断言的流，应该检查这些断言是否与模式和框架匹配。这里使用fetch_assertions的原因是我们通常可以应用简单的测试来消除数据库中的许多条目，使其不再是成功匹配的候选项。如果我们消除了fetch_assertions并简单地检查数据库中所有断言的流，系统仍然可以工作，但计算效率会降低，因为我们需要对匹配器进行更多的调用。

function find_assertions(pattern, frame) {
    return stream_flatmap(
                datum => check_an_assertion(datum, pattern, frame),
                fetch_assertions(pattern, frame));
}

函数check_an_assertion以数据对象（断言）、模式和框架作为参数，并返回一个包含扩展框架的单元素流，或者如果匹配失败则返回null。

function check_an_assertion(assertion, query_pat, query_frame) {
    const match_result = pattern_match(query_pat, assertion,
                                       query_frame);
    return match_result === "failed"
           ? null
           : singleton_stream(match_result);
}

基本模式匹配器返回字符串failed或给定框架的扩展。匹配器的基本思想是逐个元素地检查模式与数据，累积模式变量的绑定。如果模式和数据对象相同，则匹配成功，我们返回迄今为止累积的绑定框架。否则，如果模式是一个变量（由 4.4.4.7 节中声明的is_variable函数检查），我们通过将变量绑定到数据来扩展当前框架，只要这与框架中已有的绑定一致。如果模式和数据都是对，我们（递归地）将模式的头与数据的头进行匹配以产生一个框架；然后在这个框架中，我们将模式的尾与数据的尾进行匹配。如果这些情况都不适用，则匹配失败，我们返回字符串failed。

function pattern_match(pattern, data, frame) {
    return frame === "failed"
           ? "failed"
           : equal(pattern, data)
           ? frame
           : is_variable(pattern)
           ? extend_if_consistent(pattern, data, frame)
           : is_pair(pattern) && is_pair(data)
           ? pattern_match(tail(pattern),
                           tail(data),
                           pattern_match(head(pattern),
                                         head(data),
                                         frame))
           : "failed";
}

这是一个通过添加新绑定来扩展框架的函数，如果这与框架中已有的绑定一致的话：

function extend_if_consistent(variable, data, frame) {
    const binding = binding_in_frame(variable, frame);
    return is_undefined(binding)
           ? extend(variable, data, frame)
           : pattern_match(binding_value(binding), data, frame);
}

如果框架中没有变量的绑定，我们只需将变量的绑定添加到数据中。否则，我们在框架中将数据与框架中变量的值进行匹配。如果存储的值只包含常量，那么它必须在模式匹配期间由extend_if_consistent存储，匹配只是简单地测试存储的值和新值是否相同。如果是，则返回未修改的框架；如果不是，则返回失败指示。然而，存储的值可能包含模式变量，如果它是在统一期间存储的（见 4.4.4.4 节）。存储的模式与新数据的递归匹配将为这个模式中的变量添加或检查绑定。例如，假设我们有一个框架，其中$x绑定到list("f", $y)，而$y未绑定，我们希望通过将$x绑定到list("f", "b")来扩充这个框架。我们查找$x并发现它绑定到list("f", $y)。这导致我们在同一个框架中将list("f", $y)与建议的新值list("f", "b")进行匹配。最终，这个匹配通过添加$y绑定到"b"来扩展框架。变量$x仍然绑定到list("f", $y)。我们从不修改存储的绑定，也不会为给定变量存储多个绑定。

extend_if_consistent使用的函数来操作绑定在 4.4.4.8 节中定义。

4.4.4.4 规则和统一

函数apply_rules是find_assertions（4.4.4.3 节）的规则类比。它以模式和框架作为输入，并通过应用来自数据库的规则形成一个扩展框架流。函数stream_flatmap将apply_a_rule映射到可能适用的规则流（由fetch_rules选择，4.4.4.5 节），并组合结果框架的流。

function apply_rules(pattern, frame) {
    return stream_flatmap(rule => apply_a_rule(rule, pattern, frame),
                          fetch_rules(pattern, frame));
}

函数apply_a_rule使用 4.4.2 节中概述的方法应用规则。它首先通过将规则结论与给定框架中的模式统一来扩充其参数框架。如果成功，它就在这个新框架中求值规则主体。

然而，在发生这些情况之前，程序会将规则中的所有变量重命名为唯一的新名称。这样做的原因是为了防止不同规则应用的变量相互混淆。例如，如果两个规则都使用名为$x的变量，那么每个规则在应用时可能都会向框架中添加一个$x的绑定。这两个$x互不相关，我们不应该被误导以为这两个绑定必须一致。我们可以设计一个更聪明的环境结构来代替重命名变量；然而，我们选择的重命名方法是最直接的，即使不是最有效的（见练习 4.76）。这里是apply_a_rule函数：

function apply_a_rule(rule, query_pattern, query_frame) {
    const clean_rule = rename_variables_in(rule);
    const unify_result = unify_match(query_pattern,
                                     conclusion(clean_rule),
                                     query_frame);
    return unify_result === "failed"
           ? null
           : evaluate_query(rule_body(clean_rule),
                            singleton_stream(unify_result));
}

提取规则的部分的选择器rule_body和conclusion在 4.4.4.7 节中定义。

我们通过将唯一标识符（如数字）与每个规则应用关联，并将此标识符与原始变量名结合起来来生成唯一的变量名。例如，如果规则应用标识符为 7，我们可能会将规则中的每个$x更改为$x_7，将规则中的每个$y更改为$y_7。（函数make_new_variable和new_rule_application_id包含在第 4.4.4.7 节的语法函数中。）

function rename_variables_in(rule) {
    const rule_application_id = new_rule_application_id();
    function tree_walk(exp) {
        return is_variable(exp)
               ? make_new_variable(exp, rule_application_id)
               : is_pair(exp)
               ? pair(tree_walk(head(exp)),
                      tree_walk(tail(exp)))
               : exp;
    }
    return tree_walk(rule);
}

统一算法被实现为一个函数，它以两个模式和一个框架作为输入，并返回扩展的框架或字符串"failed"。统一器类似于模式匹配器，只是它是对称的 - 变量允许在匹配的两侧。函数unify_match基本上与pattern_match相同，只是下面有一个额外的子句（标记为***），用于处理右侧对象为变量的情况。

function unify_match(p1, p2, frame) {
    return frame === "failed"
           ? "failed"
           : equal(p1, p2)
           ? frame
           : is_variable(p1)
           ? extend_if_possible(p1, p2, frame)
           : is_variable(p2) // *
           ? extend_if_possible(p2, p1, frame) // *
           : is_pair(p1) && is_pair(p2)
           ? unify_match(tail(p1),
                         tail(p2),
                         unify_match(head(p1),
                                     head(p2),
                                     frame))
           : "failed";
}

在统一中，就像单向模式匹配一样，我们只希望接受框架的提议扩展，只有当它与现有绑定一致时才会这样。在统一中使用的函数extend_if_possible与模式匹配中使用的函数extend_if_consistent相同，只是在程序中有两个特殊检查，标记为***。在第一种情况下，如果我们尝试匹配的变量未绑定，但我们尝试匹配的值本身是（不同的）变量，则有必要检查该值是否已绑定，并且如果是，则匹配其值。如果匹配的双方都未绑定，我们可以将其中一个绑定到另一个。

第二个检查处理尝试将变量绑定到包含该变量的模式的情况。只要在两个模式中重复一个变量，这种情况就会发生。例如，考虑在两个模式list($x, $x)和list($y, 包含 $y 的表达式)中统一，在其中$x和$y都未绑定的框架中。首先，将$x与$y匹配，将$x绑定到$y。接下来，将相同的$x与包含$y的给定表达式匹配。由于$x已绑定到$y，这导致将$y与表达式匹配。如果我们认为统一器是在找到一组使模式相同的模式变量的值，那么这些模式暗示了查找一个$y，使得$y等于包含$y的表达式。我们拒绝这样的绑定；这些情况由谓词depends_on识别。另一方面，我们不希望拒绝将变量绑定到自身的尝试。例如，考虑统一list($x, $x)和list($y, $y)。将$x绑定到$y的第二次尝试将$y（$x的存储值）与$y（$x的新值）匹配。这由unify_match的equal子句处理。

function extend_if_possible(variable, value, frame) {
    const binding = binding_in_frame(variable, frame);
    if (! is_undefined(binding)) {
        return unify_match(binding_value(binding),
                            value, frame);
    } else if (is_variable(value)) { // *
         const binding = binding_in_frame(value, frame);
        return ! is_undefined(binding)
               ? unify_match(variable,
                             binding_value(binding),
                             frame)
               : extend(variable, value, frame);
    } else if (depends_on(value, variable, frame)) { // *
        return "failed";
    } else {
        return extend(variable, value, frame);
    }
}

函数depends_on是一个谓词，用于测试提议作为模式变量值的表达式是否依赖于该变量。这必须相对于当前框架来完成，因为表达式可能包含已经依赖于我们测试变量的值的变量的出现。depends_on的结构是一个简单的递归树遍历，我们在必要时替换变量的值。

function depends_on(expression, variable, frame) {
    function tree_walk(e) {
        if (is_variable(e)) {
            if (equal(variable, e)) {
                return true;
            } else {
                const b = binding_in_frame(e, frame);
                return is_undefined(b)
                       ? false
                       : tree_walk(binding_value(b));
            }
        } else {
            return is_pair(e)
                   ? tree_walk(head(e)) || tree_walk(tail(e))
                   : false;
        }
    }
    return tree_walk(expression);
}

4.4.4.5 维护数据库

设计逻辑编程语言的一个重要问题是安排事物，以便在检查给定模式时尽可能少地检查不相关的数据库条目。为此，我们将断言表示为一个列表，其头部是表示断言信息类型的字符串。我们将断言存储在单独的流中，每种信息类型一个流，在一个由信息类型索引的表中。要获取可能匹配模式的断言，我们返回（以便使用匹配器进行测试）所有具有相同头部（相同信息类型）的存储断言。更聪明的方法也可以利用帧中的信息。我们避免构建用于索引程序的标准；相反，我们调用体现我们标准的谓词和选择器。

function fetch_assertions(pattern, frame) {
    return get_indexed_assertions(pattern);
}
function get_indexed_assertions(pattern) {
    return get_stream(index_key_of(pattern), "assertion-stream");
}

get_stream函数在表中查找流，并在没有存储内容时返回一个空的流。

function get_stream(key1, key2) {
    const s = get(key1, key2);
    return is_undefined(s) ? null : s;
}

规则也是类似地存储，使用规则结论的头部。一个模式可以匹配具有相同头部的规则结论的规则。因此，当获取可能匹配模式的规则时，我们获取所有结论具有与模式相同头部的规则。

function fetch_rules(pattern, frame) {
    return get_indexed_rules(pattern);
}
function get_indexed_rules(pattern) {
    return get_stream(index_key_of(pattern), "rule-stream");
}

add_rule_or_assertion函数由query_driver_loop用于向数据库添加断言和规则。每个项目都存储在索引中。

function add_rule_or_assertion(assertion) {
    return is_rule(assertion)
           ? add_rule(assertion)
           : add_assertion(assertion);
}
function add_assertion(assertion) {
    store_assertion_in_index(assertion);
    return "ok";
}
function add_rule(rule) {
    store_rule_in_index(rule);
    return "ok";
}

要实际存储断言或规则，我们将其存储在适当的流中。

function store_assertion_in_index(assertion) {
    const key = index_key_of(assertion);
    const current_assertion_stream =
                get_stream(key, "assertion-stream");
    put(key, "assertion-stream",
        pair(assertion, () => current_assertion_stream));
}
function store_rule_in_index(rule) {
    const pattern = conclusion(rule);
    const key = index_key_of(pattern);
    const current_rule_stream =
                get_stream(key, "rule-stream");
    put(key, "rule-stream",
        pair(rule, () => current_rule_stream));
}

模式（断言或规则结论）存储在表中的键是它以字符串开头的字符串。

function index_key_of(pattern) { return head(pattern); }

4.4.4.6 流操作

查询系统使用了一些流操作，这些操作在第 3 章中没有介绍。stream_append_delayed和interleave_delayed函数与stream_append和interleave（第 3.5.3 节）类似，只是它们接受了一个延迟参数（就像第 3.5.4 节中的integral函数）。这在某些情况下会推迟循环（参见练习 4.68）。

function stream_append_delayed(s1, delayed_s2) {
    return is_null(s1)
           ? delayed_s2()
           : pair(head(s1),
                  () => stream_append_delayed(stream_tail(s1),
                                              delayed_s2));
}
function interleave_delayed(s1, delayed_s2) {
    return is_null(s1)
           ? delayed_s2()
           : pair(head(s1),
                  () => interleave_delayed(delayed_s2(),
                                           () => stream_tail(s1)));
}

stream_flatmap函数在查询求值器中用于在帧流上映射函数并组合结果帧流，它是第 2.2.3 节中为普通列表引入的flatmap函数的流模拟。然而，与普通的flatmap不同，我们使用交错过程累积流，而不是简单地追加它们（参见练习 4.69 和 4.70）。

function stream_flatmap(fun, s) {
    return flatten_stream(stream_map(fun, s));
}
function flatten_stream(stream) {
    return is_null(stream)
           ? null
           : interleave_delayed(
                  head(stream),
                  () => flatten_stream(stream_tail(stream)));
}

求值器还使用以下简单函数生成由单个元素组成的流：

function singleton_stream(x) {
    return pair(x, () => null);
}

4.4.4.7 查询语法函数和实例化

我们在第 4.4.4.1 节中看到，驱动循环首先将输入字符串转换为 JavaScript 语法表示。输入被设计成看起来像 JavaScript 表达式，以便我们可以使用第 4.1.2 节中的parse函数，并且还支持javascript_predicate中的 JavaScript 表示。例如，

parse('job($x, list("computer", "wizard"));');

产生

list("application",
     list("name", "job"),
     list(list("name", "$x"),
          list("application",
               list("name", "list"),
               list(list("literal", "computer"),
                    list("literal", "wizard")))))

标签"application"表示，从语法上讲，查询将被视为 JavaScript 中的函数应用。函数unparse将语法转换回字符串：

unparse(parse('job($x, list("computer", "wizard"));'));
'job($x, list("computer", "wizard"))'

在查询处理器中，我们假设了断言、规则和查询的查询语言特定表示。函数convert_to_query_syntax将语法表示转换为该表示。使用相同的示例，

convert_to_query_syntax(parse('job($x, list("computer", "wizard"));'));

产生

list(“job”, list(“name”, “$x”), list(“computer”, “wizard”))

查询系统函数，如第 4.4.4.5 节中的add_rule_or_assertion和第 4.4.4.2 节中的evaluate_query，使用下面声明的选择器和谓词，如type、contents、is_rule和first_conjunct，对查询语言特定表示进行操作。图 4.8 描述了查询系统使用的三个抽象屏障以及转换函数parse、unparse和convert_to_query_syntax如何连接它们。

图 4.8 查询系统中的语法抽象。

处理模式变量

在查询处理过程中，谓词is_variable用于查询语言特定表示，并在实例化过程中用于 JavaScript 语法表示，以识别以美元符号开头的名称。我们假设有一个char_at函数，它返回一个字符串，该字符串仅包含给定位置的给定字符串的字符。⁷⁵

function is_variable(exp) {
    return is_name(exp) && char_at(symbol_of_name(exp), 0) === "$";
}

唯一变量是通过规则应用（在 4.4.4.4 节）中的以下函数构建的。规则应用的唯一标识符是一个数字，每次应用规则时都会递增。⁷⁶

let rule_counter = 0;
function new_rule_application_id() { 
    rule_counter = rule_counter + 1;
    return rule_counter;
}
function make_new_variable(variable, rule_application_id) {
    return make_name(symbol_of_name(variable) + "_" +
                     stringify(rule_application_id));
}

函数`convert_to_query_syntax`

函数convert_to_query_syntax通过简化断言、规则和查询，将 JavaScript 语法表示递归转换为查询语言特定表示，使得应用程序的函数表达式中的名称的符号成为标记，除非该符号是"pair"或"list"，则构建一个（未标记的）JavaScript 对或列表。这意味着convert_to_query_syntax在转换过程中解释构造函数pair和list的应用，并且处理函数（如 4.4.4.3 节的pattern_match和 4.4.4.4 节的unify_match）可以直接操作预期的对和列表，而不是在解析器生成的语法表示上进行操作。javascript_predicate的（单元素）“参数”列表保持未处理，如下所述。变量保持不变，文字简化为其包含的原始值。

function convert_to_query_syntax(exp) {
   if (is_application(exp)) {
     const function_symbol = symbol_of_name(function_expression(exp));
     if (function_symbol === "javascript_predicate") {
       return pair(function_symbol, arg_expressions(exp));
     } else {
       const processed_args = map(convert_to_query_syntax,
                                  arg_expressions(exp));
       return function_symbol === "pair"
              ? pair(head(processed_args), head(tail(processed_args)))
              : function_symbol === "list"
              ? processed_args
              : pair(function_symbol, processed_args);
     }
   } else if (is_variable(exp)) {
     return exp;
   } else { // exp is literal
     return literal_value(exp);
   }
}

对此处理的一个例外是javascript_predicate。由于其谓词表达式的实例化 JavaScript 语法表示被传递给 4.1.1 节的evaluate，来自parse的原始语法表示需要保持在表达式的查询语言特定表示中。在 4.4.1 节的这个例子中

and(salary($person, $amount), javascript_predicate($amount > 50000))

convert_to_query_syntax生成一个数据结构，其中 JavaScript 语法表示嵌入在查询语言特定表示中：

list("and",
     list("salary", list("name", "$person"), list("name", "$amount")),
     list("javascript_predicate",
          list("binary_operator_combination",
               ">",
               list("name", "$amount"),
               list("literal", 50000))))

为了求值已处理查询的javascript_predicate子表达式，4.4.4.2 节的函数javascript_predicate调用嵌入的 JavaScript 语法表示的$amount > 50000的instantiate_expression（下文）来替换变量list("name", "$amount")为一个文字，例如list("literal", 70000)，表示$amount绑定的原始值，这里是 70000。JavaScript 求值器可以求值实例化的谓词，现在表示为70000 > 50000。

表达式的实例化

4.4.4.2 节的函数javascript_predicate和 4.4.4.1 节的驱动循环在表达式上调用instantiate_expression，以获得一个副本，其中表达式中的任何变量都被给定帧中的值替换。输入和结果表达式使用 JavaScript 语法表示，因此从实例化变量中得到的任何值都需要从其在绑定中的形式转换为 JavaScript 语法表示。

function instantiate_expression(expression, frame) {
   return is_variable(expression)
          ? convert(instantiate_term(expression, frame))
          : is_pair(expression)
          ? pair(instantiate_expression(head(expression), frame),
                 instantiate_expression(tail(expression), frame))
          : expression;
}

函数instantiate_term以变量、对或原始值作为第一个参数，并以帧作为第二个参数，并递归地将第一个参数中的变量替换为帧中的值，直到达到原始值或未绑定变量。当过程遇到对时，将构造一个新的对，其部分是原始部分的实例化版本。例如，如果在帧f中将$x绑定到对[$y, 5]，并且$y又绑定到 3，那么将instantiate_term应用于list("name", "$x")和f的结果是对[3, 5]。

function instantiate_term(term, frame) {
    if (is_variable(term)) {
        const binding = binding_in_frame(term, frame);
        return is_undefined(binding)
              ? term // leave unbound variable as is
           : instantiate_term(binding_value(binding), frame);
    } else if (is_pair(term)) {
        return pair(instantiate_term(head(term), frame),
                    instantiate_term(tail(term), frame));
    } else { // term is a primitive value
        return term;
    }
}

函数convert构造了一个 JavaScript 语法表示，用于instantiate_term返回的变量、对或原始值。原始中的一对变成了 JavaScript 的对构造函数的应用，原始值变成了文字。

function convert(term) {
    return is_variable(term)
           ? term
           : is_pair(term)
           ? make_application(make_name("pair"),
                              list(convert(head(term)),
                                   convert(tail(term))))
           : // term is a primitive value
             make_literal(term);
}

为了说明这三个函数，考虑查询时发生的情况

job($x, list("computer", "wizard"))

其 JavaScript 语法表示在第 4.4.4.7 节开头给出，由驱动循环处理。假设结果流的帧g将变量$x绑定到["Bitdiddle", $y]，变量$y绑定到["Ben", null]。

instantiate_term(list("name", "$x"), g)

返回列表

list("Bitdiddle", "Ben")

将convert转换为

list("application",
     list("name", "pair"),
     list(list("literal", "Bitdiddle"),
          list("application",
               list("name", "pair"),
               list(list("literal", "Ben"),
                    list("literal", null)))))

应用于查询的 JavaScript 语法表示和帧g的instantiate_expression的结果是：

list("application",
     list("name", "job"),
     list(list("application",
               list("name", "pair"),
               list(list("literal", "Bitdiddle"),
                    list("application",
                         list("name", "pair"),
                         list(list("literal", "Ben"),
                              list("literal", null))))),
          list("application",
               list("name", "list"),
               list(list("literal", "computer"),
                    list("literal", "wizard")))))

驱动循环取消解析此表示并将其显示为：

'job(list("Bitdiddle", "Ben"), list("computer", "wizard"))'

函数`unparse`

函数unparse通过应用第 4.1.2 节的语法规则将给定的 JavaScript 语法表示转换为字符串。我们仅描述了unparse用于第 4.4.1 节示例中出现的那些表达式的类型，将语句和其余类型的表达式留给练习 4.2。通过stringifying其值来转换文字，将名称转换为其符号。应用通过取消解析函数表达式格式化，我们可以假定这里是一个名称，后面跟着用括号括起来的逗号分隔的参数表达式字符串。二元运算符组合使用中缀表示法格式化。

function unparse(exp) {
    return is_literal(exp)
           ? stringify(literal_value(exp))
           : is_name(exp)
           ? symbol_of_name(exp)
           : is_list_construction(exp)
           ? unparse(make_application(make_name("list"),
                                      element_expressions(exp)))
           : is_application(exp) && is_name(function_expression(exp))
           ? symbol_of_name(function_expression(exp)) +
                 "(" +
                 comma_separated(map(unparse, arg_expressions(exp))) +
                 ")"
           : is_binary_operator_combination(exp)
           ? "(" + unparse(first_operand(exp)) +
             " " + operator_symbol(exp) +
             " " + unparse(second_operand(exp)) +
             ")"
           〈unparsing other kinds of JavaScript components〉
           : error(exp, "unknown syntax – unparse");
}
function comma_separated(strings) {
    return accumulate((s, acc) => s + (acc === "" ? "" : ", " + acc),
                      "",
                      strings);
}

函数unparse可以在没有子句的情况下正常工作

: is_list_construction(exp)
? unparse(make_application(make_name("list"),
                           element_expressions(exp)))

但在模式变量由列表实例化的情况下，输出字符串将是不必要冗长的。在上面的例子中，处理查询

job($x, list("computer", "wizard"))

产生将$x绑定到["Bitdiddle", ["Ben", null]]的帧，unparse产生

'job(list("Bitdiddle", "Ben"), list("computer", "wizard"))'

但是，如果没有子句，它将产生

'job(pair("Bitdiddle", pair("Ben", null)), list("computer", "wizard"))'

明确构造了构成第一个列表的两个对。为了实现第 4.4.1 节中使用的更简洁的格式，我们插入了一个子句来检查表达式是否构造了一个列表，如果是的话，我们将其格式化为list的单个应用，该应用是我们从表达式中提取的元素表达式的列表。列表构造是文字null或pair的应用，其第二个参数本身是列表构造。

function is_list_construction(exp) {
    return (is_literal(exp) && is_null(literal_value(exp))) ||
           (is_application(exp) && is_name(function_expression(exp)) &&
            symbol_of_name(function_expression(exp)) === "pair" &&
            is_list_construction(head(tail(arg_expressions(exp)))));
}

从给定的列表构造中提取元素表达式相当于收集pair的应用的第一个参数，直到达到文字null。

function element_expressions(list_constr) {
    return is_literal(list_constr)
           ? null // list_constr is literal null
           :      // list_constr is application of pair
             pair(head(arg_expressions(list_constr)),
                  element_expressions(
                      head(tail(arg_expressions(list_constr)))));
}

查询语言特定表示的谓词和选择器

函数type和contents，由evaluate_query（第 4.4.4.2 节）使用，指定了查询语言特定表示的句法形式由其头部的字符串标识。它们与第 2.4.2 节中的type_tag和contents函数相同，只是错误消息不同。

function type(exp) {
    return is_pair(exp)
           ? head(exp)
           : error(exp, "unknown expression type");
}
function contents(exp) {
    return is_pair(exp)
           ? tail(exp)
           : error(exp, "unknown expression contents");
}

以下函数由query_driver_loop（第 4.4.4.1 节）使用，指定规则和断言通过assert命令添加到数据库中，函数convert_to_query_syntax将其转换为形式的一对["assert", rule-or-assertion]：

function is_assertion(exp) {
    return type(exp) === "assert";
}
function assertion_body(exp) { return head(contents(exp)); }

以下是and、or、not和javascript_predicate语法形式（第 4.4.4.2 节）的谓词和选择器的声明：

function is_empty_conjunction(exps) { return is_null(exps); }
function first_conjunct(exps) { return head(exps); }
function rest_conjuncts(exps) { return tail(exps); }
function is_empty_disjunction(exps) { return is_null(exps); }
function first_disjunct(exps) { return head(exps); }
function rest_disjuncts(exps) { return tail(exps); }
function negated_query(exps) { return head(exps); }
function javascript_predicate_expression(exps) { return head(exps); }

以下三个函数定义了查询语言特定规则的表示：

function is_rule(assertion) {
    return is_tagged_list(assertion, "rule");
}
function conclusion(rule) { return head(tail(rule)); }
function rule_body(rule) {
    return is_null(tail(tail(rule)))
           ? list("always_true")
           : head(tail(tail(rule)));
}

4.4.4.8 帧和绑定

帧被表示为绑定的列表，绑定是变量-值对：

function make_binding(variable, value) {
    return pair(variable, value);
}
function binding_variable(binding) {
    return head(binding);
}
function binding_value(binding) {
    return tail(binding);
}
function binding_in_frame(variable, frame) {
    return assoc(variable, frame);
}
function extend(variable, value, frame) {
    return pair(make_binding(variable, value), frame);
}

练习 4.68

路易斯·里森纳想知道为什么simple_query和disjoin函数（第 4.4.4.2 节）是使用延迟表达式实现的，而不是定义如下：

function simple_query(query_pattern, frame_stream) {
    return stream_flatmap(
               frame =>
                 stream_append(find_assertions(query_pattern, frame),
                               apply_rules(query_pattern, frame)),
               frame_stream);
}
function disjoin(disjuncts, frame_stream) {
    return is_empty_disjunction(disjuncts)
           ? null
           : interleave(
                  evaluate_query(first_disjunct(disjuncts), frame_stream),
                  disjoin(rest_disjuncts(disjuncts), frame_stream));
}

您能举例说明这些更简单的定义会导致不良行为的查询吗？

练习 4.69

为什么disjoin和stream_flatmap交错流而不是简单地附加它们？给出说明交错效果更好的例子。（提示：为什么我们在 3.5.3 节中使用interleave？）

练习 4.70

flatten_stream为什么在其主体中使用延迟表达式？以下定义它会有什么问题：

function flatten_stream(stream) {
    return is_null(stream)
           ? null
           : interleave(head(stream),
                        flatten_stream(stream_tail(stream)));
}

练习 4.71

Alyssa P. Hacker 建议在negate，javascript_predicate和find_assertions中使用stream_flatmap的简化版本。她观察到在这些情况下映射到帧流中的函数总是产生空流或单例流，因此在组合这些流时不需要交错。

a. 填写 Alyssa 程序中的缺失表达式。

function simple_stream_flatmap(fun, s) {
    return simple_flatten(stream_map(fun, s));
}
function simple_flatten(stream) {
    return stream_map(〈??〉,
                      stream_filter(〈??〉, stream));
}

b. 如果我们以这种方式改变它，查询系统的行为会改变吗？

练习 4.72

为查询语言实现一个名为unique的语法形式。unique的应用应该成功，如果数据库中满足指定查询的项目恰好有一个。例如，

unique(job($x, list("computer", "wizard")))

应该打印一个项目流

unique(job(list("Bitdiddle", "Ben"), list("computer", "wizard")))

由于 Ben 是唯一的计算机巫师，而

unique(job($x, list("computer", "programmer")))

应该打印空流，因为有不止一个计算机程序员。此外，

and(job($x, $j), unique(job($anyone, $j)))

应列出所有只由一个人填写的工作以及填写它们的人。

实现unique有两个部分。第一部分是编写处理这种语法形式的函数，第二部分是使evaluate_query分派到该函数。第二部分是微不足道的，因为evaluate_query以数据导向的方式进行分派。如果您的函数被称为uniquely_asserted，您只需要

put("unique", "evaluate_query", uniquely_asserted);

和evaluate_query将为每个type（头）为字符串"unique"的查询分派到此函数。

真正的问题是编写函数uniquely_asserted。这应该将unique查询的contents（尾部）作为输入，以及一系列帧的流。对于流中的每个帧，它应该使用evaluate_query来查找满足给定查询的所有扩展帧的流。任何流中不恰好有一个项目的流都应该被消除。剩下的流应该被传回来累积成一个大流，这是unique查询的结果。这类似于not语法形式的实现。

通过形成一个列出监督恰好一个人的所有人的查询来测试您的实现。

练习 4.73

我们将and的实现作为查询的系列组合（图 4.6）是优雅的，但效率低下，因为在处理and的第二个查询时，我们必须为第一个查询产生的每个帧扫描数据库。如果数据库有N个元素，并且典型查询产生的输出帧数量与N成比例（比如N / k），那么为了处理第一个查询产生的每个帧，需要N²/k次模式匹配器调用。另一种方法是分别处理and的两个子句，然后寻找所有兼容的输出帧对。如果每个查询产生N / k个输出帧，那么这意味着我们必须执行N²/k²个兼容性检查——比我们当前方法所需的匹配次数少k倍。

设计一个使用这种策略的and的实现。您必须实现一个函数，该函数以两个帧作为输入，检查帧中的绑定是否兼容，如果是，则生成一个合并两组绑定的帧。此操作类似于统一。

练习 4.74

在第 4.4.3 节中，我们看到not和javascript_predicate可能会导致查询语言在应用到变量未绑定的帧时给出“错误”的答案。想出一种修复这个缺点的方法。一个想法是通过向帧附加一个“承诺”来进行“延迟”过滤，只有当足够的变量被绑定时才能实现过滤操作。我们可以等到执行所有其他操作之后再执行过滤。然而，出于效率的考虑，我们希望尽快进行过滤，以减少生成的中间帧的数量。

练习 4.75

将查询语言重新设计为一个非确定性程序，以使用第 4.3 节的求值器来实现，而不是作为一个流程过程。在这种方法中，每个查询将产生一个单一的答案（而不是所有答案的流），用户可以输入retry来查看更多答案。你会发现，我们在本节构建的许多机制都被非确定性搜索和回溯所包含。然而，你可能也会发现，你的新查询语言在行为上有微妙的差异。你能找到一些例子来说明这种差异吗？

练习 4.76

当我们在第 4.1 节实现 JavaScript 求值器时，我们看到了如何使用局部环境来避免函数参数之间的名称冲突。例如，在求值中

function square(x) {
    return x * x;
}
function sum_of_squares(x, y) {
    return square(x) + square(y);
}
sum_of_squares(3, 4);

在square和sum_of_squares中的x之间没有混淆，因为我们在一个特别构造的环境中求值每个函数的主体，该环境包含局部名称的绑定。在查询系统中，我们使用了一种不同的策略来避免在应用规则时出现名称冲突。每次应用规则时，我们都会使用新的名称对变量进行重命名，这些名称保证是唯一的。对于 JavaScript 求值器的类似策略将是放弃局部环境，而是在应用函数时每次重命名函数的主体中的变量。

为查询语言实现一个使用环境而不是重命名的规则应用方法。看看你是否可以在你的环境结构上构建，以创建处理大型系统的查询语言构造，比如块结构函数的规则类比。你能把这些与在特定上下文中进行推理（例如，“如果我假设P是真的，那么我就能推断出A和B。”）作为解决问题的方法联系起来吗？（这个问题是开放式的。）

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

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

过滤器

4.4.4.3 通过模式匹配查找断言

4.4.4.4 规则和统一

4.4.4.5 维护数据库

4.4.4.6 流操作

4.4.4.7 查询语法函数和实例化

处理模式变量

函数`convert_to_query_syntax`

表达式的实例化

函数`unparse`

查询语言特定表示的谓词和选择器

4.4.4.8 帧和绑定

练习 4.68

练习 4.69

练习 4.70

练习 4.71

练习 4.72

练习 4.73

练习 4.74

练习 4.75

练习 4.76

热门文章

最新文章

相关课程

相关电子书

相关实验场景

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

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

过滤器

4.4.4.3 通过模式匹配查找断言

4.4.4.4 规则和统一

4.4.4.5 维护数据库

4.4.4.6 流操作

4.4.4.7 查询语法函数和实例化

处理模式变量

函数convert_to_query_syntax

表达式的实例化

函数unparse

查询语言特定表示的谓词和选择器

4.4.4.8 帧和绑定

练习 4.68

练习 4.69

练习 4.70

练习 4.71

练习 4.72

练习 4.73

练习 4.74

练习 4.75

练习 4.76

热门文章

最新文章

相关课程

相关电子书

相关实验场景

函数`convert_to_query_syntax`

函数`unparse`