Andrew K. Wrightのmatchを読む

いくつかのScheme処理系のパターンマッチライブラリとして採用されているAndrew K. Wrightのmatchライブラリがある。

このmatchライブラリがどのようなものかは、日本語だとGaucheのutil.matchモジュールのドキュメントがわかりやすい。

このmatchライブラリのソースを手に入れて(@SaitoAtsushiさんにいただきました。感謝！)、読んでみようとしているのだけどなかなかに手ごわそうで、途中で心が折れてしまわないように、途中経過の自分用メモ内容をネットにあげながら自分を追い込もうと思う。

基本的には関数単位で、役割や内容を呼んで行く。

手元のソースコード上にもコメントとしてメモを書いているため、全ての説明メモをここに記述することは出来ないけどある程度わかるようには書くように心がける。

先頭に記述されている、matchの動作を制御するための変数と関数群は後回し。

genmatch

genletrec

gendefine

pattern-var? (λ (x) ...)

シンタックス

dot-dot-k? (λ (s) ...)

error-marker (λ (match-expr) ...)

'unspecifiedの時は、単にundefinedな値を返す。undefinedな値は(cond (#f #f))で生成している。
'errorまたは'failは実行時エラーを発生させる。
'matchはマッチ式の追加情報とともに実行時エラーを発生させる。

unreachable (λ (plist match-expr) ...)

validate-pattern (λ (pattern) ...)

(match 123
  [(? string? x) (list 'string x)]
  [(? number? x) (list 'number x)])

各節のパターン部である、(? string? x)と(? number? x)がそれぞれ渡されて処理される。

validate-pattern自体は内部で定義されているordinary関数に引数のpatternを渡すことしかしていない。

内部にヘルパー関数が定義されているため、別々に説明する。

simple? (λ (x) ...)

リテラル

ordinary (λ (p) ...)

【余談だけども】ここの巨大なif式はcondを展開したような形になっている。
はじめてみた時は若干引いてしまったが慣れてしまえば難しいことをしている式ではなかった。
だけどこの巨大なif式はcondの偉大さを教えてくれるいい例な気がする。

vector

シンタックス

quasi (λ (p) ...)

pが(unquote X)なら(ordinary X)になる。
pが((unquote-splicing X))なら(ordinary X)になる。
pが((unquote-splicing X) *)なら(append (ordlist X) (quasi *))になる。(*は(cdr p)を意味する。)

【また余談です】ここのunquote-splicingのチェックでは、unquote-splicingが複数引数を持つようになっているとunquote-splicingの処理と認識しないようになっている。
これはr5rs（と、たぶんr7rs)では複数引数を取るunquote-splicingの動作が未定義になっているためだと思う。
処理系によっては独自の解釈で複数引数を受け付けるようになっていた気がするが、その処理系ではここのチェックはどうなってるんだろう？

pが(X ...)なら*1( (quasi (cdr p)))

vector

シンタックス

ordlist (λ (p) ...)

シンタックス

bound (λ (pattern) ...)

bound (λ (p a k) ...)

再帰

(match '(foo bar)
  [('baz x) x] ... パターン1
  [(x y) x]) ... パターン2

パターン1ではx、パターン2ではxとyの様なシンボルのこと。

引数kはbound関数終了時に実行する関数。おそらくkは継続を表す。

bound処理本体ではpがどのような値かを判別しながら処理している。

たとえばpが、

'_だった場合

(or p1 p2 ..)だった場合

(not p1 p2 ..)だった場合

(x ...)だった場合（ちなみにここの...はdot-dot-k?的なシンボルのこと)
Vectorだった場合

boundv (λ (plist a k) ...)

Vector

bound* (λ (plist a k) ...)

再帰

クロージャ

find-prefix (λ (b a) ...)

(find-prefix '(1 2 3) '(2 3)) => '(1)

permutation (λ (p1 p2) ...)

(permutation '(1 2) '(2 3)) => #f
(permutation '(3 2 1) '(2 1 3)) => '(1 3)

異なる要素を持っていれば#f。

同じであればリストが返るのだが、呼出元では全てnot関数を通っているので値は使用されていない。

inline-let (λ (let-exp) ...)

(let ([x 1]
      [y (lambda () 2)]
      [z 3])
  (+ x y)

上記のlet式は次のように変換される。

(+ 1 (lambda () 2))

　定数の置き換えと参照されていない変数の削除が行われ、最後にletの束縛部が一つもなければ実行部分だけに変換される。

この関数も内部にヘルパー関数を持っているため、別々に説明する。

occ (λ (x e) ...)

const? (λ (sexp) ...)

isval? (λ (sexp) ...)

small? (λ (sexp) ...)

gen (λ (x sf plist erract length>= eta) ...)

(match '(1 2) [...] [...])

の様なマッチ式の場合、xには'(1 2)が渡される。

引数sfは、現在処理中のパターン以前ですでに実行されている値へのパターンマッチテストのリストが渡される。

実際には、(string? x)や(equal? x pattern)、(not (null? x))などテスト関数のリストになっている。

この引数は、すでにパターンマッチが確認されている値に関しては重複してテストを行わないように最適化するために利用されている。

たとえば以下のマッチ式の場合、

(match '((1 . 2) 3)
  [((_ . 2) (? string?)) 'string] ;;パターン１
  [((_ . 2) (? number?)) 'number]);;パターン２

パターン１とパターン2では、

最素に(_ . 2)というパターン
マッチして欲しい構造は長さ2のリスト

Gauche

(let ((x '((1 . 2) 3)))
  (let ((pat2-body (lambda () 'number))
        (pat1-body (lambda () 'string)))
    ;;パターン１とパターン２の共通の構造テストで、((_ . 2) _ ...)という構造になっているとこまでチェックしている。
    (if (and (pair? x) (pair? (car x)) (equal? (cdar x) 2) (pair? (cdr x)))
      (if (string? (cadr x))
        (if (null? (cddr x))
          (pat1-body)
          (match:error x))
        (if (and (number? (cadr x)) (null? (cddr x)))
          (pat2-body)
          (match:error x)))
      (match:error x))))

コメントに書いているように、最初の長いifで共通部分を一気にテストしている。

しかし共通部分のテストでは長さが2以上のリストであるというところまでしかテストしていないため、パターンのそれぞれで長さが2かどうかのテストを行っている。

引数plistには、bound関数がパターン部分を解析した結果を含んだデータのリストが渡される。

リストの一要素は一つのパターンに対応している。

引数erractは、パターンマッチに失敗した際に実行する式を生成する関数が渡される。

この関数を実行すると、(match:error x)の様な式が生成される。

引数length>=とetaには、(gensym)で生成されたユニークなシンボルが渡される。

以下、まだ未調査。出来次第追記します。

*1:quasi X) ...)になる。

それ以外は)((quasi (car p