冬休みということで少し時間があるのでいろいろ勉強しているのですが、なんとなくLisp処理系を書いてみたくなったのでRubyで実装してみたいと思います。
Lisp処理系の実装というとshemeの仕様を理解して実装するのが一般的らしいのですが、冬休みで時間も限られているのでとりあえずLisp風の入力に対する電卓レベルの機能をRubyで書いてみました。
※そもそもLispの機能自体をよく知らないのでどこまで真面目にかけるか分かりませんが気が向いたら続けて書いてみたいと思います。
このレベルだとまだ比較的短いです。せっかくなのでブログにも挙げておきたいと思います。
書いてみたコード
補足・解説
LispはLisp Processing の通り、リスト構造を使って処理するのが特徴ですが、処理系を実装しようとしてみるとその特徴がよく分かります。
最初C言語で書こうとしていましたが、そもそもList構造のコードを書くのも面倒だなということでとりあえずRubyで書いてみました。
普通の電卓コードは結構前にC言語でかいた事がありますが、電卓を書く際のこつとして、中間記法を後置記法に変換するのがポイントになります。
例えば、 1 + 2 であれば、 1 2 + という順番に変換して、スタックをうまく使うとカッコつきの演算がかなり素直に実装できます。
Lispの場合は四則演算の計算する場合、中間記法ではなく前置記法になります。上記の 1 + 2 はLispでは(+ 1 2)と書きます。
また、(1 + 2) * 3 のような式は(* (+ 1 2) 3) のような書き方になります。
後置記法はスタックで処理するのに適していますが、前置記法はリスト構造で前から順番に処理するのに適していることが実際に(電卓レベルですが)処理系を実装してみるとよく分かりました。
こうして四則演算の入力に対する処理系を書いてみると、
では人間はどうして中間記法を使うんだろうか？
という疑問が湧いてきます。
もしかしたら脳内の構造はスタックでもリストでもない構造になっているじゃないかなと思いました。
感想
文字列の解析部のコードがかなりRubyらしくないというかダサい感じになりました。もう少し綺麗にできそうなオーラが漂っています。※異常系の処理も書いていません。
手抜きしたところと、Rubyらしさを活かしてもっと手抜き出来るところもあるのでコードとしては微妙ですがあとでC言語に書き直したいということもあるのであまり手抜きしすぎるとC言語に直す時に「あれっ!?ここどうしよっかな・・・」みたいなことになりそうな気がします。
Lispの実装についてよく知らないので、gaucheのドキュメントとか読んでみたらスタックマシンを使って実装しているそうでした。
Lispの処理系というのは真面目に作る場合やはりVMから作る必要があるんだろうか・・・
VMを作るといってもRubyを使えばスタックマシンの実装はそんなには難しくはない(書くコード量は多くはない)だろうけど、なんというか気合と時間はそれなりに必要になりそうで多分時間が足りなくなる気がする。
