超簡単! スタックマシンを作ろう!

注意
ここで述べられている内容は、私が試行錯誤の末に至った一つの考えです。確かな情報源があるわけではないので、読み物程度にとらえてください。
また、作り方をそのまま解説しているわけではありません。考え方のみを載せています。

目次

0. なぜ作るのか
1. Lexerを作ろう
2. LIFOの極意を知ろう
3. APIを確定させよう
4. 自作言語を動かそう
5. まとめ

0. なぜ作るのか

既存言語の高級さ

現代の実用性を持った言語というのは、高度に抽象化されています。例えばローカル変数宣言という一つをとっても、その裏側にあるシステムは高度に隠蔽されています。そのため、我々は裏側を意識せずにコードを書くことができるのです。

自作言語の透明度

これまで述べた既存言語の特徴とは反して、自作言語というのは非常に明確な動作を保証します。ある時刻における、存在する変数の一覧を表示することもできますし、いつも書いているコードの裏側でどれほどの操作が行われているのかを実感することができます。

完全に閉じた世界

自作言語は、ソフトウェアの中では完全に閉じた世界です。書きたいコードを持った時に、ネットサーフィンが先陣を切ることはありません。その中で起きたコードエラーなどはすべて、論理的に解決可能となります。これは外界との相互作用が最小限となっている環境の特徴です。

選択肢を絞る利点

豊富な選択肢というのは、時にエンジニアを苦しめます。配列の中身を一つずつ取り出していく処理の、過剰なほどの多様性を実感したことがあるのではないでしょうか。また、その言語のAPIを読んでいた時に、どこで使うか見当もつかない構文を見つけたことがあるのではないでしょうか。選択肢を絞るということは、悩む時間が極端に減少するということです。必ずしも書きやすくなるとは限りませんが、追加した構文は想定した理由を含むでしょう。だからこそ、選択肢を絞るということは一定の価値を孕んでいるのです。

1. Lexerを作ろう

Lexerとは

Lexerというのは、厳密には生のデータからプログラムで扱えるデータへ変換するシステムのことです。ここでは、文字列として受け取ったコードをコンピュータが理解できるように下ごしらえする部分という風にとらえてください。例えば、以下の文を考えます。

i  = 0x5f3759df - ( i >> 1 );

式の意味を理解する必要はありません。ただ、Lexerに通すとこうなります。

["i", "=", "0x5f3759df", "-", "(","i", ">>", "1", ")", ";"]

コンピュータにとって、空白 というのは特別な意味を持ちません。もちろん、人間からすればそこには明らかに空白があって、ここで単語が途切れるということが直ちにわかります。しかし、コンピュータが読んでいるのは0と1の羅列にすぎず、空白 というのは一種の並び方に過ぎないのです。故に、人間が咀嚼してやる必要があります。優秀な言語には優秀なLexerが付くものですが、本題の簡単なスタックマシンを作るうえでは宝の持ち腐れ、猫に小判、豚に真珠です。ここでは無視するとします。

スライス天国

では、具体的にどのようにLexerを作ればいいのでしょうか。まず初めに思い付くのは、空白 で分割する方法です。空白の前後で文字列を区切り、以下のコードを分解してみましょう。

public static final
String    HELLO_WORLD = "Hello World";

変数宣言の途中で改行するのはまれではありますが、それでも合法であってほしいですよね。また、空白が連続する部分も不自然ではありますが、違法と感じたことはないと思います。では先ほどのルールで咀嚼してみましょう。

["public", "static", "final", "\nString", "", "", "", "Hello_WORLD", "=", "\"Hello", "World\";"]

頭を見れば一見正しいように思えます。しかし、そううまくは行きません。なぜでしょうか。一つずつ取り上げます。ただし、\"や\nというのは特殊文字で、それぞれ"と改行を表します。

["\nString"]

まずはここです。コードの中には見られない\nという要素が邪魔をしています。これはテキストエディタが有能すぎるために起こるものです。通常、改行された直後の文章は一行下に、頭を左端に置かれます。

今日はいい天気だった。
ビット操作をするには最適だ。

これは、コンピュータが読むと改行自体が文字でおかれます。

今日はいい天気だった。\nビット操作をするには最適だ。

といった具合です。テキストエディタは、これを人間が読みやすいように解釈しているのです。普段は隠されていた文字が、一つの文字として認識されてしまったわけですね。次に、

["String", "", "", ""]

について考えましょう。これは、空白 に挟まれた文字列に中身があるかどうかを確認していないため起こるものです。空白 を文字-に置き換えれば、

String----HELLO_WORLD

となっていて、隣り合う-の間に空っぽの文字列がある、と判断されたようです。次に、

["\"Hello", "World\";"]

