右上➚

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

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

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 について、２つの引数のうち、大きい方を返す」関数です。
明示的に max<int> や max<double> とすることで、int や double についての「大きい方を返す」関数を得ています。

テンプレート引数の推論

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

int x = max(1, 0);

これは、テンプレート引数の型推論の結果です。
max 関数の第一引数、第二引数はそれぞれ T です。そして、実際に渡されている 1 や 0 は int 型です。
これらの情報から、コンパイラは 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++でデータ型にとらわれずにコードを書くことを可能にする機能であり、C++においてはジェネリックプログラミングに用いられる。
テンプレート (プログラミング) - Wikipedia)より

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

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

例

では一つの例として、スタックというデータ構造をプログラムに落としこむことを考えます。
まずは 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* を使う場合のデメリットは、型システムを台無しにしている点です。(malloc や free が必要であることは 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 コンパイラ

Rust のパーサコンビネータライブラリの一つである Marwes/combine: A parser combinator library for Rust を使ってみています．
詳しい使い方はきちんとしたドキュメントがあるのでそちらを参照してください．
ざっくりいうと Haskell の parsec: 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 という形で呼び出すようにする必要があるようです．
きちんと明示的に指定しないと，結局型推論するはめになって意味がないということのようです．

C++ でパーサコンビネータを書きました

C++ Boost コンパイラ

C++ で構文解析といえば，Boost.Spirit や yacc系などが有名ですが，どうにも使うの辛かったので作りました．

2016/05/01 追記　

いろいろ更新しました．肯定先読み以外はプリミティブも実装し終わっているかと思います．
ドキュメントはまだ無いのですが，すべての機能についてテストは書いてあるので，それを見てもらえればなんとか使い方もわかるかと思います．

agatan/coco

coco::combix がパーサコンビネータライブラリの namespace です．

Boost.Spirit は高機能かつ高性能なんですが，かなり変態的な構文で記述する必要があり(まぁ C++ なんですけど)，さらにその性能や便利さ，構文のために異常なまでにテンプレートを多用しています．私は構文解析後の構文木の構築に Boost.Variant を使ってみているのですが，Boost.Spirit と Boost.Variant の両面から，ジェネリックすぎるがゆえのコンパイルエラー爆発攻撃を食らって本当に辛いです．

そこで，Haskell の parsec や Rust の combine を参考にしつつ，C++ でパーサコンビネータを書いてみました．(実際これを使ってもコンパイルエラーは割りと発狂しますが)

例

例となるコードは agatan/coco-combix-demo においてあります．
ドキュメントもないので，なんとなく雰囲気だけコードから読み取る必要があります．(例に出ていない機能もちょいちょい実装されてしまっています．)

以下にちょっと簡略版のコードを載せてみます．ありがちな電卓です．AST を作らず直接計算しています．

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

#include <coco/combix.hpp>

namespace cbx = coco::combix;

using stream_type = cbx::iterator_stream<std::string::const_iterator>;

cbx::parser<int, stream_type> expression();

cbx::parser<int, stream_type> number() {
  return cbx::expected(cbx::map(cbx::many1(cbx::digit()),
                                [](auto&& is) {
                                  int acc = 0;
                                  for (auto i : is) {
                                    acc = acc * 10 + i;
                                  }
                                  return acc;
                                }),
                       "integer number");
}

cbx::parser<int, stream_type> factor() {
  return cbx::choice(
      number(),
      cbx::between(cbx::skip(cbx::token('('), cbx::spaces()),
                   cbx::skip(cbx::token(')'), cbx::spaces()),
                   cbx::skip(cbx::lazy_fun(expression), cbx::spaces())));
}

cbx::parser<int, stream_type> term() {
  auto op = cbx::map(
      cbx::skip(cbx::choice(cbx::token('*'), cbx::token('/')), cbx::spaces()),
      [](auto c) -> std::function<int(int, int)> {
        if (c == '*') {
          return std::multiplies<int>();
        } else {
          return std::divides<int>();
        }
      });
  return cbx::chainl1(cbx::skip(factor(), cbx::spaces()), op);
}

cbx::parser<int, stream_type> expression() {
  auto op = cbx::map(
      cbx::skip(cbx::choice(cbx::token('+'), cbx::token('-')), cbx::spaces()),
      [](auto c) -> std::function<int(int, int)> {
        if (c == '+') {
          return std::plus<int>();
        } else {
          return std::minus<int>();
        }
      });
  return cbx::chainl1(cbx::skip(term(), cbx::spaces()), op);
}

int main() {
  std::string src;
  std::getline(std::cin, src);
  auto n = number();
  auto stream = cbx::range_stream(src);
  auto const parser = expression();
  if (auto res = cbx::parse(parser, stream)) {
    std::cout << res.unwrap() << std::endl;
  } else {
    std::cout << cbx::to_string(res.unwrap_error()) << std::endl;
  }
}

特徴

parsec を知っている方であれば読めるはずです...
特徴としては，多くのパーサは入力ストリームの型に依存せずに作れるようになっていることです．例えば，あらゆる入力一つを受け付け消費する any というパーサは，入力が char のストリームであろうと int のストリームであろうとパースを実行できるようになっています．
本来はエラーメッセージの爆発や読みづらさを防ぐために，すべてのパーサ自体にストリームの型をひも付けたかったのですが，そうすると，any を使うたびに，any<cbx::iterator_stream<typename std::vector<int>::const_iterator>>() とか any<cbx::iterator_stream<std::string::const_iterator>>() とかしなくてはなりません．これは Haskell や Rust と違って C++ の型推論が限定的であるためです．(Haskell や Rust では後でその値がどう使われているかも推論の根拠として使われます．)
そこで，パーサ自体には入力ストリームの型を指定させずに，実際にパースする部分で初めて入力ストリームの型を検査することにしました．

で，cbx::parser<int, stream_type> はパーサを type erasure を使ってラップします．普通に使っていると簡単に cbx::expected<cbx::map_parser<cbx::many1_parser<cbx::digit_parser>, (lambda at ...)>> 型とかが出てきます(cbx::expected(cbx::map(cbx::many1(cbx::digit()), [](auto&&) {...}), "integer number") の型です)
これを関数定義のたびに書くとか発狂してしまうので，type erasure を使って型をラップし短絡します．
ただしパフォーマンスの観点から行くとおそらく型をラップするために仮想関数を使ってしまうので，インライン展開等がきかなくなると思われます．まぁ仕方ないです．
ただ，型を膨らませすぎずに適度にラップしてやると，コンパイルエラーの内容がかなり読みやすくなるはずです．なのでなんかわからんけどエラーになるっていうときは細かくパーサを分割してラップしてやると良いかもしれません．

まとめ

あまりにもドキュメントやコメント書かなすぎてひどいですが，ちょっと構文解析したいとかっていうときに便利だと思います．
Boost.Spirit と違って普通に C++ のプログラムとして書けます．(Boost.Spirit も C++ プログラムとして書けてはいるんですが，なんかあれはあれで別の言語を覚えているような気分になってしまったので...)

あと PEG のプリミティブをまだ完全に実装していないと思います．先読みや否定先読みが出来ません．(実装します…)

Rust における return文の LLVM IR 表現について

コンパイラ Rust LLVM
  • if 文が値を返す
  • return 文を持つ

以上のような特徴を持つ言語はどういう感じでコンパイルされるのか知りたくて，Rust について調べてみました．

Rust では以下の様なことが出来ます．

fn f() {
  let x = if cond {
    return None;
  } else {
    1
  };
  ...
}

Scala とかもできると思います．cond が真だった場合は，x の値を返すのではなく，関数から抜けてしまうという意味です．

これを Rust ではどんな LLVM IR に落とし込んでいるのか．

return 文がない場合

fn noreturn(x: isize) -> isize {
  x
}

最も単純な場合です．この場合，生成される LLVM IR は，

define internal i64 @_ZN4hoge8noreturn17h811bf1a871f85432E(i64) unnamed_addr #0 {
entry-block:
  %x = alloca i64
  store i64 %0, i64* %x
  %1 = load i64, i64* %x
  ret i64 %1
}

