アルゴリズムの擬似コードを書く際は、いわゆる手続き型のスタイルで書くことが多いかと思います。つまり、更新可能な変数とループを使います。
一方、私がよく書くのは関数型言語で、これは更新可能な変数やループの代わりに末尾呼び出しを使用します。
では、アルゴリズムを提示してそれを関数型言語で実装する、というスタイルの文章を書く場合、アルゴリズムの擬似コードはどう書けばいいのでしょうか？
（ここでは、アルゴリズムの停止性、計算量、不変条件の明示等の観点から擬似コードの方が有益であり、関数型のコードだけを書けば良いというものではない、という立場を取ります。）
続きを読む前にこういう記事を書きました：
かいつまんで説明しておくと、Universal Machineというのは2006年のICFP Programming Contestで挑戦者が実装する必要のあるVMです。これは速ければ速いほどいいので、JITコンパイルに挑戦したくなります。2年前の記事ではAArch64向けのJITコンパイラーを書きました（私の家の最速マシンがM1 Macだったので）。
時は流れ、私の家の最速のマシンはM1 MacからRyzen搭載ミニPCへ交代しました。なので、x86_64版のJITコンパイラーも書きたくなりました。
今回対応したのはUnix系で、Windows版は未実装です。
続きを読む