跟踪lambda表达式评估

Question

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

我希望Scheme解释器打印所有的评估步骤，如SICP Section 1.1.5, "The Substitution Model for Procedure Application"所示。

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

激励例如

鉴于Church数从SICP Exercise 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）。

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

这是我想的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

这是很容易与组合子般的方程（什么was once called applicative style I believe）

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应该真正被mnemonically命名为：

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 combinations evaluation过程跟踪的步骤，

• 评价相结合，做到以下几点：
  1. 评估相结合的子表达式。
  2. 将作为最左边的子表达式（运算符）的值的过程应用于作为其他子表达式（操作数）的值的参数。

和1.1.5 sustitution model for procedure application

• 要的化合物过程适用于参数，与由对应的参数替换的每个形式参数评估过程的主体。

我们得到

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} 

，然后计算将根据s和z的实际定义进行。以上所示的等式（1）用较短的符号表示。

Answer 2

给球拍的内置步进一试，有在这个answer有点如何做。