右上➚

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

再帰的 grep ツール crepe を作っています

再帰的にパスをたどりながらパターンにマッチする行を検索する grep 系のツールを作っています。

agatan/crepe

有名どころとしては、ack とか ggreer/the_silver_searcher(ag) とか monochromegane/the_platinum_searcher とか tkengo/highway なんかがあります。群雄割拠ですね。

これらの有名ツール達はそれぞれ特徴があって(速さとか出力形式とかエンコード対応とか)便利に使わせていただいております。
今回 crepe を作ろうと思った理由は、なんとなく C++ でちゃんとスレッド立てて並行処理みたいなコードを書いてみたくなったからです。

速度等も測っていないのでどこまで意味があるのか怪しいのですが、とりあえず現状 3 つの仕事を並列に動かしています。

一つ目は出力を担当するスレッドで、マッチ結果を受け取って出力するだけです。
二つ目はマッチを担当するスレッドで、ファイル名と FILE* を受け取ってマッチ結果を生成し出力担当スレッドに渡します。
三つ目はパスを walk するスレッドで、ディレクトリを掘りながらファイルを開いてマッチスレッドに送ります。

現状はまだ部分一致の matcher しか実装していないので正規表現や fuzzy マッチは未実装です。
標準入力かパスから部分一致する行を探してきて出力します。
出力形式は ag に近い形式で、ファイルごとにグループ分けして行番号とともに出力します(オプションでこの辺の挙動はいじれるようにはなっています)

バイナリファイルっぽいファイルはスキップするようになっています。

やりたいこと

最終目標として crepepeco のような interactive な検索を実装してみたいなと思っています。
agpeco の組み合わせで云々みたいなユースケースが割りとあるなぁと思ったので。
ただこれメモリ使用量とか速度上の制約からまともに働くのかはよくわかっていません。
単純に考えると、ユーザが一文字入力するたびにファイルの read からやり直す必要があるので...
入力ファイルが多すぎた場合にどこまでキャッシュするのかとかその辺を相当うまくやらないと死ぬのでは?という気がします。

短期的な目標としては

  • .gitignore 対応 (意外とめっちゃ面倒で苦しんでいます)
  • fuzzy マッチ
  • 正規表現マッチ

あたりから順にやっていきたいなと思っています。とりあえずこっちからやろうかなと思います。

というわけで気合を入れる意味も込めて記事にしました。プルリクやフィードバック大歓迎なのでぜひよろしくお願いします。

C++ で result 型を作る

Haskell や Rust など多くの強力な型システムを持つプログラミング言語は、Either とか Result といった「失敗するかもしれない」計算の値を示す型を持っています。

現在の C++ の標準ライブラリにはこのような型はありませんので、それを自作してみようというわけです。

ちなみに現在策定中のC++17には std::optional が入ることが決定しているようです。これは、result と同様に失敗するかもしれな値を示しますが、失敗した原因がなんなのかを通知する仕組みを持っていません。

そもそもどういう型か

Rust の Result 型を例にみてみます。

enum Result<V, E> {
  Ok(V),
  Err(E),
}

Rust における Result 型はだいたいこんな感じで定義されています。

Result は型引数を2つとります。V が成功時の値で、E が失敗時のエラー情報です。 例えば、fn parse_int(s: &str) -> Result<isize, String>; は、文字列を受け取り、それが整数としてパース出来れば isize に変換し、Ok(isize) として返します。 もし整数としてパース出来ないなどのエラーがあれば、それを String で表現し、Err(String) で返します。

本質的にはこれが全てです。ここに、Result から中身を取り出す(Err なら panic する)関数などを定義してあげれば便利にエラー状態を表現できます。
(Rust の try マクロはとても便利ですよね)

まずはベースとなる result を作る

まずはベースとなる result 型を作ってみます。

template <typename T, typename E>
struct result {

  result(T const& ok) : t(tag::OK) {
    ok_ = ok;
  }

  result(E const& e) : t(tag::OK) {
    err_ = e;
  }

  ~result() {
    switch (t) {
      case tag::OK:
        ok_.~T();
        break;
      case tag::ERROR:
        err_.~E();
        break;
    }
  }

  result(result const& r): t(r.t) {
    switch (t) {
      case tag::OK:
        ok_ = r.ok_;
        break;
      case tag::ERROR:
        err_ = r.err_;
        break;
    }
  }

  T const& get() const {
    if (t != tag::OK) {
      throw "invalid get operation";
    }
    return ok_;
  }

  E const& get_error() const {
    if (t != tag::ERROR) {
      throw "invalid get operation";
    }
    return err_;
  }

private:
  enum class tag {
    OK,
    ERROR,
  };
  tag t;
  union {
    T ok_;
    E err_;
  };

};

かなり雑ですが、ざっくりこんな感じになるはずです。 C++11 から拡張されて自由度がかなり高くなった union がとても便利です。

これで result<int, std::string>(1).get() とやれば 1 が返るし result<int, std::string>(std::string("test")).get_error()"test" が返るはずです。

C++ でやると何が難しいか

