逆ポーランド記法

isamさんがRustを試しだしたそうだ。

以前に書いたが、Rustと言うプログラミング言語はぶっちゃけ、C/C++を置き換える目的で開発されてる、と見て良い。

ただし、C/C++みたいなシステムプログラミング分野で、いきなりOSを作ったり、と言う実例は出ないだろう。

そして、関数型言語っぽい機能が満載に見えるRustだが、C/C++に近くガベージコレクタを持たないRustで「あらゆるアプリケーションを書こうとする」のは多分自滅と言えば自滅なんだよな。

それは今どき「何が何でも全部C/C++で書こうとする」と言うのに近い程無駄だ。

したがって、現状で考えうるRustを使うべき何か、と言うと速度が遅いとクリティカルな問題が生じるアプリケーションになるんじゃないか。

Webブラウザ
ビデオゲーム
プログラミング言語

多分こんなトコだと思う。

Mozillaがお膝下なんで、実際Firefoxの一部は既にRustで書かれたりしてる模様だ。

ゲームはどうなんだろうね。可能性は高いんだけど、問題は任天堂やSONY、Microsoftと言うゲーム機ベンダが開発キットにRustを指定するにはまだ時間がかかるとは思ってる。あと、ザーッと検索する限り、OpenGLとかUnityとRustを組み合わせる試みが行われてるようだが、どうも実験段階を超えてないようだ。

いずれにせよ、この辺は今後の展開に期待かな。

一番手っ取り早くRustを使って成果を挙げられる、とすればプログラミング言語の開発だろう。

「え?」とか思う向きもあるかもしんないけど、そもそもC/C++で、現状のコンピューティング環境だと、「プログラム全部を書く」っつーのは大変なわけ。その「大変さ」を緩和するには「C言語で書かれたプログラミング言語を作って、大部分ではそれでラクをする」ってのが解なんだよ。

つまり、Rustもガベージコレクタが無い以上、そこそこプログラミングに大変な思いはするだろう、って事は言えるのね。っつー事は一番Rustを使って「比較的簡単で、応用範囲が効きそうな分野」と言うと「プログラミング言語を作る」事だと思う。

たとえばRustでScheme書いて、処理系作る、ってのは一番やりやすそうな事ではあるのね。いや、俺はやんないけど(笑)。いずれにせよ、Rustを使った応用としては一番「あり得る」パターンなのかな、とは思ってる。

んで、僕は全然読んでないんですが、isam氏が使ってる実践Rust入門とか、その著者陣は完全にその辺読んでるんじゃねぇのかな、とか思った。一番望ましい範疇のプログラミングをするとすれば、簡単でも、プログラミング言語実装っぽい例を紹介すべきなんじゃないか、ってのは的を射てると思う。

そう、isam氏のブログの話だと、いきなりRPN(Reverse Polish Notation: 逆ポーランド記法)を紹介してる、っつーんだけど、話聞いた限り「さもありなん」って思っちゃったのね。

ここで逆ポーランド記法を知らない人の為にザックリ紹介しておこう。

たとえば僕らがフツー数式書く時こう書くじゃない。

足し算：3 + 6
引き算：6 - 3
掛け算：3 * 6
割り算：6 / 3

まあ、掛け算とわり算の記号はコンピュータ上だとアスタリスク(*)とスラッシュ(/)使うけど。いずれにせよ、小学校の時学んだ書き方だよな。

こういう風に数字と数字で演算記号を挟むような書き方を「中置記法」と呼ぶ。

「と呼ぶ」って事は、これが唯一の表記方法ではない、って事なんだよな。

逆ポーランド記法、あるいは後置記法、と言うのは同じ数式をこう書くわけ。

足し算：3 6 +
引き算：6 3 -
掛け算：3 6 *
割り算：6 3 /

演算子が最後に置かれてる。

小学校からずーっと中置記法に馴染んでくると、これはちと異様に見えるんだよな(笑)。

ところがだ。実際の話、コンピュータの「内部」ではこの後置記法、略してRPNって呼ぶけど、これで計算が行われてる確率が高いのね。

何度かチラっと書いてきたんだけど、たとえばプログラミング言語を使ってプログラムを書いたあと、コンパイルとかしたら、最初にそのプログラミング言語の「構文解析」を行う。これで作られた結果を抽象構文木、っつーんだけど、それに対してやっと演算を始めるのね。

その演算を「実行する」過程で、多分一番使われてるのが、この後置記法表現なんじゃないか。

詳しい過程は、isamさんへのコメントにも書いたけど、このページが易しく解説してくれてると思う。

日曜プログラミングで電卓を作ってみる:

この処理で使われてるのがスタックマシン、と言われてる方式。ひっじょーに単純な方式で、メモリをスタック、って使い方をして実行する。これと後置記法はメチャクチャ相性が良い。

世の中の、たとえばJavaなんつープログラミング言語の仮想マシンの形式もこれだし、この形式の仮想マシンを持ってるプログラミング言語は星の数程あるのね。

