並列論理和

興味深いお題。ちょっと要約してます。

第一引数と第二引数のどちらかが真になったら、もう一方の引数に関わらず真を返す」ような論理和演算「por」は実装できるでしょうか?つまり、以下のようなプログラムが1を返す「por」マクロは書けるでしょうか?

int f() { return 1; }
int g() { return g(); }

int main() {
  return por(f(), g()) && por(g(), f()) && !por(0, 0);
}

ただし、OSのシステムコールや割り込み等は使わないこととします。もちろん、上のmain関数以外の使い方をした場合でも、ちゃんとporとして動作しないと駄目です。(MLやSchemeだったら、intを受け取るマクロのかわりに、boolを返す関数を受け取るような高階関数としてもOKです。)

http://d.hatena.ne.jp/sumii/20070511/p6

schemeで書くならこんな感じだろう。

(define-syntax por
  (syntax-rules ()
    ((_ p1 p2)
     (let ((t1 p1)
           (t2 p2))
       (dynamic-wind
           (lambda()
             (set! p1
               (lambda()
                 (or (t2) (p1))))
             (set! p2
               (lambda()
                 (or (t1) (p2)))))
           p1
           (lambda()
             (set! p1 t1)
             (set! p2 t2))
         )))))

(define (f) #t)
(define (g) (g))
(define (false) #f)
(and (por f g) (por g f) (not (por false false))) ;; -> #t

しかし、以下のような形で再帰している場合に対応できてない。何かよい方法はあるだろうか?

(define (f) #t)
(define (g) (g))
(define (h) (g))
(por h f) ;; -> 上の実装では無限ループ

Document ID: ed66a9c450ee96b58947e9b0c9926a21