Boost.Spirit.X3 の練習 2

Boost.Spirit.X3 の練習1 - プログラミングのメモ帳➚に引き続き，Boost.Spirit.X3 のお勉強メモです．

セマンティックアクション

構文解析にはセマンティックアクションというのがつきものです．
yacc や parsec など有名な構文解析のためのツール/ライブラリにもありますね．

セマンティックアクションとは，定義したパーサのルールにマッチした時に実行するプログラムのことです．
といってもわかりにくいと思うので，コードを出してしまいます．

以下のコードは，浮動小数点数にマッチしてその値を標準出力に出力するパーサの定義です．

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>


namespace x3 = boost::spirit::x3;

auto const print_action =
  [](auto& ctx) { std::cout << _attr(ctx) << std::endl; };

int main()
{

  std::string src{ "( 123.4 )" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);

  auto parser = ("(" >> x3::double_ >> ")")[print_action];

  bool success = x3::phrase_parse(first, last, parser, x3::ascii::space);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  }
}

$ clang++ -std=c++14 main.cpp
$ ./a.out
123.4

パーサの結果を受け取らないようにしています．parser は double を返しますが，その結果は無視しています．
そして，セマンティックアクション部分で，出力を行っています．

auto const print_action の定義が，セマンティックアクションです．
C++14 のジェネリックラムダの機能をつかっています．
セマンティックアクションは，X3 パーサのコンテキストを第一引数に取ります．
その具体的な型を気にしてはいけません．ジェネリックラムダで受け取ります．
_attr(ctx) で，現在マッチしているパーサの attribute にアクセス出来ます． "(" >> x3::double_ >> ")" の attribute は double 型なので，_attr(ctx) はマッチした浮動小数点数になります．

Qi のセマンティックアクションは，関数オブジェクトなどを単純に使用することが出来ませんでした(?) が，X3 ではセマンティックアクションはただの関数オブジェクトです．
パーサのコンテキストを引数に受け，結果や attribute への参照をそのまま関数内で扱えるようになったため，セマンティックアクションの記述がより 普通 の関数っぽくかけるようになったと感じました．

名前付きパーサの定義

今までのサンプルでは，シンプルなパーサを１つ定義しているだけでした．
一方現実には，パーサが再帰的になることは珍しくありません．

そこで，パーサの名前を前方宣言し，あとから定義を記述するようなパーサの書き方を使用します．

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>


namespace x3 = boost::spirit::x3;

namespace detail {

  x3::rule<class constant, int> const constant;

  auto const constant_def = x3::int_;

  BOOST_SPIRIT_DEFINE(constant);

} // namespace detail

using detail::constant;

int main()
{

  std::string src{ "123" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);


  int result;
  bool success = x3::phrase_parse(first, last, constant, x3::ascii::space, result);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  } else {
    std::cout << "Parse: " << result << std::endl;
  }
}

namespace detail の中身がパーサの定義になっています． (namespace を分けたのは，constant そのものの名前以外を隠すためです．) X3 では，x3::rule<class, result type> というテンプレートクラスがパーサルールになります．class 部分は今は前方宣言だけで構わないようです．(後で on_error とかの属性を付与する際に必要になる？)
result type はそのパーサが返すべき値になります．

つまり，x3::rule<class constant, int> const constant; は，int 型の値を返す，特別な属性を持たない constant という名前のパーサを宣言したことになります．

そして，その実装は constant_def という名前で与えられます．
hogehoge_def という名前にする規約のようです．(BOOST_SPIRIT_DEFINE 部分を書き換えれば違う名前にしても大丈夫のようだが，素直に従っておけば良さそう)
今回はシンプルに x3::int_ そのものとしています．

最後に BOOST_SPIRIT_DEFINE することで，constant というパーサの宣言と，constant_def という実装をひも付けます．

使い方は今までと全く同じです．

使ってみる

セマンティックアクションと名前付きパーサの両方を使って，整数を受け取って2倍にした値を返すパーサを書いてみます．

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>


namespace x3 = boost::spirit::x3;

namespace detail {

  auto const twice = [](auto& ctx) { _val(ctx) = _attr(ctx) * 2; };

  x3::rule<class constant, int> const constant;

  auto const constant_def = x3::int_[twice];

  BOOST_SPIRIT_DEFINE(constant);

} // namespace detail

using detail::constant;

int main()
{

  std::string src{ "123" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);


  int result;
  bool success = x3::phrase_parse(first, last, constant, x3::ascii::space, result);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  } else {
    std::cout << "Parse: " << result << std::endl;
  }
}

