2015年1月18日日曜日

すごい erlang のすごさがわからないくらいまで学ぶ。できればゆかいに。

昨日急に Erlang のコードをいじらなければならなくなりまして。
別にがっつり開発するとかメンテするとか大袈裟な話じゃなく、ちょっと弄ってちょっとの間動かせればいいのです。
目的もバイト列のパーサーだから Erlang らしいスレッドモデルは使わない。
それくらいを目標に、他言語話者が Erlang を学んだところをメモっておきます。

ランタイムや開発環境は brew install erlang で一発です。
パッケージ内には emacs の erlang-mode も入ってますので、

((setq load-path (cons "/usr/local/opt/erlang/lib/erlang/lib/tools-2.6.15/emacs/" load-path))
(setq erlang-root-dir "/usr/local/opt/erlang/")
(setq exec-path (cons "/usr/local/opt/erlang/bin/" exec-path))
(require 'erlang-start))

と書いたら ok.
C-c C-k でコンパイル、 erlang シェルの起動まで一発であります。
らくちんらくちん。

文法

Erlang は結構古い言語で 86 年登場だそうなので C++ と同世代くらいでしょうか。
しかしながら文法はかなりモダンな機能が多く、かと思えば全然モダンじゃないところもあってアクセルを踏んだりエンストするような感じもあり、乗り物酔いしそうです。

他の言語であれば、一つの文は 式; でブロックは { 文 ... } で……みたいな大枠から説明できるのですが、 Erlang の文は文脈依存の構文が多く、なんとも一言では説明できません。
もっとも原始的な文を
Expr.
と言うことはできるですが、多くの手続き型言語がこれの列挙をする文法なのに対し、 Erlang はこれだけ解ってもどうにもならない文法だと思います。
……といってもなかなか伝わらないと思うので、僕の見た厄介な例に目線を合わせる意味で、こんな例を書いておきます。

-module(test).
-export([func/2]).

func({A, B, C, _} = Tuple, A) when A > 1,
            B > 1;
            C > 1 ->
    io:fwrite("func({A,B,C,_}, A)\n"),
    case A of 2 when B > 2 ->
        io:fwrite("Tuple = ~w\n", [Tuple])
    end;
func({A, B, C, _}, _) ->
    io:fwrite("func({A,B,C, _}, _)\n").

手続き型か、いや関数型プログラミング言語か……というよりどことなく BNF 記法による構文解析を思い出します。
なんとなく見てわかるところと、解らないところがあると思います。

解るところは:
  • test モジュールと関数 func が定義されている
  • 関数は複数定義され、　template の特殊化のように動くようだ
  • 特殊化は when 条件式によっても細かく制御できるようだ
  • {} は何らかの無名構造体を構成するようだ
  • io:fwrite() は printf() のようなものだ
C++11 の variadic template はお気に入りの機能で、記述が冗長なことを除けばこれを（大枠では）すんなり理解できると思います。
パッと見、疑問に思うところは
  • 文末の記号があったりなかったり、複数の種類があるのは何なの？
  • . (dot) が文末なのに、本体のコードではたった一回しか登場しないじゃん
  • -> と ; の厳密な定義は何？
  • ; の定義によっては二つ目の func は一つ目の func の中に定義されているようにも見えそうだけど、どうなるの？
  • 一つ目の func({A, B, C, _} = Tuple, A) は特殊バージョンにとしては二つ目の func とあまり違わないように見えるが、パターンマッチが動くのだろうか？
  • when の条件式が複数あるけどこれはどう評価されるの？
  • case も when も条件分岐だと思うけど、二つあるのは何なの？
  • if じゃダメなの？
  • = は何なの？
ということでしょうか。
これらの疑問には、個別の解説を読むより公式のドキュメントが一番わかりやすく答えてくれました。

関数の宣言は関数節の集合

公式ドキュメントによる仕様をみてみましょう。
  • 関数宣言はセミコロンに区切られた関数節からなり、 .(dot) で終端する
  • 関数節は節頭と節本体を -> で繋いだもの
  • 関数節本体は一つ以上のカンマで区切られた式からなる
と書かれています。
つまり、下記は全体で一つの関数 Name の宣言であると言えます。
一つ一つが関数節であり、下線部は各関数節の頭です。関数節はそれぞれセミコロンで区切られ、.(dot) で終端します。
下の構文は公式ドキュメントのものですが、関数節が一つの場合はセミコロンで終端しそうに見えますが、 関数宣言は . で終端すると定義されているのでまぁ、文章で書かれた定義のほうに従うようです。

Name(Pattern11,...,Pattern1N) [when GuardSeq1] ->
    Body1;
...;
Name(PatternK1,...,PatternKN) [when GuardSeqK] ->
    BodyK.
 
各節は構文解析器のノードと一緒です。全ての引数についてパターンがマッチし when 節が還元すれば、その関数が還元します。呼ばれるわけです。
variadic なテンプレート引数展開や特殊化はまず汎用版を宣言してから特殊バージョンを宣言しますが、この場合は逆であり、節ごとに緩くしていきます。
when シークエンスからなる（ガード節というらしい）は省略可能です。
関数節頭の () 内は、仮引数リストというよりパターンであることは予想通りですが、仮引数リストのようにも機能します。
引数の数をアリティと呼び、アリティが違えば別の関数とされるのは他の言語と一緒です。
上の、 func 関数の場合は引数は 2 個で、フルネームは test:func/2 であります。
パターンとは項ですが、未拘束変数が許されています。
詳しくは後述しますが、ここでは C++ の人に解りやすいパターンの例をあげておきます。
func/2 は未拘束変数 A を持ち、第二引数の値によって特殊化……のように動きます。
 




func(A, 0) -> io:fwrite("zero\n");


func(A, 1) -> io:fwrite("one\n");
func(A, 2) -> io:fwrite("two\n");
func(A, _) -> io:fwrite("other\n").







when 節

続いて when 節を見てみましょう。

ここでいう when 節とは when GuardSeq で表現される節です。 

ここはドキュメントで明示されるまでは信じられないような仕様でありまして、


    

  • カンマで区切られたガード式の集合がガードである
    

    • 

  • セミコロンで区切られたガードの集合がガードシーケンスである
    

    • 


とされています。

いやまぁ、　C/C++ だってカンマ演算子を使ってギョッとするようなコードを書くことはできますが、仕様でこう書かれてしまうと「アアア……」となってしまいます。


違いは、ガードは全部評価され全部が true にならなければなりません。ガードシーケンスは順番に評価されて true になればシーケンス全体が還元します。  




ガード式とは、 Erlang の式ですが、全部使えるわけではなく、副作用のあるようなことはできません。

引数リストはパターンでなければならないので、 式は書けません。

仕様では"a subset of the set of valid Erlang expressions" と表現されております。

副作用がないのだから、ガードシーケンスやガードの残りの式は評価されない(will not)ようです。

大体 C++ の条件式の評価と同じですが、この辺は評価が決まっている C++ とは違いますね。



ちなみに、ある解説によるとセミコロンは orelse 演算子の意味とありましたので、ガード節においてはセミコロンは演算子であると考えたほうが意味的には合っていると思います。しかし文法上はセミコロンで区切られていると明示されているので、演算子であるという理解だと無理があるように思います。

僕はそっちの解説を先に読んでしまったので激しく混乱しましたが……。



以上のことを頭に入れて when 節をもう一度よーく見てみましょう。

さっきも書きましたが、引数リストはパターンしか書けません。ガードには式が書けます。





func({A, B, C, _} = Tuple, A) when A > 1,

            B > 1;

            C > 1 ->



これは要するに (A > 1 && B > 1) || C > 1 と解釈できます。

これが true ならこの関数が呼ばれます。





パターンとマッチとパターンマッチと式

さて、 Erlang に特徴的なことのうち、難しい文法の話も大詰めでります。 

ここまでナアナアにしていた関数の引数リストを理解しなければなりません。

ちなみに、 {} はタプルの宣言で、変数は大文字で始まらなければなりません。





({A, B, C, _} = Tuple, A)



引数リストはパターンの列挙だということを理解しても尚、上の例には首を捻るところがあります。 


    

  • タプル中の A と第二引数 A の関係は？
    • 

  • = は式なのではないのか？
    • 


仕様では、パターンは項と同じように表現される構造体であるが、未拘束の名前を使ってもよいとあります。

すなわち、 A とか B といった名前が宣言なしでそこに登場することは問題ありません。

引数は {A, B, C, _} などに拘束されるわけです。（_ は無名オブジェクト）

{A, B, C, _} = Tuple のほうも同様で = はマッチ演算子とされますが、パターン中に現れることを許されております。



マッチ演算子を使って評価を行うことをパターンマッチングと呼びますが、パターンマッチングに成功すると右辺の項を左辺のパターンに拘束します。例えばこうです。





X = 1.

1 = X.



X を 1 に拘束します。一度拘束してしまえば、 1 = X も同じです。右辺が評価可能な項であり、 1 もパターンであるからです。

X=1 は何度も評価できますが、一度拘束してしまえば X=2 は拘束できなくなります。

(erlang shell においては f(X). とすれば X は未拘束になり、再度拘束できるようになります）

これは X が const になってしまうのではなく、エラーメッセージによると「X と 2 はマッチしません」という、要するに X=n. というのは正確には、マッチを使って拘束していた、ということになります。

この仕組みで、引数リストはマッチをしつつ未拘束変数に実引数を拘束している、と思われます。

通常、パターンマッチでは右辺は項でなければならず、未拘束変数は項とはならないっぽいです（本当？）が、パターンであれば未拘束変数が許されます（これは本当）。

関数頭の宣言は (Patterns...) とありますので、パターンであることが明白なので、マッチの右辺も常にパターンであると見做され、右辺に未拘束変数が来ることを許されているのかなぁと思いますが……書いてて全然信じられませんね。自分でも何言ってんだろうこの人と思います。 

実際、引数リストに = (マッチ演算子)を使ってマッチしつつ拘束を行う場合、 {} = Tuple と Tuple = {} は等価であります。それどころか Tuple = ({} = Tuple1) とかでもいけます。 

なぜ解り難いほうを使って例にしたのかというと、公式ドキュメントの例ではこの順番だったからです。僕の見ていたソースでも全部 {} = Tuple のほうでした。



パターンマッチングでは基本は Pattern = Term です。

引数リストにおいてはなぜか Pattern = Pattern です。

右辺はパターンでない限り、未拘束変数はエラーになってしまいます。その代わり、右辺の評価を使って関数呼び出しなどができます。





Ret = func().



という、ごくありふれたあれですね。 





さて、パターンマッチングを使って引数を拘束することは解りました。

この関数が呼ばれたということは、全てのパターンマッチングが成功したということですので、全変数が拘束済みであります。



ここまでで大体明確になったと思いますが変数 A はたった一度拘束されるので、関数呼び出しの時に何度評価されても、矛盾がおきればマッチングは失敗し、その関数は呼ばれなくなります。

erlang のタプルは無名で、オブジェクトの名前をつけないでアクセスするので、タプル中の A と第二引数の A は同じ名前でアクセスされます。

従って、タプルの A と第二引数の A は同じでなければマッチングは失敗します。



erlang shell で実際に確かめてみます。

emacs で C-c C-k でコンパイルすると、 erlang shell にモジュールがロードされるっぽいので実行は簡単です。 





187> test:func({2, 3, 3, 0}, 2).

func({A,B,C,_}, A)

Tuple = {2,3,3,0}

ok



188> test:func({2, 3, 3, 0}, 5).

func({A,B,C, _}, _)

ok

ちなみにタプルが {A, B, C} がタプルの名前を使わず A, B, C としてアクセスされるなら Tuple という名前は何なのかと思いましたが、タプル全体にアクセスするのにこの名前を使用します。サンプルでは io:fwrite() の引数に使っています。

これは全体にアクセスしたいとき、同じオブジェクトを再構築するのを避けるためのシンタックスシュガーであると仕様にはあります。

更にちなみに、名前付きの、所謂構造体を使う場合は record を使います。

R = #Type { MemberList } で構築されます。アクセスするには R#Type.member という、二日したら多分もう覚えていないであろう変態的文法のようです。型推論あるんだから頼むよ！ 





case of

大方疑問は解消しましたが、文末の問題についてはまだ一つ気持ち悪いところがあります。

case が -> を還元したあとの終端規則です。予約語 end がいきなり登場してますが、いいんでしょうか。






case Expr of
    Pattern1 [when GuardSeq1] ->
        Body1;
    ...;
    PatternN [when GuardSeqN] ->
        BodyN
end




 


仕様によると、いいんです。

ああ、何なのこの煩わしい曖昧な書き方は。Pattern が一個しかないときはセミコロン要るの？要らないの？

関数宣言のときもそうだったでしょう。あっちは自然言語で定義が書かれてたけど。

この書き方を素直に解釈するとダメそうに見えるんですけど、試した限り Pattern が一個しかないときはセミコロンあるとダメっぽいです。


 

パターンにはパターンか定数式しか書けないので、 when ガード節を取ることができます。

待てよ？パターンということは未拘束変数も書けるのだろうか？と試したところ、仕様通り書けました。

しかし未拘束変数とのマッチは失敗するはずだと思いきや、なぜかマッチは成功してしまいました。


 




foo(A) ->
    case A of UnboundX ->
     io:fwrite("matched to unbound\n");
    0 ->
     io:fwrite("matched to zero")
    end.



212> test:foo(0).

matched to unbound

ok



ok じゃねえよ！！

C++ の default ラベルみたいなことができるように無名オブジェクトを使って _ -> ignored が動くようにしてあるのかなぁ。

それともバグかなぁ。バグだとしてももうこれを直したら死人が出ると思うし、直せないよなぁ。



if 文もありますが if 文との最大の違いは、 case はいずれかのパターンにマッチしなければランタイムエラーとなります。





サンプルで動きを確かめる



上にあげたサンプルは、特に意味はありませんが文法のいやらしい所を満載しており、 erlang shell 上で引数を変えて呼び出すといやらしい動きをします。  



C>1 が false でも A>1, B>1 ならば特殊バージョンが呼ばれる



190> test:func({2, 3, 0, 0}, 2).

func({A,B,C,_}, A)

Tuple = {2,3,0,0}





C>1 も A>1 も false なら特殊バージョンは呼ばれない



231> test:func({0, 2, 0, 0}, 0).

func({A,B,C, _}, _)

ok





そもそもタプルの構造が違えば _ であってもマッチしない



235> test:func({2, 3, 2}, 2).

** exception error: no function clause matching test:func({2,3,2},2) 





特殊バージョンが呼ばれる。しかし case Expr of Pattern にマッチしないのでエラー



193> test:func({3, 3, 3, 0}, 3).

func({A,B,C,_}, A)

** exception error: no case clause matching 3





特殊バージョンが呼ばれる。しかし case のガードにマッチしないのでエラー



227> test:func({2, 2, 3, 0}, 2).

func({A,B,C,_}, A)

** exception error: no case clause matching 2







バイナリの扱い

例外や悪夢のような -spec の文法、多彩なライブラリや組み込みデータ型についてはスルーします。

まぁ、大体の文法は解りました。

一番興味があるのは erlang の強力なマッチングはバイナリでどうなるかということです。

もう一晩これを書いてるので、簡単なメモを書いて寝たいです。



バイナリは Bin = <<SegList>> で表現されます。

Bin = <<1:1, 0:7>> ならば 0x80 になります。

Bin = <<1:8>> は 0x01 です。 0xff ではありません。 

では Bin = <<1:4, 0:4>> ならば 0x10 ですね。

カンマで区切られたゼロ個以上の各要素を、セグメントと呼びます。

セグメントの完全な表記は Value:Size/Type となっています。



ちなみにサイズの合計は 8 bits の境界に揃っている必要はありませんが、他の型と変換する場合など、当然ながら必要となるシーンはあります。





バイナリのマッチング



MSB というか、 8bit 以上の任意の長さのビット列の一番左のビットにマッチし、続く 7bit を取得し、残りは気にしないという関数 bin を考えます。





bin(<<1:1, R:7, _/bitstring>>)->

    io:fwrite("MSB 1 (rest:~w)\n", [R]);

bin(<<0:1, R:7, _/bitstring>>) ->

    io:fwrite("MSB 0 (rest:~w)\n", [R]);

bin(<<_/bitstring>>) ->

    io:fwrite("unmatched <<_>>\n").



/bitstring という型の指定は重要です。

この例では、8bit 以上の任意の長さのビット列を扱いたいので、ビット列のセグメントがどのように作られたかに依存したくはありません。マッチの場合は、これがないとセグメントの数や長さに依存するようになってしまい、 <<1:1, 0:7, 0:*>> などとして生成されたバイナリにしかマッチしなくなってしまいます。

/bitstring は一つのセグメントについてあればよいようです。



最後の bin(<<_/bitstring>>) は、ビット列の長さが 7bits 以下の場合にここに還元します。



では実際の動きを見てみましょう。





MSB=1 のビット列の場合



273> test:bin(<<128:8>>).

MSB 1 (rest:0)

ok





MSB=0 のビット列の場合



274> test:bin(<<127:8>>).

MSB 0 (rest:127)

ok



セグメントを明示して作ったビット列



268> test:bin(<<1:1, 5:7>>).

MSB 1 (rest:5)

ok



/binary を指定しているので、生成時のセグメントには依存しません。





267> test:bin(<<129:8, 0:128>>).

MSB 1 (rest:1)

ok

271> test:bin(<<129>>).

MSB 1 (rest:1)

ok





まとめ

強力なライブラリと list, map などのデータ構造……。興味は尽きないのですが、取り急ぎ、自分が必要とするところだけを駆け足で見てみました。

なかでもバイナリマッチングは強力で、パフォーマンスまではわかりませんが、かなり面白いです。

なんでこんなに俺得仕様なのかといえば、 Erlang は元々携帯電話の基地局などで使われていたと聞きます。当然何層ものパケットを解析してディスパッチ先を決め、割り込みにも高速に応答しなければなりません。そのせいでしょうか。

現在はスケールしやすさが買われているようです。

実際に動かしてみると、仮想マシン上のシステムにしてはなかなか IO の応答性がよくてときめきました。

携帯電話の基地局といえば、かつて WindRiver の VxWorks で動いているシステムを見たことがありますが、ああした環境の小さな OS で動けば、かなり使い手のある言語/環境だと思います。













投稿者



時刻:





















ラベル:
,

















0 件のコメント:















コメントを投稿
























        

      









登録:
コメントの投稿 (Atom)