Cách sử dụng macro lược đồ để hiển thị cây đánh giá

Question

Tôi đã sửa đổi mã cho hàm count-change trong SICP sao cho nó sẽ hiển thị một cặp bất cứ khi nào hàm đệ quy. Cặp này có dạng "(cc a k)" -> "(cc a (- k 1))" hoặc "(cc a k)" -> "(cc (- a (d k)) k)", mục tiêu của tôi là xây dựng một tệp DOT để hiển thị đệ quy bằng cách sử dụng GraphViz.

Dưới đây là một hình ảnh ví dụ, tạo ra từ mã bên dưới:

Dưới đây là mã chương trình:

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

Mã ban đầu là here.

Tôi đã đọc về macro lược đồ và tôi nghĩ rằng họ có thể giải quyết vấn đề này bằng cách cho phép tôi 'kết thúc' cuộc gọi đến (cc.) Trong câu lệnh begin với màn hình để hiển thị những gì đang diễn ra tại thời điểm đệ quy .

Làm cách nào để thực hiện điều này bằng các macro lược đồ?

LƯU Ý: Tôi biết rằng hình ảnh của tôi không chính xác, tôi cần phải tìm cách tạo các nút khác biệt, sao cho biểu đồ là một cây chứ không chỉ là một DAG. Tuy nhiên, đó là nằm ngoài phạm vi của câu hỏi này.

Answer 1

Macro không phải là thứ bạn muốn ở đây. Các công cụ thích hợp hơn cho việc làm này là một chức năng địa phương đơn giản mà biết cả những lập luận cũ và mới để cc và xử lý in ra các văn bản graphviz và thực hiện cuộc gọi đệ quy:

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

Bạn đã không nói gì Đề án thực hiện bạn đang sử dụng, nhưng đối với một số triển khai, có một số dọn dẹp cú pháp nhỏ có thể được thực hiện để làm cho mã này trông đẹp hơn.

Answer 2

Dưới đây là một cách tiếp cận để trừu tượng mô hình jacobm gợi ý rằng:

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