コンピュータは「掛け算は足し算とする」を理解できるか - 檜山正幸のキマイラ飼育記 (はてなBlog)

「お手軽で実用的なジェネリックスへの道は遠い」で演算子オーバーロードの話をしました。演算子オーバーロードが欲しかったひとつの理由は、トロピカル代数の計算をコンピュータで出来ないかな、と思ったことです。例えば、トロピカル代数*1のひとつであるmin-plus半環では、次のような計算になります。

1 + 1 = 1
2 + 3 = 2
2 * 3 = 5
2 * 0 = 2
3 + ∞ = 3
3 * ∞ = ∞

こんな計算を、そのまんま（関数呼び出しとかにしないで）書けたらいいな、ということです。C++11でやってみます。

min-plus半環

min-plus半環については、（max-plus半環と共に）次の記事で紹介しています。

零の概念とmax-plus半環の紹介

その応用例のひとつは：

プログラムの実行時間を計る事と半環の代数

min-plus半環での計算は、普通の計算とは違います。その対応をまとめておきます。

min-plus半環における役割	実際には
足し算	min（小さい方）
掛け算	足し算
零	∞
一	0

min-plus半環も半環（足し算と掛け算が出来る）ので、行列計算とかは、普通の数とまったく同じく定義できます。完全なジェネリックスのもとでは、普通の行列計算ライブラリがmin-plus係数でも使えるはずです。まー、「はず」なだけだけど。

min-plus係数の行列計算により、（一般化）距離空間の実験や確認とかもできちゃうはず（「はず」なだけ）。

順序集合や距離空間も実はモノイドだった

行列計算はともかくとして、min-plus半環そのものを定義します。

C++11でうまくいく

結果を先に言うと、C++11でほぼ期待どおりになります。

// tropical.cpp

//
// ... 途中省略 ...
//

/*
 * デモ
 */

// 略記用
MinPlus operator"" _mp(long double x) {
  MinPlus t = x;
  return t;
}

// 略記用
MinPlus operator"" _mp(unsigned long long int x) {
  MinPlus t = x;
  return t;
}

// 略記用
MinPlus const inf = MinPlus::Infinity;

// 計算してみる
int main()
{

  // 1 + 1 = 1
  std::cout << "1 + 1 = "
	    << 1_mp + 1 << std::endl;
  // 2 + 3 = 2
  std::cout << "2 + 3 = "
    	    << 2 + 3_mp << std::endl;
  // 2 * 3 = 5
  std::cout << "2 * 3 = "
    	    << 2 * 3_mp << std::endl;
  // 2 * 0 = 2
  std::cout << "2 * 0 = "
    	    << 2 * 0_mp << std::endl;
  // 3 + ∞ = 3
  std::cout << "3 + ∞ = "
    	    << 3 + inf << std::endl;
  // 3 * ∞ = ∞
  std::cout << "3 * ∞ = "
    	    << 3 * inf << std::endl;
  return 0;
}

コンパイル＆実行。



$ g++ tropical.cpp
$ ./a.exe

1 + 1 = 1

2 + 3 = 2

2 * 3 = 5

2 * 0 = 2

3 + ∞ = 3

3 * ∞ = ∞
$

ソースコード内で 1 + 1 と書けば、さすがにこれは2になります。数値をmin-plus半環の要素だと思って書いても、コンパイラは心のなかまでは察してくれません。「これはmin-plus半環の要素だよ」と示すために、C++のユーザー定義リテラルというものを使ってみました。1_mp のように_mp接尾辞を付けるとmin-plusな要素と解釈します。

使ってはみたけど、ユーザー定義リテラルってあんまり便利じゃないですね。mp(1) のように普通の関数で書いても同じ、つーか、普通の関数のほうが簡単。

それはともかく；二項演算の場合、どっちか片方の項に_mpを付ければ、もう一方は型変換してmin-plus要素に揃えてくれるようです。式のなかで、1つでもmin-plus要素だと明示すれば、他は普通の数値で書いても大丈夫。(1_mp + 3 + inf) * 5 + 3 * 2 とかも期待どおりに計算してくれます。C++11の構文解析と型変換はよくできてますね、関心しました。

