【^】パターンマッチ【$】 - NyaRuRuが地球にいたころ

パターンマッチ話の続き．

パターンマッチと単一化

複合代入 (多重代入) という見方もあれば，一方向単一化という見方もあって，つまりは Prolog ぐらい知っておけということっすか．この辺には値モデルと名札モデル，実装と理論，ボトムアップとトップダウンの対比な趣も感じたり．

Erlang, Oz/Mozart, Prolog, 単一化

Erlangのこと、あれこれやってたから、弾さんのコメントがあった。 http://blog.livedoor.jp/dankogai/archives/50832431.html そろそろerlangについて一言いっとくかで、変数束縛が

Variable = Value.

なのに、関数定義が

function(Aargument) -> blah, blah, blah.

てのはどうよ? と書いているが、弾さん、こんなのさ、どうよ？と挑発されたら、﹁お前がバカ﹂の一言で終わり。＼(^O^)／ = が単なる変数束縛だと思っているところが、もう、アウト！＼(^O^)／これ、ココロは、Prologの単一化(ユニフィケーション, unification)なんだよ。だから、関数定義とは別の記号をっているんだと思うけどね。ま、個人的には同じ記号だろうが別の記号だろうが、どうでもいいことだけど、変数の束縛は単一化の特殊ケースだということは、知っておいていいと思う。 HaskellやOCamlなどもそう思うし、Erlang, Oz/Mozart(MozartはOzの実装) もそうだけど、Prolog以後のヨーロッパの言語って、Prolog的なものをうまく入れてるなと思う。これらの言語にあるパターンマッチは、おれには全部Prologの単一化の簡略版に思えるからね。 HaskellもOCamlもErlangもそうだけど、このパターンマッチは、Prologとは違って、片方向なんだよね。 http://www.amazon.co.jp/exec/obidos/ASIN/193435600X/showshotcorne-22/ Joe Armstrong著﹁Programming Erlang: Software for a Concurrent World﹂では、= の動作は、Prologの単一化でバックトラックがないものくらいに考えてくれなんて脚注があるが、片方向だと、フツー、単一化とは言いがたいので、それでパターンマッチだといってるんだろうね。言葉も一般向けだし。他の言語の = が片方向なのに比べ、Ozの = は双方向になっている。どういう意味かといえば、Ozで、X, Z, Bが宣言はされているが、未束縛だとすると、

[X 'b'Z] = ['a' B 'c']

と書いたら、Xは'a'、Zは'c'、Bは'b'になる。ちゃんとした単一化だから。= の左辺と右辺の両方を書き換えてマッチさせようとしているわけ。Oz言語の仕様を実装したMozartでやると実際そうなる。プログラミングスタイルとしては、推奨されないようだが。ガウディ本よりOzの解説．

2.8.2 単一化と内包 (entailment)

変数に値を束縛することは，単一化 (unification) と言われる操作の特殊な場合である．単一化︿Term1﹀=︿Term2﹀において，可能ならば格納行きに 0 個以上の束縛を追加することにより，部分値︿Term1﹀と部分値︿Term2﹀を等しくすることができる．例えば f(X Y) = f(1 2) は　2つの束縛 X=1 と Y=2 を行う．2つの項を等しくできなければ，例外が発生する．部分値があるから単一化に意義がある．完全値しかなければ，単一化は無意味である． Haskell の入門記事にも Prolog の名が．

4 Case 式とパターン照合

パターン照合の例は前に length や fringe の関数の定義の際に示しました。この節ではパターン照合のプロセスを詳細に見ていきましょう( §3.17 ) ( Haskell におけるパターン照合は、たとえば Prolog のような、論理プログラミング言語にみられるものとは違いがあります。とくに、Haskell の照合は﹁一方向﹂です。一方 Prolog の照合は(単一化による)﹁双方向﹂で、その評価機構のなかで暗黙のバックトラックによるもです。) こっちにも．次にListにおけるmapの定義を見てみましょう。﹁Haskell 98 言語とライブラリ改訂レポート﹂では，mapは以下のように定義されています︵参考リンク，なお﹁Haskell 98 言語とライブラリ改訂レポート﹂での定義は，実装の参考になるよう関数の意味を示したものであることに注意してください。効率よりも関数の意味が明確になることを意識して定義されているため，実際に処理系のライブラリとして実装されているものとは異なることがあります︶。