セマンティックアクション内では，パーサの result type に _val(ctx) でアクセス出来ます． _val(ctx) は参照を返すので，ここに適当な値を代入してやれば，パーサの返り値にすることが出来ます．
_attr(ctx) は先程と同じです．x3::int_ の attribute は int です．

実行してみると，Parse: 246 が返るはずです．

一旦まとめ

セマンティックアクションと名前付きパーサの宣言と定義をまとめました．
Qi のころより，セマンティックアクションはかなり書きやすくなっている気がします．
今回の例では，_attr(ctx) が単純な値だったのでわかりやすいですが，x3::int_ >> x3::double_ の _attr(ctx) は Boost.Fusion が登場したりしてちょっとややこしそうです．

また，再帰的パーサを定義できるようにパーサの宣言をまとめたのに，再帰的パーサを書いていませんが，これは別記事に電卓でも作ってまとめたいと思います．

Boost.Spirit.X3 の練習1

Boost.Spirit.X3 の練習1

Boost.Spirit.X3 という C++ のための パーサコンビネータライブラリを使ってみています．
Boost.Spirit というと， C++ の黒魔術の塊みたいなイメージがあります． ちなみに Boost.Spirit.Qi が安定版のパーサコンビネータライブラリで， X3 はまだ開発中のようなので注意してください．

X3 は Qi と異なり，C++14 以降の規格を前提にしています．そのため，ジェネリックラムダなどを用いてよりわかりやすいプログラムが書けるようになっているようです．
Qi はコンパイル時間が爆発していたのですが， X3 だと多少マシのようです．

第一歩

まずは猛烈にシンプルなパーサを使ってみましょう． X3 も Qi 同様に定義済みのパーサがあるので，それを単純に使用するだけのサンプルです．

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>


int main()
{
  namespace x3 = boost::spirit::x3;

  int result;
  std::string src{ "123" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);
  bool success = x3::parse(first, last, x3::int_, result);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  } else {
    std::cout << "Parse: " << result << std::endl;
  }
}

コンパイル & 実行

$ clang++ -std=c++14 int_parser.cpp
$ ./a.out
Parse: 123

Boost.Spirit.X3 を使用する場合は, #include <boost/spirit/home/x3.hpp> とすればオッケーです．(これは使用していない機能のヘッダも読み込んでしまっているので，コンパイルは重くなります… が，これ以降使う機能を増やす度にヘッダを書き換えるのは面倒ですし，X3 の機能の多くを使用するプログラムの場合は，大差ないと思います．)

名前空間は boost::spirit::x3 です．頻繁に出てくるので namespace x3 でエイリアスしました．

実際にパースしている部分は,

bool success = x3::parse(first, last, x3::int_, result);

の部分です．
x3::parse は，第一引数にソース文字列の先頭イテレータ，第二引数にソース文字列の終端イテレータをとります．
第三引数が，パーサの定義です．ここでは， x3::int_ という定義済みパーサを使用しました． これは, 整数を表す文字列を受けて，それを整数に変換するパーサです． たとえば "1" を 1 に変換します．整数以外にあたった場合はマッチせず，パースに失敗します．(x3::parse の返り値が false になる) 第四引数は，指定したパーサの返す値です．ここちょっと説明が難しいですね．
x3::int_ は int 型の値を返すパーサです(これを x3::int_ の attribute が int 型であると表現している？).
そこで，x3::int_ の返す値を格納する変数として，int result の参照を渡しているという感じです．
パースが成功していれば，result の中身は x3::int_ の返り値になっているはずです．

パースの成否判定は success と first == last で行います．

