巨大数でわかる Elixir の魅力

このエントリーは Akatsuki Advent Calendar 2022 の13日目の記事です。

昨日は jyllsarta さんの「自作ゲームのコードで見る、ChatGPTのテストケース生成」でした。

ChatGPT にソフトウェアテストの観点出しをさせるアイデア、実用的で面白いですね。出力を完全には信頼せずに利点はしっかり引き出すうまい付き合い方だと思います。人も AI も、付き合いは距離感が大事🎅

はじめに

Elixir とは、大雑把にいうと Web アプリケーションバックエンドの実装にうってつけな特徴を備える関数型プログラミング言語です。本エントリでは言語そのものの詳しい説明は省きますが、ちょっとした数学の問題を解くことでその魅力をお伝えできたらと思います。

題材は「ふぃっしゅ数」です。いわゆる巨大数のひとつで、ふぃっしゅっしゅさんがグラハム数を超えるべく考案しました。この数を求めるプログラムを Elixir で書いてみましょう。

巨大数とは？

詳しい説明は省略しますが、雑に表現するとめちゃくちゃでかい数です。天文学的と言っても到底足りないくらいでっかく、例えば「観測可能な全宇宙に存在する陽子の数」とされるエディントン数 $N_{Edd} = 136 \times 2^{256}$ がかわいく思えてくるほどにでかい数が巨大数論ではドカドカ展開されます。エンジニアにとって馴染深い例えを出すなら、SHA-256で生成できるハッシュの総数は $2^{256}$ です。エディントン数にけっこう近いですが、超えられてはいませんね。かわいいもんだぜ。

ふぃっしゅ数バージョン１

ふぃっしゅ数も巨大数のひとつ。しかもただデカさだけを追い求め、デカいということ以外に意味のない純粋な巨大数です。それではふぃっしゅ数バージョン１について概要に触れましょう。ふぃっしゅっしゅさんの著作から巨大数の考え方について一部引用しますと、

「いかにして大きな数を作るか」というプロセスを一般化すると、大きな数と増加の程度が大きい関数を生み出していくプロセスだと表現できる。

(「巨大数論 第2版」 p.89 より引用)

とのこと。この考え方を元に定義された最初のふぃっしゅ数がふぃっしゅ数バージョン1です。
おもしろいね。
そしてふぃっしゅ数は、2022年現在だと2013年に考案されたバージョン7まであります。
おそろしいね。

それでは定義をみていきます。

定義

１. 自然数と関数のペアから自然数と関数のペアへの写像 $S（S変換）$ を以下で定義する。

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

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

\begin{align}
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)
\end{align}

２. 自然数、関数、変換の組から同様の組を生み出す写像 $SS（SS変換）$ を以下で定義する。

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

　　ここで右辺は $((自然数, 関数), 変換)$ の形をしているが、これを $(自然数, 関数, 変換)$ の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と定義する。

う〜んちょっと難しいですね。めちゃくちゃフワッとしたイメージとしては、ひたすら関数の再帰を繰り返して増加の程度を膨らます感じでしょうか。

Elixir の出番

上記の定義をコードにしたのがこちらになります。

defmodule FishNum do
  # S変換
  def s_transfom(m, f) do
    g = &g(&1, f)
    {g.(m), g}
  end

  def b(0, n, f), do: f.(n)
  def b(m, 0, f), do: b(m-1, 1, f)
  def b(m, n, f), do: b(m-1, b(m, n-1, f), f)

  # g(x)関数
  def g(x, f), do: b(x, x, f)

  # SS変換
  def ss_transform(m, f, s) do
    s = &Enum.reduce(1..(&2.(&1)), {&1, &2}, fn _, {m, f} -> s.(m, f) end)
    {m, f} = s.(m, f)
    {m, f, s}
  end

  # 初期値 (3, f(x)=x+1, S変換) で63回SS変換！
  def main(_args) do
    1..63
    |> Enum.reduce({3, &(&1 + 1), &s_transfom/2}, fn _, {m, f, s} -> ss_transform(m, f, s) end)
    |> elem(0)
    |> IO.puts
  end
