もう少し学んだところをメモっておかねば消化不良です。
ビット操作
ビット列の生成とマッチングまでは前回メモってあるけども、それだけではパーサーは（大体）書けません。
バイナリの生成いろいろ
バイナリの生成について細かい規則は、公式のここにかなりしっかり書かれているので迷うところは実際少なかったです。唯一迷ったのは "The Erlang Type Language" という章に書かれた、バイナリの一般式は <<_:M, _:_*N>> であり他のは省略系だとあったところです。
これが頭の片隅に残っていたので試したところ、 <<1:8, 0:32*8>> などと食わすと無情なシンタックスエラーであります。
他に合わせて << SegList >> とか書けばいいのに……と思ったのですが、これは Erlang の組み込み型を定義する上での記法の記法であり、 Erlang の文法ではありません。
バイナリかビット列か
組み込み型 bitstring は 1 ビットの列です。<<1:3>> は 2 進でいう 001です、
組み込み型 binary は 8bits 境界に並んだビット列です。生成時、 <<1>> とビット幅を指定しなければこれは /binary になります。ビット列でいうと <<1:8>> です。
両者は、組み込み型としては別ですが、前項で確認したように組み込み型はあくまで erlang にとっては（ユーザープログラムよりも）事前定義された型に過ぎず、ユーザー定義型と違いはありません。
ならばビット列を使って、わざと 8bits 境界にマッチするようなバイナリを作ったら、それは bitstring と binary のどちらにマッチするのでしょうか。
bytes(<<B/binary>>)->
io:fwrite("binary B:~w\n", [B]);
bytes(<<B/bitstring>>)->
io:fwrite("bitstring B:~w\n", [B]).
321> test:bytes(<<0>>).
binary B:<<0>>
322> test:bytes(<<0:7, 0:2>>).
bitstring B:<<0,0:1>>
324> test:bytes(<<0:9>>).
bitstring B:<<0,0:1>>
326> test:bytes(<<0:8>>).
binary B:<<0>>
327> test:bytes(<<1:1, 1:7>>).
binary B:<<129>>
328> test:bytes(<<1:1, 1:7, 1:1>>).
bitstring B:<<129,1:1>>
329> test:bytes(<<0, 0>>).
binary B:<<0,0>>
330> test:bytes(<<0, 1:1, 1:7>>).
binary B:<<0,129>>
332> test:bytes(<<0:4, 0:5, 1:6, 1:1>>).
binary B:<<0,3>>
全体の長さが 8bits アラインであれば、各セグメントのアラインがどうであっても、 binary にマッチするようです。
ビットの展開
バイナリ内からマッチした部分で引数に拘束される値はどうなるでしょうか。上位 7bit を取り出してみます。
rst(<<R:7, _:1>>)->
io:fwrite("R:~w\n", [R]).
341> test:rst(<<128>>).
R:64
ok
342> test:rst(<<255>>).
R:127
ok
なるほど。ビット列からそのまま射影されるのでなく、論理右シフトされるのですね。
算術シフトではありませんから符号には注意が要りそうです。
ん……本当？ 型修飾には signed/unsigned を書けたはず。そう思って試してみると……
rst(<<R:7/signed, _:1>>)->
io:fwrite("R:~w\n", [R]).
344> test:rst(<<255>>).
R:-1
ok
345> test:rst(<<128>>).
R:-64
ok
おー、算術シフトになった！
ちなみにデフォルトは unsigned だと仕様にも書かれておりました。
型修飾リストにはエンディアンも書けるようです（デフォルト:big）。
すげえ！！
バイナリのトラバース
公式のドキュメントを参考に、ビット列全体の処理の取り扱いについて調べました。4.7 Appending to a Binary です。このセクションではごく短い例を挙げています。
繰り返し処理
このコンテキストで書くのも急というか、本来昨日のエントリに書いておいて然るべき内容でありますので、ここでは簡単にしか触れませんが、実のところ erlang にはループがありません。再帰を使いましょう。昔の Lisp なんかの関数型や、テンプレートメタプログラミングと一緒です。
与えられたリストの中から最下位ビットだけを取り出して、第二引数の binary に追加したものを構築する append_bin() を考えます。
[] はリストです。 car/cdr といったリスト操作を明示的に呼び出す代わりにパターンマッチ [CAR|CDR] を使用します。これは variadic template と同じですね。
この場合は、再帰の終端は append_bin([], Acc) -> Acc. であり、 CDR が空になるとこちらにマッチするので Acc がそのまま返ります。
末尾再帰ですので、この場合は C++ 同様に暗黙にループによる最適化が期待できそうです。
lsb_of(<<_:7, LSB:1>>) -> LSB.Acc というのは再帰ステップを通じて与えられる任意の変数ですが、 erlang においてはアキュムレータという名前で親しまれているようです。
append_bin([CAR|CDR], Acc) ->
LSB = lsb_of(<<CAR>>),
append_bin(CDR, <<Acc/binary, LSB>>);
append_bin([], Acc) ->
Acc.
379> test:append_bin([1, 2, 3, 4, 5], <<>>).奇数,偶数,奇数,... なのでこれで大丈夫のようです。
<<1,0,1,0,1>>
結果はバイナリ binary であります。 bitstring に詰め込む場合はもっと簡単で、
append_bin([CAR|CDR], Acc) ->だけでよく、 LSB を取り出す操作を関数にする必要さえありません。
append_bin(CDR, <<Acc/bitstring, CAR:1>>);
append_bin([], Acc) ->
Acc.
ドキュメントによると、最近のバージョン(R12B)から再帰ステップ間の Acc はコピーされなくなっていて効率的になったとあります。意図的に参照を用いる必要はないようです。素晴らしいですね。
非常に美しく書けましたが、不満はあります。
ビット列のトラバースがしたかったのに、いつの間にかリストのトラバースの話になっていた！
再帰の話が混じったので一度リストにしましたが、バイナリを受けるバージョンはもっと簡単になります。
append_bin(<<CAR:8, CDR/binary>>, Acc) ->
append_bin(CDR, <<Acc/bitstring, CAR:1>>);
append_bin(<<>>, Acc) ->
Acc.
406> test:append_bin(<<1, 2, 3, 4, 5>>, <<>>).うーん、良い……。
<<21:5>>
チャンクの扱い
erlang で扱うバイナリはかなり良いことが解ってきましたが、さすがにこれで何百 MB もあるバイナリを扱ってよいかどうか気になります。上の例では末尾再帰に出来ましたが、そうでない場合はスタックが延々と伸びて行ってしまいます。
できれば適当なチャンクに区切って処理したい。
そういうときは標準ライブラリ (stdlib ではなく kernel) を使いましょう。
file:open() して開いた FD に対してシーク位置を指定した file:pread() すればいいっぽいですが、パフォーマンスについては Performance のセクションにかなり長めの警告が書かれています。
これは言い換えれば、 read()/write() には恐らくライブラリレベルのバッファが存在しないようで、アプリケーションが自分でバッファを作る必要がある。
ストリームリードならさほど気にしなくていい場合が多いでしょうが、この辺はケースバイケースです。
他にも open 時に指定出来る mode によって、遅延書き込みや先読みを有効にさせてシステムコールの削減、スループット向上を期待できそうです。
一通り似たライブラリがありながらも C/C++ の標準ライブラリとはかなり思想が違うなという印象です。
データ構造
erlang のデータはリスト、タプル、マップと人気のあるものは一通り揃えている感じがあって素敵ですが、馴染みのある構造体も使いたいです。バイナリをパースしたらそれを馴染みのある構造体に入れて取り回したいというのは自然な欲求なのではないでしょうか。
タプルでもいいけどオブジェクトに名前が欲しい……。タプルでもリストでも、 {X=0, Y=1, Z=2} という風に各要素に名前を付けられるけど、同じ構造のタプルを複数扱うとき大変。
レコードを使えばよいようです。
-record(Name, {Field1 [= Value1],レコードの定義はやや仰々しく、 -record ディレクティブを使ってコンパイラに示す必要があります。
...
FieldN [= ValueN]}).
インスタンス化
#Name{Field1=Expr1,...,FieldK=ExprK}
T = #rec{x, y, z}.などとして使います。名前付きタプルという感じでしょうか。
アクセス
Expr#Name.FieldExpr はインスタンスで Name はレコード型名、 Field はメンバ名です。
やや気持ちが悪い。オブジェクトの名前を使って各要素にアクセスしたいだけなのにちょっと大袈裟ですね。 erlan shell からアクセスしずらいのも難です。
もっといい方法があるのかも知れませんが……。
まとめ
というわけで、ここ二日で学んだところは概ね以上です。僕の必要な知識は大体手に入れたのでよしとしましょう。
0 件のコメント:
コメントを投稿