たらいまわし

「たらいまわし関数」というものを知っているだろうか。私は「C言語による最新アルゴリズム辞典」で初めて知った。(もう10年以上も前の話だ。)解説文の中に「特に用途は無い」と書かれているのが気にかかっていた。調べてみると原形は竹内関数というもので、その名が示すとおりに竹内氏が考案したものらしい。しかし、McCarthy氏が誤った形をアメリカで広めてしまい、それと区別するために「たらいまわし関数」と呼ぶようになったという経緯だとのこと。竹内氏はLisp界では名の知れた人でその著書「初めての人のためのLISP」はLisp入門書としては好評なようだ。
で、たらいまわし関数の入出力の関係にはたしかに何の意味もない。意味があるのはその計算量だ。シンプルな定義でありながら、計算量が爆発的に増える。それを利用してベンチマークテストに用いられたりすることもある。もうひとつ、遅延評価の例としてもよく使われる。実際に遅延評価でどの程度の差が出るのか試してみよう。
たらいまわし関数を素直にCで書くと以下のようになる。

/* tarai.c  TARAI-function */
#include <stdio.h>

int tarai(int x, int y, int z)
{
  if (x <= y) return y;
  return tarai(tarai(x - 1, y, z),
	       tarai(y - 1, z, x),
	       tarai(z - 1, x, y));
}

int main(void) {
  printf("%d\n", tarai(192, 96, 0));
  return 0;
}

遅延評価を導入してみよう。Cで書くのは面倒なのでこちらはC++で書くことにする。

/* tarai.cpp  TARAI-function (lazy-version) */
#include <iostream>
using namespace std;

class tarai {
  const int x, y;
  const tarai* tp;
public:
  tarai(int y)
    : x(y), y(y), tp(NULL) {}

  tarai(int x, int y, const tarai& t)
    : x(x), y(y), tp(&t) {}

  operator int() const {
    return (x <= y) ? y :
      (int) tarai(tarai(x-1,y,*tp),
		  tarai(y-1,*tp,x),
		  tarai(*tp-1,x,y));
  }
};

int main(void) {
  cout << tarai(192, 96, 0);
  return 0;
}

さて、いったいどれくらいの速度差が出るだろうか？手元にC/C++のコンパイラがある人は是非試してみて欲しい。
因みに、計算量が爆発する類似の関数にAckermann関数というのもあるが、これは遅延しても意味がない。

初めての人のためのLISP (ソフトウェアライブラリ (3))

C言語による最新アルゴリズム事典 (ソフトウェアテクノロジー)