へびにっき

『プログラミングErlang』15章本文では

1. 単語ごとに分割する
2. 単語の両端に空白を付加する
3. 3文字ずつ取り出す

という3段階の手順になっている。これを1段階に、すなわち先頭から順番に3文字ずつ抜き出していくアルゴリズムに変更してみた。

-define(NL, $\r,$\n).
 
% 先頭に改行を付加して処理開始
my_scan_trigrams([?NL|_]=L, F, A) -> each_trigram(L, F, A);
my_scan_trigrams(L, F, A) -> each_trigram([?NL|L], F, A).
 
each_trigram(L, F, A) ->
    case L of
	%% 終端の処理
	[?NL]      -> A;
	[?NL, X]   -> F([$\s, X, $\s], A);
	[X,   Y]   -> F([X,   Y, $\s], A);
	%% 単語の先頭
	[?NL, X, ?NL|T] -> each_trigram([?NL |T], F, F([$\s, X, $\s], A));
	[?NL, X, Y  |T] -> each_trigram([X, Y|T], F, F([$\s, X, Y  ], A));
	%% 単語の途中
	[X,   Y, ?NL|T] -> each_trigram([?NL |T], F, F([X,   Y, $\s], A));
	[X,   Y, Z  |T] -> each_trigram([Y, Z|T], F, F([X,   Y, Z  ], A))
    end.

微々たる差ではあるが、少しだけ速い。

Counting by my_scan_trigrams - No of trigrams=3357707 time/trigram=0.46476926068891655
Counting by scan_word_list - No of trigrams=3357707 time/trigram=0.5411714006016606

先日の続き。

file:open/2 に raw オプションを指定した場合の IoDevice の実体はポート+αだった。ということは、ポートに対するBIFを使えば、プロセス終了時の挙動も確かめられるはずである。

次のようなコードで確認してみた（rpc/2 の定義は省略）。

-module(raw_test).
-compile(export_all).
 
start() ->
    Pid = spawn(fun test/0),
    io:format("The process which opened the file is ~p.~n", [Pid]),
    Port = rpc(Pid, get),
    io:format("The opened port is ~p.~n~n", [Port]),
    io:format("is_process_alive: ~p~n", [erlang:is_process_alive(Pid)]),
    io:format("port_info: ~p~n~n", [erlang:port_info(Port)]),
    rpc(Pid, close),
    io:format("is_process_alive: ~p~n", [erlang:is_process_alive(Pid)]),
    io:format("port_info: ~p~n", [erlang:port_info(Port)]).
 
test() ->
    %% IoDeviceのUndocumentedな内部構造に依存
    {ok, {_,_,{Port,_}}} = file:open("raw_test.erl", [read, raw]),
    test(Port).
 
test(Port) ->
    receive
	{From, get} ->
	    From ! {self(), Port},
	    test(Port);
	{From, close} ->
	    From ! {self(), close}
    end.

実行結果は次のようになった。

The process which opened the file is <0.60.0>.
The opened port is #Port<0.1695>.

is_process_alive: true
port_info: [{name,"efile"},
            {links,[<0.60.0>]},
            {id,1695},
            {connected,<0.60.0>},
            {input,9},
            {output,18}]

is_process_alive: false
port_info: undefined

ファイルを開いたプロセスが生きているときにはきちんとポートの情報が取れる。links や connected に pid が入っていることも確認できる。プロセスが終了するとポート情報は undefined となり、ポートが閉じられたことが分かる。

IoDevice の内部実装についてはともかく、「ファイルを開いたプロセスが終了したとき、自動的にファイルが閉じられる」という挙動については信用しても良さそうだ。例えば『プログラミングErlang』14章のSHOUTcastサーバではクライアントがTCP接続を閉じたときにコントローラプロセスがクラッシュするという仕様になっているが、このときにもきちんとファイルは close される、ということになる。

先日示したコード

play_songs(Socket, Pid, I) ->
    {Bin, Header} = rpc(Pid, next_block),
    write_data(Socket, Bin, {I, Header}),
    play_songs(Socket, Pid, I+1).

これは形式的には「外部イテレータ」のように見える。

そして「内部イテレータ」の形式に書き換えることもできる。

play_songs(Socket) ->
   each_song_block(fun(Bin, Header, I) ->
                            write_data(Socket, Bin, {I, Header}),
                            I+1
                    end, 0).