となります． 名前がマングルされていますが，上記の noreturn 関数です． やっていることは単純で，第一引数を読み込んで返すだけです．

return に相当する文が一つのみの場合

fn onereturn(x: isize) -> isize {
  let y = if x == 0 {
    1
  } else {
    x
  };
  return x;
}

実際に値を返す部分が一箇所しかない場合です．途中に分岐があっても最終的に一箇所になっていれば多分同じ結果になります．

define internal i64 @_ZN4hoge9onereturn17h8b718f32daa6a379E(i64) unnamed_addr #0 {
entry-block:
  %x = alloca i64
  %y = alloca i64
  store i64 %0, i64* %x
  %1 = load i64, i64* %x
  %2 = icmp eq i64 %1, 0
  br i1 %2, label %then-block-18-, label %else-block

then-block-18-:                                   ; preds = %entry-block
  store i64 1, i64* %y
  br label %join

else-block:                                       ; preds = %entry-block
  %3 = load i64, i64* %x
  store i64 %3, i64* %y
  br label %join

join:                                             ; preds = %else-block, %then-block-18-
  %4 = load i64, i64* %x
  br label %clean_ast_10_

return:                                           ; preds = %clean_ast_10_
  ret i64 %4

clean_ast_10_:                                    ; preds = %join
  br label %return
}

