ふぃっしゅ数で始める継続渡しスタイル(CPS) Part1

「ふぃっしゅ数」とは

近年にわかに注目を集めつつある、「巨大数論」と呼ばれる数学の分野で、ふぃっしゅっしゅ氏が考案した巨大数です。
巨大数wikiによれば、2021/01/21現在、バージョン7まで考案されています。
この記事ではバージョン1を扱いますが、巨大数wikiによれば、定義は以下の通りです。

---

[1] $S$変換と呼ばれる変換を以下で定義する。

S(m, f(x)) = (g(m), g(x))

ただし$g(x)$は以下で与えられる。

\displaylines{
B(0, n) = f(n)\\
B(m + 1, 0) = B(m, 1)\\
B(m + 1, n + 1) = B(m, B(m + 1, n))\\
g(x) = B(x, x)
}

[2] $SS$変換と呼ばれる、(自然数, 関数, 変換) の3つ組から同様の3つ組への写像$SS$を以下で定義する。

SS(m, f, S) = (S^{f(m)}(m, f), S^{f(m)})

ここで右辺は((自然数, 関数), 変換)の形をしているが、これを(自然数, 関数, 変換)の3つ組と同一視する。

[3] 3つ組$(m_0, f_0, S_0)$を$m_0 = 3$、$f_0(x) = x + 1$、$S_0$は$S$変換とするとき、

SS^{63}(m_0, f_0, S_0)

の第1成分をふぃっしゅ数バージョン1、第2成分をふぃっしゅ関数バージョン1と定義する。

---

..........。


何を言っているか、分かりますかね？


見慣れない方が多いと思われるのは、"$SS^{63}$" などの変換の右上に数が載っている表記くらいでしょうか。
これは、$SS$変換を右上に乗っている数だけ繰り返すという意味になります。

つまり、たとえば"$SS^3(m, f, S)$"という表記であれば、以下の演算を意味します。

SS(SS(SS(m, f, S)))

さて、数式の意味がぼんやり見えてきたかと思いますが、そんなに難しいことをやっている数式には見えないんじゃないでしょうか？
ですが、実際に$B$関数に入れる数を増やしながら計算してみると、計算回数が爆発的に増えていくことが分かります。
どのように増えていくかは、$B$関数によく似た関数である、アッカーマン関数のwikipediaページをご参照ください。

実装してみる

ふぃっしゅ数バージョン1の計算ロジックが分かったところで、これをプログラムしていきます。
今回は僕の得意言語であるJavaで実装していきます。

import java.math.BigInteger;
import java.util.function.UnaryOperator;

public class FishNumberV1 {

    public static void main(String[] args) {
        BigInteger result = calculate();
        System.out.println(result);
    }

    private static BigInteger calculate() {

        Trio trio = new Trio(BigInteger.valueOf(3), x -> x.add(BigInteger.ONE), FishNumberV1Orig::S);
        for (int i = 0; i < 63; i++) {
            trio = SS(trio);
        }
        return trio.getM();
    }

    private static Pair S(Pair pair) {

        BigInteger m = pair.getM();
        UnaryOperator<BigInteger> f = pair.getF();

        UnaryOperator<BigInteger> g = x -> B(x, x, f);
        return new Pair(g.apply(m), g);
    }

    private static BigInteger B(BigInteger m, BigInteger n, UnaryOperator<BigInteger> f) {

        if (m.equals(BigInteger.ZERO)) {
            return f.apply(n);
        } else if (n.equals(BigInteger.ZERO)) {
            return B(m.subtract(BigInteger.ONE), BigInteger.ONE, f);
        }

        return B(m.subtract(BigInteger.ONE), B(m, n.subtract(BigInteger.ONE), f), f);
    }

    private static Trio SS(Trio trio) {
        UnaryOperator<Pair> repeatS = p -> repeatS(p, trio.getS());
        return new Trio(repeatS.apply(trio), repeatS);
    }