もう1つのポイントは、フツーのプログラミング言語の構文解析を取っ払っても、比較的人間が扱いやすい方式なの。単純だし。そしてメモリを大量に使わないんで、コンパクトに仕上げられる。

だから昔の科学技術演算用の電卓とか、ハードウェア・スタックマシンになってて、後置記法で入力とかしてたのね。

Appleを立ち上げる際に、スティーブ・ウォズニアックが資金を得る為に売っぱらったHP(ヒューレットパッカード)社製の電卓、ってのがそれ。あと、亡くなった任天堂の社長、岩田聡も最初にプログラミングしてたのがHP社製の電卓なのね。

スティーブ・ウォズニアックがApple社立ち上げの際の資金稼ぎに売っぱらったHP社の電卓、HP-65。1 + 2 を計算するには 1 2 + ENTER と入力する。つまり直接スタックマシンを弄るような設計になっていた。

任天堂の故・岩田聡社長が高校生の頃、新聞配達でお金を稼いで購入したHP-67。後の天才プログラマはこれでプログラミングを学んだらしい。当然逆ポーランド記法による電卓だ。

逆ポーランド記法のプログラミング言語だと構文解析が複雑じゃない為小さく出来、メモリが少なくて済み、ぶっちゃけ組み込み用途にも向いている。

たとえば、アドビが元々レーザープリンタに搭載する為に作ったプログラミング言語、PostScriptなんかもHPの電卓よろしく、逆ポーランド記法のプログラミング言語だ。

PostScript互換のフリーなプログラミング言語、GhostScriptでの逆ポーランド記法での計算例。
6.1 5.2 4.3 mul add 3.4 2.5 div 1.6 mul sub は (6.1 + 5.2 * 4.3) - 3.4 / 2.5 * 1.6 を表す。
なお、逆ポーランド記法はポーランド記法と違い、通常は2引数を取るカタチとなっている。

さて、ここではRustに代わってまずはPythonでRPNの電卓を作ってみよう。

isamさんが公開してるオリジナルのRustコードは以下のようになっている。

このままベタ移植を試みてもいいんだけど、ちとPythonには厄介な点がある。

それは文字列を数値に直す際、「数値」と言う大まかな変換が行えない事だ(もっともRustもそうだが)。

たとえば、Racketなら

> (string->number "3.5")
3.5
> (string->number "3")
3
>

と文字列が表してる数値が浮動小数点数だろうと整数だろうと構わずに数値に変換してくれる。

ところが、Pythonは動的型付の癖にこういった「大雑把な」変換が出来ない。

>>> int("3.5")
Traceback (most recent call last):
File "<pyshell#49>", line 1, in <module>
int("3.5")
ValueError: invalid literal for int() with base 10: '3.5'
>>> float("3.5")
3.5
>>> float("3")
3.0
>>> int("3")
3
>>>

これはちと頂けない。

もちろん、型判定と条件分岐を駆使すりゃ何とかなるんだけど、考えるだけでメンド臭い。

これの回避策は取り敢えず後回しにしよう。

最初にライブラリoperaterをimportする。

import operator as op

operatorモジュールは四則演算の演算子の関数版を提供してる。+はop.add、-はop.sub、*はop.mul、/はop.truedivとなっている。

これらを使えばPythonでもLisp的に前置記法的な記述が出来る。

>>> 1 + 2
3
>>> op.add(1, 2)
3
>>> 3 - 2
1
>>> op.sub(3, 2)
1
>>> 2 * 3
6
>>> op.mul(2, 3)
6
>>> 4 / 3
1.3333333333333333
>>> op.truediv(4, 3)
1.3333333333333333
>>>

「Lisp的に」と書いたが、別にLisp的にしたいからこういう記述法を選んだわけじゃあない。これを使った方が関数的に記述出来るので、統一的な計算が可能なんだ。じゃないと一々マトモに中置記法で演算子を書かなければならなくなる。

このoperatorモジュールで用意されてる関数スタイルの四則演算子と辞書型を利用して、取り敢えず変換テーブルを設定する。

table = {'+' : op.add, '-' : op.sub, '*' : op.mul, '/' : op.truediv}

こうしておけば、四則演算子記号の文字列を見つけた時、わざわざそれ用の分岐コードを書かなくて済む。

次にPythonでのスタックの扱いを考えよう。

当然スタックはリストを使って表現する。

問題は、pushとpopをどうやって実装するか、だ。

たとえば

stack = [1]

だった時、次の表現がpushを表すとしよう。

stack += [2]

そうするとstackは次のように更新されている。

>>> stack
[1, 2]
>>>

一般に、スタックへpushするとメモリの先頭に値が挿入されるような印象があるが、Pythonの場合、ケツに挿入する、と考えた方が実装は簡単になる。

よって、上のような「逆順のスタック」をここでは是としようと思う。

そして、popだけど、これはまともな実装法を考えないで良い。

たとえば今、ここでスタックが

stack = [1, 2, 3]

と言う状況だったとする。ここで演算子+がやってきた、と。

その場合、2引数なので、2回popして、計算結果をまたスタックにpushして・・・と考えると煩わしい。

