すごいErlangゆかいに学んだメモ 第1章～第9章

すごいErlangゆかいに学ぼう！

Erlang の勉強のため写経したりメモ書きしたものです。
とても分かりやすく良い本なので、Erlangに興味ある人は購入されることをオススメします。

第１章

アトム

• アトムはアトム表で参照されていてガベージコレクションの対象にならない。4byte(32bit sys) or 8byte(64bit sys) のメモリを消費するので、動的にアトムを生成するのはメモリ枯渇の原因になるので、やらないこと。また、アトムの最大個数は 1048577個、これは設定で変更可能。
• Erlang では なんでも比較できる
  • 言語設計思想。
• true , false は単にそういうアトムであるだけだが、言語実装と深く結びついてるのでOK
• true < 1 は false , なぜなら、上述の通りなんでも比較可能だから。

タプル

• 最初の要素がアトムなタプルを タグ付きタプル という。

リスト

• あきらかにErlangでもっとも使われるデータ構造
• 文字列 = 整数のリスト
  • Erlang の最悪な部分の一つ
• Erlang には組み込みの文字列型はない
• 結合と要素の削除は　++ と --
  • どちらも右結合
  • 複数の ++ や -- が並んだ時、右から左へ実行される。
• リスト操作はまずヘッドをみる
  • 一番高速にアクセスできるから
  • [Head |Tail ]
• [1 | 2] は 非真正リスト とよばれる。
  • 構文的に正しいが、Erlang的にはだいたいエラーの原因なので使うな
  • 正しいリストは、テイルが [] つまり空リスト、例えば [1|[2| [] ]] は正しい。
  • [1|[2]] は自動的に正しくなるが、 [1|2] テメーはダメだ。

リスト内包表記

[X || X <- [1,2,3,4,5,6,7,8], X rem 2 =:= 0].

• 末尾の条件部分は , で区切れば複数設定可能
• X <- [...] の部分は 生成式 という
  • 生成式は , で区切れば複数個おける。
  • パターンマッチできる。
    • パターンマッチしなかったとき、例外は投げられず単に無視されるだけ

バイナリデータ

bit構文

• バイナリデータを読みやすいセグメントに分けたもの
  • デフォルト 8bit 区切り

Color = 16#F09A29.
Pixel = <<Color:24>>.  %% <<240, 154, 41>>

• バイナリでのパターンマッチもできる

  • デフォルト 8bit 区切り
  • パターンマッチするときも、セグメント数を合わせないと no match error
  • セグメント数を調整したければ、マッチ側で :bit数 でビット数を指定してセグメント数と総ビット数をあわせること。

• バイナリパターンマッチにおける [ヘッド|テイル]

  • 糖衣構文がある
  • <<Byte:8, Rest/binary>> = BinData.
  • Rest/binary はどんな長さのバイナリでも、ここに突っ込まれる。
    • リストで言うテイル

• バイナリ構文

1. 値
2. 値:サイズ
3. 値/型指定子リスト
4. 値:サイズ/型指定子リスト

型指定子リスト

• 型-符号フラグ-エンディアン-ユニット という書式
  • 使わない部分あれば省略可能
• 型は、ビット列がどのデータ型で扱われるのかを指定
  • bits = bitstring
  • byte = binary なので注意
• 符号フラグは signed / unsigned か
• エンディアンは
  • little
  • big
  • native(実行環境のCPUと同じ)
• ユニットは、各セグメントのサイズ
  • unit:整数 のように書く
  • 整数部は 1～256
  • bit, float ではデフォルト1, byte ではデフォルト8(これは上述の通り)
  • utf8, utf16, utf32 はもう型名にユニット数が指定されているんで、いらない

Hoge = <<25:4/unit:8>>.  %% 4がバイトサイズ(4byte), 8がセグメントサイズ(8bit)
<<0, 0, 0, 25>> = Hoge.  %% よって 32bit / 8 = 4セグメント

ビット単位のバイナリ操作

• 先頭に b(bit) がついた演算子

  • bsl(bit shift left) 左シフト
  • bsr(bit shift right) 右シフト
  • band, bor, bxor, bnot

• いくらビット演算が簡単でも、動画変換や画像処理は Erlang では遅いので、素直に別の言語使いましょう。

バイナリ文字列

<<"this is a binary string">>.

• 通常の文字列(リスト)より省メモリ
• よりCの文字列に近い
• バイナリ文字列をタプルのタグに使うのは止めろ
  • 普通にアトム使え

バイナリ内包表記

<< <<X>> || <<X>> <= <<1,2,3,4,5>>, X rem 2 == 0>>.