について考えましょう。これは二つの異なる問題を含んでいます。まずは、文字列内の空白 でも分割してしまっているということ。もう一つは、空白が無くても独立すべき;のような文字の存在です。つまり、期待する結果は以下のようになります。

["\"Hello World\"", ";"]

以上より、想像よりも多くのケースが存在することが分かります。これらを解決するためには、

• "で囲われた領域でない
• 必ず独立した単語を形成する文字列がない
• 前後どちらか一方は空白の文字列でない

ときは空白 で区切ることができます。それ以外にも、

• ;や:、さらに()[]{}~^-+*%\nなどは単独で単語を作る
• ->や&&``||など、二文字以上で単語を作る

といった場合もあります。もちろん、ここで述べたのは一例であって、言語によってその定めるキーワードは様々です。これらを頭に入れて自分だけのLexerを作りましょう!

……これでは満足できませんか?
そのような方々はぜひ実物を見てください。

コメントアウト

コメントアウトというのは説明書のようなものです。

// ここでインクリメント(間違い)
i --;

コメントの使い方については様々議論があります。コメントを使わないとわからないコードを書くべきではないとか、コメントで日記を書くなとかも議論されています。
さて、コメントアウトはプログラムの実行に一切の影響を与えません。すなわち、コンピュータにコードを食べさせるうえで、これを残しておく意味がありません。Lexerでフィルタを書いてしまいましょう。簡単に書くならば、//を見つけたら\nを見つけるまで走らせて、何食わぬ顔でその次から処理を再開しましょう。それだけです。#の派閥であれば、その処理を書いてどうぞ。変な話、commentとかでもいいわけです。その場合、変数名としても関数名としてもcommentという一般的な単語が使えなくなるわけですけどね。

2. LIFOの極意を知ろう

LIFOとは

LIFOとは、“Last In First Out"の略、日本語では「後入れ先出し」と呼ばれます。「最後に入れたものを最初に取り出す」というのが唯一のルールであり、それ以上難しいことなどありません。一応具体例を見てみましょう。左詰めで配列を考えます。

[0, 1, 2, 3]

この状態では3のみが取り出せます。 ここに4を入れると

[0, 1, 2, 3, 4]

となり、この状態では4のみが取り出せます。
それだけです。特別難しいことはないと思われます。

英語ではわかりませんが、日本語の文脈においては積み重ねる概念として扱われます。例としてお皿を積み重ねましょう。一度にモテるお皿を一枚とすると、一番上に追加するか一番上を取り除くことしかできないですよね。「積み重ねる」という動作から、後入れ先出しに対して追加する動作を「積む」と言ったりします。
英語では追加することを"push”、取り出すことを"pop"と言います。こちらの方が使うことが多いと思われます。よく配列を用いることから、“push"はappendを用いられる場合もありますが、LIFO自体に対しては"push"が一般的だと思います。主観です。

Shunting-Yard Algorithmのすゝめ

さて、本格的なアルゴリズムの話です。逆ポーランド記法というのをご存じでしょうか。簡単に言えば、

1 + 2 // 中間記法
+ 1 2 // 前置記法 = ポーランド記法
1 2 + // 後置記法 = 逆ポーランド記法

の三つがあります。単純に書き方の問題ですが、ここに人間とコンピュータの間でどれほど感覚に違いがあるかを実感するでしょう。当然、我々からすれば中間記法が最もわかりやすいかつ慣れている書き方だと思います。しかし、スタックマシンを作るうえではおそらく逆ポーランド記法が最もわかりやすいのです。

1 + 2 * (6 / 2 - 5)

という式を考えてみます。逆ポーランド記法で表せば

1 2 6 2 / 5 - * +

となります。ここで、数値が来たらその値をpush、演算子が来たら上位二つの数値をpopして、計算してpushするのを考えます。つまり、

1:  1
2:  1  2
6:  1  2  6
2:  1  2  6  2
/:  1  2  3       (6 / 2 = 3)
5:  1  2  3  5
-:  1  2 -2       (3 - 5 = -2)
*:  1 -4          (2 * (-2) = -4)
+: -3             (1 + (-4) = -3)

という計算ができてしまいます。これにより以下の利点を得ます。

• 括弧を排除できる
• 数値の場合と演算子の場合の、簡単なルールで計算機を実装できる
• 左から計算が確定できる

詳しく後に述べます。少し難しい話になるため、読みたい方だけどうぞ。
そして、読みやすい中間記法から、この素晴らしい逆ポーランド記法へ変換できるアルゴリズムがShunting-Yard Algorithmというわけです。これだけでもこのアルゴリズムの素晴らしさが分かりますね。また、計算量がO(n)に収まる、再帰処理が存在しないという利点もありますが、後に述べます。
以上です。

