Scheme扩展过程调用

Question

给定一个函数,如fibonacci重复的树递归实现,我如何在表达式的评估中显示每个步骤(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))

我知道使用quasiquoting,你可以部分评估一个表达式,如:

`(+ ,(* 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中的内置步进器,您可以看到每个中间步骤.有一点怎么看这个答案,恰好也显示了斐波纳契函数.