7

我修改了count-changeSICP 中函数的代码，以便在函数递归时显示一对。该对的形式为"(cc a k)" -> "(cc a (- k 1))"or "(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。但是，这超出了这个问题的范围。

4

2 回答 2

4

宏不是你想要的。更适合这项工作的工具是一个简单的本地函数，它知道新旧参数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))))))

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

于 2013-02-11T04:59:54.590 回答
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)))))
于 2013-02-11T18:00:59.370 回答