C++ で難しいのは、Rustより弱い型推論が引き起こす問題です。
Rust では、Ok(1isize) とか Err("error!".to_owned()) とすれば、その値がどういう型であることが期待されているのかまで含めて型推論や単一化が行われます。 すなわち、Ok(1isize) だけを見てもエラーの型がわからないため、Result<isize, E>E を決定することが出来ないが、Rust は強力な型推論機構を持つため、これを決定することが出来ます。

一方、C++ では result<int, std::string> f() { return 1; }int から result<int, std::string> の暗黙変換がきくので可能ですが、result<int, int> などとした瞬間、暗黙変換に頼ることはできなくなります。 そこで、出来れば ok(1) とか err("test") という感じにしたいのですが、これは一筋縄では行きません。

template <typename T, typename E> 
result<T, E> ok(T);

これだと T は推論されても E が推論されないので、ok<int, std::string>(1) などとしなければなりません。これは使いづらすぎます。

じゃあどうするか

先ほどとは違う形ですが、やっぱり暗黙の型変換を応用します。

要するに ok を表す型と error を表す型を区別しつつ、result<V, E> とはなるべくシームレスに変換をしたいというわけですから、それぞれ専用の型を作ってしまえば良いのです。

template <typename T>
struct ok_value {
  explicit ok_value(T t): t(t) {}

  template <typename V, typename E>
  operator result<V, E> () const;

private:
  T t;
};

template <typename T>
template <typename V, typename E>
ok_value<T>::operator result<V, E> () const {
  return result<V, E>(t);
}

template <typename T>
ok_value<T> ok(T t) {
  return ok_value<T>(t);
}

ok 側だけ示しました。
ok 関数はテンプレートになっており、T 型の値をとって ok_value<T> を返します。(本当は値渡し以外にも対応すべきですが、簡単のために値渡しだけ実装しています)

ok_value<T> は型変換演算子 operator result<V, E>() const を持ちます。これによって ok_value から result への暗黙変換が可能になります。

ok_value<T>result<T, E> に変換出来れば良さそうに見えるのですが、それでは不十分です。
ok("test")ok_value<const char*> を返します。ok_value<T> -> result<T, E> の変換しか提供していない場合は、result<std::string, E> への変換ができなくなってしまいます。これは不便ですよね。
そこで新たにテンプレート引数を導入することでこれを解決しています。もっときちんとやるなら std::is_constructible などを使ってチェックをするべきだとは思いますが。

error 側もほぼ同様のコードを書いてやれば、

result<int, std::string> parse_digit(char c) {
  if (c < '0' || '9' < c) {
    return error("invalid character");
  }
  return ok(c - '0');
}

というように書けます。

まとめ

T から result<T, E> への暗黙変換を許すという方針も全然ありだとは思いますが、個人的に Rust などで ok なら ok と明示するスタイルに慣れているので、こっちのほうが気に入っています。
明らかに正常に値を返していそうな感じがコードにあらわれて好きです。

暗黙の型変換って危険だしあまり良いイメージはないと思うのですが、やっぱりあれば便利ですね。 C++ を使っている時点で気を抜いたら死なので、「取り扱いを把握して全力で注意しながら使えば危険じゃない」という気持ちで便利に使いたいものです。

C++テンプレートイディオム CRTP

C++テンプレートの有名なイディオムとして、CRTPというものがあります。 今回はそれについて。 複雑な部分特殊化みたいな話もないですし、メリットもわかりやすい良いイディオムだと思うので、ちょっとまとめておきます。 (Control キーのことをよく CTRL と書くので、CTRP とタイポしがち)

詳細はこちらを参照してください。 More C++ Idioms/奇妙に再帰したテンプレートパターン(Curiously Recurring Template Pattern) - Wikibooks)

CRTPの利点

細かい実装の話の前に、CRTPを使うと何がうれしいのかを簡単に。

静的 Template Method パターンの実現_ 。これがCRTPの利点です。

Template Method パターンについてはここでは説明しませんが、大枠のアルゴリズムを共有しつつその内部で使用する実装の詳細をクラスごとに切り替えるといった目的に使われるデザインパターンです。

通常 Template Method パターンを C++ で実現しようと思うとどうしても仮想関数を使うことになると思います。これによって実行時のオーバヘッドがかかってしまいます。 Template Method パターンは、いわゆるクラスベースの動的なポリモーフィズムを必要としないクラスであっても、アルゴリズムの共有やボイラープレートコードの削減に非常に有用なパターンです。 これを静的に実現するのが CRTP の目的なのです。

実装

CRTP とは、その名の通り、奇妙に再帰したテンプレートのパターンのことです。 情報量0の文章ですね。実際のコードも見たほうがわかりやすいと思います。

以下に、compare というメソッドから比較演算子derive (自動導出) する例をのせます。

#include <iostream>

template <typename T>
struct comparable {
  template <typename U>
  friend bool operator==(comparable const& lhs, U const& rhs) {
    return static_cast<T const&>(lhs).compare(rhs) == 0;
  }

  template <typename U>
  friend bool operator>(comparable const& lhs, U const& rhs) {
    return static_cast<T const&>(lhs).compare(rhs) > 0;
  }