この場合は別プロセスを立ち上げる必要は無い。逆に考えると、プロセスとメッセージパッシングの考え方を用いることで、内部イテレータ（的な処理）を外部イテレータ（的な処理）に書き換えることができる……と言えそうである。

内部イテレータを外部イテレータに、という話題では、確か「コルーチン」が云々という議論があったはず……と思って検索してみたら、案の定興味深いページがいろいろと見つかった。

• メイン・ルーチン、サブルーチンそしてコルーチン
• [Think IT]第4回：並列処理が可能な関数型言語「Erlang」
• アクターモデル – Wikipedia

マルチプロセスとメッセージパッシングによる真の並列性を備えたErlangならば、コルーチンと同等の構造も容易に作れる……という理解で良いのだろうか。

14.7の『SHOUTcastサーバ』はこの本の中で2番目の山場だと思う。send_file/5 とか、処理の見通しが悪過ぎて投げ出したくなった……。が、頑張ってなんとか読み進めている。

まず「ファイルの中の、ある範囲内にランダムアクセスする」処理を分離したい。というわけで次のようなモジュールを書いた。一見して明らかなように、露骨にOOを意識している。

-module(filerange).
-export([open/2, close/1, pread/3]).
-record(file_with_range, { io, min, max }).
 
open(File, Min, Max) ->
    {ok, Io} = file:open(File, [read, binary, raw]),
    #file_with_range{io=Io, min=Min, max=Max}.
 
close(#file_with_range{io=Io}) ->
    file:close(Io).
 
pread(#file_with_range{io=Io, min=Min, max=Max}, Offset, Size) ->
    Start = Min + Offset,
    End   = Start + Size,
    if
	End > Max ->
	    case file:pread(Io, Start, Max - Start) of
		{ok, Data} -> {less, Data};
		eof -> {less, <<>>}
	    end;
	true ->
	    {ok, Data} = file:pread(Io, Start, Size),
	    {exact, Data}
    end.

しかしこれではイマイチだ。グローバルなモジュールの名前空間を占有する割には、さほど汎用的なコードではない。というか別に汎用的にするつもりもない。単に処理のスコープを分割したいだけだ。しかしそういう気軽な分割に用いるには、モジュールという単位は大げさ過ぎる……。

そこでふと、以前に「様々なプログラミングパラダイムを全てプロセスとメッセージ送信に還元していくのがErlang流だ」と考えたことを思い出した。そうだ、これも別プロセスで動かしてしまおう！

filerange_server(File, Min, Max) ->
    {ok, Io} = file:open(File, [read, binary, raw]),
    filerange_loop(Io, Min, Max).
 
filerange_loop(Io, Min, Max) ->
    receive
	{From, {pread, Offset, Size}} ->
	    Start = Min + Offset,
	    End   = Start + Size,
	    if
		End > Max ->
		    case file:pread(Io, Start, Max - Start) of
			{ok, Data} -> From ! {self(), {less, Data}};
			eof        -> From ! {self(), {less, <<>>}}
		    end;
		true ->
		    {ok, Data} = file:pread(Io, Start, Size),
		    From ! {self(), {exact, Data}}
	    end,
	    filerange_loop(Io, Min, Max);
	{From, close} ->
	    From ! {self(), file:close(Io)}
    end.

これで名前空間は適切に分割され、汎用の rpc で呼び出せるようになった。デバッグも簡単だ。

erl> Pid = spawn(fun() -> myshout:filerange_server("AtoZ.txt", 5, 20) end).
<0.37.0>

erl> myshout:rpc(Pid, {pread, 0, 5}).
{exact,<<"FGHIJ">>}

erl> myshout:rpc(Pid, {pread, 10, 5}).
{exact,<<"PQRST">>}

erl> myshout:rpc(Pid, {pread, 0, 100}).
{less,<<"FGHIJKLMNOPQRST">>}

さらに調子に乗って play_songs/3 の中の曲選択部分も別プロセスとして分離した結果、「曲データを無限に読み出し続ける」という処理は次のように簡潔な記述になった。

play_songs(Socket, Pid, I) ->
    {Bin, Header} = rpc(Pid, next_block),
    write_data(Socket, Bin, {I, Header}),
    play_songs(Socket, Pid, I+1).

いい感じだ。何となくErlangのプロセスの面白さが分かってきた気がする。

先日コメント欄で教えていただいた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.