言語への転換

Shunting-Yard Algorithmを学ぶと、LIFOの扱い方がより深く学べるかと思います。ここで解説すると非常に長くなってしまうため、気になった方は各自調べて頂きたいです。
このアルゴリズムを読むと、LIFOというのを一時的な演算の貯蔵庫として扱っているように見えますね。少なくとも私は、そうした視点でLIFOを捉えたことがなかったので、とても可能性を感じました。ここに意味づけをしていきましょう。

sum = a + b

という代入の式を考えましょう。これを変換すれば、

sum a b + =

となってほしいですね。代入の演算子=というのは、その前後の演算がすべて消費されてから消費したい、すなわち優先度がかなり低い演算子です。
では、スタックマシン用に改造してみましょう。

push 1 push 2 push 3

という命令が来たとします。重要なのは、pushという命令が来た時点で、コンピュータはその内容を知らないという点です。また同時に、命令によって取る引数の数が異なるという点も厄介です。少ないルールでこれを実現するためにはどうすればいいでしょうか。ここで活躍するのがShunting-Yard Algorithmなのです。演算子、ここではpushなどの命令に関して貯蔵庫とみなすと、命令スタックの中で最上位のものとコード上で次に出てきた命令との優先順位の比較を行います。そうすると、各命令に対して引数となる長さが確定します。これをそのまま各命令へと引き渡すことで、命令の中で完結した滑らかなインターフェースを実現できるわけです。美しいですね(主観)。

補足

ここで述べる内容は少々難しいものなので、読み飛ばしていただいて構いません。

括弧の厄介さ

括弧というのはとても厄介です。数式上の括弧をとらえなおせば、塊を作る記号でしょう。左から走査したとき、

1 + (.....

となってしまえば、一つ目の演算子+の結果が確定しません。そのため、後にあるであろう)を探す必要があり、括弧が入れ子構造を取ることを考えると再帰処理を免れません。

ルールの簡単さ

中間記法で計算しようとした場合、単純に考えると演算子を見つけた場合に前後の値を取得することになるでしょう。上で述べた括弧の存在もありますし、+-の左右に*/などがあればそちらを優先しなければなりません。具体的に書かずとも複雑であることが分かるでしょう。

左から確定できるすばらしさ

中間記法において、

1 + 2 ......

という状態は計算順序が確定していません。のちに+が続けば一番優先になりますし、後に*が続けば二番目以降になります。つまり、ここまで読んだ時点で計算し始めることができないのです。これが起きない、つまり左から確定できる状態というのはとても素晴らしいことだとわかりますね。

O(n)について

Shunting-Yard Algorithmにおいてある単語は、二通りの経路を辿り結果に入れられます。つまり、O(n)です。

再帰処理が存在しない美しさ

好き勝手にフレームスタックを入れられてしまうと、すぐStackOverflowを起こします。長い数式で再帰処理を用いれば、それだけ危険ということです。
ちなみにPythonで再帰処理を行うと、その深度自体に上限があるので十分とは言えません。

3. APIを確定させよう

最低限性

スタックマシンということで、最低限何をしてほしいか、何をさせることができるようにしたいかを考える必要があります。ここで欲張ってしまえば、完成はさらに遠くなってしまうので、妥協を妥協しないようにしなければなりません。以下、私が採用した最低限の例を載せます。

• 出力
• 入力
• 演算
• 条件
• 回帰
• 待機

以上です。
線形代数で基底の考え方がありますが、それを知っているのならば理解は容易でしょう。つまり、すべての欲しい機能がこれらの組み合わせによって実現できるかどうかの議論に落ち着くわけです。

妥協点

複雑さを回避するため、以下のことを無視しました。

• 小数
• オブジェクトとしての文字列

以上です。これらを無視した理由を述べます。
小数については、実際は再現可能であるというのと演算の複雑性の観点から排除しました。再現可能であるというのは、floatやdouble、いわゆる浮動小数点数のbit列を構成する領域、仮数と指数を整数で表すことができるということです。その通りに実装すればコードが非常に複雑にはなりますが、ここでは言語の作りやすさを重視します。

オブジェクトとしての文字列というのは、広く言えばmalloc、つまり可変長データのことです。ここでの言語を作るうえで、オブジェクト管理は親言語に依存させました。なぜならば、現代の主流であるヒープ領域の管理などは、単純化されたスタックマシンにとってあまりに複雑すぎるのです。

これは余談ですが、現在、多少本格的と言ってもいいVM(仮想マシン)の製作をしております。そこではこれらの概念を無視することなく、しっかりと実装する予定です。

デバッグ用

外見が非常に不透明なシステムを作る際は、デバッグ用の命令を追加しましょう。ここでは主に、現在のスタックの中身が該当すると思われます。