  template <typename U>
  friend bool operator<(comparable const& lhs, U const& rhs) {
    return static_cast<T const&>(lhs).compare(rhs) < 0;
  }
};

struct person : comparable<person> {
  int age;

  int compare(person const& rhs) const {
    return age - rhs.age;
  }
};

int main() {
  person p1, p2;
  p1.age = 10;
  p2.age = 100;

  std::cout << std::boolalpha << (p1 == p2) << std::endl;
  std::cout << std::boolalpha << (p1 < p2) << std::endl;
  std::cout << std::boolalpha << (p1 > p2) << std::endl;
}

person クラスには operator== など定義していないにもかかわらず、person を比較することが出来ています。

CRTPの中心となるのは struct person : comparable<person> という部分です。 クラスを定義する際に、自分をテンプレート引数にとるクラスを継承するというコード、これこそが「奇妙な再帰」なのです。 実際、struct person : comparable<person> の部分ではまだ person がどんな実装になるかはわかっていません。奇妙ですね。

さて、まずは person の中身を見てみます。 person では、person const& を引数にとり、それが自分より大きければ正の値を、小さければ負の値を、等しければ0を返すような、compare というメソッドを定義しています。 person の仕事はこれだけです。

comparable は、テンプレート引数にひとつの型をとります。
comparable はその型が compare というメソッドをもつことを期待しています。(暗黙のインターフェース)
comparable の仕事は compare というひとつのメソッドから、operator==, operator<, operator> を自動的に導くことです。
Template Methodパターンをご存じの方ならすんなり理解できるかと思います。

CRTP のすごいところは、仮想関数をまったく使わないことです。つまり、実行時のテーブルルックアップは発生しません。すべてが静的に決定されるのです。

おまけ

先に挙げた compare から operator== を自動導出する例ですが、HaskellOrd 型クラスを意識しています。

class Eq a => Ord a where
  compare :: a -> a -> Ordering
  (<), (<=), (>), (<=) :: a -> a -> Bool
  max, min :: a -> a -> a

Ord 型クラスのインスタンスになるためには、最低でも compare を実装している必要があります。 逆にいえば、compare だけ実装すれば、他の関数は自動的に実装されます。

Haskell では、Ord になるためには Eqインスタンスである必要があります。 これを C++ で表現するためには、

template <typename T>
struct ord : eq<T> {
  ...
};

こんな感じでしょうか。もちろん型クラスの代替にはなりえないんですけどね。 Haskell の型クラスの利点のひとつである、最小限のインターフェース実装による関数の自動導出っぽいこともできるよというお話でした。

実際にテンプレートライブラリを書いてみて改めて有用性がわかったテクニックでした。 拙作の coco にも導入したい... すべてのパーサにユーティリティメンバ関数を追加するみたいなことが出来るはず... いつかやります。

C++ のテンプレートの実装

C++ のテンプレートがなぜ必要で,どんな構文・種類のものがあるかについては前回までにまとめました。
というわけで次は C++ ではテンプレートという機能を使用するとどんなバイナリが生成されるのかについて見ていきます。
C++ のテンプレートの強力さとか勘所みたいなものを把握するために非常に重要な部分なので、覚えておくとよいと思います。

C++ でテンプレートをコンパイルしてみる

早速ですが、実際に C++ でテンプレートを使っているコードをコンパイルしてみます。
アセンブリよりも LLVM IR のほうがわかりやすいかな?と思うので、LLVM IR を clang++ で生成させてみます。 (LLVM IR については 大学院生のためのLLVM | インフラ・ミドルウェア | POSTD あたりを読んでおくとなんとなく概念がつかめると思います。公式はLLVM Language Reference Manual — LLVM 3.9 documentation

対象となるコードはこちら。

// main.cpp
template <typename T>
T identity(T x) {
  return x;
}

int main() {
  float f = 0.0f;
  identity(f);

  int d = 0;
  identity(d);
  return 0;
}

clang++ で LLVM IR を生成させるには,-S -emit-llvm をオプションに指定します。また、今回のコードは最適化されてしまうとほとんどコードが残らないので、最適化を抑制するよう、-O0 を付けます。

$ clang++ -O0 -S -emit-llvm main.cpp

すると main.ll というファイルが出来ています。これが LLVM IR です。

IR を読む

LLVM IR は,LLVM というコンパイラ基盤技術における中間表現 (Intermediate Representation) です。
ざっくり言うと、アーキテクチャに依存しない、読みやすいアセンブリです。

main.ll はそこまで長くないですが、エッセンスだけ抜粋します。

define i32 @main() #0 { ;; main 関数
  %1 = alloca i32, align 4
  %f = alloca float, align 4
  %d = alloca i32, align 4
  store i32 0, i32* %1
  store float 0.000000e+00, float* %f, align 4
  %2 = load float* %f, align 4
  %3 = call float @_Z8identityIfET_S0_(float %2)
  store i32 0, i32* %d, align 4
  %4 = load i32* %d, align 4
  %5 = call i32 @_Z8identityIiET_S0_(i32 %4)
  ret i32 0
}

