（略）を問い詰める会と curry

もう先週になってしまうのですが C++WG 会議の後に行われた「（略）を問い詰める会」に参加してきました。
結構な人数が参加されていたのですが、半分くらいの方としかお話できなかったんじゃないかなあ…少し残念でした。

id:rti7743 さんが途中「カリー化って何なんでしょう」ということを言われて、あーだこーだ言い合って、そこから「C++0x ならカリー化関数を書けるはず！」ということになって、その場はそれで終わりました。

ということで、実際に書いてみました。

…思っていたよりずっと大変でした。

#include <tuple>
#include <type_traits>
#include <functional>

using namespace std;

template <unsigned int N>
struct apply_impl {
  template <typename Fun, typename ...Args, typename ...BoundArgs>
  static auto impl(Fun fun, tuple<Args...> t, BoundArgs... args) -> typename result_of<Fun (Args...)>::type {
    return apply_impl<N-1>::impl(fun, t, std::get<N-1>(t), args...);
  }
};

template <>
struct apply_impl<0> {
  template <typename Fun, typename ...Args>
  static auto impl(Fun fun, tuple<Args...> t, Args... args) -> decltype(fun(args...)) {
    return fun(args...);
  }
};

template <typename Fun, typename ...Args>
auto apply(Fun fun, tuple<Args...> t) -> typename result_of<Fun (Args...)>::type {
  return apply_impl<sizeof...(Args)>::impl(fun, t);
}

template <typename Ret, typename Args>
struct RetType;

template <typename Ret>
struct RetType<Ret, tuple<>> {
  typedef Ret type;
};

template <typename Ret, typename ArgsHead, typename ...ArgsTail>
struct RetType<Ret, tuple<ArgsHead, ArgsTail...>> {
  typedef typename RetType<Ret, tuple<ArgsTail...>>::type Partial;
  typedef function<Partial (ArgsHead)> type;
};

template <typename T>
struct curry_impl;

template <>
struct curry_impl<tuple<>> {
  template <typename Ret, typename ...Args>
  static auto impl(Ret (*fun)(Args...), tuple<Args...> t) -> Ret {
    return apply(fun, t);
  }
};

template <typename UnBoundArgsHead, typename ...UnBoundArgsTail>
struct curry_impl<tuple<UnBoundArgsHead, UnBoundArgsTail...>> {
  template <typename Ret, typename ...Args, typename ...BoundArgs>
  static auto impl(Ret (*fun)(Args...), tuple<BoundArgs...> t) -> typename RetType<Ret, tuple<UnBoundArgsHead, UnBoundArgsTail...>>::type {
    return [fun, t](UnBoundArgsHead arg){ return curry_impl<tuple<UnBoundArgsTail...>>::impl(fun, tuple_cat(t, make_tuple(arg))); };
  }
};

template <typename Ret, typename ...Args>
auto curry(Ret (*fun)(Args...)) -> typename RetType<Ret, tuple<Args...>>::type {
  return curry_impl<tuple<Args...>>::impl(fun, make_tuple());
}

いきなりこのコードを読むのはかなり大変なはずなので、まずは curry の擬似コードを書きます。