• リスト内包表記と違うところは、

  1. <- が <= になってる
  2. [] が <<>> になってる

• RGBバイナリを操作する例

%% <= を使えばバイナリデータも生成器にできる
Pixels = <<213, 45, 132, 64, 76, 32, 76, 0,0, 234, 32, 15>>.
RGB = [ {R, G, B} || <<R:8, G:8, B:8>> <= Pixels ].
%% 逆もできる, リストからバイナリデータへ
BRGB = << <<R:8, G:8, B:8>> || {R, G, B} <- RGB >>.

• <-. <= の生成器を使おうが、バイナリを生成するときは、生成された要素に型が明示されてる必要がある。
  • Erlang では生成器のデフォルトは 8bit/integer を推測する

%% 生成された値がバイナリだと明示する例。
<< <<Bin>> || <<Bin>> <- [<<1,2,3>>] >>.  %% Bin <- だとエラー、 受け取り変数が Bin だと整数になって <<Bin>> できない
<< <<Bin/binary>> || Bin <- [<<0,1>>] >>.  %% Bin/binary がないとエラー。受け取るデータがバイナリだとErlang側に明示しないとだめ。

---

第２章モジュール

• 属性と関数からなる
  • 属性とは作成者やバージョンなどのメタ情報

%% hoge.erl
-module(hoge).

• モジュール属性は、ファイル名と一致する必要がある。

  • 一致していないとコンパイルされない

• -import はコードの可読性を下げるので基本使うな

  • python で from hoge import * しないのと大体同じ
  • -import(lists, [hoge/1, ..]) はあるかも
    • なぜなら lists モジュールはかなり頻繁に使われるんで

コンパイル

• シェル
  • $ erlc [フラグ] hoge.erl
• Erlangの関数から (モジュール内でも記述可能)
  • compile:file(hoge.erl).
• Erlangシェルから
  • c(hoge).

コンパイルオプション

1. -debug_info
   • 常に有効に指定置くのが好ましい。省略したところでディスクスペースをちょっと節約する程度
2. -{outdir, ディレクトリ}
   • .beamファイルの生成場所
3. -export_all
   • 全部 export する。開発中によく使う。プロダクション環境では使わない。
4. -{d, マクロ} or -{d, マクロ, 値}
   • モジュールで使われるマクロを定義。単体テストでよく使われる。テストフラグを与えたりとか。

使用例

-compile([debug_info, export_all]).

ネイティブへのコンパイル

対象環境で動作するネイティブコードも生成できる。最大20%くらい早くなるとか。
普通の .beam はVM用のバイトコードなのでクロスプラットフォーム。
当然ネイティブ化した .beam はクロスプラットフォームじゃなくなる。

hipe モジュールを使う

hipe:c(hoge.erl, [option1, option2]).

シェルでは
c(hoge, [native]). とする。

早くはなるけど、 hipe でネイティブコンパイルは 高速化の最後の手段 だと思うように。

マクロの宣言

-define(MACRO, value).
-define(add(X, Y), X+Y).

C の #define と似てる。
コード内のマジックナンバーを抽象化したりとかする。

• アクセスは ?MACRO な形式。

%% 以下はデフォルトで定義済み
?MODULE  %% 現在のモジュール名
?FILE  %% ファイル名
?LINE  %% 行番号

マクロ定義でのコンパイル時の分岐

いわゆる ifdef
コンパイル時にマクロ定義して渡したりして分岐させたりとか。
c(hoge, [{d, 'TEST'}]). とか。

-ifdef(TEST).
-define(DO_TEST(), io:format("do test")).
-else.
-define(DO_NOT_TEST(), io:format("do not test")).
-endif.

第3章 関数の構文

関数節は ; で区切られ、 関数宣言 まとめられる。

関数宣言とは、大きな一文みたいなもので、最後がピリオド . で終わる。

通常のパターンマッチで比較できるものは

1. 既知の数
2. アトムのような一意な値
3. N個の要素、みたいな抽象的な値
4. _

で、型とか値の範囲を調べられない。これを解決するのがガード節

ガード

• ガード式では副作用は許可されないので、ユーザー定義関数は使えない
  • Erlang には多くの副作用があるので、パターンマッチとかではユーザーを信用してない

is_big(X) when X > 100 -> true;
is_big(_) -> false.

ガード節にはガード式が必要。
ガード式とは、

• 成功時に true
• 失敗時に false or 例外

ガード式では以下の区切りで式を複数個おける

• , と andalso (短絡評価)
• ; と orelse (短絡評価)