return という BasicBlock ができています．これは return 文が現れると作られるよう？です． で，その中では単純に x に該当する値を返しています．

最後の return x; 文を 単純に x に置き換えてみると，

define internal i64 @_ZN4hoge9onereturn17h8b718f32daa6a379E(i64) unnamed_addr #0 {
entry-block:
  %x = alloca i64
  %y = alloca i64
  store i64 %0, i64* %x
  %1 = load i64, i64* %x
  %2 = icmp eq i64 %1, 0
  br i1 %2, label %then-block-18-, label %else-block

then-block-18-:                                   ; preds = %entry-block
  store i64 1, i64* %y
  br label %join

else-block:                                       ; preds = %entry-block
  %3 = load i64, i64* %x
  store i64 %3, i64* %y
  br label %join

join:                                             ; preds = %else-block, %then-block-18-
  %4 = load i64, i64* %x
  ret i64 %4
}

となります． return ブロックが消えていますね．なので return 文があると return ブロックが作られる、で良さそう？

複数のパスから値を返す

fn multireturn(x: isize) -> isize {
  let y = if x == 0 {
    return -1;
  } else {
    x
  };
  y
}

さて，では最初に述べた，if の分岐内にある return についてです． これは，

define internal i64 @_ZN4hoge11multireturn17had379e8ce5a18f08E(i64) unnamed_addr #0 {
entry-block:
  %sret_slot = alloca i64
  %x = alloca i64
  %y = alloca i64
  store i64 %0, i64* %x
  %1 = load i64, i64* %x
  %2 = icmp eq i64 %1, 0
  br i1 %2, label %then-block-18-, label %else-block

then-block-18-:                                   ; preds = %entry-block
  store i64 -1, i64* %sret_slot
  br label %return

else-block:                                       ; preds = %entry-block
  %3 = load i64, i64* %x
  store i64 %3, i64* %y
  br label %join

join:                                             ; preds = %else-block
  %4 = load i64, i64* %y
  store i64 %4, i64* %sret_slot
  br label %return

return:                                           ; preds = %join, %then-block-18-
  %5 = load i64, i64* %sret_slot
  ret i64 %5
}

こうなりました． まず，return 文があるため？，return ブロックが作られています． しかし今回は，パスによって返すものが違います．(値が違うという意味ではなく，同じ変数ですらないという意味です...)

よく IR を読むと，関数の頭で %sret_slot という名前でスタック領域を確保していることがわかります． そして，return ブロック内では，これを読んできて返しています．
さらに，if 文の then 節にあたる，then-block-18- というブロックでは，%sret_slot に値を格納して return ブロックへジャンプしています． else 節のあとの部分 (join ブロック) でも同様に, %sret_slot に値を格納して return ブロックへジャンプしています．

