6

このページでは、投稿の後に、手順としての非常に短い実装を示すコメントがあります。amb

(define (amb-backtrack)
  (error "no solution found"))

(define (amb . args)
  (call/cc (lambda (return)
             (let ((backtrack amb-backtrack))
               (map (lambda (x)
                      (call/cc (lambda (k)
                                 (set! amb-backtrack k)
                                 (return x))))
                    args)
               (backtrack 'fail)))))

しかし、私は通常amb、マクロとして実装されていると考えています。schemers.orgのFAQや、DoraiSitaramの本にもあります。

(define amb-fail '*)

(define initialize-amb-fail
  (lambda ()
    (set! amb-fail
      (lambda ()
        (error "amb tree exhausted")))))

(initialize-amb-fail)

(define-macro amb
  (lambda alts...
    `(let ((+prev-amb-fail amb-fail))
       (call/cc
        (lambda (+sk)

          ,@(map (lambda (alt)
                   `(call/cc
                     (lambda (+fk)
                       (set! amb-fail
                         (lambda ()
                           (set! amb-fail +prev-amb-fail)
                           (+fk 'fail)))
                       (+sk ,alt))))
                 alts...)

          (+prev-amb-fail))))))

つまり、マクロバージョンは長く、理解するのが少し難しくなります。プロシージャバージョンと比べて利点はわかりませんでした。もちろん、マクロよりもプロシージャを使用したいと思います。見逃したことはありますか？

4

1 に答える 1

7

違いは、プロシージャ呼び出しが常にすべての引数を評価することです。

(amb 1 (very-expensive-computation))

のプロシージャバージョンをamb使用して、を実行してvery-expensive-computationから、を生成し1ます。それ以降のすべての計算でyield1で十分な場合は、結果値が使用されない計算に多くの時間を浪費していることになります。@Eli Barzilayがコメントで述べているように、ambを使用してすべての自然数を生成するなどの無限の非決定論をモデル化すると、さらに悪いことが起こります。

マクロバージョンはこれを回避するため、その動作はPrologなどの非決定論的プログラミング言語の動作に近くなります。

于 2011-04-24T14:59:57.123 に答える