3

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

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

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

激励例子

鉴于SICP 练习 2.6中教会数字的定义：

(define zero (lambda (f) (lambda (x) x)))

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

和任务：

直接定义oneand two（不是根据zeroand 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)))
>
4

2 回答 2

2

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

于 2013-02-16T00:40:32.537 回答
1

使用类似组合器的方程，这很容易（我相信曾经被称为应用风格）

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))).

现在很清楚fand的预期含义是什么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}

然后根据 和 的实际定义进行s计算z。这就是上面显示的等式(1)用较短的符号表示的内容。

于 2013-02-16T21:11:23.473 回答