この記事は Akatsuki Games Advent Calendar 2023 の20日目の記事です。
昨日はnaoya kohdaさんの「MotionBuilder のスケルトンを強制的にTポーズにさせるスクリプト」でした。
機能自体はシンプルでありつつも需要はなかなか大きそうな便利スクリプトだなと思いました。

はじめに

株式会社アカツキゲームスでサーバエンジニアとして働いている杉山です。
普段の業務では主にAWSやRuby on Railsなどを用いて開発しています。
学生の頃は競技プログラミング打ち込んでいました。
Advent Calendarを書くにあたり、せっかくなら普段触れていないような分野の記事が書きたいなと思いネタを探していたところ、面白そうなプログラミング言語（？）を見つけたので深ぼってみることにしました。

FRACTRANとは

概要

FRACTRANは難解プログラミング言語として分類されるもので、ジョン・コンウェイによって作られたものです。
コンウェイさんといえば巨大数の文脈でたびたび出てくるコンウェイのチェーン表記などでも有名ですね。
難解プログラミング言語という言葉に厳密な定義はありませんが、実用性に乏しく意図的に読解を困難にしたような性質を持つプログラミング言語のことを呼びます。

細かい説明をするよりまずはFRACTRANのコードの例を見てみましょう

\displaylines{
    \biggl( \frac{455}{33}, \; \frac{11}{13}, \; \frac{1}{11}, \; \frac{3}{7}, \; \frac{11}{2}, \; \frac{1}{3} \biggr)
}

ぱっと見コード...ではないですね。この通り、FRACTRANは正の既約分数の列として表すことができます。

このようにして与えられた分数列に対して、以下の操作を行うことで動作します。

入力としてある整数 $n$ を用意します
分数列を左から順に見ていき、$n$ とその分数の積が初めて整数となるような分数を $f$ とします。もしそのような分数が存在しなければ停止します。
$n$ の値を $nf$ に置き換え、2に戻ります

この一連の操作が停止したときの $n$ の値が出力となります。

例として初期値 $n = 72$ のときの操作をいくつか見てみます（なぜ72なのかは後ほど説明します）。

$n$ との積が整数となる最も左の分数は $\frac{11}{2}$ なので、$n = 72 ・ \frac{11}{2} = 396$ に置換される
同様の操作を行う。$n$ との積が整数となる最も左の分数は $\frac{455}{33}$ なので、$n = 396 ・ \frac{455}{33} = 5460$ に置換される

（何回か繰り返す）

同様の操作を行う。$n$ との積が整数となる最も左の分数は $\frac{1}{3}$ なので、$n = 3 ・ 5^6 ・ \frac{1}{3} = 5^6$ に置換される
$n = 5^6$ のとき、$n$ との積が整数となる分数は存在しないため、停止する

初期値が $n=6$ の場合、最終的な出力として $n = 15625 = 5^6$ が得られました。

分数列を用いて何ができるのか

FRACTRANの操作方法がわかったところで、この分数列の意味を考えていきます。
結論からいうと、先ほど例に挙げた分数列は「与えられた2数の積を計算する」という作業を行うことができます。
入力の数は1つしかないじゃないかと疑問に思うはずなので、順を追って考えていきます。

まず、先ほどの計算における本質をわかりやすくまとめると「素因数それぞれが変数に対応し、素因数の指数がその変数に格納される値である」という解釈になります。
先ほどの例で考えてみます。
初期値である $n = 72$ は素因数分解すると $2^3 ・3^2$ と表すことができます。
この初期値を「$v2 = 3, v3 = 2$」のような二つの変数と値をセットしている」と解釈してみます。
これに対し、出力は $n = 5^6$ 、つまり「$v5 = 6$」となっています。
ここまでくると先ほど述べた「与えられた2数の積を計算する」という意味が理解できると思います。

先ほどの分数列は任意の自然数 $a, b$ を設定し、初期値を $n = 2^a3^b$ として所定の操作を行うと、出力として $n = 5^{ab}$ を得ることができます。

乗算が実現できる仕組み

なぜこのような計算が実現できるのでしょうか。
まず、どのように乗算を実現するかを考えてみると「答えとなる変数にv3の値を足す、という操作（ループ）をv2回繰り返した時の答えの値」というシンプルな操作を思いつきます。
答えを格納する変数をv5とすると疑似コードは次のようになります。

v5 = 0
while v2 > 0
  v2 -= 1
  v5 += v3
end
puts v5

ではこのコード通り3つの変数で実現できるかというとそう上手くはいきません。