map :: (a->b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

mapの関数を定義している等式が，データ構成子が[]である場合と(:)である場合の二つ存在しているのがわかりますね。この場合分けを行っているのが﹁パターン照合︵pattern matching，パターンマッチ︶﹂と呼ばれる機能です。このように，文字列だけではなく，データ構成子などのより広い範囲のデータ型の構成要素を対象としている点が，正規表現のパターン照合とは違います。また型やPrologなどの論理型言語の﹁単一化︵unification︶﹂とは異なり，﹁左側のパターン照合によって値に束縛した変数が右側で使用される﹂という一方通行になっている点にも注意してください。正規表現のグループに名前を付ける話も，一般化された変数束縛の一方向バージョンという理解でいけそうですね． (追記) ﹃薄いブログ - ホワット・ア・ワンダフル・ワールド﹄も読むとよさそう．

有名言語での実装とかシンタクスとか

ちょうど k.inaba さんの記事にまとまっていた．なんか正規表現の話しかしてないな。なんでだろ。﹁列﹂に対するパターンマッチの機能以外は、Extractor (Scala) とか [PPT] Active Pattern (F#) とか View Pattern (Haskell) とかで任意の抽象データ型に好きなだけパターンマッチできるようになった時点で、私的にはかなり満足できちゃってるんですよね、たぶん。あんんまり話を混ぜない方がよかった気がしてきた。まあいいや。みんなで混乱しましょう。

使い道を考えてみる 1

Kazzzz の日記の"言語が思考を規定する" というエントリが面白いので。確かに、プログラミング言語はそれが想定しているモデルがあるので問題解決に与える影響は少なくないと思います。

それをちょっと考えるのに一つの問題を設定して考えます。問題設定はnを1から初めてその2乗を足していき、和が2000を初めて超えたとき和はいくつになるかという問題を考えます。

例えば以前紹介したこの問題，2000 以下の数字を文字Xに，それより大きな数字を文字Yに置き換えてみると，よくある正規表現の問題に見えてきます．

var seq = 1.UpToInfinity() // [1, 2, 3, 4, ...] .Select(x => x * x) // [1, 4, 9, 16, ...] .Scan((sum, x) => sum + x) // [1, 5, 14, 30, ...] .Select(x => x <= 2000?'X' : 'Y'); // ['X', 'X', ..., 'X', 'Y', 'Y', ...]
XXXXXXXXXXXXXXXXXYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYYY....... ^ この位置に対応する数値を求めたい

整数リストを無理矢理アルファベットやひらがなにエンコードし，正規表現で問題を解くってのもありなのかも．

使い道を考えてみる 2

パターンにマッチする全ての組み合わせを列挙しつつ，興味があるパラメータのみ束縛してそこからさらにマップを行いたい，みたいなことがよくあります．例えば最近注目されているようなスケーラブルなストレージは，RDBMS とはちょっと雰囲気が違いますが，微妙に構造を持っていたりするのでそこをうまく使いたい．具体的には，多数の JSON 形式のデータから興味がある部分のみを全て取り出したいとか，流行の Bigtable な感じのデータから必要な列のみ取り出したりとか．似た方向では google:query-by-example．微妙にニュアンスが違いますが PowerShell にてこんなのとかも．

ls C:/*/*/f* |
% {switch -regex ($_.FullName) {'(?<drive>.):\\(?<rootdir>.*?)\\(.*?)\\(?<rest>.*)' {$matches}}} |
% {$_['drive'] + ':/' + $_['rootdir'] + '/(snip)/' + $_['rest']}

PowerShell だと，Provider を自作することでデータを階層構造にマップできますが，これをうまく使うと，ファイル検索のアナロジーで探索問題を記述できたりします．再帰関数とか書けないよという人でも，﹁再帰的にファイルを探してくれるコマンド﹂なら使えるよってのはありそうな．とまあそんな感じで，パターンマッチと(一方向な)一般化変数束縛をうまいことシンタックス的に統合しつつ，やや複雑な構造をもったストレージで遊べないものかなと．