amb

非決定性計算を行うための「曖昧な（ambiguous）」特殊形式。 初出は John McCarthy. A Basis for a Mathematical Theory of Computation. In P Braffort and D Hirschberg, editors, Computer Programming and Formal Systems. North-Holland, 1967。

参考

• http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-28.html#%_sec_4.3 SICP 4.3 節（日本語版 では p.245）
• CSW:amb define-syntax を使った実装例
• tyschemej:t-y-scheme-Z-H-16.html define-macro を使った実装例
• http://shugo.net/jit/20051029.html#p02 Ruby による実装と実行例
• http://www.shido.info/lisp/scheme_amb.html の実装例

実装

• 紫藤氏の実装
• 紫藤氏の実装を参考に、call/ccの、push!、失敗したらpop!の様子を、もっと強調してみました。 - gemma(2006/10/18 14:58:04 PDT)

  ;; stack of cc.
  (define fail '())
  
  ;;; nondeterminsm macro operator
  (define-syntax amb
    (syntax-rules ()
      ((_) ((pop! fail)))
      ((_ a) a)
      ((_ a b ...)
       (call/cc
        (lambda (cc)
          (push! fail (lambda ()
                        (cc (amb b ...))))
          a)))))
  
  (define (solve)   
    (let ((i (amb 4 6 7))
          (j (amb 5 8 11)))
      (if (prime? (+ i j))
          (list i j)
          (amb))))
  
  (print
   (call/cc
    (lambda (cc)
      ;; initial value for fail
      (push! fail
             (lambda ()
               (cc 'no-choise)))
      (solve))))
  

prime?はここにあります。Scheme:数遊び

• Scheme:CPSのmatchは、ambをCPSで書き直したものと理解できます。スタックを、CPSでクロージャに保存しているだけ。 - gemma(2006/12/12 00:33:17 PST)