右上➚

プログラミングに関するメモをのこしていきます

Boost.Spirit.X3 で簡易電卓を実装 1

C++ Boost コンパイラ

agtn.hatenablog.com agtn.hatenablog.com

引き続き，Boost.Spirit.X3 です．
今回は，前回までの知識をつかって，簡易電卓を実装してみます．

仕様

今回定義する電卓は，

  • +
  • -
  • *
  • /

の 4 つの演算と単項の - をサポートします．
また，整数型のみを扱うものとします．
(, ) でくくることで，演算子の結合優先順位を書き換えられ，* と / は + と - より優先されるとします．

要するに整数の四則演算のみをサポートする電卓です．

このような電卓を実装するサンプルは Boost.Spirit.X3 以外のライブラリ/ツールでも大量に出てくると思います．
今回は，構文解析そのものというよりは Boost.Spirit.X3 の使い方についてメモしたいので，構文解析そのものの話はぐぐってみてください．

パーサの骨格

演算子の結合規則をサポートするために，primary(定数と () で囲まれた式), neg_expr(単項 -), mul_expr(*, /), add_expr(+, -), expression というパーサをそれぞれ定義します．
先頭から順に結合強度が強くなっています．(expression が最弱, primary が最強)

primary は () で囲まれた式，つまり "(" > expression > ")" を受け付ける必要があり，また，primary 自体も expression の一部です．
したがって，この規則を定義するためには，再帰的なパーサを記述する必要があります．

X3 で再帰的なパーサを記述する方法は前回の記事にまとめました．

  struct primary;
  struct neg_expr;
  struct mul_expr;
  struct add_expr;
  struct expression;

  x3::rule<primary, int> const primary;
  x3::rule<neg_expr, int> const neg_expr;
  x3::rule<mul_expr, int> const mul_expr;
  x3::rule<add_expr, int> const add_expr;
  x3::rule<expression, int> const expression;

それぞれのパーサは attribute として整数型を持ちます．ここに演算結果が格納されることになります．
struct primary などは，今は前方宣言のみで十分です．on_error などを実装したくなった時に定義します．

primary

まずは primary を定義します.
primary は整数定数か， () で囲まれた expression を受理します．

auto const primary_def =
    x3::int_
  | "(" > expression > ")"
  ;

attribute を考慮しなければこんな感じでしょうか．expression は既に宣言されているので使用可能です．(expression の実装がこの時点で見えていなくても使用できます.)

単純に attribute を結果として返すセマンティックアクションはこの後もよく出てくるので，ヘルパとして定義しておきます．

namespace detail {

  decltype(auto) assign()
  {
    using x3::_attr;
    using x3::_val;
    return [](auto&& ctx) { _val(ctx) = _attr(ctx); };
  }

} // namespace detail

assign は attribute を結果に代入する関数オブジェクトを返します．
関数にする必要が特にありませんが，この後出てくるヘルパと見た目を合わせたいので関数にしました．

これを使うと，

auto primary_def =
    x3::int_[detail::assign()]
  | ("(" > expression > ")")[detail::assign()]
  ;

こんな感じで primary が定義できます．

単項マイナス

次に neg_expr を定義します． セマンティックアクションを考えなければ，

auto const neg_expr_def =
    primary
  | "-" > primary
  ;

となります．
"-" > primary のセマンティックアクションとしては，attribute を符号反転して結果に格納するというアクションが求められます．
ここはちょっと汎用的に，attribute に関数オブジェクトを適用して結果に格納するアクションを返すような関数を定義して解決してみます．

namespace detail {
  template <typename F>
  decltype(auto) assign_f(F&& func)
  {
    return [func](auto&& ctx) { _val(ctx) = func(_attr(ctx)); };
  }
} // namespace detail

assign_f は assign と異なり，関数オブジェクトを１つ引数に取ります．
そして，その関数オブジェクトを _attr(ctx) に適用し結果に格納します．

これを使って，neg_expr は

auto const neg_expr_def =
    primary[detail::assign()]
  | ("-" > primary)[detail::assign(std::negate<int>{})]
  ;

となります．std::negate は <functional> で定義された型で，ここでは int 型の値を符号反転する関数オブジェクトとして使用しています．

乗除

次に結合強度が強いのは * と / です．
ちょっとわかりにくいですが，セマンティックアクションを無視すれば，mul_expr は

auto const mul_expr_def =
    neg_expr
    >> *(
        ("*" >> neg_expr)
      | ("/" >> neg_expr)
    )
  ;

と定義できます．mul_expr は 1 や (1 + 2), -1 の後に，* 1 とか / -3 とか * (1 - 2) とかが 0 回以上現れるような式です．
1 * -2 はちょっと気持ち悪い気もしますが… 今気がついたので許してください．

セマンティックアクションとしては，("*" >> neg_expr) が現れる度に，_val(ctx) を _val(ctx) * _attr(ctx) に更新すれば良いです．
始めの neg_expr の結果を _val(ctx) に格納すれば，_val(ctx) は常に現在の計算結果を表すことになります．("*" >> neg_expr) は現在の計算結果に，今処理した式(* の後に続く式のこと) を処理した結果をかければ良いということです．

というわけで分かりにくいとは思いますが，ほしいアクションは，

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

です．