define linkonce_odr float @_Z8identityIfET_S0_(float %x) #1 { ;; identity<float> の実体
  %1 = alloca float, align 4
  store float %x, float* %1, align 4
  %2 = load float* %1, align 4
  ret float %2
}

define linkonce_odr i32 @_Z8identityIiET_S0_(i32 %x) #1 { ;; identity<int> の実体
  %1 = alloca i32, align 4
  store i32 %x, i32* %1, align 4
  %2 = load i32* %1, align 4
  ret i32 %2
}

コメントでも書きましたが、3 つの関数が定義されていることがわかると思います。 ここで重要なのは、 identity<int>とidentity<float>がそれぞれ別の関数として定義されている ことです。

identity<int>identity<float>main の中で使われています。
つまり、テンプレートは、「使った分だけ実体が作られる。かつその処理はコンパイル時に終わる。」ということがわかります。
たとえばソースコード中に identity<bool> の実体化を要求するコードがあれば、その時はじめて identity<bool> が作られます。 独自定義でも構いません。identity<MyClass> の実体化を要求するコードがあれば、その時はじめて identity<MyClass> が作られます。

もちろん、一度実体化されたテンプレートは再利用されます。つまり、identity<int> を要求するコードが、一つのソースコードに何度現れても、ただひとつの identity<int> が生成されます。

Java との比較

Java にもジェネリクスという仕組みがあります。
概念的にはテンプレートに似たものなので、比較してみます (テンプレートの方がより強力ですが、型を汎用化したいという目的であれば、両者とも同様に使用できます。)

同じようなコードをコンパイルしてバイトコードを見てみます。

class Main {
  static <T> T identity(T x) {
    return x;
  }

  public static void main(String[] args) {
    Integer d = 1;
    Float f = 0.0f;
    Main.identity(f);
    Main.identity(d);
  }
}

javac Main.java してから、javap -v Main します。これでバイトコードが出力されます。

