計劃擴展程序調用

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

我知道，使用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中的內置步進器，您可以看到每個中間步驟。有關如何看到這個answer，這恰好也顯示斐波納契函數。