. と ; は例外発生時はキャッチしてもみ消してスルー。
andalso と orelse は例外をキャッチせず返してくる(例外発生した時点でガード式は失敗となる)

if節

• ガードパターン とも呼ばれる。
  • when hoge な部分を関数内部で呼び出せるということか。

if_func(N) ->
    Ret = if N =:= 1 -> one;
             N =:= 2 -> two;
             true -> other  %% 多言語でいう else
          end.

• true による catch-all は、基本避けるべき。

case of 式

• 関数のヘッド全体のようなもの
  • 多分、関数定義のパターンマッチ部分のことを言ってる
  • 複数の関数定義でパターンマッチさせている部分を、ひとつの定義関数内で case of を使用してパターンマッチに相当させることもできるということか。

insert(X, []) ->
    [X];
insert(X, Set) ->
    case lists:member(X, Set) of
        true -> Set;
        false -> [X|Set]
    end.

if, case の使い分け

• case of

  • 関数のパターンマッチ部分に相当

• if

  • パターンマッチ後のガード部分に相当

• 使い分けに明確な回答はない。

• ２つ以上の引数をチェックするときは関数ヘッドでパターンマッチするほうがベター

• if はガードで実現できる。

  • 手軽なガード(?)

結論：慣れるしかない

---

第4章 型

• Erlang は動的型付け言語なので、エラーはランタイム時に取得される
  • Let it Fail の思想なので、動的型が原因で落ちても気にしない
  • 復帰できればOK

型変換

erlang:list_to_integer("54").  %% 54

• hoge_to_fuga という関数名
  • 型名_to_型名 という規則
  • 型が追加されると、BIFの種類が増えてしまう欠点

パターンマッチで型を判別したい

%% 宣言的な書き方
hoge(X) when is_integer(X) -> integer_to_list(X);
hoge(X) when is_list(X) -> list_to_integer(X).

%% だいたい以下のような意味
%% type_of という BIF はないので注意
%% Erlang的に好ましくない書き方
fuga(X) ->
    case type_of(X) of
        integer -> integer_to_list(X);
        list -> list_to_integer(X)
    end.

• ガード式で判別

  • 型テストBIF
  • ガード式でも使える特別な関数

• Erlang では、 起こると期待されることのみ実装 するべき

  • 恐れず速やかにエラーを出させるコードを推奨

• 型テストBIFをガードに使うような 宣言的記法 が好まれる

  • type_of のような関数の返り値から分岐するようなのは暗黙的な感じがして良くない

第5章 再起

%% 末尾再帰ではない
fact0rial(N) when N == 0 -> 1;  %% factorial(0) -> 1;
factorial(N) when M > 0 -> N * factorial(N-1).

