シンボル集合のリストによる安直実装

scheme メモ

毎度ながら、 内容の薄い懐古趣味を一席。
K. Dybvig Three Implementation Models for Scheme, 1987 (以下、 3imp) では、 手続きをフラット・クロージャへコンパイルするのに、 自由変数と束縛変数の集合演算を用います。 その集合演算には、 リストによる安直実装が例示してあります。 3imp の set-union 関数と set-intersect 関数を転載してみます。 記法は私好みに修正してあります。

; 3imp 93 page より転載。
(define (set-member? x U)       ; x ∈ U
 (cond
  ((null? U) #f)
  ((eq? x (car U)) #t)
  (else (set-member? x (cdr U)))))

(define (set-cons x U)          ; {x} ∪ U
 (if (set-member? x U)
  U
  (cons x U)))

; (set-union '(a b c d e) '(b d f g h)) => (e c a b d f g h)
(define (set-union U1 U2)       ; U1 ∪ U2
 (if (null? U1)
  U2
  (set-union (cdr U1) (set-cons (car U1) U2))))

; (set-intersect '(a b c d e) '(b d f g h)) => (b d)
(define (set-intersect U1 U2)   ; U1 ∩ U2
 (cond
  ((null? U1) '())
  ((set-member? (car U1) U2) (cons (car U1) (set-intersect (cdr U1) U2)))
  (else (set-intersect (cdr U1) U2))))

set-union 関数は末尾呼び出しのループで、 set-intersect 関数は非末尾呼び出しで書いてあります。 set-union の実行例で、 U2 の前に U1 にしか含まれない要素が U1 の出現順の逆にならんでいるのは、 ループで書いているためです。 一方、 set-intersect では再帰呼び出しの結果を cons するので U1 中の出現順に並びます。
本来、 set-union 関数と set-intersect 関数は、 両方とも同じ流儀で記述できるはずです。 書き直してみましょう。 まず、 数学による定義から直訳し、 set-union 関数を非末尾呼び出しで書いてみます。 3imp の set-intersect はこちらに属すので略します。

; (set-union '(a b c d e) '(b d f g h)) => (a c e b d f g h)
(define (set-union U1 U2)
 (cond
  ((null? U1) U2)
  ((set-member? (car U1) U2) (set-union (cdr U1) U2))
  (else (cons (car U1) (set-union (cdr U1) U2)))))

非末尾呼び出しでは、 U1 中の出現順に並べた結果が得られます。 ですが、 集合ですから、 要素の並び順は関係ありません。 末尾呼び出しで蓄積変数へ cons することで、 逆順の結果にしても平気です。

; (set-union '(a b c d e) '(b d f g h)) => (e c a b d f g h)
(define (set-union U1 U2)
 (let loop ((U1 U1) (U2 U2) (V U2))
  (cond
   ((null? U1) V)
   ((set-member? (car U1) U2) (loop (cdr U1) U2 V))
   (else (loop (cdr U1) U2 (cons (car U1) V))))))

; (set-intersect '(a b c d e) '(b d f g h)) => (d b)
(define (set-intersect U1 U2)
 (let loop ((U1 U1) (U2 U2) (V '()))
  (cond
   ((null? U1) V)
   ((set-member? (car U1) U2) (loop (cdr U1) U2 (cons (car U1) V)))
   (else (loop (cdr U1) U2 V)))))

3imp の set-union はこちらに属していますが、 set-cons を展開して表記を上に揃えると蓄積変数をケチっていることがわかります。 そのため、 set-member? で先頭側に付け加えた一致するはずがない要素との比較が生じてしまい、 最遅ケースが蓄積変数を使うよりも遅くなります。

; 3imp の set-union に set-cons を展開したもの
(define (set-union U1 U2)
 (cond
  ((null? U1) U2)
  ((set-member? (car U1)) (set-union (cdr U1) U2))
  (else (set-union (cdr U1) (cons (car U1) U2)))))

おまけで、 3imp が破壊操作する自由変数を探すのに使う set-minus 関数も、 set-intersect と同じ流儀の非末尾呼び出しで書いてあります。 これも、 蓄積変数を使った末尾呼び出しで書き直すことができます。

; (set-minus '(a b c d e) '(b d f g)) => (e c a)
(define (set-minus U1 U2)
 (let loop ((U1 U1) (U2 U2) (V '()))
  (cond
   ((null? U1) V)
   ((set-member? (car U1) U2) (loop (cdr U1) U2 V))
   (else (loop (cdr U1) U2 (cons (car U1) V))))))

流儀を統一しておいた方が美しかっただろうとは思えます。 3imp が流儀を統一していないのは、 末尾呼び出しでもそうでなくても、 どちらでも集合演算が記述できるどころか、 流儀を混ぜて使っても平気なことを示すため、 という深淵なる思慮があったのかもしれません。 ま。 でも、 末尾呼び出し流儀では、 蓄積変数ぐらいは使って欲しかったと思ったりしたのでした。