Sposób korzystania z makr programu do wyświetlania drzewa oceny

Question

Zmodyfikowałem kod funkcji count-change w SICP, tak aby wyświetlał parę, gdy funkcja się powtarza. Ta para ma postać "(cc a k)" -> "(cc a (- k 1))" lub "(cc a k)" -> "(cc (- a (d k)) k)", moim celem jest stworzenie pliku DOT do wyświetlenia rekursji drzewa za pomocą GraphViz.

Oto przykład obraz uzyskany z poniższego kodu:

Oto kod programu:

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

Oryginalny kod jest here.

Przeczytałem o makrach programów i myślę, że mogliby rozwiązać ten problem, pozwalając mi na "zawijanie" wywołań do (cc..) W oświadczeniu begin z wyświetlaczami, aby wyprowadzić to, co dzieje się w czasie rekursji .

Jak można tego dokonać za pomocą makr schematu?

UWAGA: Wiem, że mój obraz jest niedokładny, muszę znaleźć sposób na odróżnienie węzłów, aby wykres był drzewem, a nie tylko DAG. Jest to jednak poza zakresem tego pytania.

Answer 1

Makra nie są tym, czego potrzebujesz. Bardziej odpowiednim narzędziem do tego zadania jest prosta funkcja, która zna lokalny zarówno starych i nowych argumentów cc i uchwyty drukując tekst Graphviz i dokonywania wywołanie rekurencyjne:

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

nie powiedziałeś co implementacja Scheme używasz, ale w przypadku niektórych implementacji istnieje kilka drobnych poprawek składniowych, które można również zrobić, aby ten kod wyglądał ładniej.

Answer 2

Oto podejście do abstrakcyjnego wzoru, który jacobm proponuje:

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