さて，では / の場合を考えます．
/ の場合であってもほとんどは * と同じであることがわかります．
ほしいアクションは

[](auto&& ctx) { _val(ctx) = _val(ctx) / _attr(ctx); }

であり，* と / の違いしか有りません．

そこでこれも関数にまとめてしまいます．

namespace detail {

  template <typename Op>
  decltype(auto) calc_op(Op&& op)
  {
    return [op](auto&& ctx) { _val(ctx) = op(_val(ctx), _attr(ctx)); };
  }

} // namespace detail

こんな関数を定義して，

auto const mul_expr_def =
    neg_expr[detail::assign()]
    >> *(
        ("*" >> neg_expr)[detail::calc_op(std::multiplies<int>{})]
      | ("/" >> neg_expr)[detail::calc_op(std::divides<int>{})]
    )
  ;

と使います．
calc_op は関数オブジェクトを引数に取り，_val(ctx) と _attr(ctx) に適用した結果を格納するアクションを返します．

add_expr は mul_expr とほぼおなじなので詳細はスキップします．

expression

最後に expression です．これは単純に add_expr と一致します．
命名のわかりやすさと，今後拡張していく際に便利そうということで分けてあるだけです．

auto const expression_def =
    add_expr[detail::assign()]
  ;

確認

コード全体を掲載します．

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

#include <iostream>
#include <string>
#include <functional>

namespace x3 = boost::spirit::x3;

namespace grammar {

  namespace detail {

    decltype(auto) assign()
    {
      using x3::_attr;
      using x3::_val;
      return [](auto&& ctx) { _val(ctx) = _attr(ctx); };
    }

    template <typename F>
    decltype(auto) assign_f(F&& func)
    {
      return [func](auto&& ctx) { _val(ctx) = func(_attr(ctx)); };
    }

    template <typename Op>
    decltype(auto) calc_op(Op&& op)
    {
      return [op](auto&& ctx) { x3::_val(ctx) = op(x3::_val(ctx), x3::_attr(ctx)); };
    }

  } // namespace detail

  struct primary;
  struct neg_expr;
  struct mul_expr;
  struct add_expr;
  struct expression;

  x3::rule<primary, int> const primary;
  x3::rule<neg_expr, int> const neg_expr;
  x3::rule<mul_expr, int> const mul_expr;
  x3::rule<add_expr, int> const add_expr;
  x3::rule<expression, int> const expression;

  auto const primary_def =
      x3::int_[detail::assign()]
    | ("(" > expression > ")")[detail::assign()]
    ;

  auto const neg_expr_def =
      primary[detail::assign()]
    | ("-" > primary)[detail::assign_f(std::negate<int>{})]
    ;

  auto const mul_expr_def =
      neg_expr[detail::assign()]
      >> *(
          ("*" >> neg_expr)[detail::calc_op(std::multiplies<int>{})]
        | ("/" >> neg_expr)[detail::calc_op(std::divides<int>{})]
      )
    ;

  auto const add_expr_def =
      mul_expr[detail::assign()]
      >> *(
          ("+" > mul_expr)[detail::calc_op(std::plus<int>{})]
        | ("-" > mul_expr)[detail::calc_op(std::minus<int>{})]
      )
    ;

  auto const expression_def =
      add_expr[detail::assign()]
    ;

  BOOST_SPIRIT_DEFINE(
      primary,
      neg_expr,
      mul_expr,
      add_expr,
      expression
      );

} // namespace grammar
using grammar::expression;

int main()
{
  std::string str;
  std::getline(std::cin, str);

  auto first(std::cbegin(str));
  auto const last(std::cend(str));

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

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

  std::cout << "Parsed: " << result << std::endl;
  return 0;
}

実行してみます．

$ clang++ -std=c++14 main.cpp
$ ./a.out
1 + 2 * 3
Parsed: 7
$ ./a.out
(1 + 2) * 3
Parsed: 9

演算子の優先順位が正しく解決できていることが確認出来ます．

まとめ

今回は，セマンティックアクションで計算自体を行ってしまいましたが，普通は抽象構文木(AST) に変換するためにセマンティックアクションを使うのが正道だと思います．
X3 は AST のための色々を提供してくれていますが，自前で作った AST でもちょっと苦労はするかもしれませんが変換できるはずなので，時間があれば，自前 AST に変換してから実行する電卓も作ってみたいと思います．

また，AST に変換して計算する場合，AST に位置情報を付与することで，エラーレポートが便利になったりするはずです( 0 除算のエラーを通知する際，どの部分でのエラーなのかを吐いてくれればうれしいですよね).
パース失敗時にもどこで失敗したのかをレポートしてくれたほうが便利です．
X3 で on_error, on_success を使ってこれらを実装してみようと考えています．

今回のコードでは decltype(auto) など，C++14 の機能を使っています．X3 は C++14 前提のライブラリなので，迷いなくこういった機能を使用できて幸せデスね．

Boost.Spirit.X3 の練習 2

C++ コンパイラ Boost

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

C++ Boost コンパイラ

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 でも終了します)

f:id:agtn:20151029220921p:plain

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

感想

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

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

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

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 が気になります
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の話題です. ちょっと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サーバ, 意外とすんなりかけましたね. 例外関係があまりよく理解できていない感じがしますが...
非同期版が気になります. 調べてみます.