stack machine (compiler) calc - cranebirdの日記

スタックマシンによる簡易計算機の vm は昨日作ったので、コンパイラを作る。といっても手抜きで、S 式を入力にする。
これは、字句解析、構文解析を省略するということ。「S式の良さ」(http://practical-scheme.net/wiliki/wiliki.cgi?Lisp%3AS%E5%BC%8F%E3%81%AE%E7%90%86%E7%94%B1)などが参考になる。そしてそれが Lisp の良さ。

「『構文解析』…そんな言葉は使う必要がねーんだ。
なぜならオレ(Lisp 使い)やオレたちの仲間(Scheme 使い)は、その言葉を頭の中に思い浮かべた時には！
実際に構文木を書き下しちまってもうすでに(構文解析は)終わってるからだ！
だから使った事がねェーッ！『S式を書き下した』なら使ってもいいッ！」

(- (+ 12 3) 4) 式が与えられると、
PUSH 12
PUSH 3
ADD
PUSH 4
SUB
という命令が生成されるようにすればいい。これも手抜きで、+,- は常に二個引数を取ることにする。
コンパイラは http://www.hpcs.is.tsukuba.ac.jp/~msato/lecture-note/comp2007/note1.html そのままで、以下のとおり。

式が数字であれば、その数字をpushするコードを出す。

式が演算であれば、左辺と右辺をコンパイルし、それぞれの結果をスタックにつむコードを出す。その後、演算子に対応したスタックマシンのコードを出す。

式のコンパイルしたら、PRINTのコードを出しておく。

これを Common Lisp で書くと、

(defun compile-calc (sexp)
  (cond
   ((null sexp) nil)
   ((numberp sexp) (list (cons 'push sexp)))
   ((and (consp sexp) (= 3 (length sexp)))
    (let ((op (ecase (car sexp)
		(+ 'add)
		(- 'sub))))
      (append (append (compile-calc (second sexp)) 
		      (compile-calc (third sexp))) (list (list op)))))
   (t (error "unexpected sexp:~a" sexp))))

(defun compile-and-run-calc (sexp)
  (let ((vm (make-instance 'calc)))
    (setf (codes vm) (compile-calc sexp))
    (run vm)
    (*print vm)
    vm))

st-machine(77): (compile-and-run-calc '(- (+ 12 3) 4))
calc: 11
#<codes: ((push . 12) (push . 3) (add) (push . 4) (sub)) stack: nil>

List の処理がちょっと冗長で格好悪いが、一応コンパイラとして動作した。Common Lisp でこの種のプログラムを書くときは、対話的に少しずつ結果を確かめながらできるのが嬉しい。

コンパイラなんてたいしたことない？まさか。
id:higepon さんや shiro さんの gauche を見れば、制約条件の中で効率的なコードを生成するためには、設計が重要で、それが本当に大変なことであるのは明らか。（MonaOS の scheme シェル、higepon さんの格闘をリアルタイムで読めるのはとても面白い。もっと理解できればもっと面白いに違いない。）

次はもう少し命令のあるスタックマシンを、例の素晴らしい講義資料を参考にしながら作ってみる。