まとめ

というわけで，様々な Rust コードを LLVM IR に変換して見てみた結果，複数のパスから値を返す場合は，「ローカル変数として返り値を定義し，そこに返したい値を格納してから return に goto」という形になっていることがわかりました．

(ほとんど LLVM IR を乗っけるだけになってしまった...)

ちなみに ...

if 文の返す値をそのまま返す

fn ifreturn(x: isize) -> isize {
  if x == 0 {
    1
  } else {
    x
  }
}

Rust に慣れていないとちょっとわかりにくいですが，x == 0 の場合は 1 を返し，そうでない場合は x を返す関数です．

これは，

define internal i64 @_ZN4hoge8ifreturn17hcdaab6e376d6c95cE(i64) unnamed_addr #0 {
entry-block:
  %sret_slot = alloca i64
  %x = alloca i64
  store i64 %0, i64* %x
  %1 = load i64, i64* %x
  %2 = icmp eq i64 %1, 0
  br i1 %2, label %then-block-15-, label %else-block

then-block-15-:                                   ; preds = %entry-block
  store i64 1, i64* %sret_slot
  br label %join

else-block:                                       ; preds = %entry-block
  %3 = load i64, i64* %x
  store i64 %3, i64* %sret_slot
  br label %join

join:                                             ; preds = %else-block, %then-block-15-
  %4 = load i64, i64* %sret_slot
  ret i64 %4
}

こうなります．やっていることは上記の例たちとあまり変わりません． しかし，return 文がないので？，return ブロックが作られていません．が, %sret_slot は定義されていますね...
これはどういうことなんでしょう．rustc のコードを読むべきなのかもしれませんが，イマイチ内部処理が想像しにくいです...

普通に翻訳していったら，

let x = if x == 0 { 1 } else { x };
x

と同じ感じになる気がするので，%sret_slot という名前が出てくる余地は無い気がするのですが...(実質同じ処理ではあります) 分岐が直接返戻値になる場合は特別扱いしているのかな？

C++ の複雑な型を整形するプログラムを作りました

C++

テンプレートをバリバリ使っている C++ プログラムのコンパイルエラーが，死ぬほど辛かったので作りました． 型を綺麗に出力するだけです． C++の型版 jq みたいなやつありそうだけど無いのかな？

agatan/tf

たとえば，

boost::spirit::x3::raw_directive<boost::spirit::x3::lexeme_directive<boost::spirit::x3::sequence<boost::spirit::x3::alternative<boost::spirit::x3::char_class<boost::spirit::char_encoding::standard, boost::spirit::x3::alpha_tag>, boost::spirit::x3::literal_char<boost::spirit::char_encoding::standard, boost::spirit::x3::unused_type> >, boost::spirit::x3::kleene<boost::spirit::x3::alternative<boost::spirit::x3::char_class<boost::spirit::char_encoding::standard, boost::spirit::x3::alnum_tag>, boost::spirit::x3::literal_char<boost::spirit::char_encoding::standard, boost::spirit::x3::unused_type> > > > > >::parse<__gnu_cxx::__normal_iterator<const char *, std::__cxx11::basic_string<char> >, boost::spirit::x3::context<boost::spirit::x3::error_handler_tag, const std::reference_wrapper<boost::spirit::x3::error_handler<__gnu_cxx::__normal_iterator<const char *, std::__cxx11::basic_string<char> > > >, boost::spirit::x3::context<boost::spirit::x3::skipper_tag, const boost::spirit::x3::char_class<boost::spirit::char_encoding::ascii, boost::spirit::x3::space_tag>, boost::spirit::x3::unused_type> >, std::__cxx11::basic_string<char>, char>

こんなエラーがよく有りますよね．

これを tf の標準入力に流しこむと，

