自作スタック言語 Rustack では再帰呼び出しが for 文より強力
今回は拙著「Rustで作るプログラミング言語」の発売を記念して、宣伝を兼ねたちょっとした小ネタです。
この本では Rust を使用して自分でプログラミング言語を自作する手順をステップバイステップで紹介しているのですが、そこで出来上がる言語には Rustack と Ruscal という２つがあります。ここでは、その一つ目である Rustack の、本では紹介しきれなかった、ちょっとした特性を紹介したいと思います。
スタックベース言語 Rustack
詳しくは書籍を参照していただければと思いますが、 Rustack は逆ポーランド記法を基本とした極めて構文要素が少ないプログラミング言語です。例えば階乗は再帰呼び出しを使って次のように書けます。
/factorial { 1 factorial_int } def
/factorial_int {
/acc exch def
/n exch def
{ n 2 < }
{ acc }
{
n 1 -
acc n *
factorial_int
}
if
} def
10 factorial puts
知っている人は PostScript によく似ていることに気づいたかと思います。逆ポーランド記法で有名な言語には他に Forth がありますが、あまり似ていません。
この言語は最小限のチューリング完全な言語を実装する練習台として設計されているため、制御構文が if と for の２種類しかありません。しかし、実は for すらもいらないということをここで示します。
本では for 文の実装方法は紹介していませんが、完成版の言語と WebAssembly によるオンラインデモには利便性のために組み込みの for 文を用意しています。これは PostScript と似たように[1]、次のように３つの引数を取ります。
<start> <end> {block} for
この for 「関数」を実行すると、 {block} の中身のコードが <start> と <end> の間だけ繰り返されます。ブロックの実行前には繰り返し変数がプッシュされます。イメージ的には次の C コードのような動作です。
for (int i = <start>; i < <end>; i++) {
{block}
}
マンデルブロー集合の描画
計算能力のベンチマークとしてマンデルブロー集合の描画を例にとります。
このコードは地味に長いのでこちらのリンクを参照してください。私の環境では描画時間は 7.6 秒でした。
ここで肝になるのは収束判定とその繰り返し数を返す次の関数です。この関数は次の複素数の漸化式の絶対値が2を超えるまでの繰り返し数をループで計算し、255を超える場合は iters 変数を更新しません。
/mandelconverger {
/cimag exch def
/creal exch def
/iters exch def
/imag exch def
/real exch def
0 255 {
{ 4 real real * imag imag * + < }
{ }
{
/iters exch def
/real_next real real * imag imag * - creal + def
/imag 2 real * imag * cimag + def
/real real_next def
} if
} for
iters
} def
本当は、絶対値が2を超えた時点で計算を打ち切りたいのですが、 for 文には途中で繰り返しを打ち切る手段がないので、空ブロック { } を255回まで回しています。
これを再帰呼び出しで書き直したものはこちらにありますが、上記のループに相当する関数は次のように書き直されています(mandel という関数内の画像のピクセルをスキャンする部分には未だに for 文を使っていますが、この議論には直接関わらないのでご容赦ください)。
/mandelconverger {
/cimag exch def
/creal exch def
/imag exch def
/real exch def
/loop {
/iters exch def
/imag exch def
/real exch def
{
4 real real * imag imag * + <
255 iters < or
}
{ iters }
{
/real_next real real * imag imag * - creal + def
/imag 2 real * imag * cimag + def
/real real_next def
real imag iters 1 + loop
} if
} def
real imag 0 loop
} def
loop という内部関数を定義し、その中から自分自身を再帰的に呼び出しています。
real imag iters 1 + loop という部分がそれで、繰り返し数を1だけ増やしてから呼び出しています。
ここで注目に値するのは、 if 文の条件部にある次のコードです。
{
4 real real * imag imag * + <
255 iters < or
}
これは前述の絶対値が2を超える場合の打ち切り判定と、255以上の繰り返しの打ち切りの両方を行っています。条件部が true (=非ゼロ)の場合は次のように再帰呼び出しをせずにその時点での繰り返し数を返しています。これはループの早期リターンに相当します。
{ iters }
Rustack には break 文はないので[2]、再帰呼び出しは for 文よりもフローの細かな制御ができるという点でより強力ということになります。 for 文だと255回のループは必ず255回回さなくてはなりません。計算が途中で確定する場合であってもです。
もちろん実行結果は for 文のものと全く同じですが、処理時間は私の環境では 21 秒でした。余計なループは削減したのに処理時間は伸びてしまいました。これはループの繰り返しのたびにスタックフレームを積んで変数を初期化するオーバーヘッドによるものだと考えられます。末尾再帰最適化を施せばループ相当になり高速化できると思われますが、そこまですると教育用言語としては複雑になりすぎるのでこのままにしておきます[3]。この言語は速度の追求を目的としたものではなく、チューリング完全性のデモが存在意義です。
ちなみに、拙作の別の言語 rusty-parser でも同じようにマンデルブロー集合の描画のサンプルを載せてありますが、こちらはバイトコードにコンパイルしてから実行することで 100ms 程度で同じ WebAssembly 上でも同じ描画ができます。 Rustack がいかに非効率な言語かが分かると思います。
論理式のショートサーキット評価
もう一つ、 Rustack には構文上避けられない非効率性があります(実行モデルが遅すぎるという点は除いて)。それは論理演算子です。
C 系の言語では || や &&、 Rustack では and と or という演算子ですが、これらはまともな言語であれば左のオペランドを評価した結果が右のオペランドを評価するまでもなく決定する場合は、右を実行しません。例えば、 C 系の言語では次の２つの式では f() は実行されません。
true || f()
false && f()
これはショートサーキット評価などと呼ばれています。ちなみに、ビット演算子 | と & には、このショートサーキット評価は行われません。理由は考えればわかりますね。[4]
ショートサーキット評価は条件式が複雑になると計算量の削減に役立つことがありますが、 Rustack では演算子レベルで実装する術がありません。やるとしたら実行を遅延させることができる唯一の言語構成要素であるブロックを引数に取る次のような演算子になると思いますが、これはネストするとすごく読みにくそうです。
{lhs} {rhs} or
{lhs} {rhs} and
ここで lhs, rhs はそれぞれ左辺(left-hand side)、右辺(right-hand side)を示します。
まとめ
このように、 if 式と再帰呼び出しだけで複雑そうに見える計算もできてしまいます(実行速度は度外視していますが)。条件分岐とサブルーチン呼び出しと繰り返しがあれば、チューリング完全になるという例です。繰り返しはループ構文でも再帰呼び出しでも構いませんが、構文を極力単純化するなら関数定義と再帰呼び出しがより強力です。これはプログラミング言語と呼ぶための最低限の構成要素と言えます。
-
PostScript の for 文は
<start> <step> <end> {block}の4つの引数を取りますが、私が実装するときにそれをすっかり忘れていました。よってこの構文は PostScript 互換ではありません。 ↩︎ -
PostScript には exit コマンドがあり、最も最近のループから抜けることができる C でいう break に相当するものですが、 Rustack には面倒なので実装していません ^^; ↩︎
-
Rustack にはステップ実行と仮想マシンの状態の可視化機能があるので、最適化によってデータモデルが変わってしまうとデバッグが困難になってしまいます。 ↩︎
-
他にも演算子の優先順位も異なりますが、細かい話になるので割愛します。 ↩︎
Discussion