如何使用方案宏來顯示評估樹

Question

我修改了SICP中count-change函數的代碼，以便在函數遞歸時它將顯示一對。這對的形式是"(cc a k)" -> "(cc a (- k 1))"或"(cc a k)" -> "(cc (- a (d k)) k)"，我的目標是建立一個DOT文件來顯示使用GraphViz的樹狀遞歸。

下面是一個例子的圖像，從下面的代碼生成：

這裏的方案的代碼：

; Count Change 

    (define (count-change amount) 
     (cc amount 5)) 

    (define (cc amount kinds-of-coins) 
     (begin 
     (cond ((= amount 0) 1) 
      ((or (< amount 0) (= kinds-of-coins 0)) 0) 
      (else (+ 
      (begin 
       (display "\"") 
       (display `(cc ,amount ,kinds-of-coins)) 
       (display "\"") 
       (display " -> ") 
       (display "\"") 
       (display `(cc ,amount ,(- kinds-of-coins 1))) 
       (display "\"") 
       (display "\n") 
       (cc amount (- kinds-of-coins 1)) 
       ) 
      (begin 
       (display "\"") 
       (display `(cc ,amount ,kinds-of-coins)) 
       (display "\"") 
       (display " -> ") 
       (display "\"") 
       (display `(cc ,(- amount (first-denomination kinds-of-coins)) ,kinds-of-coins)) 
       (display "\"") 
       (display "\n") 
       (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins) 
       ) 
      ) 
      )))) 

         ; first-denomination takes the number of kinds of coins and returns the denomination of the first kind 
     (define (first-denomination kinds-of-coins) 
     (cond ((= kinds-of-coins 1) 1) 
      ((= kinds-of-coins 2) 5) 
      ((= kinds-of-coins 3) 10) 
      ((= kinds-of-coins 4) 25) 
      ((= kinds-of-coins 5) 50))) 

    (count-change 11) 

原始代碼是here。

我已閱讀關於方案宏，我認爲他們可以解決這個問題，允許我在begin語句中用'wrap'調用（cc。）語句來顯示遞歸時正在發生的事情。

這怎麼可以用Scheme宏來完成？

注意：我知道我的圖像是不準確的，我需要找到一種使節點不同的方法，以便圖形是一棵樹，而不僅僅是一個DAG。但是，這超出了這個問題的範圍。

Answer 1

宏不是你想要的。這份工作的更合適的工具是知道新舊和參數cc並處理打印出的文本graphviz的，使遞歸調用一個簡單的本地函數：

(define (cc amount kinds-of-coins) 
    (let ((recur (lambda (new-amount new-kinds) 
       (begin 
        (display "\"") 
        (display `(cc ,amount ,kinds-of-coins)) 
        (display "\"") 
        (display " -> ") 
        (display "\"") 
        (display `(cc ,new-amount ,new-kinds)) 
        (display "\"") 
        (display "\n") 
        (cc new-amount new-kinds))))) 
    (cond ((= amount 0) 1) 
      ((or (< amount 0) (= kinds-of-coins 0)) 0) 
      (else (+ 
       (recur amount (- kinds-of-coins 1)) 
       (recur (- amount (first-denomination kinds-of-coins)) kinds-of-coins)))))) 

你沒有說什麼計劃實施你正在使用，但對於某些實現，還有一些小的語法清理可以完成，以使代碼看起來更好。

Answer 2

這裏的抽象是jacobm暗示模式的方法：

;; Add graphviz tracing to a definition: 
(define-syntax define/graphviz-trace 
    (syntax-rules() 
    [(_ (id args ...) body ...) 
    (define (id args ...) 
     (let* ([real-id id] 
       [old-args (list args ...)] 
       [id (lambda (args ...) 
        (define new-args (list args ...)) 
        (print-trace 'id old-args new-args) 
        (real-id args ...))]) 
     body ...))])) 

;; print-trace: symbol list list -> void 
(define (print-trace id old-args new-args) 
    (display "\"") 
    (display `(id ,@old-args)) 
    (display "\"") 
    (display " -> ") 
    (display "\"") 
    (display `(id ,@new-args)) 
    (display "\"") 
    (display "\n")) 

; first-denomination takes the number of kinds of coins and 
; returns the denomination of the first kind 
(define (first-denomination kinds-of-coins) 
    (cond ((= kinds-of-coins 1) 1) 
     ((= kinds-of-coins 2) 5) 
     ((= kinds-of-coins 3) 10) 
     ((= kinds-of-coins 4) 25) 
     ((= kinds-of-coins 5) 50))) 

;; Example: 
(define/graphviz-trace (cc amount kinds-of-coins) 
    (cond ((= amount 0) 1) 
     ((or (< amount 0) (= kinds-of-coins 0)) 0) 
     (else (+ (cc amount (- kinds-of-coins 1)) 
       (cc (- amount (first-denomination kinds-of-coins)) 
        kinds-of-coins)))))