Andrew Wright のパターン・マッチングのリストのコピー

Scheme で親しまれている Andrew Wright のパターン・マッチング・マクロのパターンは ... を使ってリストに一致させることができます。 この場合、 次のようにリストを作成してパターン変数に結びつける機能の副産物で、 リストのコピーを生じることがあります。

(define foo '(foo ((x 1) (y 2)) z))

(match foo
 (('foo ((v a) ...) m ...) (list 'v v 'a a))
 (else #f))
;=> (v (x y)
;    a (1 2))

最初は cadr の位置を取り出すだけのパターンから始めます。 これは、 cadr の位置にある項目の素性をまったくチェックせずに、 パターンにマッチしてパターン変数 b を foo の cadr を結びつけます。

(define foo '(foo ((x 1) (y 2)) z))

(match foo
 (('foo b m ...) (list 'b b 'cadr? (eq? b (cadr foo)) 'm m))
 (else #f))
;=> (b ((x 1) (y 2)) cadr? #t m (z))

パターンを変更して次のように書いてもパターン変数 b を foo の cadr に結びつけることには変わりません。 上と違うのは、 パターン・マッチングの際に foo の cadr が list? で真になるチェックが入るようになることです。

(match foo
 (('foo (b ...) m ...) (list 'b b 'cadr? (eq? b (cadr foo)) 'm m))
 (else #f))
;=> (b ((x 1) (y 2)) cadr? #t m (z))

厳密に記述するならば、 上のパターンは下と等価であるものとして扱われます。 リストのデータ構造にマッチングするだけのパターンと、 それに成功したときにパターン変数を結びつけるパターンを組み合わせてあります。

(match foo
 (('foo (and (_ ...) b) m ...) (list 'b b 'cadr? (eq? b (cadr foo)) 'm m))
 (else #f))
;=> (b ((x 1) (y 2)) cadr? #t m (z))

ところが、 次のように記述すると、 動作が変わります。 このパターンの意味は、 foo の cadr が入れ子のリストになっていることをチェックし、 成功したときに foo の cadr のコピーへパターン変数 b に結びつけます。 結びついているのはリストのコピーなので、 eq? が偽になります。 コピーするレベルは、 パターンの最も深いレベルを除きます。 2重リストのときは、 トップレベルだけのコピーになり、 3重リストのときは、 トップレベルとさらに一段深いレベルをコピーします。

(match foo
 (('foo ((b ...) ...) m ...) (list 'b b 'cadr? (eq? b (cadr foo)) 'm m))
 (else #f))
;=> (b ((x 1) (y 2)) cadr? #f m (z))

and パターンで、これと等価なパターンにすると、 変数を含むパターンの繰り返しになります。 このように書き直したパターンで変数が置いてあるレベルの外の部分をコピーするという意味になります。

(match foo
 (('foo ((and (_ ...) b) ...) m ...) (list 'b b 'cadr? (eq? b (cadr foo)) 'm m))
 (else #f))
;=> (b ((x 1) (y 2)) cadr? #f m (z))

リストの入れ子構造になっていることをチェックしてから、 foo の cadr へパターン変数 b を結びつけたいなら、 リストの構造を表すパターンと変数を分けます。 このように書いておけば、 コピーしなくなります。

(match foo
 (('foo (and ((_ ...) ...) b) m ...) (list 'b b 'cadr? (eq? b (cadr foo)) 'm m))
 (else #f))
;=> (b ((x 1) (y 2)) cadr? #t m (z))

応用として、 古い LISP 風に連想リストを環境フレームに使う解釈系で、 let 構文のバインディング部分のリスト構造にマッチングしたとき、 バインディング部分へパターン変数を結びつけて無用なコピーを避けるには、 次のように記述します。

(match form
 (('let (and (((? symbol?) _) ...) binding) body ...)
  (let ((env (cons
              (map (lambda (w) (cons (car w) (evaluate (cadr w) env))) binding)
              env)))
   (evaluate-sequence body env))))

といっても、 Scheme の場合、 解釈系の環境に変数リストと値リストに分けてフレームにぶらさげるやりかたが一般的で、 リストのコピーを生じてくれる方が便利です。

(match form
 (('let (((? symbol? vars) args) ...) body ...)
  (let ((env (cons
              (cons vars
                    (map (lambda (e) (evaluate e env)) args))
              env)))
   (evaluate-sequence body env))))