方案扩展过程调用

Question

给定一个函数，例如斐波那契递归的树递归实现，我如何显示表达式求值的每个步骤，例如 (fib 5)？

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1)
                 (fib (- n 2))))))

例如我想输出:

(fib 5)

(+ (fib 4) (fib 3))

(+ (+ (fib 3) (fib 2)) (+ (fib 2) (fib 1)))

(+ (+ (+ (+ (fib 1) 0) (fib 1) (+ (fib 1) 0)) (+ (+ (fib 1) 0) (fib 1)))

(+ (+ (+ (+ 1 0) 1 (+ 1 0)) (+ (+ 1 0) 1))

我知道使用准引用，您可以部分计算表达式，如:

`(+ ,(* 3 4) (- 0.1 2))   ; evaluates to -┐
(+ 12 (- 0.1 2))          ;          <----┘

但是，我一直无法用它来展示评估中的每一步。我知道我可以像 Peter Norvig 的 lis.py 那样修改方案解释器，但我想要一种在语言本身内做到这一点的方法。我该怎么做？

Answer 1

你是说，像这样？

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else `(+ ,(fib (- n 1))
                  ,(fib (- n 2))))))

例如:

(fib 5)
=> '(+ (+ (+ (+ 1 0) 1) (+ 1 0)) (+ (+ 1 0) 1))

当然，上面的代码只会返回评估的最终结果。使用像 Racket 中的内置步进器，您可以看到每个中间步骤。有关如何查看的一些信息 answer ，它也恰好显示了斐波那契函数。