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.

Answer 2

Here's an approach to abstract the pattern that jacobm suggests:

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