boost::spirit::x3::raw_directive<
    boost::spirit::x3::lexeme_directive<
        boost::spirit::x3::sequence<
            boost::spirit::x3::alternative<
                boost::spirit::x3::char_class<
                    boost::spirit::char_encoding::standard,
                    boost::spirit::x3::alpha_tag
                >,
                boost::spirit::x3::literal_char<
                    boost::spirit::char_encoding::standard,
                    boost::spirit::x3::unused_type
                >
            >,
            boost::spirit::x3::kleene<
                boost::spirit::x3::alternative<
                    boost::spirit::x3::char_class<
                        boost::spirit::char_encoding::standard,
                        boost::spirit::x3::alnum_tag
                    >,
                    boost::spirit::x3::literal_char<
                        boost::spirit::char_encoding::standard,
                        boost::spirit::x3::unused_type
                    >
                >
            >
        >
    >
>::parse<
    __gnu_cxx::__normal_iterator<
        constchar*,
        std::__cxx11::basic_string<
            char
        >
    >,
    boost::spirit::x3::context<
        boost::spirit::x3::error_handler_tag,
        conststd::reference_wrapper<
            boost::spirit::x3::error_handler<
                __gnu_cxx::__normal_iterator<
                    constchar*,
                    std::__cxx11::basic_string<
                        char
                    >
                >
            >
        >,
        boost::spirit::x3::context<
            boost::spirit::x3::skipper_tag,
            constboost::spirit::x3::char_class<
                boost::spirit::char_encoding::ascii,
                boost::spirit::x3::space_tag
            >,
            boost::spirit::x3::unused_type
        >
    >,
    std::__cxx11::basic_string<
        char
    >,
    char
>

こうなります．

単純に <, >, , を見てインデントを調整しながら出力しているだけです． 空白はスキップします．

構文解析とかは全くしていないので，コンパイルエラーをそのまま流し込んでも悲惨な事になります． あと今気がついたのですが，const hoge が consthoge になっていますね． 修正しました

boost::spirit::x3::raw_directive<
    boost::spirit::x3::lexeme_directive<
        boost::spirit::x3::sequence<
            boost::spirit::x3::alternative<
                boost::spirit::x3::char_class<
                    boost::spirit::char_encoding::standard,
                    boost::spirit::x3::alpha_tag
                >,
                boost::spirit::x3::literal_char<
                    boost::spirit::char_encoding::standard,
                    boost::spirit::x3::unused_type
                >
            >,
            boost::spirit::x3::kleene<
                boost::spirit::x3::alternative<
                    boost::spirit::x3::char_class<
                        boost::spirit::char_encoding::standard,
                        boost::spirit::x3::alnum_tag
                    >,
                    boost::spirit::x3::literal_char<
                        boost::spirit::char_encoding::standard,
                        boost::spirit::x3::unused_type
                    >
                >
            >
        >
    >
>::parse<
    __gnu_cxx::__normal_iterator<
        const char *,
        std::__cxx11::basic_string<
            char
        >
    >,
    boost::spirit::x3::context<
        boost::spirit::x3::error_handler_tag,
        const std::reference_wrapper<
            boost::spirit::x3::error_handler<
                __gnu_cxx::__normal_iterator<
                    const char *,
                    std::__cxx11::basic_string<
                        char
                    >
                >
            >
        >,
        boost::spirit::x3::context<
            boost::spirit::x3::skipper_tag,
            const boost::spirit::x3::char_class<
                boost::spirit::char_encoding::ascii,
                boost::spirit::x3::space_tag
            >,
            boost::spirit::x3::unused_type
        >
    >,
    std::__cxx11::basic_string<
        char
    >,
    char
>

Type Erasure による Visitor パターンの実装

C++ コンパイラ

プログラミングしていて，木構造をうまく扱いたいという状況は結構良くあると思います．
代数的データ型とパターンマッチを持つ言語であればとても美しく完結に表現できる木構造ですが，オブジェクト指向言語でやろうと思うと結構たいへんです．
典型的には Visitor パターンというやつを用います．デザインパターン - Visitor パターン再考 - Qiitaが非常にわかりやすく，理解の助けになりました．ありがとうございます．