    private static Pair repeatS(Pair pair, UnaryOperator<Pair> s) {
        BigInteger m = pair.getM();
        UnaryOperator<BigInteger> f = pair.getF();
        BigInteger times = f.apply(m);

        for (BigInteger i = BigInteger.ZERO; i.compareTo(times) < 0; i = i.add(BigInteger.ONE)) {
            pair = s.apply(pair);
        }
        return pair;
    }

    private static class Pair {

        private final BigInteger m;
        private final UnaryOperator<BigInteger> f;

        private Pair(BigInteger m, UnaryOperator<BigInteger> f) {
            this.m = m;
            this.f = f;
        }

        protected BigInteger getM() {
            return m;
        }

        protected UnaryOperator<BigInteger> getF() {
            return f;
        }
    }

    private static class Trio extends Pair {

        private final UnaryOperator<Pair> s;

        private Trio(BigInteger m, UnaryOperator<BigInteger> f, UnaryOperator<Pair> s) {
            super(m, f);
            this.s = s;
        }

        private Trio(Pair pair, UnaryOperator<Pair> s) {
            this(pair.getM(), pair.getF(), s);
        }

        private UnaryOperator<Pair> getS() {
            return s;
        }
    }
}

これで、実装できたので、mainメソッドを実行してみます。

Exception in thread "main" java.lang.StackOverflowError
	at main.FishNumberV1.B(FishNumberV1.java:48)
	at main.FishNumberV1.B(FishNumberV1.java:51)
	at main.FishNumberV1.B(FishNumberV1.java:51)
	at main.FishNumberV1.B(FishNumberV1.java:51)
	at main.FishNumberV1.B(FishNumberV1.java:51)
	.
	.
	.
	(以降、数十行同じメッセージが続く)

Process finished with exit code 1

StackOverFlowErrorで落ちてしまいました...。
$B$関数に相当するメソッドが再帰を際限なく繰り返すために、スタックが深くなりすぎて、上限を超えてしまったようです...。
この再帰地獄、どうすれば抜けることができるのか!？

末尾呼び出し と 末尾再帰

そのカギを探るため、ここからは末尾呼び出しと末尾再帰について、見ていきましょう。

「末尾呼び出し」とは

ある関数fが、別の関数gを呼び出すとします。gの呼び出しがfのリターン前の最後の処理であるとき、gの関数呼び出しを 末尾呼び出し（tail call） と呼びます。

これが何を意味しているか、以下のコードをご覧ください。

function f() {
    if (b()) { // b()は末尾呼び出しではない
        return g(); // g()は末尾呼び出し
    } else {
        return h() + i(); // i()は末尾呼び出しではない。当然ながらh()も末尾呼び出しではない。
    }
}

上記ソースにおいては、以下のようになります。

• if分の条件で呼び出しているb()は、リターン前の最後の処理ではないため、末尾呼び出しではありません。
• g()はリターン前の最後の処理なので、末尾呼び出しです。
• h()はもちろん、i()もコード上は最後にありますが、後続に+の加算処理があるので、末尾呼び出しではありません。←ここ、テストに出るので間違えないように! (出ねえよ)

「再帰関数」とは

念の為説明しておくと、ある関数の中で、自分自身を呼び出している関数を 再帰関数（recursive function） と呼びます。
上記のふぃっしゅ数バージョン1の実装例では、B関数が再帰関数に当たります。

「末尾再帰」とは

再帰関数のうち、自分自身の呼び出しが末尾呼び出しになっているものを、 末尾再帰（tail recursive） と呼びます。
上記のふぃっしゅ数バージョン1の実装例では、B関数が末尾再帰に当たります。

---

さて、ここまでなぜ「末尾呼び出し」やら「末尾再帰」の紹介をしてきたかと言うと、 「末尾再帰最適化」 と呼ばれるコード最適化の恩恵を受けることができるからです！ (言語仕様による ←これ大事)

そもそも「スタックオーバーフロー」とは

