へびにっき

先日コメント欄で教えていただいた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の中でリンク操作を実行する部分）がお互いにリンク操作を取りあってしまう状態だ。ここで問題が起きると、プログラムは期待通りには動かないだろう。

(続きを読む…)

チャットサーバとクライアントのテスト

グループの全員の名前を表示するコードを追加してみよう

→ gsのlistboxオブジェクトを使用して実装した

すべてのグループの一覧を表示するコードを追加してみよう

→ 同じくgsのlistboxを使用して実装した

1対1の会話を追加してみよう

→ メンバー一覧の中からユーザ名を選んでメッセージ送信を行うと、そのユーザに対してのみメッセージが届くようにした（スクリーンショット中「765pro」グループの「Haruka」と「Miki」のやり取り）。また自分を選ぶと自分にだけ表示されるようにした（「Yukiho」のメッセージ）

グループコントローラをサーバマシンで動かさずに、グループに最初に入ったユーザのところで動かすためのコードを追加してみよう

→ どうしても理解できなかったので実装しなかった

以下雑感。

chat_serverとchat_groupはPidを管理するために微妙に異なるデータ構造を使っている。これが非常にイケてない。DRY原則に従って、lib_pid_assocというモジュールを作って統合した。例えば要素を取り除くremove関数は以下の通り。

remove(Pid, Assoc) ->
    remove(Pid, Assoc, []).
 
remove(_,   [], L)             -> {"????", L};
remove(Pid, [{Key, Pid}|T], L) -> {Key, reverse(L, T)};
remove(Pid, [H|T], L)          -> remove(Pid, T, [H|L]).

gsのlistboxオブジェクトは、一度何かのアイテムを選択してしまうと、マウス操作では非選択状態に戻せなくなるらしい（少なくとも私はその方法を発見できなかった）。さすがに不便なので、Membersラベルをクリックしたら選択を解除するコードを追加しておいた。

loop(W) ->
  receive
  %...
        {gs, label_m, buttonpress, _, _} ->
            gs:config(listbox_m, {selection, clear}),
            loop(W);
  %...
  end.

パッと見の印象ほど複雑ではないし、難しくもない（入門書の例なんだから当然か）。いくつか明文化されていない設計方針を読み取れれば、かなり見通しがよくなる。

状態遷移モデル

オートマトンがどうとか理論的なことはよく分からないが、「状態」と「状態遷移」の考え方が使われていることは素朴に理解できる。状態は、全体が receive … end で構成された関数として表現されており、メッセージの受信を引き金として別の関数を呼び出す（＝遷移）か、末尾再帰で自分自身を呼び出す（＝遷移無し）、もしくは終了する。

状態を表す関数は名前も特徴的である。普通の関数は「動詞＋目的語」が多いが、状態の関数は「形容詞または*loop」の形をしている。

この状態遷移モデルについて、本文中では11.3のチャットクライアントの説明の中でわずかに示唆されている。どうせなら状態遷移図でも載せておけばより分かりやすかったのではないかと思うのだが、説明が煩雑になることを避けたのか、あるいは後々OTPを用いる際には不要になる概念なのか……今の段階ではまだ分からない。

オブジェクト指向

状態遷移モデルにおける「状態」の関数は、オブジェクト指向における「オブジェクト」との類似性も併せ持っている。すなわちプロセスがインスタンスであり、ループの引数がインスタンス変数であり、応答するメッセージがメソッドである。io_widgetが特に分かりやすい。

この類似性は、ある意味当たり前ではある。なぜならメッセージ送信モデルはオブジェクト指向の先祖の一つだからだ。

……
状態遷移モデルにせよオブジェクト指向にせよ、様々なプログラミングパラダイムを全てプロセスとメッセージ送信に還元していくのがErlang流、という理解で良いのだろうか。

最後にコードの中に見つけた変なところを挙げておく。

• io_widget:update_state/3 は不要。またio_widget:loopで{updateState}を受ける部分も不要
• chat_group:delete/3 で、lists:reverse/2 の引数が逆（これだと削除するごとにリストが逆順になるので意味がない）
• io_widget:widget/1 内のpackerの設定が変。maxよりminが大きかったり、minとmaxが同じだったり（fixedを使えば済む用途のはず）

どこまで突っ込むべきか、悩ましい。

• lib_chanの実装にどこまで突っ込むか
• GUIプログラミングにどこまで突っ込むか
• 11.7の演習にどこまで付き合うか

lib_chanの詳細は本の末尾、付録Dで解説されている。だから当面は使い方だけ覚えて、実装については後回しで良い……と判断したいところなのだが、そうも言っていられない。11章までに載っている説明では、IRC Liteのコードを理解することはとてもできないからだ。

