ラムダ計算と無限ラムダ多項式(18) - エレファント・ビジュアライザー調査記録

たらい回し関数の調査

たらい回し関数は変数を使わない例には使えそうにないですが、調査を継続します。「wikipedia:竹内関数」に書かれている高速化をやってみます。C# で書いた以下のプログラムについて考えます。

        public static string Test()
        {
            int count = 0;
            int tarai(int x, int y, int z)
            {
                count++;
                if (x <= y)
                {
                    return y;
                }
                else
                {
                    return tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y));
                }
            }
            return $"{tarai(12, 6, 0)}, count = {count}";
        }

普通に $\mathrm{tarai}(12, 6, 0)$ を実行すると結果は以下のようになります。

12, count = 12604861

呼ばれている回数は 12604861 回となります。

遅延評価

$x \le y$ のときは $z$ を計算する必要はないので、 $z$ をクロージャー化すると呼び出し回数を減らすことができます。

        public static string Test()
        {
            int count = 0;
            int tarai(int x, int y, Func<int> zf)
            {
                count++;
                if (x <= y)
                {
                    return y;
                }
                else
                {
                    return tarai(tarai(x - 1, y, zf), tarai(y - 1, zf(), () => x), () => tarai(zf() - 1, x, () => y));
                }
            }
            return $"{tarai(12, 6, () => 0)}, count = {count}";
        }

結果

12, count = 109

呼び出し回数は 109 回になりました。

メモ化

Dictionary に $(x, y, z)$ の組を保存し、同じ組に対しては一度しか計算をしないようにします。

        public static string Test()
        {
            Dictionary<(int, int, int), int> dic = new Dictionary<(int, int, int), int>();
            int count = 0;
            int tarai(int x, int y, int z)
            {
                count++;
                if (x <= y)
                {
                    return y;
                }
                else
                {
                    if (dic.ContainsKey((x, y, z)))
                    {
                        return dic[(x, y, z)];
                    }
                    else
                    {
                        int val = tarai(tarai(x - 1, y, z), tarai(y - 1, z, x), tarai(z - 1, x, y));
                        dic[(x, y, z)] = val;
                        return val;
                    }
                }
            }
            return $"{tarai(12, 6, 0)}, count = {count}";
        }