へびにっき

先日コメント欄で教えていただいたErlangの新しい正規表現モジュール re。使える正規表現の種類やマッチの特性・性能は PCRE に準ずるので、現代的な諸プログラミング言語と比較しても遜色ないレベルの機能を備えている。正規表現なしの文字列処理なんて考えられない！という人もこれで安心。

さらに、古い regexp モジュールと比較して、マッチ対象や正規表現自体を iodata() で構成することができるという点は注目に値する。

erl> re:run([<<"Ama">>, $m, "i ", [<<"Haru">>, "ka"]], ["^", "A.+a", "$"]).
{match,[{0,12}]}

マッチや置換の結果を取得する方法も柔軟に選択できるので、「一連のバイナリから特定のパターンを抜き出してリスト（文字列）として取得する」なんてことも簡単にできる。例えば『プログラミングErlang』193ページの scavenge_urls:gather_urls は次のように書き換えられる。

gather_urls(Bin) ->
    case re:run(Bin, "<a href.+?</a>", [global, dotall, {capture, first, list}]) of
	{match, L} -> L;
	_ -> []
    end.

id3_v1:trim も次の通り簡潔に。

trim(Bin) ->
    re:replace(Bin, "[ \\0]+$", "", [{return, binary}]).

…
ちなみに re モジュールはEEP(Erlang Enhancement Proposal) 11として提案され、R12B-3において実験的なモジュールとして取り込まれたようだ。Erlangは今なお活発に開発が続けられているんだなあ…。『プログラミングErlang』はR11B-5を基準に書かれているから、たまには最新情報をチェックしていかなくては。

みんな大好き正規表現が13章で初登場。Erlangのregexpモジュールについて調べてみた。

（追記：コメント欄にて、PCREベースの新しい正規表現モジュール re の存在を教えてもらいました。こちらも後で調べてみます）

実装・性能

regexpモジュールはErlnagで実装されている。code:which(regexp) でソースファイルを探してコメントを読んでみると、NFAに変換せずに独自の内部表現とパターンマッチで実装されているらしい（その方がずっと速いから、とのこと）。内部表現は regexp:parse を使って確認することができる。

erlang> regexp:parse("xxx|yyy").
{ok,{'or',{concat,{concat,120,120},120},
          {concat,{concat,121,121},121}}}

この実装を読み解いてみるのも面白いかも知れない。

ただし独自実装の宿命として、機能は貧弱だし遅い。本家ドキュメントのEfficiency Guide 3.1にも Don’t use the regexp module in time-critical code. と書いてある。

マッチの性質

正規表現によるマッチを行う関数として、match と first_match という2種類の関数が用意されている。

• first_match は最も左でマッチした結果を返す（最左マッチ）
• match は文字列中の全ての位置でマッチを行い、最も長くマッチした結果を返す

erlang> regexp:first_match("xx xxxx xxxxxx", "x+").
{match,1,2}
erlang> regexp:match("xx xxxx xxxxxx", "x+").
{match,9,6}

first_match の方が速いので、単にマッチするかどうか調べるだけなら first_match を使った方が良い。

またどちらの関数も、その位置でマッチする最長のものを見つけようとする（最長マッチ）。

erlang> regexp:first_match("xxxxyyyy", "x+(yy)?(yyyy)?").
{match,1,8}

よって first_match は、いわゆるPOSIX NFAと同じ最長最左マッチを行うことになる。これは perl や ruby など従来型NFAとは異なる動作である。

irb> $& if /x+(yy)?(yyyy)?/ =~ "xxxxyyyy"
=> "xxxxyy"

lib_find:files/5 の改善

『13.8 findユーティリティ』に出てくる lib_find:files/5 がイマイチだと感じたので、自分なりに修正してみた。以下の点を変更している。

• regexp:match/2 の代わりに regexp:first_match/2 を使うようにした
• accumulator の処理を lists:foldl/3 に委託した
• マッチ対象を「ファイルの完全パス」から「ファイル名」に変更した

(続きを読む…)

先日の続き。

実は書いているうちに新たな疑問が浮かんできて、再度考え直していた。その結果、先日の内容には少し嘘が含まれていたことにも気付いた（詳細は「問題点4」の中で）。やっぱり「徹底検証」だとか格好つけるもんじゃないね！

(続きを読む…)

『プログラミングErlang』138ページ。この1ページを理解するのに丸一日以上要したのは、単に私の頭が鈍いから、というだけではない！と思ったので、これから2回に分けて徹底的に検証していくことにする。

問題となる部分の引用：

on_exitとkeep_aliveにはちょっとした間違いがあるのに気付いただろうか？次のようなコードを書くと：

Pid = register(…),
on_exit(Pid, fun(X) -> ..),

この2つの文の間でプロセスが死んでしまう可能性がある。on_exitが評価される前にプロセスが死ぬとリンクは作られないので、on_exitプロセスは期待どおりの仕事をしてくれなくなる。そのような状況は2つのプロセスがNameに同じ値を指定して同時にkeep_aliveを評価しようとすると発生する。この状況は競合状態と呼ばれる。2つのコード（上記のコードと、on_exitの中でリンク操作を実行する部分）がお互いにリンク操作を取りあってしまう状態だ。ここで問題が起きると、プログラムは期待通りには動かないだろう。

(続きを読む…)