正在跟踪lambda表达式求值

Question

我在Scheme中遇到了一些看起来很棘手的lambda表达式的问题，我想看看解释器是如何评估它们的。

我希望Scheme解释器打印所有评估步骤，如SICP第1.1.5节"程序应用的替代模型"所示。

我正在寻找一个使用任何Scheme解释器的解决方案。我已经尝试过Racket的跟踪，但它只跟踪过程调用，而不是每个表达式。

激励示例

给出SICP练习2.6中教会数字的定义：

(define zero (lambda (f) (lambda (x) x)))
(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))

任务：

直接定义one和two（而不是根据zero和add-1）。

我想对照评估(add-1 zero)和(add-1 (add-1 zero))的结果来检查我对one和two的定义。

这就是我希望Scheme解释器打印出来的内容：

> (add-1 zero)
(add-1 (lambda (f) (lambda (x) x)))
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
(lambda (f) (lambda (x) (f ((lambda (x) x) x))))
(lambda (f) (lambda (x) (f x)))
>

Answer 1

试试Racket的内置步进器，这个答案中有一些操作方法。

Answer 2

这对于像方程这样的组合子来说非常容易（我相信曾经被称为应用风格）

zero f x = x
add1 n f x = f (n f x)
one f x = add1 zero f x = f (zero f x) = f x         **(1)**
two f x = add1 one f x = f (one f x) = f (f x)       **(2)**

有了组合子，一切都变了：a b c d实际上是(((a b) c) d)，a b c = d等价于(define a (lambda (b) (lambda (c) d)))。

现在很清楚f和x的意图是什么：x代表"零"数据元素的具体实现，f代表"后继"操作的具体实施，与给定的"零"的具体实施兼容。f和x实际上应该以助记法命名：

zero s z = z
add1 n s z = s (n s z)

看起来不再那么棘手了，有了更方便的语法，对吧？无论如何，lambda本身就是一个印刷事故。现在，

one s z = s z         ; e.g. (1+ 0)
two s z = s (s z)     ; e.g. (1+ (1+ 0))

---

根据SICP 1.1.3组合评估程序、跟踪步骤

• 要评估组合，请执行以下操作：
  1. 计算组合的子表达式
  2. 将作为最左边子表达式（运算符）值的过程应用于作为其他子表达式（操作数）值的参数

和1.1.5程序应用的替代模型

• 若要将复合过程应用于参数，请使用相应的参数替换每个形式参数来评估过程的主体

我们得到

add1 zero = 
  ( n f x => f (n f x) ) ( f x => x ) =
  ( f x => f ( ( f x => x ) f x ) )

这里的替换实际上停止了，因为结果是一个简单的lambda表达式，即不是一个组合。只有当提供了两个以上的参数时，评估才会完全完成：

add1 zero s z = 
  ( n f x => f (n f x) ) ( f x => x ) s z =
  ( f x => f ( ( f x => x ) f x ) ) s z =
  ( x => {s} ( ( f x => x ) {s} x ) ) z =    ; {s} is definition-of s
  {s} ( ( f x => x ) {s} {z} ) =             ; {z} is definition-of z
  ; must find the value of the operand in combination
  {s} ( ( x => x ) {z} ) = 
  {s} {z}

然后根据CCD_ 20和CCD_。这就是上面显示的方程（1）用较短的符号表示的。