竹内関数（たけうちかんすう）は、プログラミング言語処理系のベンチマークなどに使われる、再帰的に定義された関数である。
電電公社研究員（当時）の竹内郁雄が、1974年の夏前の頃、このような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである。竹内関数と命名したのは野崎昭弘である。
与える数によって関数の再帰呼び出しの回数が非常に増え、計算量が大きくなるため、コンピュータの性能測定などに用いられる。
⇧ 皆様、ご存知、竹内郁雄 氏によって生み出された関数ですね！私は、勉強不足につき初めて知りましたけどね！あ、どうもボクです。
というわけで、関数について、レッツトライ～。
竹内関数って？ Takeuchi function とも呼ばれてるらしい
冒頭のWikipediaさんの説明であったように、「竹内郁雄」氏によって作り出された関数ですね。
⇧ こちらのダンディーなお方が、ご本人様のようです。
再帰的に定義される、3個の引数 x, y, z をとる次のような関数である。
定義からわかるように処理を次々にたらい回しにしていくことから、たらいまわし関数、たらい関数 (Tarai function) とも呼ばれる（後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある）。
⇧ この式については、
ところがうまくしたもので、これはどんな整数 x, y, z を与えても、値が x または y または z になるのである。しかし、コンピュータにこの定義を与えると、恐ろしく時間がかかる。例えば、n を正の整数とすると
tarai(2n, n, 0)
は、ざくっと言って n の n 乗（nn）に比例した時間がかかる。例えば、n = 10 とすると n = 2 の場合の25億倍の時間がかかる！ これだけの時間をかけて答えは 2n である。定義をチラリと眺めれば分かるように、大小比較で枝分かれするほかには、1を引く引き算と関数呼び出ししかしていないが、x, y, z の位置がクルクル回っている。これが tarai、つまりタライ回し関数と当初名付けた理由である。
という仕組みのようです。
不動点コンビネータって何ぞ？
何と言うか、
⇧ 上記サイト様の記事で、「竹内関数」なるものの存在を知ったわけですが、その中で、「不動点コンビネータ」なるものも出てきまして、記事を拝見させていただいたのですが...わ、分からん！
すごい、ザックリ言うと、
この辺は全然詳しくないんですがラムダ計算で再帰を行うことが出来るアレっぽいです。
⇧ ということみたいです。
Wikipediaさんによりますと、
不動点コンビネータ（ふどうてんコンビネータ、英: fixed point combinator、不動点結合子、ふどうてんけつごうし）とは、与えられた関数の不動点（のひとつ）を求める高階関数である。不動点演算子（ふどうてんえんざんし、英: fixed-point operator）、パラドキシカル結合子（英: paradoxical combinator）などとも呼ばれる。ここで関数fの不動点とは、f(x) = xを満たすようなxのことをいう。
と説明があり、
- 任意の関数f に対し、p = g(f)とすると, f(p) = p が成立する
事を指す。
が成立する事であるとも言い換えられる。
と説明が続き、
第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子に束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。
⇧ な、何と！ラムダへ繋がるという！
型無しラムダ計算（英: untyped lambda calculus）においては、ハスケル・カリーのY = λf·(λx·f (x x)) (λx·f (x x))という不動点コンビネータがよく知られている。
型無しラムダ計算には無数の不動点コンビネータが存在するが、一方で単純型付きラムダ計算などのより限定的な計算モデルでは、不動点コンビネータは必ずしも存在するとは限らない。
⇧ 「カリー化」の名前の由来になった人、「ハスケル・カリー」さん。
「Yコンビネータ」「Zコンビネータ」とかもWikipediaさんで説明が出てきますね。
竹内関数、またの名を、Takeuchi function をJavaで実装してみる
というわけで、
⇧ 上記サイト様のソースコードを写経させていただきました。
Eclipse を起動し、適当なJavaプロジェクトを作成し、クラスも作成で。
ソースコードはこんな感じで。
package main;
import java.util.function.Function;
import java.util.function.Supplier;
public class TestTakeuchiFunction {
interface TriFunction<X, Y, Z, R> {
R apply(X x, Y y, Z z);
}
interface Tarai extends TriFunction<Integer, Integer, Supplier<Integer>, Integer> {
}
interface Dak extends Function<Dak, Tarai> {
}
static Tarai fpComb(Function<Tarai, Tarai> f) {
Function<Dak, Tarai> func = d -> f.apply((x, y, z) -> d.apply(d).apply(x, y, z));
Dak dak = d -> f.apply((x, y, z) -> d.apply(d).apply(x, y, z));
return func.apply(dak);
}
public static void tarai() {
// 竹内関数を定義
Function<Tarai, Tarai> function = tarai -> (x, y, z) -> x <= y ? y : tarai.apply(
tarai.apply(x - 1, y, z),
tarai.apply(y - 1, z.get(), () -> x),
() -> tarai.apply(z.get() - 1, x, () -> y));
// 竹内関数を生成
Tarai tarai = fpComb(function);
// 竹内関数を実施した結果を出力
System.out.println(tarai.apply(20, 10, () -> 5));
}
public static void main(String[] args) {
// TODO 自動生成されたメソッド・スタブ
tarai();
}
}
んで、実行してみたけど、
よく分からん...
というか、
ジョン・マッカーシーは竹内関数を記憶違いで z を返すように変更し、これがTak関数として広まった。以下がその定義である。
計算量はずっと少ない（たとえば tarai(12, 6, 0) では 12,604,860 回 tarai が呼ばれるのに対し、 tak(12, 6, 0) では tak は 63,608 回しか呼ばれない）。
みたいな感じで、関数が何回呼ばれたかの確認をしたかったのだが...
テストクラスとか作って、JUnitとかで試せばメソッド実行回数とかチェックできるんですかね？
時間ある時に、ソースコードの意味を読み解かねばですかね...やっぱり関数型インターフェイスに慣れる気がしないと思う今日この頃であった。
今回はこのへんで。
