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

Question

我count-change在SICP中修改了函数的代码,以便在函数recurses时显示一对.该对是形式"(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)

原始代码在这里.

我已经阅读了有关方案宏的内容,我认为他们可以通过允许我在begin带有显示的语句中"封装"对(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))))))

您没有说明您正在使用什么方案实现，但对于某些实现，也可以进行一些小的语法清理，以使此代码看起来更好。