そうじゃなくって、逆順からリストをスライスして演算子を適用した結果を一気に結合してしまえばいいんだ。

具体的にはこう書く。

stack = stack[:-2] + [op.add(*stack[-2:])]

ケツからスライスする場合、インデックスにマイナスが付く事をまずは利用してる。

>>> stack[:-2]
[1]
>>> stack[-2:]
[2, 3]
>>>

そしてここで使ってるアスタリスク(*)は掛け算記号じゃない。アンパック、と言う機能だ。

昔ならLispよろしくapplyを使ってたケースなんだけど、今はリストの角カッコを外して要素をバラバラにして関数を適用する方が推奨されている。

>>> apply(op.add, [2, 3])　# 昔の書き方
5
>>> op.add(*[2, 3])　　　# 今の書き方
5
>>>

このスライスとリストのアンパッキングを利用して演算を一気に書きあげるわけだ。

ここまで下準備してしまえば、あとは一気に関数rpnを書き下す。

def rpn(exp):
　stack = []
　for token in exp.split():
　　try: stack += [int(token)]
　　except ValueError:
　　　try: stack += [float(token)]
　　　except ValueError:
　　　　stack = stack[:-2] + [table[token](*stack[-2:])]
　return stack[-1]

最初に書いた通り、Pythonだと文字列からトークンを切り出して、それが「数値」と大雑把に判定する事は難しいし、また「数値」と言う大雑把な変換も不可能だ。

条件分岐が煩わしいので、いっそ例外処理を使って切り抜けよう。とにかく取り敢えずはトークンをint型に変換してみる。失敗したらfloat型に変換してみる。int型でもfloat型にも変換出来なかったらそれは四則演算子だ、と言う疑いになる。そうすれば、そのトークンが表してる関数を設定したtableから引っ張ってこよう。値は関数名なんだけど、ファーストクラスオブジェクトなんで、直接アンパックした部分リストに適用が可能だ。

こうすればメンドい条件分岐を避けつつコードを記述する事が可能だ。これで失敗したら失敗した時である(笑)。Rust版も「その他」はエラーを投げてるんで、これで機能的には充分、になる。

あとは、main関数部分を書けばいいだけ、だ。

if __name__ == '__main__':
　exp = "6.1 5.2 4.3 * + 3.4 2.5 / 1.6 * -"
　ans = rpn(exp)
　print("{0} = {1:.4f}".format(exp, ans))

全体的にはこうなる。 => ソースコード1

さて、次はインタプリタを作ってみよう。

とは言ってももうEval部分はある。rpnと言う関数がそれだ。

だからmain部分を改造すれば良い。

先程書いたrpnはトークンが数字や四則演算子じゃなかった場合、エラーを投げる。

REPLはそれをキャッチして再入力を施すようにすれば良い。

あとは、

quitと入力されたらインタプリタが終了する。 => import sysしてsys.exit()すれば良い。
入力用プロンプトとして"rpn > "と表示する。
出力は計算結果のみで良い。

程度にしておけば良いだろう。

if __name__ == "__main__":
　while True:
　　exp = input("RPN > ")
　　if exp == "quit":
　　　sys.exit()
　　else:
　　　try:
　　　　print("{:.4f}".format(rpn(exp)))
　　　except:
　　　　print("不正な入力です。")
　　　finally:
　　　　exp

全体的にはこうなる。 => ソースコード2

いずれにせよ、「処理内容」が明確に書き上がってればREPLを構成する、つまりインタプリタ化する事は屁の河童、っちゅう事だ。

「すべてのソフトウェアは原理的にはインタプリタである」

この言葉を真言のように唱えよう。

さて、isamさんがもう1つ面白い事を書いてる。

再帰使えそう

うん、使えるでしょう。

ただ、RustもPythonもそうなんだけど、末尾再帰最適化の機能がない言語処理系だと、別に無理して再帰は書かんでエエと思う。

特にVisual Basicはマイクロソフトが認めてるくらいに再帰そのものが苦手なんで、無理して使わなくてもいいでしょう。

その「言語処理系への信頼度が高くないと」一般に再帰には手を出さん方が良いかも。

逆に言うと「再帰へっちゃら」なLisp言語族とか、あるいはgcc/clangみたいな末尾再帰最適化可能なコンパイラは頑強性(ロバスト性とか呼ぶ)が桁違いなんです。

同じお題をRacketで書くとこんなカンジかな。

(define *table* (hasheq '+ + '- - '* * '/ /))

(define (rpn exp)
　(let loop ((tokens (string-split exp)) (stack '()))
　　(if (null? tokens)
　　　(car stack)
　　　(let ((token (car tokens)))
　　　　(let ((num (string->number token)))
　　　　　(loop (cdr tokens)
　　　　　　　　(cons
　　　　　　　　　(or num (apply (hash-ref *table* (string->symbol token))
　　　　　　　　　　　　　　　　(reverse (take stack 2))))
　　　　　　　　　((lambda (x)
　　　　　　　　　　(if num
　　　　　　　　　　　x
　　　　　　　　　　　(drop x 2))) stack))))))))