でも、対話的インタプリタではないので、式を手で入力してその場で試すことが出来ないのですよね。実験用には、これは痛い。世の中、なかなかうまくいかんもんだわ。

この下にソースコード。

// tropical.cpp

#include <stdexcept>
#include <iostream>

class MinPlus {
  double _val;
  static const double _internal_infinity;
  static double _min(double x, double y);
  static double _sum(double x, double y);

public:
  static const MinPlus Infinity;
  static const MinPlus Zero;
  static const MinPlus One;

  MinPlus(double x);
  MinPlus();

  bool is_infnity() const {return _val == _internal_infinity;}
  double val() const {return _val;}
  void val(double x);
  MinPlus& operator +=(MinPlus m);
  MinPlus& operator *=(MinPlus m);

};

/* 
 * 定数の定義 
 */
const double MinPlus::_internal_infinity = -1;
const MinPlus MinPlus::Infinity = MinPlus::_internal_infinity;

// MinPlusの零とは無限大のこと
const MinPlus MinPlus::Zero = MinPlus::Infinity;
// MinPlusの一とは0のこと
const MinPlus MinPlus::One = 0;

/*
 * 内部使用の関数
 */

// 無限大を考慮したmin
double MinPlus::_min(double x, double y) {
  if (x == _internal_infinity) return y;
  if (y == _internal_infinity) return x;
  if (x <= y) return x;
  return y;
}

// 無限大を考慮した和
double MinPlus::_sum(double x, double y) {
  if (x == _internal_infinity) return _internal_infinity;
  if (y == _internal_infinity) return _internal_infinity;
  return x + y;
}

/*
 * 公開する関数
 */

// 値の設定
void MinPlus::val(double x) {
  if (x == _internal_infinity || x >= 0) {
    _val = x;
  } else {
    throw std::out_of_range("Invalid MinPlus value");
  }
}

// コンストラクタ
MinPlus::MinPlus(double x) {
  val(x);
}

// デフォルトコンストラクタ
MinPlus::MinPlus() {
  _val = _internal_infinity;
}

// 足し算して代入： 足し算は小さいほう
MinPlus& MinPlus::operator +=(MinPlus m) {
  double min = _min(_val, m._val) ;
  _val = min;
  return *this;
}

// 掛け算して代入： 掛け算は足し算
MinPlus& MinPlus::operator *=(MinPlus m) {
  double sum = _sum(_val, m._val) ;
  _val = sum;
  return *this;
}

// 値の足し算
MinPlus operator+(MinPlus m, MinPlus n) {
  MinPlus t = m;
  return t += n;
}

// 値の掛け算
MinPlus operator*(MinPlus m, MinPlus n) {
  MinPlus t = m;
  return t *= n;
}

// 書き出し
std::ostream& operator<<(std::ostream &out, MinPlus m) {
  if (m.is_infnity()) {
    return out << "∞";
  } else {
    return out << m.val();
  }
}

/*
 * デモ
 */

// 略記用
MinPlus operator"" _mp(long double x) {
  MinPlus t = x;
  return t;
}

// 略記用
MinPlus operator"" _mp(unsigned long long int x) {
  MinPlus t = x;
  return t;
}

// 略記用
MinPlus const inf = MinPlus::Infinity;

// 計算してみる
int main()
{
  std::cout << (1_mp + 3 + inf) * 5 + 3 * 2<< std::endl;
  // 1 + 1 = 1
  std::cout << "1 + 1 = "
	    << 1_mp + 1 << std::endl;
  // 2 + 3 = 2
  std::cout << "2 + 3 = "
    	    << 2 + 3_mp << std::endl;
  // 2 * 3 = 5
  std::cout << "2 * 3 = "
    	    << 2 * 3_mp << std::endl;
  // 2 * 0 = 2
  std::cout << "2 * 0 = "
    	    << 2 * 0_mp << std::endl;
  // 3 + ∞ = 3
  std::cout << "3 + ∞ = "
    	    << 3 + inf << std::endl;
  // 3 * ∞ = ∞
  std::cout << "3 * ∞ = "
    	    << 3 * inf << std::endl;
  return 0;
}

*1:広義のトロピカル代数＝エキゾチック代数のことです。