ここで、ここまで末尾呼び出しやら再帰関数やらを見てきたきっかけとなった、スタックオーバーフローについて見ていきます。
プログラムが実行される際には、メモリの上限というものが存在します。
このメモリ領域が関数を呼び出す毎に消費されていき、上限に達した際に、「メモリが足りなくて、これ以上プログラムを実行できないよ」と白旗を上げることを、スタックオーバーフローと呼びます。

末尾呼び出し最適化 と 末尾再帰最適化

そんな関数を呼び出せば呼び出すほど消費されていくメモリ領域ですが、末尾呼び出しの形で実装すると、メモリが消費されることなくプログラムが実行される仕組みがあります。

これが 「末尾呼び出し最適化」 と言われる技術です。

「末尾呼び出し最適化」とは

先程のコード例をここでもう一度見てみましょう。

function f() {
    if (b()) { // <- (B)
        return g(); //  <- (C)
    } else {
        return h() + i();
    }
}

f();  // <-(A)

ここで、関数呼び出し毎に、以下のようにメモリに呼び出し情報が積まれていくとイメージしてみてください。(位置A)
returnTo は関数の終了時の戻り先を表しています。

呼び出し情報
f:returnTo:(A)

位置Bにおいては、以下のようになります。

呼び出し情報
b:returnTo:(B)
f:returnTo:(A)

一方、位置Cにおいては、以下のようになります。

呼び出し情報
g:returnTo:(C)
f:returnTo:(A)

この時、f()の結果はg()の結果そのものなので、f()の呼び出し情報をメモリに残しておく必要はありません。
そのため、g()の呼び出し時にメモリ領域を新たに生成するのではなく、f()の呼び出し情報をg()の呼び出し情報に再利用することができます。
これを 末尾呼び出しの除去（tail call elimination） と呼び、コンパイラや実行環境が行う末尾呼び出しの除去を 末尾呼び出し最適化（tail call optimization） と呼びます。

位置Cにおいて、末尾呼び出しの除去が行われると、メモリに積まれる呼び出し情報は以下のようになります。

呼び出し情報
g:returnTo:(A)

「末尾再帰最適化」とは

先程も紹介したように、「末尾再帰」とは再帰関数のうち、自分自身の呼び出しが末尾呼び出しになっているものです。
したがって、末尾呼び出し最適化の仕組みを持つ言語においては、末尾再帰の形で再帰関数を実装すれば、メモリを消費することなく実行することができるので、スタックオーバーフローが起きません！！
素晴らしい！！

この、末尾再帰の関数で行われる末尾呼び出しの最適化を 末尾再帰最適化 と呼びます。

どのように実装する？

ここまで、スタックオーバーフローが発生するような再帰地獄から抜け出すためのカギを探るための前提知識を長々と説明してきました。
ここまで読んで、「じゃあ、ふぃっしゅ数のめっちゃ再帰する関数を末尾再帰で実装すればええやん！」と思ったあなた！ m9(・Д・)
この記事では Java で実装しているのですが、何と、Javaでは末尾再帰最適化に対応していません！

「何...だと...?」
と絶望しかけた、そこのあなた！ m9(・Д・)
末尾再帰最適化を実現する方法は他にもあります！
では、ここからは待ちに待った、その実現方法をご紹介します！！！

...

と、言いたいところですが、前提知識の紹介だけですごく長くなってしまったので、実現方法の紹介は 「ふぃっしゅ数で始める継続渡しスタイル(CPS) Part2」 でさせていただきます。
この記事を最後まで読んでいただいた方は、次号の執筆までお待ち下さい。m(_ _)m

次回予告

立ち塞がるスタックオーバーフロー。
末尾再帰最適化ができず嘆くJavaプログラマの前に、救いの手を差し伸べるCPS(継続渡しスタイル)。
ふぃっしゅ数を求めたいと願う人類の挑戦は、果たしてどこへ向かうのか...?

次回、「ふぃっしゅ数で始める継続渡しスタイル(CPS) Part2」

さぁて、この次も、サービスサービスぅ！

©evangelion

参考

• ふぃっしゅ数バージョン1
• 末尾再帰による最適化
• 末尾再帰最適化について