class Main
/* 中略 */
{
  Main();
    descriptor: ()V
    flags:
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: invokespecial #1                  // Method java/lang/Object."<init>":()V
         4: return
      LineNumberTable:
        line 1: 0

  static <T extends java.lang.Object> T identity(T);
    descriptor: (Ljava/lang/Object;)Ljava/lang/Object;
    flags: ACC_STATIC
    Code:
      stack=1, locals=1, args_size=1
         0: aload_0
         1: areturn
      LineNumberTable:
        line 3: 0
    Signature: #14                          // <T:Ljava/lang/Object;>(TT;)TT;

  public static void main(java.lang.String[]);
    descriptor: ([Ljava/lang/String;)V
    flags: ACC_PUBLIC, ACC_STATIC
    Code:
      stack=1, locals=3, args_size=1
         0: iconst_1
         1: invokestatic  #2                  // Method java/lang/Integer.valueOf:(I)Ljava/lang/Integer;
         4: astore_1
         5: fconst_0
         6: invokestatic  #3                  // Method java/lang/Float.valueOf:(F)Ljava/lang/Float;
         9: astore_2
        10: aload_2
        11: invokestatic  #4                  // Method identity:(Ljava/lang/Object;)Ljava/lang/Object;
        14: pop
        15: aload_1
        16: invokestatic  #4                  // Method identity:(Ljava/lang/Object;)Ljava/lang/Object;
        19: pop
        20: return
      LineNumberTable:
        line 7: 0
        line 8: 5
        line 9: 10
        line 10: 15
        line 11: 20
}
SourceFile: "Main.java"

注目すべきは // Method identity:(Ljava/lang/Object;)Ljava/lang/Object; というコメントのついた行です。
2 行ありますが、それぞれ identity(d)identity(f) に相当します。

Integer.valueOfFloat.valueOf を含むコメントを見ていただければわかると思いますが、このコメント部分には呼び出しているメソッドの型が記されています。
つまり、identityInteger で呼んでも Float で呼んでも Object identity(Object) を呼んでいるということです。

これは Javaジェネリクスの大きな特徴で型消去などと呼ばれる性質です。ジェネリクスによる型はすべてコンパイル時にのみ利用され、実行時にはすべて Object として表現しつつ適切にキャストを挟むような構造になっています。
キャストはキャストでも、正しいことがコンパイラによって保証されたキャストになるので、List よりも List<String> のほうが安全というわけです。

それぞれの利点と欠点

テンプレートやジェネリクスを実現する方法として、2つの例を上げました。
一つは C++ の採用している方式で、テンプレート引数ごとに新しく実体を作ってしまう方式です。
もう一つは Java の採用している方式で、Object のようにすべての型を受け取れる基底クラスのようなものを用いて、実行時には型情報を残さない方式です。

今回はたまたま C++Java を例にあげましたが、他の言語でもこのような方式を使っている言語は多いです。(みんなだいすき D 言語は C++ の方式を採用しています)

さてそれぞれの利点と欠点についてです。

Java 方式

  • 利点
  • 欠点
    • 実行時にやることが増えるのでオーバヘッドがある

C++ 方式

  • 利点
    • 実行時オーバヘッドなし(全てコンパイル時に解決される)
  • 欠点
    • バイナリサイズの増加
    • 分割コンパイルが困難 (テンプレートを実体化しようと思うと、型情報だけでは足りない。使用者側が定義そのものをまるまる知っている必要がある。)

こんな感じでしょうか。
この比較はあくまで型を汎用化したいという目的に関しての比較です。C++ のテンプレートにできて Javaジェネリクスに出来ないことはたくさんあります。

まとめ

C++er はみんな実行時のオーバヘッドが嫌いです。テンプレートは、今までに紹介してきた使用法からは想像も出来ないほど豊富な計算を、コンパイル時にすべて行うことが出来ます。実行時のオーバヘッドなしで。
コンパイル時にテンプレートの解決が終わるということは、強力な最適化が望めるということでもあります。つまり、実行時のキャストといったわかりやすいオーバヘッド以上に、実行速度には差が生まれるでしょう。

というわけで今回はテンプレートの実現方法について、Java と比較しながら説明してみました。

C++ テンプレートの種類と構文

前回テンプレートがなぜ必要なのかについて簡単にまとめたので、今回はその構文や種類についてまとめたいと思います。

agtn.hatenablog.com

アウトライン

  • テンプレートの種類と構文
  • クラステンプレート
  • 関数テンプレート
  • メンバテンプレート
  • エイリアステンプレート(C++11〜)
  • 変数テンプレート(C++14〜)
  • まとめと今後

テンプレートの種類と構文

C++ のテンプレートは,大きく 5 種類に分類することが出来ます。

  1. クラステンプレート
  2. 関数テンプレート
  3. メンバ関数テンプレート
  4. エイリアステンプレート
  5. 変数テンプレート

これらについて、以降で詳しくまとめていきます。

まずざっくり共通するシンタックスを示しておきます。

定義する

何かのテンプレートを定義したい場合は、通常の定義の前に template 宣言を記述します。

template <typename T>
class stack {
  ...
};

複数のテンプレート引数を取りたい場合や、型以外のテンプレート引数を取りたい場合には、以下のようにします。

template <typename T, int N>
class my_array {
  ...
};

上の例はクラステンプレートでしたが、関数でもエイリアスでも、template を宣言する部分は共通です。

使用する(インスタンス化)

次にテンプレートを使用する場合です。
テンプレートはあくまでテンプレートなので、使用する際には、具体的なテンプレート引数を与えて実体化する必要があります。これを インスタンス といいます。

インスタンス化の構文も、テンプレートの種類によらず基本的には共通しています。

stack<int> int_stack;
my_array<std::string, 5> five_strings;

テンプレート名 < 引数 > という感じです。
一応注意書きをしておきますと、stack<stack<int>>シンタックスエラーになる場合があります。 意味としては stack<int> のスタックです。
stack<stack<int>>コンパイルエラーになる場合は、使っているコンパイラが古いかもしれません。 C++03 では、>> の部分がシフト演算子として解釈されてしまうためです。
g++ -std=c++11 とか clang++ -std=c++11 とか g++ -std=c++14 とか clang++ -std=c++14 とか、コンパイラが新しい規格を参照するようにオプションを渡してあげれば動きます。
(もし動かない場合はコンパイラが古すぎます。もう 2016 年ですから、最低でも C++11 以降を使いましょう。別物です。)

では、以降、それぞれのテンプレートについて詳しく見ていきます。

クラステンプレート

クラステンプレートは、クラスのテンプレートです。前回の stack がこれにあたります。
一番わかり易いユースケースは、コンテナ型の定義でしょう。
スタックや単方向リスト、ハッシュマップなど、内部に保持する型に依存しないデータ構造を定義するために使えます。

前回の stack を再掲しておきます。

template <typename T>
class stack {
public:
  stack() : data(), n() {}

  void push(T x) {
    if (n >= MAX_ELEM) {
      throw "stack is full!!";
    }
    data[n++] = x;
  }

  T pop() {
    if (n < 0) {
      throw "stack is empty!!";
    }
    return data[--n];
  }
private:
  T data[MAX_ELEM];
  int n;
};

関数テンプレート

関数テンプレートは以下の様なものです。

template <typename T>
T max(T left, T right) {
  if (left > right) {
    return left;
  } else {
    return right;
  }
}

int x = max<int>(1, 0); // => x == 1
double y = max<double>(0.5, 100.0); // => y == 100.0

max 関数は、「ある型 T について、2つの引数のうち、大きい方を返す」関数です。
明示的に max<int>max<double> とすることで、intdouble についての「大きい方を返す」関数を得ています。

テンプレート引数の推論

実は、関数テンプレートの場合、明示的にテンプレートを引数を渡す必要がない場合があります。
今回の max 関数はまさにそのケースです。

int x = max(1, 0);

これは、テンプレート引数の型推論の結果です。
max 関数の第一引数、第二引数はそれぞれ T です。そして、実際に渡されている 10int 型です。
これらの情報から、コンパイラT == int であることを推論します。
したがって暗黙に max<int> と指定されることになります。
この推論は色々複雑だったりしますが、はじめは引数から単純に推論できれば推論されると思っておけば良いんじゃないかなと思います。

一方、クラステンプレートなど、関数テンプレート(とメンバ関数テンプレート)以外のテンプレートの場合には、この推論は行われません。
勘違いしやすいので気をつけましょう。特にクラステンプレートは間違いやすいです。

メンバ関数テンプレート

class printer {
public:
  explicit printer(std::ostream& os) : os(os) {}

  template <typename T>
  void print(T const& v) {
    os << v;
  }
private:
  std::ostream& os;
};

メンバ関数テンプレートは、関数テンプレートとほとんど同じです。違いは、メンバ関数として定義されていることだけです。

printer p(std::cout);

ここまではテンプレートでもなんでもないただのクラスです。

p.print(0);
p.print("abc");
p.print<double>(0.1);

こんな感じで使います。関数テンプレートとほぼ同じですね。

エイリアステンプレート

エイリアステンプレートは、C++11 から使用できるテンプレートです。

template <typename T, typename U>
struct pair;

template <typename T>
using with_int_t = pair<T, int>;

using で型名のエイリアスを作ることが出来ますが、それをテンプレートにすることが出来ます。

with_int_t<bool> p(true, 0);  // pair<bool, int> p(true, 0);
with_int_t<std::string> s("abc", 100);  // pair<std::string, int> s("abc", 100);

ちなみに C++11 より前は、エイリアステンプレートの代替として、

template <typename T>
struct with_int {
  typedef pair<T, int> type;
}

with_int<bool>::type p(true, 0); // pair<bool, int> p(true, 0);

という記述をしていました。(今でもライブラリなどで現役の表現ですので覚えておきましょう)

変数テンプレート

最後の変数テンプレートは、C++14 から使用できるテンプレートです。

template <typename T>
constexpr T pi = static_cast<T>(3.1415926);

int x = pi<int>;
double y = pi<double>;

constexpr は定数式というやつです。

ちなみに C++14 より前は、代替として

template <typename T>
struct pi {
  static const T value = static_cast<T>(3.1415926);
};

int x = pi<int>::value;
double y = pi<double>::value;

という記述をしていました。(こちらも現役の表現です)

まとめと今後

というわけで今回はテンプレートの種類とそれぞれのシンタックスについてまとめてみました。
今後、特殊化や部分特殊化などのお話をするときに種類によって微妙に違いがあったりするので、しっかり区別しておいたほうが良さそうです。

C++ : なぜテンプレートが必要なのか

こんにちは。
ちょっと C++ への熱を冷まさないために、C++ のテンプレートについてまとめてみたいと思います。

対象

  • C++ のテンプレートが怖い人
  • C++コンパイルエラーメッセージが怖い人
  • C++ の規格とブログポストを比較して誤りを探したい人(もし誤っていたら教えて下さい...)

テンプレートとは

プログラミングにおけるテンプレートは、静的型付けのC++でデータ型にとらわれずにコードを書くことを可能にする機能であり、C++においてはジェネリックプログラミングに用いられる。
テンプレート (プログラミング) - Wikipedia)より

