如何使用方案宏来显示评估树

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