Erlangの標準GUIライブラリ gs については、公式サイトの『GS User’s Guide』が非常に分かりやすい。頭から順に目を通していって、最後の「Built In Objects」を必要に応じて参照すれば、十分に事足りると思われる。

11.7の演習には、問題の意図がよく分からないものがいくつかある。「1対1の会話を追加してみよう」。これはちょっと曖昧過ぎる。「グループコントローラを、グループに最初に入ったユーザのところで動かそう」。これはグループに最初に入ったユーザのマシンをサーバとして機能させる、という意味なのだろうか？もしそうなら、今とは全く異なるアーキテクチャを考えなければならない気がする……。それとも他に選択肢があるのか？

『プログラミングErlang』11章のIRC Lite。オーム社のサイトからコードを落として実行しても、うまく動かなかった。以下、解決までの道のり。

lib_md5が無いというエラーになる

これは原著のフォーラムで解決策が見つかった。

getting error on starting chat-client: lib_md5 missing?

socket_distでmakeを実行する前に、その一つ上のディレクトリ（日本語版ならjaerlang-code-ja）でmakeを実行しなければならない。

io_widgetのウィンドウが表示されない（Ubuntuの場合）

tk がインストールされていないと動かない。

apt-get install tk

標準ではtk 8.4がインストールされる。

io_widgetのウィンドウが表示されない（Mac OS Xの場合）

MacPortsでErlangをインストールした場合、自動的にｔｋ 8.5.5がインストールされる。しかし下のようなエラーが出て動かない。

Application initialization failed: couldn't connect to display ":0.0"
Error in startup script: couldn't connect to display ":0.0"
    while executing
"load /opt/local/lib/tk8.5/../libtk8.5.dylib Tk"
    ("package ifneeded Tk 8.5.5" script)
    invoked from within
"package require Tk 8.3"
    (file "/opt/local/lib/erlang/lib/gs-1.5.9/priv/gstk.tcl" line 7)

いろいろ検索した結果、X11.appを起動していないと動かないということに気付いた（「アプリケーション」→「ユーティリティ」→「X11.app」）。

MacPortsのtkには「quartz: Use native Mac OS X UI instead of X11」というvariantsがあって、これを有効にすればX11を起動しなくても動くかも？と思ったが、駄目だった。
……
いずれも初歩的なことなんだが、解決までにずいぶんと時間がかかってしまった。

githubに登録して、『プログラミングErlang』8章11の練習問題2のコードを載せてみた。初git。

http://github.com/tkyk/erlang-exercise—/tree/master

8章までの知識と覚えたばかりのmakeの知識を総動員して、極力凝った構成にしてある。コードは役割ごとに複数のモジュールに分割して、特にリングを構築する部分は実行時にアルゴリズムを切り替えられるようになっている。いわゆるストラテジーパターン。

次のようにコードを落としてきてmakeを実行すると

git clone git://github.com/tkyk/erlang-exercise---.git
make

erlのコンパイルが行われた後、各アルゴリズムに対応した3つのシェルスクリプトが生成される。いずれも今まで日記に書いてきたもの。

• ring_constructor_list.sh
  一番最初に作ったリストによる実装。クソ遅い。
• ring_constructor_dict.sh
  listをdictに変えて作り直したもの。
• ring_constructor_child.sh
  上2つとは異なり、再帰的にプロセスを産み出していく実装。

引数としてN（プロセス数）とM（メッセージを回す数）を与えて実行すると、erlが起動されて計算が実行され、実行時間が表示される。また make run とすると3つのスクリプトそれぞれに、何通りかのNとMを与えて自動的に実行する。

$ ./ring_constructor_child.sh 1000 1000
Constructor=ring_constructor_child, N=1000, M=1000
time=0.55, (0.563) seconds

なお、この練習問題では「リング」の定義が曖昧なので、自分なりの判断で以下の条件を課している。

1. メッセージの転送を開始できるのは始点となるプロセスのみ
2. 始点以外のプロセスは自分の”前”のプロセスを厳密に認識して、他からのメッセージは受け取らない

この条件により実装が複雑になっている部分があるので、条件を外して単純化したバージョンを別ブランチで用意した。

http://github.com/tkyk/erlang-exercise—/tree/ignore_msg_sender

lib_ring.erl以外の内容はmasterブランチと全く同じで、使い方も同じで、実行速度もほとんど同じである。

……
この練習問題にここまでこだわる理由はどこにもないのだが、Erlangに飽きないうちにできるだけのことはやっておきたい。