他の静的型付きなプログラミング言語をすでに知っている場合は,すんなり入りやすいかもしれません。
JavaScala, C# でいうところのジェネリクスに近い存在です。
OCamlHaskell だと多相とか。

雑に表現するならば、リストとか連想配列のように内部のデータ型に依らないデータ構造を、静的型のもとにどうやったらうまく表現できるかな、に対する解の一つです。

では一つの例として、スタックというデータ構造をプログラムに落としこむことを考えます。
まずは int 型のスタックを定義してみます。

#define MAX_ELEM 10

class int_stack {
public:
  int_stack() : data(), n() {}

  void push(int x) {
    if (n >= MAX_ELEM) {
      throw "stack is full!!";
    }
    data[n++] = x;
  }

  int pop() {
    if (n < 0) {
      throw "stack is empty!!";
    }
    return data[--n];
  }
private:
  int data[MAX_ELEM];
  int n;
};

簡単のため、かなりお粗末なスタックですが、最低限のスタックとしての見た目はしていると思います。

では次に、std::string 型のスタックや double 型のスタックを作りたいとなったらどうすればよいでしょうか。
コピーして int を置換しますか?あまり褒められた方法ではなさそうです。

C でのアプローチの一つ

C 言語の場合、このような問題に対しては void* というアプローチがあります。
void*java でいう Object のように扱われます。

#define MAX_ELEM 10

struct stack {
  void *data[MAX_ELEM];
  int n;
};

void push(stack *s, void *elem) {
  ....
}

void *pop(stack *s) {
  ....
}

/* Usage */
stack *s = new_stack();
int *x = (int*)malloc(sizeof(int));
*x = 1;
push(s, (void*)x);
int *y = (int*)pop(s);
printf("%d\n" *y); /* => 1 */

こんな感じでしょうか。実装の細かい部分は省略しています。
push の際にはあらゆるポインタを void* にキャストし、逆に pop する際には void* を求める型にキャストしています。
ジェネリクスのなかった頃の java は、これを Object へのキャスト・Object からのキャストとして表現していました。

