竹内関数とか、不動点コンビネータって何ぞ~? からの~、Javaで実装してみる

f:id:ts0818:20190703200027j:plain

竹内関数(たけうちかんすう)は、プログラミング言語処理系ベンチマークなどに使われる、再帰的に定義された関数である。

電電公社研究員(当時)の竹内郁雄が、1974年の夏前の頃、このような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである。竹内関数と命名したのは野崎昭弘である

与える数によって関数の再帰呼び出しの回数が非常に増え、計算量が大きくなるため、コンピュータの性能測定などに用いられる。

竹内関数 - Wikipedia

⇧  皆様、ご存知、竹内郁雄 氏によって生み出された関数ですね!私は、勉強不足につき初めて知りましたけどね!あ、どうもボクです。

というわけで、関数について、レッツトライ~。

 

 

 

竹内関数って? Takeuchi function とも呼ばれてるらしい

 冒頭のWikipediaさんの説明であったように、「竹内郁雄」氏によって作り出された関数ですね。

cybozushiki.cybozu.co.jp

⇧  こちらのダンディーなお方が、ご本人様のようです。

再帰的に定義される、3個の引数 xyz をとる次のような関数である。

定義からわかるように処理を次々にたらい回しにしていくことから、たらいまわし関数たらい関数 (Tarai function) とも呼ばれる(後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある)。

竹内関数 - Wikipedia

⇧  この式については、

 ところがうまくしたもので、これはどんな整数 xyz を与えても、値が x または y または z になるのである。しかし、コンピュータにこの定義を与えると、恐ろしく時間がかかる。例えば、n を正の整数とすると

 tarai(2n, n, 0)

は、ざくっと言って n の n 乗(nn)に比例した時間がかかる。例えば、n = 10 とすると n = 2 の場合の25億倍の時間がかかる! これだけの時間をかけて答えは 2n である。定義をチラリと眺めれば分かるように、大小比較で枝分かれするほかには、1を引く引き算と関数呼び出ししかしていないが、xyz の位置がクルクル回っている。これが tarai、つまりタライ回し関数と当初名付けた理由である。

ハッカーの遺言状──竹内郁雄の徒然苔第18回:問題児も悪くない | サイボウズ式

という仕組みのようです。

 

不動点コンビネータって何ぞ?

何と言うか、

mike-neck.hatenadiary.com

⇧  上記サイト様の記事で、「竹内関数」なるものの存在を知ったわけですが、その中で、「不動点コンビネータ」なるものも出てきまして、記事を拝見させていただいたのですが...わ、分からん!

backpaper0.github.io

nowokay.hatenablog.com

すごい、ザックリ言うと、

この辺は全然詳しくないんですがラムダ計算で再帰を行うことが出来るアレっぽいです。

セミコロンレスJavaでフィボナッチ — 裏紙

⇧  ということみたいです。

Wikipediaさんによりますと、

不動点コンビネータ(ふどうてんコンビネータfixed point combinator不動点結合子、ふどうてんけつごうし)とは、与えられた関数不動点(のひとつ)を求める高階関数である。不動点演算子(ふどうてんえんざんし、fixed-point operator)、パラドキシカル結合子paradoxical combinator)などとも呼ばれる。ここで関数f不動点とは、f(x) = xを満たすようなxのことをいう。

不動点コンビネータ - Wikipedia

と説明があり、

すなわち高階関数g が不動点コンビネータであるとは、

任意の関数f に対し、p = g(f)とすると, f(p) = p が成立する

事を指す。

不動点コンビネータの定義は、任意の関数f に対し、

が成立する事であるとも言い換えられる。

不動点コンビネータ - Wikipedia

と説明が続き、 

第一級関数をサポートしているプログラミング言語では、不動点コンビネータを用いて識別子束縛されない関数の再帰を定義することができる。そういったテクニックは、しばしば無名再帰と呼ばれる。

不動点コンビネータ高階関数であるため、その歴史はラムダ計算の発達と深く関係している。

不動点コンビネータ - Wikipedia

⇧  な、何と!ラムダへ繋がるという!

⇧  「カリー化」の名前の由来になった人、「ハスケル・カリー」さん。

「Yコンビネータ」「Zコンビネータ」とかもWikipediaさんで説明が出てきますね。

 

竹内関数、またの名を、Takeuchi function をJavaで実装してみる

というわけで、

mike-neck.hatenadiary.com

⇧  上記サイト様のソースコードを写経させていただきました。

Eclipse を起動し、適当なJavaプロジェクトを作成し、クラスも作成で。

f:id:ts0818:20190703204937p:plain

ソースコードはこんな感じで。 

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();
  }
}

んで、実行してみたけど、

f:id:ts0818:20190703213650p:plain

f:id:ts0818:20190703213714p:plain

よく分からん...

というか、

 ジョン・マッカーシーは竹内関数を記憶違いで z を返すように変更し、これがTak関数として広まった。以下がその定義である。

計算量はずっと少ない(たとえば tarai(12, 6, 0) では 12,604,860 回 tarai が呼ばれるのに対し、 tak(12, 6, 0) では tak は 63,608 回しか呼ばれない)。

竹内関数 - Wikipedia

みたいな感じで、関数が何回呼ばれたかの確認をしたかったのだが...

テストクラスとか作って、JUnitとかで試せばメソッド実行回数とかチェックできるんですかね?

 

時間ある時に、ソースコードの意味を読み解かねばですかね...やっぱり関数型インターフェイスに慣れる気がしないと思う今日この頃であった。

今回はこのへんで。