日本語の改行を適当にいい感じにするツールを作りました
必要に迫られて、HTML ページ内の改行位置をいい感じにするツールを作ってみました。
HTMLに長文を書くと、親 DOM のサイズの制約上、適宜改行がぶちこまれます。
しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。
最も有名な問題として、今すぐダウンロー
ド問題が挙げられます。
japawrap
を使うと、それっぽく日本語を解釈して <span>
でくくるみたいなことができます。inline-block
を適用すれば改行がそれっぽく入るようにできます。
Install
go get github.com/agatan/japawrap/...
で japawrap
コマンドが使えるようになります。
Usage
CLI
ファイル名を指定するか標準入力から流し込みます。
$ echo "今日も元気です" | japawrap <span class="wordwrap">今日も</span><span class="wordwrap">元気です</span>
このように適宜いい感じに wrap してくれます。
オプションとして -open string
と -close string
をサポートしているので、
$ echo "今日も元気です" | japawrap -open '<span style="display: inline-block;">' -close "</span>" <span style="display: inline-block;">今日も</span><span style="display: inline-block;">元気です</span>
みたいなことができます。
Library
一応 japawrap
はライブラリとしても使用できるようになっています。
w := japawrap.New(open, close) s := "今日も元気です" fmt.Println("%s => %s", s, w.Do(s))
これだけです。
Example
では実際に使った結果を下に記したいと思います。 文章は、上の方に自分で書いた文章をそのまま使います。
before
HTMLに長文を書くと、親DOM のサイズの制約上、適宜改行がぶちこまれます。 しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。 最も有名な問題として、今すぐダウンロード問題が挙げられます。
after
HTMLに長文を書くと、親 DOM のサイズの制約上、適宜改行がぶちこまれます。 しかし、改行位置は文節を考慮などせずにごりっと挿入されるので、多くの問題が生じることが報告されています。 最も有名な問題として、今すぐダウンロード問題が挙げられます。
こんな感じになります。猛烈に効果がわかりにくくて驚いていますが、一応効果はちゃんと出ているのではないでしょうか? HTMLを直接見ていただければどうなっているかはわかると思います。
次に青空文庫から夏目漱石「こころ」の序文を抜粋してみたのが下の画像たちです。
レスポンシブ!それなりになっている気がします。
あとがき
この問題へのアプローチとして、https://github.com/google/budou が有名だと思います。
budou
は Cloud Natural Language API を内部で使っていて、しっかり日本語の文章を構文解析しているようです。
なので非常に精度は高いと思うのですが、今僕の GCP アカウントがごにょごにょしていてぱぱっと試せる状況ではなかったので自作しました。
budou
と違ってしっかり構文解析などはしていなくて、形態素解析した後、それっぽく分割しているだけです。なので精度は落ちると思います。
一方、budou
は GCP の credentails が必要だったりと準備が必要になるので、お手軽に試せるというのは悪くないかなと思っています。
Rust の Result と Iterator
Rust には失敗するかもしれない値を表す Result<T, E>
という型があります。
std::result::Result
そして iterate できることを表す Iterator
という trait があります。
std::iter::Iterator
また、Iterator
trait は要素型を表す関連型を持ちます。例えば
ここ間違っていました。String
は Iterator<Item=char>
を impl
しています。これは char
型を要素にもつ Iterator
であることを意味します。String
が直接 Iterator
を impl
しているのではありませんでした。
たまに Iterator<Item=Result<T, E>>
のようになっている型を見かけます(T, E にはなにかしら具体的な型が入っていると思ってください)。
例えば、std::io::stdin().bytes()
の返り値である std::io::Bytes は Iterator<Item=Result<u8>>
を impl
しています。
(ちょっとわかりにくいのですがここでの Result
は std::result::Result
ではなくて std::io::Result
です。std::io::Result
は std::result::Result<T, std::io::Error>
のエイリアスです。)
さて、このような Iterator
からすべての要素が Ok(_)
であれば Ok<Vec_>>
を、Err(_)
があれば Err<_>
を返すような処理を書きたいということは割りとよくあります。
で、これを一生懸命実装しようとしていたのですが、標準ライブラリの範囲内ですでに実装されていました。べんり。
let result = std::io::stdin().bytes().collect::<Result<Vec<_>, _>>();
これだけです。これで要件を満たす Result<Vec<_>, _>
が返って来ます。すばらしい。
タネは簡単な話で Result
が FromIterator
trait を impl
しているので collect
で変換が可能であるというお話でした。
std::iter::FromIterator
値と参照について
「値」と「参照」という言葉があります。 このへんの言葉について、今の理解をまとめておこうと思います。 言葉の定義や理解が誤っている部分があればご指摘ください。
まず、前提として以下では、「値」ベースの言語として C, C++, Rust などを、「参照」ベースの言語として Java, C#, Ruby などを想定しています。 (もちろん言語によってはハイブリッドなものもあります: Crystal, Go, D, ...)
そもそも「値」「参照」とは
「値」は「実体」、「参照」は「実体へのポインタ」です。
int
の配列みたいなものを考えてみます。
[1, 2, 3]
をメモリ上にどう表現できるでしょうか。
配列ですから、単純にメモリ上のどこかに以下のような領域を作ればよさそうです。
+---+ | 1 | +---+ | 2 | +---+ | 3 | +---+
これが「値」であり配列の実体です。 そして、実体の配置されたメモリ領域へのポインタが「参照」です。
スタック上の表現
さて、プログラム上ではこの配列のようなオブジェクトを、ローカル変数としてスタック上で表現したり、関数に引数として渡したりします。 では、スタック上での配列の表現はどうなっているのか考えてみます。
ここで、「値」と「参照」という言葉が重要になります。
「値」ベースな言語では、スタック上に
+---+ | 1 | +---+ | 2 | +---+ | 3 | +---+
をそのままべたっと配置します。
一方で、「参照」ベースな言語では、ヒープ上に
+---+ | 1 | +---+ | 2 | +---+ | 3 | +---+
を配置し、スタック上では実体へのポインタという表現になります。 (必ずしもヒープに置くとは限らない?処理系や最適化によってはスタックに置くこともありえる?とにかくローカル変数などの表現としては実体へのポインタという形をとるということ)
値渡し・参照渡し
値渡しとか参照渡しという言葉があります。
以下に擬似コードを一つ書いてみます。(C 風に書いていますが C ではないと思ってください)
void inc_age(Person p) { p.age++; } Person john = Person { "john", 20 }; inc_age(john); print(john.age); // => ??
このコード、処理系が「値」ベースか「参照」ベースかで結果が異なります。
「値」ベースの場合
値ベースの言語の場合、inc_age
の引数に john
を渡した時には、inc_age
内のローカル変数(引数) p
のために、john
のコピーが作られます。
inc_age
内で p.age++
としていますが、p
は john
のコピーであって john
ではありませんから、inc_age
から戻ってきて john.age
を参照しても 20 のまま変化が無いはずです。
したがって結果として 20
が出力されます。
「参照」ベースの場合
参照ベースの言語の場合、john
変数のメモリ上での表現は、ヒープに置かれた Person { "john", 20 }
というオブジェクトへのポインタになります。
inc_age
にこれを引数として渡すと、ポインタの値がコピーされますから、p
と john
は同じオブジェクトを参照しているポインタになります。
p.age++
とすると p
が参照するオブジェクトが変更されます。これは john
が参照するオブジェクトと同一ですから、john.age
も 21 に変化します。
したがって結果として 21
が出力されます。
C の場合
C の場合、ポインタが直接表現できますから、参照渡しの挙動を模倣することができます。
void inc_age(Person *p) { p->age++; } Person john = Person { "john", 20 }; inc_age(&john); print(john.age); // => 21
p
が Person*
型であること、そして inc_age
に john
のアドレスを渡していることに注目してください。
この場合、p
は john
を参照するポインタですから、結果は 21
になります。
C++ の場合
C++ の場合、言語機能として「参照渡し」という機能があります。
void inc_age(Person& p) { p.age++; } Person john = Person { "john", 20 }; inc_age(john); print(john.age); // => 21
p
が Person&
型であること、inc_age
には john
をそのまま渡しているように見えることに注目してください。
これは C++ の提供する機能で、コンパイルすると、Person&
は実質 Person*
と同じ表現になります。
p->age
ではなく p.age
と書けること、&john
ではなく john
のままで参照渡しが実現できるようになっています。
単純なポインタを使っても同じことが出来ますが、ポインタと違って nullptr
になることがないという特徴があります。
参照のハマりやすい点
個人的に参照ベースの言語でハマりやすいなと感じるのは以下のようなコードです。
void some_function(Person p) { p.age++; p = new Person("bob", 30); } Person p = new Person("john", 20); some_function(p); println(p.name); // => john println(p.age); // => 21
p.age++
の部分は呼び出し元のオブジェクトに反映されるのに、p = new Person(...)
の部分はなんで反映されないの!ってなります。(なりません?)
本質的にポインタの値渡しにすぎないんだということを理解していればまぁ納得なのですが...
(ちなみに C++ や D の参照渡しだと p = new Person(...)
的なコードも呼び出し元に反映されます。)
値のハマりやすい点
ハマりやすいというか、気がつかないままパフォーマンスが悪くなりやすいのが値ベースの言語の弱点でしょう。
void print_object(HugeObject obj) { printf("%s\n", obj.name); } HugeObject obj = ...; print_object(obj);
このようなコードを書くと、ただ名前を表示するだけの関数が激重になる可能性があります。 値ベースの言語では、引数として値を渡すとまるっとそのコピーをつくりますから、不要にもかかわらず巨大な値のコピーを作ってしまいます。
まとめ
「ムーブセマンティクス」とか「immutable と参照」とかについてまとめようと思ったのですが、前提として「値」「参照」についてまとめていないと書きにくいなと思ったのでまとめておきました。
内部表現を知ることでハマりやすい点の回避にもつながると思うので、この辺はきちんと理解しておきたいです。
再帰的 grep ツール crepe を作っています
再帰的にパスをたどりながらパターンにマッチする行を検索する grep 系のツールを作っています。
有名どころとしては、ack とか ggreer/the_silver_searcher(ag) とか monochromegane/the_platinum_searcher とか tkengo/highway なんかがあります。群雄割拠ですね。
これらの有名ツール達はそれぞれ特徴があって(速さとか出力形式とかエンコード対応とか)便利に使わせていただいております。
今回 crepe
を作ろうと思った理由は、なんとなく C++ でちゃんとスレッド立てて並行処理みたいなコードを書いてみたくなったからです。
速度等も測っていないのでどこまで意味があるのか怪しいのですが、とりあえず現状 3 つの仕事を並列に動かしています。
一つ目は出力を担当するスレッドで、マッチ結果を受け取って出力するだけです。
二つ目はマッチを担当するスレッドで、ファイル名と FILE*
を受け取ってマッチ結果を生成し出力担当スレッドに渡します。
三つ目はパスを walk するスレッドで、ディレクトリを掘りながらファイルを開いてマッチスレッドに送ります。
現状はまだ部分一致の matcher しか実装していないので正規表現や fuzzy マッチは未実装です。
標準入力かパスから部分一致する行を探してきて出力します。
出力形式は ag
に近い形式で、ファイルごとにグループ分けして行番号とともに出力します(オプションでこの辺の挙動はいじれるようにはなっています)
バイナリファイルっぽいファイルはスキップするようになっています。
やりたいこと
最終目標として crepe
は peco のような interactive な検索を実装してみたいなと思っています。
ag
と peco
の組み合わせで云々みたいなユースケースが割りとあるなぁと思ったので。
ただこれメモリ使用量とか速度上の制約からまともに働くのかはよくわかっていません。
単純に考えると、ユーザが一文字入力するたびにファイルの 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==
を自動導出する例ですが、Haskell の Ord
型クラスを意識しています。
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.valueOf
や Float.valueOf
を含むコメントを見ていただければわかると思いますが、このコメント部分には呼び出しているメソッドの型が記されています。
つまり、identity
は Integer
で呼んでも Float
で呼んでも Object identity(Object)
を呼んでいるということです。
これは Java のジェネリクスの大きな特徴で型消去などと呼ばれる性質です。ジェネリクスによる型はすべてコンパイル時にのみ利用され、実行時にはすべて Object
として表現しつつ適切にキャストを挟むような構造になっています。
キャストはキャストでも、正しいことがコンパイラによって保証されたキャストになるので、List
よりも List<String>
のほうが安全というわけです。
それぞれの利点と欠点
テンプレートやジェネリクスを実現する方法として、2つの例を上げました。
一つは C++ の採用している方式で、テンプレート引数ごとに新しく実体を作ってしまう方式です。
もう一つは Java の採用している方式で、Object
のようにすべての型を受け取れる基底クラスのようなものを用いて、実行時には型情報を残さない方式です。
今回はたまたま C++ と Java を例にあげましたが、他の言語でもこのような方式を使っている言語は多いです。(みんなだいすき D 言語は C++ の方式を採用しています)
さてそれぞれの利点と欠点についてです。
Java 方式
- 利点
- 欠点
- 実行時にやることが増えるのでオーバヘッドがある
C++ 方式
- 利点
- 実行時オーバヘッドなし(全てコンパイル時に解決される)
- 欠点
こんな感じでしょうか。
この比較はあくまで型を汎用化したいという目的に関しての比較です。C++ のテンプレートにできて Java のジェネリクスに出来ないことはたくさんあります。
まとめ
C++er はみんな実行時のオーバヘッドが嫌いです。テンプレートは、今までに紹介してきた使用法からは想像も出来ないほど豊富な計算を、コンパイル時にすべて行うことが出来ます。実行時のオーバヘッドなしで。
コンパイル時にテンプレートの解決が終わるということは、強力な最適化が望めるということでもあります。つまり、実行時のキャストといったわかりやすいオーバヘッド以上に、実行速度には差が生まれるでしょう。
というわけで今回はテンプレートの実現方法について、Java と比較しながら説明してみました。