void* のデメリット

void* を使う場合のデメリットは、型システムを台無しにしている点です。(mallocfree が必要であることは C 言語特有の問題なのでスルー)
つまり、int のスタックから pop してきたとき、int* に正しくキャストを行う責任はプログラマにあり、コンパイラは何も手助けをしてくれないということです。
したがって、 int スタックに double の値を push したり、 double スタックから char*pop したりというミスが簡単に引き起こされてしまうということです。

そこでテンプレート

では C++ ではどのようなアプローチを取るかというと、テンプレートを使います。
今回は型に関するテンプレートの話しかしないので、javaジェネリクスも大体同じ話だと思って構わないと思います。(実行時の表現やコンパイラの動きなどの違いはあるが、対象としている問題は同じ)

さきほどの int_stack の実装では、要素型が int に固定化されてしまっているのが問題でした。
そこで、テンプレートでは、型を抽象化し、ある種の引数のように扱っています。

template <typename T>
class stack {
public:
  stack() : data(), n() {}

  void push(T x) {
    if (n >= MAX_ELEM) {
      throw "stack is full!!";
    }
    data[n++] = x;
  }

  T pop() {
    if (n < 0) {
      throw "stack is empty!!";
    }
    return data[--n];
  }
private:
  T data[MAX_ELEM];
  int n;
};

先頭の template <typename T> (template <class T> でも可)は、型引数の導入の役割を果たしています。
stack クラスの定義内に登場する T は型引数として導入された型を表します。

利用する際には、stack<int> とか stack<std::string> とか、型を stack に渡してあげればOKです。

stack<int> int_stack;
int_stack.push(1);
int_stack.push(2);
int x = int_stack.pop();
int_stack.push("abc"); // => Compile error!

stack<std::string> str_stack;
str_stack.push("abc");
str_stack.push(1); // => Compile error!

このように、同じコードをコピペすることなく、複数の型に対応したスタックという汎用的なデータ構造を表現することが出来ています。
さらに、この方法では、void*Object と異なり、型的に誤った使用方法をしようとするとコンパイルエラーになるというメリットがあります。
ランタイムエラーよりコンパイルエラーのほうがデバッグしやすいし発見しやすいですよね。

一旦まとめ

というわけで今回はテンプレートがなぜ便利かという話のほんのさわりの部分について書いてみました。
次はテンプレートやジェネリクスの実現方法、ランタイムにおける表現方法などについて書いてみます。
そこからはテンプレート引数として値をとる話や、TMP についても触れていければと思っています。

Rust のパーサコンビネータライブラリ combine を使う時の tips

Rust のパーサコンビネータライブラリの一つである Marwes/combine: A parser combinator library for Rust を使ってみています.
詳しい使い方はきちんとしたドキュメントがあるのでそちらを参照してください.
ざっくりいうと Haskellparsec: Monadic parser combinators | Hackage の Rust 版という感じです.

(ちなみに私も combine を参考に C++ でパーサコンビネータを作ってみたりしました. ) agtn.hatenablog.com

で、このライブラリ、とてもジェネリックなコードで書かれているので、かなりコンパイル時間が増加します… (Boost.Spirit 系に近いです. コンパイルエラーなどは遥かに読みやすいのであまり困ることはないですが)
パーサを書いている時にはテストは頻繁に行いたいので,ちょっとコンパイルがおそいのはつらい.

なにか解決策はないかなぁと思っていたら本家に issue がたっていました.
Extremely long compile times · Issue #21 · Marwes/combine

今回この issue にかかれていた内容を検証してみたので,ここでまとめておこうと思います.

結論

パーサの定義を,ジェネリックな構造体のメソッドとして定義するとコンパイル時間が大幅に短くなる

方法

まずはじめに言われているのは,入力ストリーム型をI: Stream<Item=char> から &str にしてしまうという方法です.

(It might be possible to specialize the parsers directly as well, say fn expr(input: State<&str>) -> ParseResult<Expr, &str> instead of fn expr<I: Stream>(input: State<I>) -> ParseResult<I, &str> )

これは作ったパーサをジェネリックな入力に対して適用することができなくなりますが,ライブラリの利用者側としては,char のストリームといったらだいたい &str だと思うので,ぶっちゃけジェネリックじゃなくてもいいじゃんという感じです.

そしてもう一つが, ジェネリックな構造体を作って,パーサの定義をその中に閉じ込めるという方法です.
ちょっとこちらはコード例を実際に見たほうがわかりやすいと思うので後で説明します.

実験コード

というわけで,

  1. ジェネリックなパーサ
  2. &str のみを受理するパーサ
  3. ジェネリックな構造体の中に定義されたジェネリックでないパーサ

の三種類について,コンパイル時間をはかってみます.

パーサ界のハローワールド,計算機で実験してみます. まずはジェネリックなパーサです.

use combine::*;
use combine::primitives::Stream;

pub fn integer<I>(input: State<I>) -> ParseResult<i64, I>
    where I: Stream<Item = char>
{
    many1::<Vec<_>, _>(digit())
        .map(|is| is.into_iter().fold(0, |lhs, rhs| lhs + (rhs as i64 - '0' as i64)))
        .parse_state(input)
}