end

どうでしょうか。数式の難しさの割には意外とスッキリ表現できてるように思いませんか？

$g(x)$ の定義の部分なんかはだいぶ読みやすいですよね。数式による定義とコードでほとんど記述が似ています。 Elixir は関数定義にパターンマッチが使えるので、こういうの書きやすいですね。

また、無名関数のお手軽さも書きやすさに寄与しています。$SS$変換はちょっと読みづらいかもしれませんが、$S$変換なんて$g(x)$をそのままポンと渡しているだけです。だいぶ単純。

$SS$変換だって実はそんなに難しいことしてません。$S$変換を繰り返しているだけです。JSとかでもよく見る関数型的なプログラミングに少しでも触れたことがあるなら、ゆっくり読んでいけば理解できる気がしませんか？

メモリ安全

Elixir(Erlang)は、うまいこと書けば末尾呼び出し最適化によって関数の再帰でメモリをほとんど消費しません。

末尾関数はメモリ消費量を増大させません。なぜなら仮想マシンは、関数が自分自身を末尾（関数内で評価される最後の式）で呼び出していたら、現在のスタックフレームを削除するからです。

（「すごいErlang愉快に学ぼう！」 p.59　より引用）

つまり呼び出し元の情報をスタックに積んだりしないため、どれだけ深い再帰を掘ってもスタックオーバーフローを起こさないのだとか。他の一般的な言語だと、深すぎる再帰はあっという間にスタックオーバーフローで倒れてしまうでしょう。ふぃっしゅ数の算出にはとんでもない深さの再帰が予想されるので、パフォーマンス的にもElixir(Erlang)はうってつけだと言えますね。

とりあえず上記のコードでは$g(x)$関数の定義部分では末尾最適化が働くはずです。再帰で無限に引き回される関数は主にコイツなのでそれ以外は許容していいでしょう。

ビルドと実行

さあ、それではコードが書けましたので、ビルドして実行してみましょう。
果たしてどんな数が出力されるのでしょうか。ワクワクしてきますね！

いざ、実行！

$ mix escript.build
$ ./fish_num

気になる結果は？

（『フカシギの数え方』 おねえさんといっしょ！ みんなで数えてみよう！ より引用）

…いえ25万年は経ってないんですが、いまだに結果は出ていません。でもそれなりに時間の経過した今も、プログラムはメモリ消費を抑えたまま元気にふぃっしゅ数を追う果てしない旅を続けています。メモリ消費あんまりないので実行したままにしてたの忘れてました。

よくよく考えたら、あまり何にも配慮してない（末尾最適化はちょっと意識しましたがそれだけの）てきとうなコードで、何日も延々と計算を続行できるってところがElixir(Erlang)のすごいところですね。

それにしてもいつ終わるんでしょうね…¹。たぶん25万年どころじゃなく宇宙が死んでも終わらないでしょうね…。ふぃっしゅ数は果てしないなあ。それに比べて人間のなんてちっぽけなことでしょう…。

まとめ

• Elixirはパターンマッチや無名関数で難しい数式もシンプルに書ける
• Elixirは末尾最適化を意識できればメモリ効率がかなり良い
• ふぃっしゅ数は呆れるくらいでかい

Elixirの魅力、伝わったでしょうか。

明日の Akatsuki Advent Calendar 2022 14日目は、 yunon_phys さんが「Engineering Managerを廃止して1年経ちました」というテーマで書いてくれるそうです。たのしみ！

1. 　まあマジレスするととっくにint型の桁溢れを起こして実数部はおかしな値になってるでしょうね。そもそもふぃっしゅ数を表現するには地球上のすべての記憶素子集めても足りないはず ↩