まず、「評価された値は必ず消費される」という原則があります。
例えば、$n = 3$ で $\frac{5}{3}$ と掛け合わせる際、「v3の値を1減らし、v5の値を1増やす」という操作に対応しています。
この時、v3の値を保持したままv5に加算し続けることはできないため、v7のような一時的な変数に値を退避させ、後でもう一度戻すという操作が必要になります。

また、「v2の値を減算する状態」と「v5にv3の値を加算する状態」のどちらであるか、というステートの管理が追加で必要になります。
新たに状態を表す変数v11を作ればよさそうですが、先ほどの「評価された値は必ず消費される」という原則に基づくと、この状態変数は2つを交互で使い回す必要があることに気づきます。
これはもう一つのステートを表す変数をv13とすることで実現可能です。
（変数の数字は素因数分解の結果に基づくため、素数の値を小さい順に用いています）

ここまでの議論を踏まえ、ざっくりとしたフローを作ってみます。

そして、各操作を分数に対応させます

操作の説明	変数の増減	対応する分数
v2 > 0のとき、減算してState2へ	v2 -= 1; v11 += 1;	$\frac{11}{2}$
v7 > 0のとき、v3に値を戻す	v7 -= 1; v3 += 1;	$\frac{3}{7}$
v2 = 0のとき、v3の値を減らす	v3 -= 1;	$\frac{1}{3}$
v13のフラグをv11に変更する	v13 -= 1; v11 += 1;	$\frac{11}{13}$
State2のとき、v3の値をv5,v7に加算する	v11 -= 1; v13 += 1; v3 -= 1; v5 += 1; v7 += 1;	$\frac{13・5・7}{11・3}$
v3 = 0になったらState1に戻る	v11 -= 1	$\frac{1}{11}$

最後に、これらの変数を呼び出される優先度の高い順に並べます。

v11, v13を判定するState2はState1より優先される
State1に戻る判定はState2の他の判定より後に評価される
v7 <- v3に値を戻す操作はState2への移動より優先度が高い
State1でv3の値を減らすとき、v2, v7ともに0である必要がある

これらを踏まえると

\displaylines{
    \biggl( \frac{455}{33}, \; \frac{11}{13}, \; \frac{1}{11}, \; \frac{3}{7}, \; \frac{11}{2}, \; \frac{1}{3} \biggr)
}

がこの計算を実現する配列として得られます（最初の2つの分数は順不同です）。

素数列挙もできる（触りだけ）

加算や減算ができるということは、それらを組み合わせてより複雑な計算も行うことができます。

例えば、コンウェイさんはPRIMEGAMEと呼ばれる、操作の中で一定のイテレーションごとに指数に素数が現れるような分数列を作りました。
素数を判定するというと複雑なアルゴリズムが必要な気がしますが、計算回数を気にしないのであれば「2以上の自分より小さな整数で全て割ってみて、いずれも割り切れなければ素数である」という除算を用いた操作で実現可能です。
分数列の構成の仕方の基礎は先ほどの例と同じなので興味があればチャレンジしてみてください。
（出典に書いてあるWikipediaの記事に分数列が載っています）

パズル要素・競技性

FRACTRANには設定次第で様々なゲーム・頭の体操のコンテンツとして活用できるんじゃないかなと考えています。

例えば「二つの数 $v2 = a, v3 = b$ を入力として、$a+b$ を出力するような分数列を作成してください」という問題を作成し、ユーザが与えられた分数列に対してこちらでランダムで入力・出力を生成して評価することでジャッジサーバのようなシステムを作ることができます。

また、やや複雑な課題に対して

使用する分数の個数を最小化する
使用する素因数の種類を最も少なくする
計算が実行される際のループ数を最小化する or 上限を設ける

など様々な条件を設定することで、単に正解を出す以外にも何度も挑戦できるような面白いコンテンツになるのではないでしょうか。

ジャッジ自体は簡単なwebフレームワークみたいなものを使えば比較的簡単に実現できると思うので、もし興味を持ってくれた方がいたら作ってみてください。

おわりに

FRACTRANというちょっと頭の体操ができる難解プログラミング言語を紹介してみました。
手続き自体はシンプルですが加算に始まり素数の列挙などの複雑な計算まで実現できるので面白いですね。
実用性は皆無ですがちょっとした話題の引き出しの一つとしては面白いと思うので、興味を持ってくれた方がいたら手元で色々遊んでみてください。

明日のアドベントカレンダーは斎田さんの「エディタ拡張のTreeViewについて」です！
アドベントカレンダーもあと5日ですね、過去19日分の記事もぜひ面白いのでよかったら読んでみてください。

最後に宣伝を。
僕の所属する株式会社アカツキゲームスでは一緒に働くエンジニアを募集しています。カジュアル面談もやっていますので、気軽にご応募ください！

難解プログラミング言語「FRACTRAN（フラクトラン）」を紐解く