pub fn factor<I>(input: State<I>) -> ParseResult<i64, I>
    where I: Stream<Item = char>
{
    between(char('('), char(')'), parser(expr)).or(parser(integer)).parse_state(input)
}

pub fn term<I>(input: State<I>) -> ParseResult<i64, I>
    where I: Stream<Item = char>
{
    let op = char('*').or(char('/')).map(|c| {
        move |lhs, rhs| match c {
            '*' => lhs * rhs,
            '/' => lhs / rhs,
            _ => unreachable!(),
        }
    });
    chainl1(parser(factor), op).parse_state(input)
}

pub fn expr<I>(input: State<I>) -> ParseResult<i64, I>
    where I: Stream<Item = char>
{
    let op = char('+').or(char('-')).map(|c| {
        move |lhs, rhs| match c {
            '+' => lhs + rhs,
            '-' => lhs - rhs,
            _ => unreachable!(),
        }
    });
    chainl1(parser(term), op).parse_state(input)
}

pub fn parse<I>(input: I) -> Result<(i64, I), ParseError<I>>
    where I: Stream<Item = char>
{
    parser(expr).parse(input)
}

それぞれの関数が一つのパーサの役割を担います.それぞれのパーサが独立していて,それぞれ別々に型変数を導入しています.

次に &str だけを受け取るパーサです.これは上記のジェネリックなパーサの,型変数を &str に置き換えるだけなのでとても簡単です.
一部だけ掲載します.

pub fn expr(input: State<&str>) -> ParseResult<i64, &str> {
     let op = char('+').or(char('-')).map(|c| {
        move |lhs, rhs| match c {
            '+' => lhs + rhs,
            '-' => lhs - rhs,
            _ => unreachable!(),
        }
    });
    chainl1(parser(term), op).parse_state(input)
}

pub fn parse(input: &str) -> Result<(i64, &str), ParseError<&str>> {
    parser(expr).parse(input)
}

最後が,ジェネリックな構造体のメソッド中に,ジェネリックでないパーサを定義して閉じ込める方法です.

use combine::*;
use combine::primitives::Stream;
use std::marker::PhantomData;

 truct P<I>(PhantomData<fn(I) -> I>);

impl<I> P<I> where I: Stream<Item = char> {
    pub fn integer(input: State<I>) -> ParseResult<i64, I> {
        many1::<Vec<_>, _>(digit())
            .map(|is| is.into_iter().fold(0, |lhs, rhs| lhs + (rhs as i64 - '0' as i64)))
            .parse_state(input)
    }

    pub fn factor(input: State<I>) -> ParseResult<i64, I> {
        between(char('('), char(')'), parser(P::<I>::expr))
            .or(parser(P::<I>::integer))
            .parse_state(input)
    }

    pub fn term(input: State<I>) -> ParseResult<i64, I> {
        let op = char('*').or(char('/')).map(|c| {
            move |lhs, rhs| match c {
                '*' => lhs * rhs,
                '/' => lhs / rhs,
                _ => unreachable!(),
            }
        });
        chainl1(parser(P::<I>::factor), op).parse_state(input)
    }

    pub fn expr(input: State<I>) -> ParseResult<i64, I> {
        let op = char('+').or(char('-')).map(|c| {
            move |lhs, rhs| match c {
                '+' => lhs + rhs,
                '-' => lhs - rhs,
                _ => unreachable!(),
            }
        });
        chainl1(parser(P::<I>::term), op).parse_state(input)
    }
}

pub fn parse(input: &str) -> Result<(i64, &str), ParseError<&str>> {
    parser(P::expr).parse(input)
}

言葉で説明すると難しいのですが,型変数を導入する部分を構造体の定義部分だけにしてあげることで,型変数をそれぞれのパーサが別々に導入する必要がなくなっています.
コードも割りとすっきりしますね.

結果

上記をコードを cfg を使ってコンパイル時に切り替えながらコンパイルしてみました.
本当はきちんと繰り返し計測すべきですが,ちょっとサボっています.まぁ何度実行してもだいたい同じくらいになったので許してください.

実装方法 コンパイル時間
ジェネリック 2.666s
&str 1.70s
構造体内で定義 1.55s

このような結果になりました.
つまり,先ほどの issue で述べられているコンパイル時間の短縮方法はかなり効き目があるということですね.
構造体の中に閉じ込める方法が,&str しか受理しないようにする方法よりもはやくコンパイルできるのは意外でした… 参照を引数にとると暗黙に lifetime 変数が導入されたと記憶しているので,その関係なのかな?

構造体内で定義する方法では,&str 以外の入力ストリーム型を受けつけることを可能にしつつもコンパイル時間を短縮できるということで,積極的にこの方式でパーサを定義するべきということがわかりました.

注意点として,構造体内で別のパーサを呼ぶときには,必ず P::term という形ではなく,P::<I>::term という形で呼び出すようにする必要があるようです.
きちんと明示的に指定しないと,結局型推論するはめになって意味がないということのようです.