%% リストの長さ
len([]) -> 0;
len([_|T) -> 1 + len(T).

• Erlang のループは全部再起で書く
• 末尾再帰されていない再起は、呼び出された関数スタックが残るので、大量に再起があるとメモリが枯渇する
  • 末尾再帰でスタックを破棄できるようにする最適化をしましょう
  • アキュムレータ で都度の結果を保存して次の再起に渡す
    • アキュムレータで途中の演算を渡せば、呼び出した側はすることが残ってないので関数スタックを破棄できる

tail_fac(N) -> tail_fac(N, 1).
tail_fac(0, Acc) -> Acc;
tail_fac(N, Acc) when N > 0 -> tail_fac(N-1, N * Acc).

• 末尾再帰にする考え方
  1. 末尾再帰ではない普通の再起で書く
  2. 途中の処理をアキュムレータにする
  3. 終了条件を書く

tail_renient_zip(Xs, Ys) -> lists:reverse(tail_renient_zip(Xs, Ys, [])).

tail_renient_zip([], _, L) -> L.
tail_renient_zip(_, [], L) -> L.
tail_renient_zip([X|Xs], [Y|Ys], L) -> tail_renient_zip(Xs, Ys, [{X, Y}|L]).

• クイックソートの例

quicksort([]) -> [];
%% Smaller, Larger を parition関数でどんどん分割していき、最後に ++ でくっつける。
quicksort([Pivot|Rest]) ->
    {Smaller, Larger} = partition(Pivot, Rest, [], []),
    quicksort(Smaller) ++ [Pivot] ++ quicksort(Larger).

%% 渡されたリストを Pivot と比較して二分する関数
partition(_, [], Smaller, Larger) -> {Smaller, Larger};
partition(Pivot, [H|T], Smaller, Larger) ->
    if H =< Pivot -> partition(Pivot, T, [H|Smaller], Larger);
       H > Pivot -> partition(Pivot, T, Smaller, [H|Larger])
    end.

• リストの内包表記で書き直すとこうなる

quicksort([]) -> [];
quicksort([Pivot|Rest]) ->
    quicksort([Smaller || Smaller <- Rest, Smaller =< Pivot])
    ++ [Pivot] ++
    quicksort([Larger || Larger <- Rest, Larger > Pivot]).

二分木を再起で実装する

リスト以外にも使い道はある

• 仕様
  • 木構造を {node, {Key, Value, Smaller, Larger}} で表す
  • 終了条件は {node, 'nil'}
    • ノードの開始もこの構造とする。
  • 同じ値のノードを挿入するとは、値を上書きする。
  • Erlang は変数は不変なので、木を操作するたび新しいデータが生成されて返される
    • 永続データ構造 のお陰でメモリのオーバーヘッドが抑えられてるので大丈夫

新しいデータの挿入・更新

%% 終了条件
insert(Key, Val, {node, 'nil'}) ->
    {node, {Key, Val, {node, 'nil'}, {node, 'nil'}});
%% 大きい、小さい値を挿入
insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey < Key ->
    {node, {Key, Val, insert(NewKey, NewVal, Smaller), Larger}};
insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey > Key ->
    {node, {Key, Val, Smaller, insert(NewKey, NewVal, Larger)}};
%% 同じ値は上書き
insert(Key, Val, {node, {Key, _, Smaller, larger}}) ->
    {node, {Key, Val, Smaller, Larger}}.

ノードの検索

lookup(_, {node, 'nil'}) ->
    undefined;
lookup(Key, {node, {Key, Val, _, _}}) ->
    {ok, Val};
lookup(Key, {node, {NodeKey, _, Smaller, _}}) when Key < NodeKey ->
    lookup(Key, Smaller);
lookup(Key, {node, {_, _, _, Larger}}) ->
    lookup(Key, Larger).

木構造のデータは自前実装より Erlang についてくる stdlib/src/gb_trees.erl を使うのが一番いいし、ソース読めば勉強になるよ。

---

第6章 高階関数

fun mod:func/1  %% 関数を関数として渡す

よくある例

• map関数

map(_, []) -> [];
map(F, [H|T]} -> [F(H)|map(F,T)].

incr(X) -> X + 1.
decr(X) -> X - 1.

map(fun incr/1, [1,2,3,4,5]).
map(fun decr/1, [2,3,4,5,6]).

• filter関数
  • filter する条件式を 述語 ということがある
  • 英語で predicate -> Pred

filter(Pred, L) -> lists:reverse(filter(Pred, L, [])).

%% Pred は true/false を返す判別関数(述語)
filter(_, [], Acc) -> Acc;
filter(Pred, [H|T], Acc) ->
    case Pred(H) of
        true -> filter(Pred, T, [H|Acc]);
        false -> filter(Pred, T, Acc)
    end.

• fold関数
  • リスト全体からひとつの答えを出す
  • 畳み込み とも
    • リストの合計や最大値や最小値を求めるような操作など

%% Start の値は問題によって異なる。
%% 総和なら0, 最大/最小の検索ならリストのヘッドなどを渡せば良い
fold(_, Start, []) -> Start;
fold(F, Start, [H|T]) -> fold(F, F(H, Start), T).

無名関数

• filter, map, fold などに食わせる判別関数の生成に使える
  • その他にもいろいろ使える。

fun(X) -> X + 1 end.
fun() -> hoge end.
fun(hoge) ->
        io:format("pattern match hoge");
    (fuga) ->
        io:format("pattern match fuga")
end.

%% 即時実行
(fun() -> "hoge" end)().
(fun(A) -> A + 1 end)(1).  % 2

クロージャ

-module(closure).
-export([main/0]).

base(A) ->
    B = A + 1,
    F = fun(A) -> A * B end,
    F(2).

base2(A) ->
    B = A + 1,
    F = fun(C) -> B * C end.

main() ->
    Ans = base(2),
    F = base2(2),
    Ans2 = F(3),
    io:format("~p~n", [Ans]),   % 6
    io:format("~p~n", [Ans2]).  % 9```

• シャドーイング (Shadowing)
  • コンパイル時に警告出る
  • クロージャ定義で、ネストしてる内部のスコープで、同じ変数名が再定義されていること
  • 構文上エラーではないが、大抵の場合ミスなので修正しておけ

---

第７章 エラーと例外

• Erlang は２つのパラダイムを持つ

  • 関数型言語
  • 並行処理

• Erlang は たいていクラッシュさせた方がいい

  • Erlang のエラー処理は並行性側の機能の一部
    • (私見:エラー処理は並行処理、というのは重要な概念っぽい)

まず、エラー処理(並行処理) に進む前に関数型言語の部分にまずは注目する

エラーの種類

1. コンパイル時エラー
2. 論理的なエラー(実装ミス)
3. ランタイムエラー
   • 関数節エラー
     • no function caluse matching)
     • ガード節での失敗やパターンマッチしなかったとき
   • case節エラー
     • no case clause matching)
     • 条件の書き忘れ、誤ったデータ型が来た、catch-all節が必要なのになかった時
   • if節のエラー
     • no true branch found
     • true になる条件がなかったとき
   • 間違ったパターンマッチのエラー
     • no match of
     • リストとタプルをパターンマッチさせたりとか、 _Hoge な変数で同じ名前のやつを複数回つかっちゃったりしたとき
   • 間違った引数で関数呼び出してエラー
     • bad argument in function
     • 例えば list_to_binary(12345). とかしちゃうと起きる
   • 未定義関数を呼び出してエラー
     • undefined function
   • 間違った演算してエラー
     • bad argument in an arithmetic expression
     • 1 + "a". とか
   • 関数じゃないものを関数として使おうとしてエラー
     • bad function
     • 123(). とかやっちゃう
   • 間違ったアリティ数を関数に渡しちゃってエラー
     • interpeted function with arity
     • 高階関数の使用時に、引数に定義数と異なる引数を与えた時とか
   • システムの限界エラー
     • プロセス数、アトム数、ノード数が限界きたとき
     • アトムの名前が長すぎたりとか

例外を発生させる

Erlang の例外３種

1. エラー (error)
   • erlang:error(Reason)
   • コードの実行をストップできる
     • if節で例外発生 → 何ができる？ → なにもできん → 修正して再コンパイルするしか… → なら実行止めろ
   • スタックトレース取得できる
2. 終了 (exit)
   • 内部終了
     • erlang:exit/1
     • 今走ってるプロセスを止める
     • erlang:error とほぼ同じ(歴史的経緯的にも使い方的にも)
     • スタックトレースは取れない
   • 外部終了
     • erlang:exit/2
     • マルチプロセスで関係してくる
3. スロー (throw)
   • 例外のクラス
   • プログラマが予想できる(できた)事態に対応するために使用する
     • フロー制御のために使う
     • error, exit とは違い、クラッシュさせない
   • throw(internal_server_error)
   • スローの対処方法をモジュールに書いておくと良いかも

投げられた例外を処理する

-module(exceptions).
-compile(export_all).

trhows(F) ->
    try F() of
        _ -> ok
    catch
        Throw -> {throw, caught, Throw}
    end.

• try ... of の間の関数を 保護されている と呼ぶ
  • 保護された区間では末尾再帰最適化が適用されないので注意
  • Erlangが例外発生を常に関してしているのでスタックを破棄できない
    • of 以降は保護されていないので末尾再帰は最適化される
• catch 部分で例外クラスが指定されない場合は throw とみなされる。

全部使う例

catchs() ->
    try F() of
        _ -> ok
    catch
        throw:hoge -> "throw(hoge) されたものとマッチ";
        error:fuga -> "erlang:error(fuga) されたものとマッチ";
        exit:piyo -> "exit(piyo) された(ry";
        _:_ -> "マッチしなかった例外を catch-all"
    end.

after 節

• 他の言語でいう finally
  • 例外の有無にかかわらず必ず実行される
  • 呼び出した関数の返り値は取得できないので、副作用コードがかかれるのが普通
    • ファイルのクローズとか
    • パターンマッチとかできないからね

of の省略

• try ... of の間には複数の式を置ける
  • 必要ない場合は of を省略できる

multiple_exp() ->
    try
        hoge(),
        fuga(),
        piyo()
    catch
        _:_ -> "catched"
    end.

catch 構文

• try .. of をさらに省略した感じ
  • 例外を発生したら、 {'EXIT', {Reason}} なタプルを返す

catch throw(whoa).  %% -> whoa
catch exit(die).  %% -> {'EXIT', die}
catch 1/0.  %% -> {'EXIT', {badarith, [スタックトレース..]}}
catch 1 + 1.  %% -> 2

よって、 catch のスタックトレースの形式から、以下のパターンマッチが可能

hoge() ->
    try catch 1 / 0 of ->
        {'EXIT', {badarith, _}} -> "error";
        N -> N
    end.

catch を挟んだ変数束縛

A = catch 1 + 1.  %% エラー、 = と catch は優先順位が同じため
A = (catch 1 + 1).  %% OK

catch の注意点

例外なのか、関数の返り値なのかわからなく場合があるので注意

%% throw がわからなくなる
hoge(1) -> fuga;
hoge(2) -> throw(fuga).
catch hoge(1).  %% fuga
catch hoge(2).  %% fuga

スタックトレースの見方

1> catch 1 / 0.
%% 最後に呼ばれた関数 {Mod, Func, Args}
{'EXIT',{badarith,[{erlang,'/',[1,0],[]},
%% エラーが起きる前に呼ばれた関数 {Mod, Func, Arity, Details} 
                   {erl_eval,do_apply,6,[{file,"erl_eval.erl"},{line,661}]},
                   {erl_eval,expr,5,[{file,"erl_eval.erl"},{line,434}]},
                   {shell,exprs,7,[{file,"shell.erl"},{line,676}]},
                   {shell,eval_exprs,7,[{file,"shell.erl"},{line,631}]},
                   {shell,eval_loop,3,[{file,"shell.erl"},{line,616}]}]}}

• Details はファイル名と行番号

  • 上記の例ではファイル名は erl_eval.erl と shell.erl

• erlang:get_stacktrace/0 でスタックトレースを取得可能

使用例：二分木で throw してみる

• 二分木を検索する例を考える
  • 以下の実装は次の問題点がある
    • true を返すとき、過去辿ってきた case .. of を経由する
    • すでに結果(true) がわかっているのに何回も true -> true してて無駄

%% 二分木から Val な値を検索する
has_value(_, {node, 'nil'}) ->
    false;
has_value(Val, {node, {_, Val, _, _}}) ->
    true;
has_value(Val, {node, {_, _, Left, Right}}) ->
    %% このケース式がスマートではない
    case has_value(Val, Left) of
        true -> true;  %% ここで何回も true を返しながらルートまで戻っていく
        false -> has_value(Value, Right)
    end.

• 上記の実装を、 throw を使って改善する
  • throw で結果(true) を例外として投げれば、一発で再起を脱出できる。
  • 他言語でいう for文の中の break っぽい。

has_value(Val, Tree) ->
    try has_value(Val, Tree) of
        false -> false
    catch
        true -> true
    end.

has_value(_, {node, 'nil'}) ->
    false;
has_value(Val, {node, {_, Val, _, _}}) ->
    throw(true);  %% 見つかったら例外投げる
has_value(Val, {node, {_, _, Left, Right}}) ->
    has_value(Val, Left),
    has_value(Val, Right).

---

第８章 : 関数型的に問題を解く

関数型言語の特徴を使って問題を解いていく。

逆ポーランド記法計算機

ポーランド記法

From: (2 + 2) / 5
To:   (/ (+ 2 2) 5)

逆ポーランド記法 (RPN: Reverse Polish Notation)

From: (2 + 2) / 5
To  : 2 2 + 5 /

逆ポーランド記法はパース処理が少なく省メモリだったため、初期の計算機に使われていたらしい。
これを作ってみる。

考える事 その1. 式の表現方法

• 普通に文字列で
  • 空白を区切りにする
  • split 処理は string:tokens でする

string:tokens("1 1 +").  %% ["1", "1", "+"]

考える事 その2. スタックの表現方法

• リストを利用する

  • Head がスタックの先頭(push)
  • Tail が既存スタック

• リストにスタックを積んでいく

  • 数値なら push
  • 演算子なら pop して必要な関数を呼び出して演算する
    • fold関数使う場面だねこれは。

%% 空白を除去してトークン化したものを rpn/2 で畳み込んで計算する
rpn(L) when is_list(L) ->
    %% リストを左から畳み込み
    [Res] = lists:foldl(fun rpn/2, [], string:tokens(L, " ")),
    Res.

%% 文字列を数値に変換
read(X) ->
    case string:to_float(N) of
        {error, no_float} -> list_to_integer(N);
        {F, _} -> F
    end.

%% スタックを解析して演算を実行する
rpn("+", [N1,N2|S]) -> [N2+N1|S];
rpn("-", [N1,N2|S]) -> [N2-N1|S];
rpn("*", [N!,N2|S]) -> [N2*N1|S];
rpn("/", [N1,N2|S]) -> [N2/N1|S];
rpn("^", [N1,N2|S]) -> [math:pow(N2,N2)|S];
rpn("ln", [N|S]) -> [math:log(N)|S];
rpn("log10", [N|S]) -> [math:log10(N)|S];
%% 演算子でないとき、文字列を数値に変えて次のトークンへ
rpn(X, Stack) -> [read(X)|Stack].

最短経路問題

• 以下の様なグラフから最短経路を探す

A =50====5===40===10== Goal
      |    |    |
      30   20   25
      |    |    |
B =10===90===2=====8== Goal

上記のグラフを以下のフォーマットで表す

road.txt

50 (Aのコスト)
10 (Bのコスト)
30 (横断のコスト)
これが続く

注意：末端のゴール部分にはコストが０の横断路があるものとする。

再帰的に考える

• 何を再起するの？
  • A と B、真ん中を経由する、どれが一番低コストかを選ぶ処理
  • 各交差点へ到達する最短のコストを算出し、最短をそのルートの重みとする
  • 次の交差点への最短コストを、既に算出した重み + 同様の計算 で算出する
    • これを再起
• 終了条件は?
  • A か B のどちらかしか選べない時
    • 三通り選べる時はまだゴールしてない

つまり以下のイメージ

`*` の部分の重みを再起で計算していく。

再起１：最初の経路でどれが低コストか決める
A ==*=====*== Goal
    |     |
B ==*=====*== Goal

       ↓

再起２：次の経路では？ (考える経路を短くする）
A ===*=== Goal
     |
B ===*=== Goal

　　　　↓

再起３：終了条件
A === Goal

B === Goal

実際には上記の処理を「終了条件」から「一般的な状態」に向かって、
どのように処理をしていくのが良いか逆に考えていく。

• 再起で書く

%% まずはファイルを開いてパースする処理
main() ->
    File = "road.txt",
    {ok, Bin} = file:read_file(File),
    parse_map(Bin).

%% binary 形式で読み込んだファイルを数値のリストまで変換する
parse_map(Bin) when is_binary(Bin) ->
    parse_map(binary_to_list(Bin));
parse_map(Str) when is_list(Str) ->
    Values = [list_to_integer(X) || X <- string:tokens(Str, "\r\n\t ")].
    group_vals(Values).

%% 読み込んだ数値を {A, B, 横断路} の形式にする
group_vals([], Acc) ->
    lists:reverse(Acc);
group_vals([A,B,X|Rest], Acc) ->
    group_vals(Rest, [{A,B,X}|Acc]).

%% 最短経路を探す
%% アキュムレータで渡されるとき、各最短経路を保存した状態で引き継がれてくる
%% (A1-A2, B1-X-A2), (B1-B2, A1-X-B2) のうち、短い方を選択していく
%% 選択の際、A, B は前回の最短経路なので必然的に,再起の各段階で最短が選ばれる
%% 例えば A1-A2, B1-X-A2 のどちらかは最短経路を反映された状態をAccに保存していくこととなる
shortest_step({A,B,X}, {{DistA,PathA}, {DistB,PathB}}) ->
    %% DistA,DistBはコメントで言うA1, B1 地点を表す (出発地点でのコスト)
    OptA1 = {DistA + A, [{a,A}|PathA]},  % A1-A2 のコスト
    OptA2 = {DistB + X + B, [{x,X}, {b,B}|PathB]},  % B1-X-A2 へのコスト
    OptB1 = {DistB + B, [{b,B}|PathB]},  % B1-B2 のコスト
    OptB2 = {DistA + X + A, [{x,X}, {a,A}|PathA]},  % A1-X-B2 へのコスト
    {erlang:min(OptA1, OptA2), erlang:min(OptB1,OptB2)}.

%% fold して畳み込み実行
optimal_path(Map) ->
    %% A, B は **ゴールした時の** の道がAかBか。
    {A,B} = lists:foldl(fun shortest_step/2, {{0,[]},{0,[]}}, Map),
    %% road.txt の書式より、最後にコスト０の横断路があるものとしている。
    %% このとき、A,B のコストの高い方のゴールは
    %% かならず {x,0} を経由して最短になる道を選択してくるはず。
    %% なので、最後の経路が {x,0} のものは最短経路ではない
    %% または {x,0} を通る分最短経路は length が短いので、そっちを選ぶとかでもよい。
    %% 実際に紙に動作を書いて確認すると、この if 動作の意味がわかりやすいかも。
    {_Dist, Path} = if hd(element(2,A)) =/= {x,0} -> A;
                       hd(element(2,B)) =/= {x,0} -> B
                    end,
    lists:reverse(Path).

第９章 Erlang の一般的なデータ構造

レコード

• C の構造体みたいなもの
• 実質は タプル上の糖衣構文
• = を使ってデフォルト引数を設定可能
  • 未定義変数があった場合、自動的に undefined アトムが束縛

-module(recode).
-compile(export_all).

-record(robot, {name, type=indutrial, hobbies, details=[]).

first_robot() ->
    #robot(name="Ralf", type=manmachine, details=["we are the robots"]}.

シェルからレコードを操作する

%% モジュールからレコード定義を読み込む
rr(ModName).
%% レコードを定義する
rd(Name, Def).
%% すべてのレコードをアンロードする
rf().
%% 特定のレコード定義を消す
Urf(Name).
rf([Name]).
%% 特定のレコード定義をプリント
rl().
rl(Name).
rl([Names]).

レコードから値を読む

1. ドット構文

• きれいな構文ではない
  • レコードがネストしていると悲惨
  • 実質はタプルなので仕方がない

Robot = #robot{name="Hutter", hobbies["Cycling"]}.
io:format("~p", [Robot#robot.hobbies]).  %% レコードの内容を読み込み

%% ネストしたレコード
Robot2 = #robot{details=#robot(name="Florian"}}.
io:format("~p", [ (Robot2#robot.details)#robot.name ]). %% カッコは必須ではない

1. パターンマッチ

-record(user, {id, name, group, age}).

%% フィルタ目のためパターンマッチ
admin_panel(#user{name=Name, group=admin}) ->
    Name ++ " は管理者";
admin_panel(#user{name=Name}) ->
    Name ++ " は管理者ではない".

%% パターンマッチ中でのレコードの展開
adult_section(U = #user{}) when U#user.age >= 18 ->
    allowd;
adult_section(_) ->
    forbidden.

レコードの更新

update(Record) ->
    Old = Record#hoge.fuga,
    New = Record#hoge{fuga=["Updated | Old]}.
    {updated, New}.

レコードは融通が聞く

• 未定義変数があってもいい
• 名前付きタプルみたいなもの
  • タプルのようにソリッドなデータ構造じゃないので、データの追加が容易
  • 名前で修飾できるのでパターンマッチの更新・修正が楽
    • タプルだったら {record, _, _, Group, _, _, Age} とかなってしまう！

レコードの共有

ヘッダファイル でレコード定義を共有する
header.hrl という拡張子。

hoge.hrl

-record(hoge, {fuga, piyo="piyo"}).

こういうファイルを .erl 中で

-include("hoge.erl")
hogehoge -> #hoge{fuga="fuga"}.

とかする。

KVS

Erlang内にある、少量のデータのための KVS風データ構造は２つ

1. proplist (プロパティリスト)

• [{Key, Val}] なタプルのリスト
  • 定義はこれだけ
    • Val 部分は省略できて、そのときは {Key, true} と同義
  • 非常にゆるいデータ構造
• proplists モジュールを使う
  • 値の検索、取得、削除の関数が定義されている
  • 更新する関数はないので cons で新しい値を先頭に追加していく
    • 一番先頭データが最新データという解釈
• 属性のリストが必要なときとかに使う。

2. orddict (順序付き辞書)

• 少量データに対するちゃんとしたKVSならこれを使う
  • proplists より厳密
  • Key は一意
  • orddict モジュールがCRUD操作の関数インターフェイスを用意してるのでそれを使う
  • 75 要素くらいまでなら使える
    • それを超えるなら別の使う

余談：配列

• Erlang の変数は変更不可の 永続的 データ
  • 配列操作は他の言語に比べて遅い
  • 行列計算とかは、NIF, ports, Cノードなどに任せたりすることが多い

より巨大な辞書

1. dict (辞書)
   • orddict で扱いきれない大量の要素を処理したいときはこれ
   • orddict と同じ関数I/Fを持つ
2. gb_trees (平衡木構造)
   • バランスを保つ木構造
   • ノードの追加・削除時に平衡を保つ操作が入るので、多少メモリや処理時間を食う

２つの使い分けは、明確なルールは言えない。どちらもパフォーマンスは同じくらい。自分でベンチマークとったりして判断してね。
あと、辞書には fold あるけど 平衡木にはないとか、いろいろ仕様も違うので確認してね。

セット

• 集合
  • 実装によって４種類のセットを扱うモジュールが用意されている

以下略

有向グラフ

• digrapho, digraph_utils モジュールの２つ
• グラフ理論の知識や、集合論の基礎知識なしで使うのはやめたほうが良い

キュー

• queue モジュール
  • 両端FIFOキューで実装されてる
  • 内部的にプッシュ用、ポップ用の２つのリストがある。
• リストの順番がちゃんと保証されたいときに使うといいかもね
  • 普通のリストと比較してパフォーマンスは確認してね。

大事なこと

• いろいろデータ構造があるけど・・
  • いつも最初にテストと計測をやること！！！