How to use scheme macros to show evaluation tree

Question

I modified the code for the count-change function in SICP so that it would display a pair whenever the function recurses. The pair is of the form "(cc a k)" -> "(cc a (- k 1))" or "(cc a k)" -> "(cc (- a (d k)) k)", my goal is to build up a DOT file to display the tree-recursion using GraphViz.

Here's an example image, generated from the code below:

Here's the scheme code:

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

The original code is here.

I have read about scheme macros, and I think that they could solve this problem by allowing me to 'wrap' calls to (cc . .) in a begin statement with displays to output what is happening at the time of recursion.

How can this be done with Scheme macros?

NOTE: I know that my image is inaccurate, I need to find a way of making the nodes distinct, so that the graph is a tree, and not just a DAG. However, that is outside the scope of this question.

Answer 1

Macros aren't what you want here. The more appropriate tool for this job is a simple local function that knows both the old and new arguments to cc and handles printing out the graphviz text and making the recursive call:

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

You didn't say what Scheme implementation you're using, but for some implementations there are some minor syntactic cleanups that can be done as well to make this code look nicer.