一方，C++ の有名なライブラリ，Boost には Boost.Variant というモジュールがあり，これまたとても美しく Visitor っぽいことが出来ます．

#include <boost/variant.hpp>
#include <string>
#include <iostream>

using sample = boost::variant<int, double, std::string>;

sample s1 = 1;
sample s2 = 2.0;
sample s3 = "sample3";

boost::apply_visitor([](auto const& v) { std::cout << v << std::endl; }, s1); // => 1
boost::apply_visitor([](auto const& v) { std::cout << v << std::endl; }, s2); // => 2.0
boost::apply_visitor([](auto const& v) { std::cout << v << std::endl; }, s3); // => sample3

しかし，Boost.Variant は非常に高機能ですが，テンプレートをガンガン使っていたりするので，コンパイルコストが大きいという問題があります．

そこで，Type Erasure を使って visitor パターンをうまく表せれば，コンパイルコストを下げられるのでは？というお話です．
Type Erasure は「型消去」とかでググると色々解説してくださっている記事などが出てくると思います．（ありがとうございます）

この話，私が考えたわけではなくて，どこかのソースコードで見たようなきがするんですが，当時は Type Erasure とか意味不明だったのでスルーしていました．
今ならなんとなくやりたいことは出来るような気がするので（＆ちょうど必要になったので）記事にしてみていますが，もしオリジナルっぽいものや同じようなことを提案しているソースコード・記事を見かけた方は是非ご連絡いただけると嬉しいです．

1st step

Visitor

今回表現したいデータ構造をまず定めます．簡単のために，足し算・掛け算・整数定数の 3 種類のノードを持つ木構造を考えます．
(1 + 2) * 3 なら， mul( add(1, 2), 3 ) みたいな感じです．

この構造を visit する Visitor クラスから先に考えます．
Visitor クラスは，visit というメンバ関数をもつ型の値を，型を消去して保持させます．

class visitor {
private:
  class visitor_base_holder {
  public:
    virtual void visit(add &) = 0;
    virtual void visit(mul &) = 0;
    virtual void visit(constant &) = 0;

    virtual ~visitor_base_holder() = default;
  };

  template <typename V> class visitor_holder : public visitor_base_holder {
  private:
    V &v;

  public:
    visitor_holder(V &v) : v(v) {}

    void visit(add &a) override { v(a); }
    void visit(mul &a) override { v(a); }
    void visit(constant &a) override { v(a); }

    virtual ~visitor_holder() = default;
  };

  std::unique_ptr<visitor_base_holder> holder;

public:
  template <typename V>
  visitor(V &v)
      : holder(std::make_unique<visitor_holder<V>>(v)) {}

  template <typename Visitable> void visit(Visitable &v) { holder->visit(v); }
};

