Exercise 4.79 · 习题

Exercise 4.79: When we implemented the Lisp
evaluator in 4.1, we saw how to use local environments to avoid
name conflicts between the parameters of procedures. For example, in
evaluating

(define (square x)
(* x x))

(define (sum-of-squares x y)
(+ (square x) (square y)))

(sum-of-squares 3 4)

there is no confusion between the x in square and the x in
sum-of-squares, because we evaluate the body of each procedure in an
environment that is specially constructed to contain bindings for the local
variables. In the query system, we used a different strategy to avoid name
conflicts in applying rules. Each time we apply a rule we rename the variables
with new names that are guaranteed to be unique. The analogous strategy for
the Lisp evaluator would be to do away with local environments and simply
rename the variables in the body of a procedure each time we apply the
procedure.

Implement for the query language a rule-application method that uses

environments rather than renaming. See if you can build on your environment

structure to create constructs in the query language for dealing with large

systems, such as the rule analog of block-structured procedures. Can you

relate any of this to the problem of making deductions in a context (e.g., “If

I supposed that P were true, then I would be able to deduce A and

B.”) as a method of problem solving? (This problem is open-ended. A good

answer is probably worth a Ph.D.)

练习 4.79：在 4.1 节实现 Lisp 求值器时，我们看到了如何用局部环境来避免过程参数之间的名字冲突。例如，在对下面的代码求值时：

(define (square x)
(* x x))

(define (sum-of-squares x y)
(+ (square x) (square y)))

(sum-of-squares 3 4)

square 中的 x 与 sum-of-squares 中的 x 不会混淆，因为我们在一个专门为局部变量构造绑定的环境中对每个过程体求值。在查询系统中，我们采用了另一种策略来避免规则应用中的名字冲突：每次应用规则时，都用保证唯一的新名字重命名变量。对于 Lisp 求值器，与之类比的策略是：取消局部环境，改为在每次应用过程时直接重命名过程体中的变量。

请为查询语言实现一种使用环境而非重命名的规则应用方法。看看能否在你的环境结构之上，为查询语言创建处理大型系统的构造，例如类似块结构过程的规则模拟物。你能将其中某些内容与在某个上下文中进行推断的问题联系起来吗（例如，“如果我假设 P 为真，我就能推导出 A 和 B。”）并将其作为一种问题求解方法？（此题是开放性的。一个好的答案很可能值一篇博士论文。）