Skip to content
2009/06/09 / highmt

ランクN列多相

おそらく間違いがあると思いますが、ランクNの列多相を実装しようとして考えたことをメモしておきます。
たぶん後でいろいろ修正。

ランク1

列多相の実装を考えてみます。

たとえば、C++では、次のように書けます。

struct Poly1
{
  int property1;
};

struct Poly2
{
  int property1;
  int property2;
};


template <class t>
int get_property1(const T& t)
{
  return t.property1;
}

Poly1 p1 = { 1 };
Poly2 p2 = { 2, 3 };
int r1 = get_property(p1); // 1
int r2 = get_property(p2); // 2

関数テンプレートget_property1は、
property1のパブリックフィールドを持つクラスを適切に取り扱うことができます。

これは、通常(exportを使わない場合)、コンパイル時にget_property1を実際の型でインスタンス化することにより実現されます。
この場合、(明示的インスタンス化をするなどしない限り)
get_property1を分割コンパイルできないことになります。

コンパイルするときに次のように変換すると分割コンパイルできます。
(ここからは想像上の例です。)

// イメージ。
int get_property1(const T& t, int (*get_property_1_impl)(const T&))
{
  return get_property_1_impl(t);
}

つまり、get_property_1_impl という、特定の型によって決まる実装を渡すようにします。
get_property1はそれを呼び出すだけなので、Tの型がわからなくてもコンパイルできます。
(ただし、ここではTが値セマンティクスでないこととしています。
値セマンティクスの場合型のサイズも必要になります。
この場合も引数として渡してあげればコンパイル可能です。)

一般のadhocな多相の場合も同様のことができます。

(これは、http://www.pllab.riec.tohoku.ac.jp/smlsharp/ja/?Foundations%2F010#f02 を参考にしました。)

ランク2

しかし、ランク2で同様のことをやろうとするとこの方法は破綻します。
ランク2とは、要するに、ランク1の多相の関数を引数とするもの、と考えることができます。

// イメージ。C++ではない。
template < class T, class U >
string concat(const T& t, const U& u, template <class V> string (*to_string)(const V& v))
{
  return to_string(t) + to_string(u);
}

C++では、(少々ぎこちないですが)次のように書けます。

template < template < class V > class ToString, class T, class U >
std::string concat(const T& t, const U& u)
{
  return ToString<T>()(t) + ToString<U>()(u);
}

template < class T >
struct MyToString;

template <>
struct MyToString<int>
{
  std::string operator()(int t)
  {
    std::stringstream ss;
    ss << t;
    return ss.str();
  }
};

template <>
struct MyToString<char>
{
  std::string operator()(char t)
  {
    std::stringstream ss;
    ss << t;
    return ss.str();
  }
};

std::string x(concat<MyToString>(1, 'a')); // "1a"

関数テンプレートconcatの引数ToStringが多相になっています。
ToStringに、多相的な実装MyToStringを渡しています。

concatでは、渡された多相的な実装をToString<T>とToString<U>のように
インスタンス化して使用します。
この場合、先程のようにconcatを分割コンパイルするためには、
ToString<T>とToString<U>を渡してもらうように変換することになります。

std::string concat(const T& t, const U& u,
  std::string (*to_string_for_T)(const T&),
  std::string (*to_string_for_U)(const U&))
{
  return to_string_for_T(t) + to_string_for_U(u);
}

あるいは、

std::string concat(const T& t, const U& u,
  std::string (*to_string_impl)(const void*))
{
  return to_string_impl[0](&t) + to_string_impl[1](&u);
}

しかし、実際には、この変換は、示された関数の型だけからは実行不可能です。
なぜなら、to_stringが実際にどのように使用されるか(どの型でインスタンス化されるか)が
示されたconcatの型からはわからないからです。
たとえば、次のように実装を変更すると、

template < template < class V > class ToString, class T, class U >
std::string concat(const T& t, const U& u)
{
  return ToString<T>()(t) + ToString<std::string>()(" and ") + ToString<U>()(u);
}

ToStringは、std::stringに対しても実装を提供しなければなりません。
変換後の形では、もらう関数ポインタが1つ増えることになります。
つまり、分割コンパイルした実装を変更すると、
結局それをリンクする側も再コンパイルが必要になります。

この方向で実際に実装する場合、次のような選択肢から選ぶことになると思います。

  • concatの引数to_stringがどのような型Vで使用されるのか、Vについてありうる型を明示し、
    concatの型情報の一部とする
    • Vが実際にはTまたはUであることを明示する
      (stringとしても使用しようとすると、VはTまたはUまたはstringということになり
      concatの型がかわることになる)   
    • Vに制約(型クラス)をつける
      (この場合列多相ではなくなる)
    • この形で出てきたVは、TかUだと決めてしまう。
      (この場合、ToString<std::string>()(" and ")のようなインスタンス化はエラーとすることになる)
  • 分割コンパイルをあきらめる
    • コンパイルにより型が変わってしまった場合リンクに失敗させ再コンパイルを促す
    • 実行時に型が一致しない場合、再リンクする
      (静的な型チェックはできなくなる)

いいかえると、adhocな多相の場合、結局ランク1に縮退すれば実装できるということになります。

これは、parametricな多相の場合は問題にはなりません。
parametricな多相の場合、インスタンス化される型に依存しないため、
型の情報がなくてもコンパイルできます。
また、動的な言語では、実行時に実装を探せばよいので(実行時エラーにはなるかもしれませんが)
問題にはなりません。

ランク3

ランク3は、ランク2の多相の関数を引数とするもの、と考えることができます。

// イメージ。C++ではない。
template < class T, class U >
string apply_concat(const T& t, const U& u, 
  template <class V, class W> string (*concat)(const V&, const W&, template <class U> string (*)(const U&)))
{
  return concat(t, u, to_string);
}

ランク3も基本的にはランク2と問題は同じです。

基本的には、引数concatをapply_concatがどのような型V,Wでインスタンス化して使うのか、がわかれば、
それに対応した実装を外から注入することができます(ランク2)。
しかし、同時に、concatに渡すための、template <class U> string (*)(const U&) の実装も
外から注入する必要があります(ランク3)。
これは、concatがこの渡された実装をどのような型Uでインスタンス化して使うのかがわかれば、
apply_concatがどのような型でそれを使うかがわかり、外から渡せます(ランク2)。

結局、V, W, Uが実際にはどのような型であるかが明示されれば、ランク1に縮退し、
ランク1の範囲で実装できることになります。

広告
%d人のブロガーが「いいね」をつけました。