今回は const 修飾についてすべて無視しています．( const を考慮するならば，各 visit について，visitor の const 性と node の const 性を考える必要があります．つまり 4 種類のメンバ関数を定義しなければなりません．）
visit した対象となるそれぞれのデータについてオーバーロードする形で visit を定義しています．
visitor のコンストラクタに，operator()(add&), operator()(mul&), operator()(constant&) を全て持つオブジェクト（C++14 のジェネリックラムダでもOK）を渡すことで，型消去された visitor が出来上がります．
visitor のコンストラクタにどんな型の値を渡しても，出来上がる visitor にはその型情報は含まれないので，様々な visitor を統一して扱う（ vector に突っ込むとか）事ができるようになります．

Node

次にノードの方について考えます． 通常，Visitor パターンでは， visit される側のクラスに accept を実装します．
visit される側のデータを統一的に扱う（ vector に突っ込むとか）ためには，継承やインターフェースを用いるのが普通です．
C++ では，Visitor 側に使った Type Erasure のテクニックが使えます．
std::vector<node> などのように，統一的にノードを扱いつつも，visit される際には，visit(add&) や visit(mul&) のような適切なオーバーロード関数を呼び出すようにしてやればオッケーです．

class node {
private:
  class node_base_holder {
  public:
    virtual void accept(visitor &v) = 0;

    virtual ~node_base_holder() = default;
  };

  template <typename T> class node_holder : public node_base_holder {
  public:
    node_holder(T const &n) : node(n) {}
    node_holder(T &&n) : node(n) {}

    void accept(visitor &v) override { v.visit(node); }

    ~node_holder() = default;

  private:
    T node;
  };

  std::shared_ptr<node_base_holder> holder;

public:
  template <typename Node>
  node(Node const &n)
      : holder(std::make_shared<node_holder<Node>>(n)) {}

  template <typename Node>
  node(Node &&n)
      : holder(std::make_shared<node_holder<Node>>(n)) {}

  void accept(visitor &v) { holder->accept(v); }

  template <typename Visitor> void accept(Visitor &v) {
    visitor visit(v);
    holder->accept(visit);
  }
};

これ結構わかりにくと思うのですが，自分でもコンパイラに怒られながら書いたのでいまいちよく分かってません．
先ほどの visitor の場合と異なり，node には特別満たすべきインターフェースは有りません．
Type Erasure を使う理由は，適切な visit 関数へのディスパッチのためです．

使う

visitor と node が出来たので，使ってみます．
その前にデータ構造を定義しておきます．

struct constant {
  int value;
};

struct add {
  node lhs;
  node rhs;
};

struct mul {
  node lhs;
  node rhs;
};

add や mul のフィールドに，node が使用されている点が大事です．
add.lhs や mul.rhs には，constant が来るか add が来るか mul が来るか分かりません．
そこで，visit 可能な型なら何でもOKという意味で，node 型の値をフィールドとします．

node n = mul{add{constant{1}, constant{2}}, constant{3}};

これで，(1 + 2) * 3 が表現できています． add や constant から node へと暗黙変換が行われていることに注意してください．

次に visitor を定義します．これは，operator() をオーバーロードした関数オブジェクトです．
式を出力する printer と 式を計算する calculator を定義します．

struct printer {
  void operator()(add &a) {
    std::cout << "(";
    a.lhs.accept(*this);
    std::cout << ")";
    std::cout << "+";
    std::cout << "(";
    a.rhs.accept(*this);
    std::cout << ")";
  }

  void operator()(mul &a) {
    std::cout << "(";
    a.lhs.accept(*this);
    std::cout << ")";
    std::cout << "*";
    std::cout << "(";
    a.rhs.accept(*this);
    std::cout << ")";
  }

  void operator()(constant &c) { std::cout << c.value; }
};

struct calculator {
  int result;
  void operator()(add &a) {
    calculator l, r;
    a.lhs.accept(l);
    a.rhs.accept(r);
    result = l.result + r.result;
  }

  void operator()(mul &m) {
    calculator l, r;
    m.lhs.accept(l);
    m.rhs.accept(r);
    result = l.result * r.result;
  }

  void operator()(constant &c) { result = c.value; }
};

こんな感じです．
visit や accept を void を返す関数として定義したので，calculator は自前のフィールドに結果を保持する必要があります． (あとで改善します)

使い方は

  node n = mul{add{constant{1}, constant{2}}, constant{3}};
  printer p;
  n.accept(p);
  calculator calc;
  n.accept(calc);
  std::cout << std::endl;
  std::cout << calc.result << std::endl;
  return 0;

です．

まとめ

この方法の利点としては，データの定義そのものに Visitor パターンのためのノイズが入らないことが挙げられます．
普通の Visitor パターンでは継承必須ですし．

const つけてないせいで一時オブジェクトが使えないので printer p; という行が必要になってしまっています．これはconstをがんばってつけるだけなのでまぁ問題有りません．
一方，calculator の方はダサいですね．値を返す visitor も定義できるようにしたい．
visitor の定義もツライです．const を考慮した場合，同じような内容のメンバ関数を 4 回ずつ書く必要がある．

このへんの問題点は解決可能な気がするので出来たら後で記事にするつもりです．

難しすぎて普通の visitor パターンで良くね？感出てきた