curry_impl(fun, bound_args_tuple, unbound_arg_types){
  if empty(unbound_arg_types.empty?)
    return apply(fun, bound_args_tuple)
  else
    return function(head(unbound_arg_types) arg){
             return curry_impl(fun, bound_args_tuple.cat(arg), tail(unbound_arg_types)
            }
}

curry(fun){
  return curry_impl(fun, (), parameter_types(fun))
}

未束縛な引数（型）がなくなるまで再帰し、全て束縛したら関数を呼び出す、という形です。引数の束縛にはタプル（std::tuple）を、関数の呼び出しには apply を利用しています。
（lambda 式に function parameter pack を capture することが可能ならタプルや apply は不要なのですが、残念なことに gcc-4.5.1 では function parameter pack の capture は実装されていません。function parameter pack の capture については FCD の 5.1.2 p23 もしくは 14.5.3 p4 を参照してください。）
次は apply の擬似コードです。

apply_impl(fun, arg_types, args_tuple, ...args){
  if (type(args...) == arg_types)
    return fun(args...)
  else
    return apply_impl(fun, arg_types, args_tuple, args..., args_tuple.get(len(args...)))
}

apply(fun, args_tuple){
  return apply_impl(fun, parameter_types(fun), args_tuple)
}

タプルには「tail」のような演算は標準では用意されていないため、タプルを減らしながら再帰する形では書くことができません。（C++0xFAQ の実装例ではあるのに…用意されてない理由を知っている人がいたら教えて下さい。）
仕方がないのでタプル内の値を function parameter pack に一つずつ追加し、全てうつし終えたら関数を呼び出します。

apply は少し前に一部界隈で話題になった std::pair の in-place construction （勝手に命名）の実装にも必要なはずで、それ以外にも役に立つ場面は多々あると思うのですが、これも「tail」同様標準では用意されていません…ませんよね？

まずは generic でない、関数ポインタ向けの apply を実装してみましょう。

#include <tuple>
using namespace std;

template <unsigned int N>
struct apply_impl {
  template <typename Ret, typename ...Args, typename ...BoundArgs>
  static Ret impl(Ret (*fun)(Args...), tuple<Args...> t, BoundArgs... args){
    return apply_impl<N-1>::impl(fun, t, get<N-1>(t), args...);
  }
};

template <>
struct apply_impl<0> {
  template <typename Ret, typename ...Args>
  static Ret impl(Ret (*fun)(Args...), tuple<Args...> t, Args... args){
    return fun(args...);
  }
};

template <typename Ret, typename ...Args>
Ret apply(Ret (*fun)(Args...), tuple<Args...> t){
  return apply_impl<sizeof...(Args)>::impl(fun, t);
}

sizeof... は parameter pack の長さを返す演算子です。parameter pack なら template parameter pack でも function parameter pack でも、長さを知ることができます。
見たままなのであまり説明するところもないのですが…

今度は generic な apply を実装してみましょう。

#include <tuple>
using namespace std;

template <unsigned int N>
struct apply_impl {
  template <typename Fun, typename ...Args, typename ...BoundArgs>
  static auto impl(Fun fun, tuple<Args...> t, BoundArgs... args)
                   -> decltype( aplly_impl<N-1>::impl(fun, t, get<N-1>(t), args...) )
  {
    return apply_impl<N-1>::impl(fun, t, get<N-1>(t), args...);
  }
};

template <>
struct apply_impl<0> {
  template <typename Fun, typename ...Args>
  static auto impl(Fun fun, tuple<Args...> t, Args... args) -> decltype(fun(args...)) {
    return fun(args...);
  }
};

template <typename Fun, typename ...Args>
auto apply(Fun fun, tuple<Args...> t) -> decltype(apply_impl<sizeof...(Args)>::impl(fun, t)) {
  return apply_impl<sizeof...(Args)>::impl(fun, t);
}

上のコードは gcc-4.5.1 ではコンパイルできません。
問題点をはっきりさせるために、もっと簡単なコードを書いてみます。

void f(int i){}
template <typename T>
auto f(T t) -> decltype(f(t)) {
  return g(t);
}

int main(){
  f(0); // f(int)
  f<int>(0); // f(T) -> f(int)
  f("const char*"); // ????
  return 0;
}

上記の「f("const char*")」を gcc-4.5.1 は「const char* を int に変換することはできない」としてエラーを出力します。f の型が決定できない、ではありません。

もっと簡単にします。

template <typename T>
auto f(T t) -> decltype(f(t)) { }

このコードがおかしいことは明らかですが、これに対して gcc-4.5.1 は「h という識別子は見つからない」としてエラーを吐きます。
テンプレートの instantiation のタイミングを考えると、この振る舞いはおかしいと思うのですが、停止性云々関係なく、少なくとも手元の gcc-4.5.1 では、このようなコードを書くことはできないようです。
言語仕様としてどうなのかは、調べたんですがよく分かりませんでした…が、こんなテストが入ったみたいなので、そのうち書けるようになりそうです。

何にせよ gcc-4.5.1 では、再帰関数の返値型を求めるのに decltype を使うことはできません。
ということで、なんとかします。必要なのは引数に渡された関数の返値型なので、それを計算してやればいいわけです。

  template <typename Fun, typename ...Args, typename ...BoundArgs>
  static auto impl(Fun fun, tuple<Args...> t, BoundArgs... args)
                   -> decltype( fun(declval<Args>()...) )
};

declval は type_traits で定義される、その型の「値」が存在しないときに値を「ごまかす」ための関数テンプレートです。実際に呼び出すことはできませんが、sizeof や decltype などの評価されない式が書ける箇所で利用することができます。
が、こんな気持ち悪いコードを書かなくても、同様のことを行うための result_of テンプレートが利用できます。result_of は名前のとおりの type function です。
result_of は FCD によれば type_traits に定義されているはずなんですが、 gcc-4.5.1 では functional にあって、ちょっとした罠になっています。

#include <functional>
  template <typename Fun, typename ...Args, typename ...BoundArgs>
  static auto impl(Fun fun, tuple<Args...> t, BoundArgs... args)
                   -> typename result_of<Fun (Args...)>::type

というわけで generic な aplly が書けました。

curry は再帰関数の返す型がそれぞれ違っていて apply のようにはいかないので、返値型を計算する type function を書いています（RetType）。
あとは特筆すべきことは特になくて、改良するとしたら generic な curry を enable_if を使って書くくらいでしょうか。書けるのかなあ…？

もっとスマートな書き方があったら教えて下さい。