4. 自作言語を動かそう

さて、ついに言語を動かす時です。以下にテスト用のゲームを載せておきます。

Fizz Buzz

言語のテストとしては非常に有名なもので、プログラミングを学ぶ際にも書いたことがある人がいるのではないでしょうか。
ここで確認できる動作は以下の通りです。

• 剰余計算・和算
• 条件分岐
• 回帰

具体的には、以下のようなコードになると思います。ただし、言語の簡単性を考慮して単純な命令に、一般性のためPythonで書きます。

i: int = 0
while true:
    i += 1
    if i > 100:
        break
    if i % 15 == 0:
        print("FizzBuzz")
        continue
    if i % 3 == 0:
        print("Fizz")
        continue
    if i % 5 == 0:
        print("Buzz")
        continue
    print(i)

以上です。

Fibonacci

変数宣言を定義しているのであれば、フィボナッチ数列ではとても面白い挙動を観察することができます。少し挙動を確認してみましょう。考えたい値をn、一つ前の値をn_1、二つ前の値をn_2として観察してみます。n = n_1 + n_2 = 2というのを実現するために、

(n_1 = n1, n_2 = n2)
push n_2    // [n2]
push n_1    // [n2, n1]
add         // [n2 + n1]
pop as n    // [] n <- n2 + n1
push n_1    // [n_1]
pop as n_2  // [] n_2 <- n1
push n      // [n]
pop as n_1  // [] n_1 <- n

のループが考えられます。しかし、もっと美しくできそうですよね。スタックの中身は変数名のない値として活用できます。つまり、変数nの代入をした4行目の時点で、変数n_1の値が保存できていれば変数nを介さずに値の遷移を実現できるはずです。

(n_1 = n1, n_2 = n2)
push n_1    // [n1]
push n_2    // [n1, n2]
push n_1    // [n1, n2, n1]
add         // [n1, n2 + n1]
pop as n_1  // [n1] n_1 <- n2 + n1
pop as n_2  // [] n_2 <- n1

といった具合です。先ほどよりも美しくなりましたね(主観)。さらに、これは小さな変化ですが、和の可換性を用いると

(n_1 = n1, n_2 = n2)
push n_1    // [n1]
dup         // [n1, n1]
push n_2    // [n1, n1, n2]
add         // [n1, n1 + n2] (n1 + n2 = n2 + n1)
pop as n_1  // [n1] n_1 <- n1 + n2
pop as n_2  // [] n_2 <- n1

と単語を一つ減らせますね。ただし命令dupは、スタックの頭をもう一度pushするという意味で、ここではn_1という値を二回pushするのと同値です。
以上です。

素数判定

素数判定には、剰余計算を多く用います。そのシステム自体は非常に単純で、

(n: 判定する数値, i: 2から)
n <= i なら終了
n % i == 0 なら素数でない -> 終了
n % i != 0 なら i++ してから繰り返す

というものです。改良するのであれば、

(n: 判定する数値, i: 2から)
n < i*i なら終了
n % i == 0 なら素数でない -> 終了
n % i != 0 なら i++ してから繰り返す

とするのもいいでしょう。

コンソールゲーム

これまで述べてきたテストコードは、実行のタイミングや回数によって結果が変わることはありません。さらに発展させて、ゲームを作ってしまいましょう。
ゲームとは言っても、ウィンドウを表示させるとなるとまた多大な労力を必要とするのは容易にわかるので、CUIベース、テキストベースのゲームを作りましょう。
どのようなゲームにするかは自由です。RPGでもいいですし、ノベルゲームもいいですね。推理ゲームも作れますし、パズルゲームだって作れます。ぜひ自分だけのゲームを作ってみてください。

一つ面白い考え方を紹介します。関数を導入しようと思ったとき、入れ子構造を許さないのであればインラインを採用することで簡単に実現することができてしまいます。つまり、

fn test(add push 1)
push 1 push 2 test add

というコードがあった時、実行位置の移動などは考えずに

push 1 push 2 add push 1 add

という風に展開することで簡単に実現できます。実装が簡単であるのにもかかわらず、書きやすさが大きく向上するので試す価値はあるのではないでしょうか。

5. まとめ

以上、「超簡単! スタックマシンを作ろう!」と題しましてその周辺の考え方から、簡単に述べてきました。いかがでしたでしょうか。これを機に言語制作を本格的に試してみるのもいいと思います。また、これらの知識はかなりいろいろなところで使えると思うので、普段のゲーム制作を違った視点で見ることができるのかもしれません。
以上です。長くなりましたが、最後までお読みいただきありがとうございました。私自身まだ拙いので、これからも学んでいきます!