if (!success || first != last) {

success はそもそもパーサにソースがマッチしなかった場合, false になります．
また，"123abc" に x3::int_ をマッチさせると，"123" だけが消費され，"abc" が残ります．この時，first は "a" の位置まで進んでいます． もしソースが先頭から終端まで，パーサにマッチしていたならば，first == last となるはずです．

というわけでこのプログラムは，x3::int_ に "123" をパースさせるプログラムでした．結果，きちんと整数の 123 が取得できていることがわかります．

コンビネータ

Boost.Spirit.X3 はパーサコンビネータライブラリです．個々のパーサを組み合わせてみましょう．

" ( 1234.5)" とか "(67.8 ) " にマッチして，double を返すようなパーサを定義してみます．

auto parser = x3::lit("(") >> x3::double_ >> x3::lit(")");
bool success = x3::phrase_parse(first, last, parser, x3::ascii::space, result);

まずは parser の定義です． x3::lit はリテラルを表します．引数にとった文字列にマッチし，何も返さないパーサです．x3::lit("(") は ( にマッチし，何も返さないパーサということになります．
x3::double_ は x3::int_ と同じく，定義済みパーサで，浮動小数点数にマッチしその値を返します．

そして重要なのが，>> です．
これは，「左辺にマッチした後，右辺にマッチするパーサ」を作り出すコンビネータです．
ここでは，x3::lit("(") >> x3::double_ ですから，( にマッチした後，浮動小数点数にマッチするパーサ，ということになります.

通常，>> は左辺の返す値と右辺の返す値のタプルを返します．(x3::int_ >> x3::double_ ならば，int と double のタプル)
しかし，左辺右辺どちらか一方が値を返さない(正確には x3::unused_type を返す) 場合には，もう一方の値だけを返します．
つまり，x3::lit("(") >> x3::double_ は double だけを返し，>> x3::lit(")") と続けても double だけが返ります．

次に，空白の読み飛ばしについてです．

bool success = x3::phrase_parse(first, last, parser, x3::ascii::space, result);

ひとつ目の例と異なり，x3::parse ではなく x3::phrase_parse を使っています．
こちらは，attribute を示す最後の引数の前に，スキップパーサを取ります． スキップパーサとは，文字通り，スキップしてほしい文字列にマッチするパーサです．
x3::ascii::space は定義済みのパーサで，スペース，改行文字，タブにマッチします．したがって，これらの文字はスキップされます． スキップ判定のタイミングは >> の部分です．つまり，"12 3" は x3::int_ でパースすると, 12 までしかマッチしません．x3::int_ >> x3::int_ とすることで，スペースがスキップされます．

#include <boost/spirit/home/x3.hpp>

#include <iostream>
#include <string>


int main()
{
  namespace x3 = boost::spirit::x3;

  std::string src{ "( 123.4 )" };

  auto first = std::cbegin(src);
  auto const last = std::cend(src);
  double result;
  auto parser = x3::lit("(") >> x3::double_ >> x3::lit(")");
  bool success = x3::phrase_parse(first, last, parser, x3::ascii::space, result);

  if (!success || first != last) {
    // parse failed
    std::cerr << "Parse failed." << std::endl;
  } else {
    std::cout << "Parse: " << result << std::endl;
  }
}

ちなみに，x3::lit("(") >> x3::double_ >> x3::lit(")") の部分ですが，operator<< の引数の内，片方がパーサであれば，char const* から暗黙変換が働くので， "(" >> x3::double_ >> ")" と書くことが出来ます．

コンビネータは他にもあります．

• |
  • a | b で，a にマッチするか b にマッチするか
  • a を先に試すので，両方にマッチする場合でも a にマッチしたことになる (PEG の特徴ですね)
  • 返り値は boost::variant<a, b> です．a と b が同じ型を返す場合はその型を返します
• >
  • >> とほぼ同じです．
  • a >> b は a にマッチして b にマッチしなかった場合，a の前にバックトラックします.
  • a > b はその場合，即座にパース失敗を通知します．
• *
  • *a という形で使う
  • a の 0 回以上の繰り返し
  • 返り値は std::vector<a>
• +
  • +a という形で使う
  • * の一回以上繰り返し版
• -
  • -a という形で使う
  • a が来ても来なくても良いというパーサ
  • 返り値は boost::optional<a>

...

> と >> の違いはわかりにくいですね．
(x3::lit("(") >> ")") | ("(" >> x3::int_ >> ")") に "(123)" を食わせると，| の後半部分にマッチしてくれます． 一方, >> を > に置換えた場合，ソース先頭の"(" がx3::lit("(") にマッチするにもかかわらず，その直後に")" が来ていないため，その時点でエラーを通知してしまいます．

一旦むすび

とりあえず最も基本的な部分をまとめてみました．
ここまでは Qi と同じなんですよね．

セマンティックアクションや on_error などの扱いががっつり変わっているようなので，一旦ここで切って，それぞれ調べてからまとめたいと思います． 何か間違い等あればぜひご指摘お願いします．

Sokoban.nim を書いてみた

Sokoban.nim を書いてみた

Nim という言語を使って倉庫番を書いてみました.

sokoban-nim

sokoban-rs に影響されました．

といっても SDL ド素人なので見た目は恐ろしく質素です． Nim の練習のつもりで書いてみました．

動作

動作としては，コマンドライン引数にステージ情報を記述したファイル名を指定します．

##########
#   .    #
#  $   . ####
# @ $       #
#           #
#############

このようなファイルを指定します． クリアするとなにも言わずに終了するようになっています．(また, ESC でも終了します)

緑がプレイヤー, 青がゴール, 赤が箱です. 箱を押して青を塞げばクリアです.

感想

Nim で遊びたくて作ってみましたが，思っていた以上に Nim が楽しいですね． ライブラリも整っていますし，特に難しいことはなくサクサク書けました．

Nim で Lisp 処理系を書いたりしていて，息抜きにGUIっぽいものをと思って書きました． Cライブラリとの連携も非常にスムーズでしたし，Nim 流行んないかなぁと思っています．

Golang での文字列連結に関するベンチマーク

まず結論

append しよう. bytes.Buffer はそんなに速くない.

きっかけ

こんな記事を見かけました.
Goでは文字列連結はコストの高い操作 - Qiita

buf += "abc" はコストが高いよーっていうお話ですね. これは golang にかぎらず, Javaとかでもよく話題になる一般的な問題だと思います.
Java だと StringBuilder を使うのが良いとされていたと思いますが, golang だと解法がいくつかあるようです.

そこで, 解法をそれぞれ紹介した後, ベンチマーク結果を載せてみたいと思います.

1. 普通に +=

まずは普通に += で連結していく方法です.

func AddString(n int) string {
    base := "abc"
    buf := ""
    for i := 0; i < n; i++ {
        buf += base
    }
    return buf
}

こんな感じですね.
これだと, 確実に n 回メモリ割り当てが発生するので遅いというのが問題となります.

2. append する

golang の string は, メモリ上では []byte と同等の表現を持ちます.
そこで, string を []byte として扱い, golang のスライスを伸長する append 関数を用いるという方法があります.

func AppendString(n int) string {
    base := "abc"
    buf := make([]byte, 0)
    for i := 0; i < n; i++ {
        buf = append(buf, base...)
    }
    return string(buf)
}

make([]byte, 0) によって, 長さ0のスライスを作って, それを伸長していく方法となっています.
このあたりは golang のスライスの表現について知っていないとわかりづらいと思うのですが, わかりやすい説明がいろいろなところで読めるので, ここでは説明しません. append 関数は, スライスの len を必要な分だけ大きくします. また, その結果 len が スライスの cap を超える長さになる場合は, スライスの cap を必要以上に大きくすします.
これは, append を繰り返し適用するような場合(今回のように)に, メモリ割り当ての回数を最小にするためです. 一度の append で大きめにメモリを確保しておくことで, 次の append ではメモリ割り当てをしなくても済む可能性が生まれます.
イメージとしては,

append の回数	0	1	2	3
len	0	3	6	9
cap	0	8	8	16

こんな感じでしょうか(あくまでイメージですが)
append は3回呼ばれていますが, メモリ割り当ては2回に抑えられています.
その分, += よりも速いだろうということですね.

2'. cap を十分量確保しておく

make によるスライスの作成の際には, 長さだけでなくキャパシティを指定することが出来ます.
したがって, はじめから append していった後の最終的なスライスの長さがわかっているのであれば, それをキャパシティに指定することで, メモリ割り当てを最小限に抑えることが可能になります.

func AppendStringWithCap(n int) string {
    base := "abc"
    buf := make([]byte, 0, 3*n)
    for i := 0; i < n; i++ {
        buf = append(buf, base...)
    }
    return string(buf)
}

3. bytes.Buffer を使う

Java の StringBuilder に近い解法ですね.
bytes.Buffer は文字通りバイト列のバッファリングを行ってくれます.
bytes.Buffer に文字列やバイト列を書き込んでいくと, 自動的にメモリ割り当てを減らすように計らってくれます.

func BufferString(n int) string {
    base := "abc"
    var buf bytes.Buffer
    for i := 0; i < n; i++ {
        buf.WriteString(base)
    }
    return buf.String()
}

こんな感じです.

ベンチマーク結果

golang にはベンチマークをとる機能も標準で付いているので, それを利用しました.

package main

import "testing"

const N = 1000

func BenchmarkAddString(b *testing.B) {
    for i := 0; i < b.N; i++ {
        AddString(N)
    }
}

func BenchmarkAppendString(b *testing.B) {
    for i := 0; i < b.N; i++ {
        AppendString(N)
    }
}

func BenchmarkAppendStringWithCap(b *testing.B) {
    for i := 0; i < b.N; i++ {
        AppendStringWithCap(N)
    }
}

func BenchmarkBufferString(b *testing.B) {
    for i := 0; i < b.N; i++ {
        BufferString(N)
    }
}

func TestEquality(t *testing.T) {
    base := AddString(N)
    tests := []string{
        AppendString(N),
        AppendStringWithCap(N),
        BufferString(N),
    }
    for _, test := range tests {
        if base != test {
            t.Fatal("not fair")
        }
    }
}

TestEquality は, すべての方法で正しく文字列を生成できていることを確認するためのテストです. ベンチマークには関係ありません.

結果

上記のファイルを用意した後, go test -bench . -benchmem とした結果を以下に示します.

PASS
BenchmarkAddString-8                5000        348347 ns/op     1592481 B/op        999 allocs/op
BenchmarkAppendString-8           200000          7346 ns/op       13056 B/op         12 allocs/op
BenchmarkAppendStringWithCap-8    300000          5461 ns/op        6144 B/op          2 allocs/op
BenchmarkBufferString-8           100000         16847 ns/op       12256 B/op          8 allocs/op
ok      github.com/agatan/bench 6.881s

というわけで, make の時点で十分なメモリを確保しておく 2' の方法が最も速く最もメモリを消費しないことがわかりました.
まぁ当たり前ですねｗｗ

より注目すべきは, 2 と 4 の結果です. 今回の結果だと, 最終的な文字列の長さがわからない場合, bytes.Buffer よりも append を使ったほうが速いという結果になっています (メモリ使用量は若干 bytes.Buffer のほうが小さい)

メモリ割り当ての回数も bytes.Buffer のほうが少なく済んでいるため, []byte と string の変換など, 文字列連結以外の部分でのオーバーヘッドが大きいため, このような結果になった可能性があります. そこで, N の値を変えて実行してみました.

N = 10 の場合

PASS
BenchmarkAddString-8             2000000           613 ns/op         224 B/op          9 allocs/op
BenchmarkAppendString-8          5000000           270 ns/op          96 B/op          4 allocs/op
BenchmarkAppendStringWithCap-8  10000000           142 ns/op          64 B/op          2 allocs/op
BenchmarkBufferString-8          5000000           251 ns/op         144 B/op          2 allocs/op
ok      github.com/agatan/bench 6.581s

N = 10000 の場合

PASS
BenchmarkAddString-8                  50      28544042 ns/op    160274378 B/op     10039 allocs/op
BenchmarkAppendString-8            20000         71285 ns/op      160768 B/op         20 allocs/op
BenchmarkAppendStringWithCap-8     30000         55262 ns/op       65536 B/op          2 allocs/op
BenchmarkBufferString-8            10000        151665 ns/op      109280 B/op         11 allocs/op
ok      github.com/agatan/bench 7.393s

結論

連結する文字列の長さや連結の回数にもよるが, おおよそ append のほうが速い！！
bytes.Buffer はいつ使えばいいの...

Golangでechoサーバ

最近 golang が気になります
golang の特徴はもはやわざわざここに書くまでも無いことだと思うので書きませんが, 気になっている理由を書いてみます.

• バイナリ(しかもポータビリティが非常に高いバイナリ)にコンパイルされること
• C/C++ には及ばずとも実行が非常に速いこと
• C/C++ ほど低レイヤーいじり放題なわけではないが, ある程度低レイヤーまで降りていけること
• コマンドラインツールからWeb アプリケーションのような高レイヤーまで十分得意であること
• interface による抽象化が, 過度でなく調度良く感じられること

こんな感じでしょうか.
Compiled Python っていう感じが非常に良さそうだなーと思っています.

というわけでHaskellに引き続き golang でも echo サーバを書いてみました

package main

import (
    "fmt"
    "io"
    "net"
)

func main() {
    listener, err := net.Listen("tcp", ":8080")
    if err != nil {
        panic(err)
    }
    for {
        conn, err := listener.Accept()
        if err != nil {
            panic(err)
        }
        go func(conn net.Conn) {
            defer conn.Close()
            echo(conn)
        }(conn)
    }
}

func echo(conn net.Conn) {
    buf := make([]byte, 256)
    for {
        n, err := conn.Read(buf)
        if err != nil {
            if err == io.EOF {
                break
            }
            panic(err)
        }
        if n == 0 {
            break
        }
        wn, err := conn.Write(buf[0:n])
        if err != nil {
            panic(err)
        }
        if wn != n {
            panic(fmt.Errorf("could not send all data"))
        }
    }
}

さすがは golang というかなんというか. ものすごく普通な空気を感じますね.
golangはこういう普通さが売りの１つだと思っています.

Haskellでechoサーバ

はいどうもー
引き続きHaskellの話題です. ちょっとHaskellでTCPソケットを使ってみたくなったので, まず簡単なものから実装してみます.

TCPソケットのチュートリアルといえばechoサーバですね！クライアントからの入力をそのまま返すサーバです.
せっかくなのできちんと複数クライアントとの同時通信を可能にしましょう.

Network.Socket

HaskellでTCPソケットを使うには, Network.Socketを使うようです. Network.Socket

ドキュメントには, 低レベルAPIがNetwork.Socketで, 高レベルAPIがNetworkと書いてあるのですが, Networkモジュールのドキュメントには, 互換性のために残してあるけどこれから使う人はNetwork.Socketを使ってくれみたいなことが書いてあります.
適当にググるとNetworkモジュールを使ったサンプルが散見されますが, ここはドキュメントにしたがって, Network.Socketを使用することにします.

ソケットの用意

TCPのサーバ側は, ソケットの作成 -> ソケットをポート番号指定でbind -> 接続受付を開始(listen) -> 接続を受け付ける(accept) というステップを踏む必要があります.
というわけでまずは指定したポート番号にbindされたソケットを用意するアクションを定義します.

import Network.Socket

serveSocket :: PortNumber -> Socket
serveSocket port = do
    soc <- socket AF_INET Stream defaultProtocol
    addr <- inet_addr "0.0.0.0"
    bind soc (SockAddrInet port addr)
    return soc

これで引数に渡したポート番号にbindされたソケットが作成されます.

accept

複数クライアントとの同時通信を実現するためには, Control.Concurrentのちからを借ります.
今回は forkIO を使って, 各コネクションごとにスレッドを起動していくことにします. (非同期版も作れるのかな？つくれたらつくります)

というわけで次は acceptしてforkIOするという処理を繰り返し行うアクションを定義します.
forkIO した後に実行するアクション(echoLoop)についてはとりあえずundefinedとします.
Haskellのundefined, とても便利ですね. 型で考えるっていうスタイルが実行しやすくなっているのは, ソースコード上にトップレベル関数の型指定を書きやすいHaskellの文法とundefinedのおかげって感じがします.

echoLoop :: Socket -> IO ()
echoLoop = undefined

-- import Control.Concurrent
-- import Control.Monad
-- が必要
acceptLoop :: Socket -> IO ()
acceptLoop soc = forever $ do
    (conn, _addr) <- accept soc
    forkIO $ echoLoop conn

forever :: Monad m => m a -> m bは引数にIOアクションを受け取り, それを無限に繰り返し実行し続けます. (無限にくりかえすので返り値の型変数bは不定)
foreverの引数には, acceptしてforkIOするアクションを渡しています.

echo

最後にソケットから読み込み, そのまま書き出すechoLoop部分を作ります.

-- import Control.Exception が必要
echoLoop :: Socket -> IO ()
echoLoop conn = do
    sequence_ $ repeat $ do
        (str, _, _) <- recvFrom soc 64
        send soc str

recvFrom :: Socket -> Int -> IO (String, Int, SockAddr)は, recvFrom conn n で, connから最大でn文字まで読み込みます. 返り値は, (読み込んだ文字列, 読み込んだ文字数, 読み込み元のアドレス??) を返します.
そして, send :: Socket -> String -> IO () でソケットに読み込んだ文字列をそのまま書き込みます.
このように, 読み込んでそのままｍ書き込むというアクションを repeatでつなげています. repeat :: a -> [a]は無限リストを作る関数です. repeat 0で[0, 0, 0, 0, ...というリストが作成されます.
このままでは [IO ()]型なので, これをsequence_ :: Monad m => [m a] -> m ()を使って１つのIOアクションにまとめ上げます.
Haskellが遅延評価だから出来る芸当ですね. 無限に繰り返す感あふれるコードになっている気がします. (forever使ったほうがいいと思います)

例外処理

recvFromは相手側がコネクションを切断するとEnd of fileの例外を投げます. forkIOしているので, １つのスレッドが例外で落ちてもサーバ全体は動き続けますが, ソケットのクローズも出来ませんし, 標準エラーになんかでてきてよろしくないので修正します.

-- import Control.Exceptionが必要
echoLoop :: Socket -> IO ()
echoLoop conn = do
   sequence_ $ repeat $ do
       (str, _, _) <- recvFrom conn 64
       send conn str
   `catch` (\(SomeException e) -> return ())
   `finally` close conn

catchとfinallyを追加しています.
どちらもJavaとかのそれと同じように動きます.
SomeExceptionはすべての例外を補足することが出来ますが, ほんとはあんまり良くないですね. ここではEOFに達した(コネクションが切断された)という場合だけを補足したいので. (どの関数がどういう場合にどんな例外を投げるのかっていうドキュメントがわからなかったのでこのままにしておきました)
そして, 例外が発生してもしなくても, 最後にかならずソケットのクローズをするようfinallyを使います.

SomeExceptionですべての例外が捕捉出来るのって不思議じゃないですか？Haskellにはオブジェクト指向っぽい型の階層関係なんてないのに. Haskellの多相性 - あどけない話このへんが関係しているっぽいなという感じがしますが詳しいことはよくわかりませんでした...

全体

module Main where

import Network.Socket
import Control.Monad
import Control.Concurrent
import Control.Exception

main :: IO ()
main = do
    soc <- serveSocket 8080
    listen soc 5
    acceptLoop soc `finally` close soc

serveSocket :: PortNumber -> IO Socket
serveSocket port = do
    soc <- socket AF_INET Stream defaultProtocol
    addr <- inet_addr "0.0.0.0"
    bind soc (SockAddrInet port addr)
    return soc

acceptLoop :: Socket -> IO ()
acceptLoop soc = forever $ do
    (conn, addr) <- accept soc
    forkIO $ echoLoop conn

echoLoop :: Socket -> IO ()
echoLoop conn = do
    sequence_ $ repeat $ do
      (str, _, _) <- recvFrom conn 64
      send conn str
    `catch` (\(SomeException e) -> return ())
    `finally` close conn

main内で listenするのを忘れずに！また, acceptLoop中に例外が発生してもソケットをクローズするようにfinallyを使っています. (まぁプログラム終了するのでいらない気もします)

動作確認

telnetコマンドでテストします.

% telnet localhost 8080
Trying 127.0.0.1...
Connected to localhost.
Escape character is '^]'.
test
test
aaa
aaa
hooooogle
hooooogle

ちょっとわかりづらいですが, 入力した文字列が即座にそのまま帰ってきていることがわかります. バッファリングの関係で, 一行ずつになっていますが.

まとめ

Haskellでechoサーバ, 意外とすんなりかけましたね. 例外関係があまりよく理解できていない感じがしますが...
非同期版が気になります. 調べてみます.

HaskellのConcurrentについて調べてまとめる (MVar編)

どうもこんにちは.

前回(HaskellのConcurrentについて調べてまとめる (IORef編) - プログラミングのメモ帳➚)の続きです.

今回はスレッド間協調のためにMVarを使う方法について調べたので, まとめたいと思います.

MVar

Haskellにかかわらず, 最近の並行処理はメッセージパッシングでやれみたいなのが流行ってますね (ScalaのAkkaやgolangのchanなど).
MVarはHaskellにおける, 容量1のメッセージボックスのようなものです. MVarを使うことで, スレッド間でメッセージのやり取りを協調的に行うことができます.
複数のスレッドが１つのMVarに対して, メッセージを入れたり取り出したりすることでスレッド間協調を行います.

基本となるAPIはこのような感じ

newEmptyMVar :: IO (MVar a)
newMVar :: a -> IO (MVar a)
takeMVar :: MVar a -> IO a
putMVar :: MVar a -> a -> IO ()
readMVar :: MVar a -> IO a

型を見ればなんとなく使い方もわかる気がしますね.
MVarを作るにはnewEmptyMVarかnewMVarを使用します. newEmptyMVarは空のメッセージボックスを作り, newMVarは第一引数を初期値としてもつメッセージボックスを作ります.

MVarにメッセージを格納するには, putMVarを使います. putMVar mvar msg で, msgをmvarに格納します.
この際, もしMVarにすでにメッセージが格納されている場合, MVarは容量1のボックスなので, putMVarがブロックされます. 他のスレッドがMVarからメッセージを取り出して空にするまで待ってから, メッセージを格納します.

一方, MVarからメッセージを読み取るには, takeMVarかreadMVarを使用します.
takeMVarはメッセージを読み取り, そのMVarを空にします. readMVarはメッセージを読み取りますが, MVarの中のメッセージはそのまま残します.
ここで, putの時と同様に, takeMVarもreadMVarもMVarにメッセージが格納されていなかった場合, 他のスレッドがMVarにメッセージを格納するまでブロックします.

というわけで簡単なサンプルコード

module Main where

import Control.Concurrent (forkIO, threadDelay)
import Control.Concurrent.MVar

main :: IO ()
main = do
    mvar <- newEmptyMVar
    forkIO $ do
        msg <- takeMVar mvar
        putStrLn $ "recv: " ++ msg
        threadDelay $ 1 * 10 ^ 6
        putMVar mvar "B"
    putStrLn "sleep 1"
    threadDelay $ 1 * 10 ^ 6
    putStrLn "wake up"
    putMVar mvar "A"
    takeMVar mvar >>= print

実行結果

sleep 1
wake up
recv: A
"B"

確かにメッセージが格納されるまで takeMVarがブロックしていることがわかります

共有変数としてのMVar

さて, MVarにはもうひとつの使い方があります. 共有変数としてのMVarです.

MVarの特徴として, 誰かがtakeしてからputするまでの間は, 他のスレッドはだれもMVarの中身に触れないという点が挙げられます.

main = do
    mvar <- newMVar 0
    forkIO $ do
        val <- takeMVar mvar
        -- 他のスレッドはMVarの中身に触れない
        putMVar mvar $ val + 1
    ...

この特徴はまさにロックの特徴といえます. ロックを取得し解放するまでは, 他のスレッドは同じロックで保護された区間にははいれません.
というわけでMVarは型レベルでロックがついた共有変数とみなすことができますね！(このへんはRustのMutexに似た空気を感じます. どちらも型レベルでロックとそれが保護する中身がつながっています)
型レベルでロックがくっついているので, 中身にアクセスするには必ずロックをとる(takeMVar)必要があり, ロックの取得忘れがありません.

さらに, Haskellは基本的に破壊的操作があまり登場しない言語であることもこのMVarロックにプラスに働きます.

例えば, 連想配列をスレッド間で共有することを考えます. また, ここでは連想配列の実装として, hashtableではなくData.Mapを使用するとします(Data.Mapはimmutableな構造になっていて, lookupはO(log n)ですが, immutableなのでHaskell上で扱いやすいというメリットがあります).

Data.Mapはimmutableなので, 一度MVarから取得してしまえばそれ以降変更される可能性もないため, ロックを保持し続ける必要がありません. そこで, 単なる読み込みの場合は, takeMVarしてすぐにputMVarで戻すだとか, readMVarで読み込むだけにすることで, ロックの粒度を小さくできます.
MVarの中身を書き換えたい場合は, 単純にロックを取得し, 書き換え後の値をputMVarします.

module Main where

import Control.Concurrent (forkIO, threadDelay)
import Control.Concurrent.MVar
import qualified Data.Map.Strict as M

main :: IO ()
main = do
    mvar <- newMVar M.empty
    forkIO $ do
        table <- takeMVar mvar
        putMVar mvar table
        -- tableを使用する操作
    forkIO $ do
         table <- readMVar mvar
         -- tableを使用する操作
    forkIO $ do
        table <- takeMVar mvar
        -- tableを変更する操作
        let newTable = ...
        putMVar mvar newTable

このようにMVarとimmutableなデータ構造を組み合わせることで, 粒度の小さいロックを実現することができます.
一方, MVarとmutableなデータ構造(IORefなど)を組み合わせる場合は, たとえ読み込みしかしない場合であっても操作が終わるまではロックを保持しておく必要があることに注意しなければなりません (IORefには前回紹介したようにatomicModifyIORefがあるのでなかなかこういう状況は起こりませんね)

また, RustのMutexと違い, MVarによるロックの模倣(?)はロックの解放を自動的には行いません. したがって例外が送出された場合にロックを開放し忘れるケースがあるので, 注意が必要です.

一旦まとめ

というわけで今回はMVarについて紹介しました. MVarでロックを実現する方に関しては, 散々言われているロックの問題点をそのまま持ってきてしまうのであまり使えないかもしれませんね...
MVarは容量1のメッセージボックスでしたが, HaskellにはChanというものもあります. こちらはgolangのchanにかなり近いもので, 容量の制限がないキューのように働かせることができます. Chanのよみとり専用のスレッドを１つ立てておき, 他の複数のスレッドがタスクをChanに書き込んでいくといったユースケースが考えられますね. こっちのほうが便利そうな気がしてきました.

ロックはいろいろ厄介で, デッドロックとか解放忘れとかの問題がついて回ります. それを解決する１つの方法としてSTMがあるようなので, 次はそれについて調べてみようと思います.