7

count-changeSICPの関数のコードを変更して、関数が繰り返されるたびにペアが表示されるようにしました。ペアはまたはの形式です"(cc a k)" -> "(cc a (- k 1))"。"(cc a k)" -> "(cc (- a (d k)) k)"私の目標は、GraphVizを使用してツリー再帰を表示するDOTファイルを作成することです。

以下のコードから生成された画像の例を次に示します。 ここに画像の説明を入力してください

スキームコードは次のとおりです。

    ; 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 に答える