stack machine

高級言語でスタックマシンのような低レベルなものを書く、というのは相当簡単。本来は C 言語とかで、低レベルなデータ構造も一緒に学ぶところだが、高級言語だと大事な点（ここでは人が見やすい言語を単純なコンピューター用の命令の列に変換する、というコンパイラというアイディア）のみに集中できる（半ば言い訳。C を触りたくないだけ）。

とりあえずスタックマシン自体理解しているか怪しい。手を動かす。
Tiny-C(http://www.hpcs.is.tsukuba.ac.jp/~msato/lecture-note/comp2007/)の講義資料と順序が逆だが、

1. PUSH,ADD,SUB,PRINT を命令としてもつスタックマシンを実装
2. S 式で書いた計算式をコンパイルする関数を実装

という手順で Common Lisp で手を動かしてみる。例によって vm を CLOS のオブジェクトとして。

(defpackage :st-machine)
(in-package :st-machine)

(defclass calc()
  ((codes :accessor codes :initform nil)
   (stack :accessor stack :initform nil)))

(defmethod print-object ((vm calc) stream)
  (print-unreadable-object (vm stream)
    (format stream "codes: ~a stack: ~a" (codes vm) (stack vm))))
  
(defun exec-calc (codes)
  (let ((vm (make-instance 'calc)))
    (setf (codes vm) codes)
    (run vm)))

(defmethod stack-empty-p ((vm calc))
  (= 0 (length (stack vm))))

;; instruction set 
;; PUSH n
;; ADD
;; SUB
;; PRINT
;; (POP)
(defmethod *push ((vm calc) n)
  (push n (stack vm))
  vm)

(defmethod *pop ((vm calc))
  (if (stack-empty-p vm)
      (error "Stack Underflow")
    (pop (stack vm))))

(defmethod *add ((vm calc))
  (let* ((a (*pop vm))
	 (b (*pop vm)))
    (*push vm (+ a b))
    vm))

(defmethod *sub ((vm calc))
  (let* ((a (*pop vm))
	 (b (*pop vm)))
    (*push vm (- b a))
    vm))

(defmethod *print ((vm calc))
  (format t "calc: ~a~%" (*pop vm))
  vm)

(defmethod run ((vm calc))
  (loop for (opcode . operand) in (codes vm)
      do
	(ecase opcode
	  (push (*push vm operand))
	  (add (*add vm))
	  (sub (*sub vm))
	  (print (*print vm)))))

手を動かしてみると、別に難しくも何ともない。成長したということか。次はコンパイラか。
※さらにその次は、Tiny C 用のもう少し命令の充実したスタックマシン、Tiny C あるいは Lisp 用のスタックマシンを実装して勉強。
そうすると、 gauche のスタックマシンが読めるようになる、はず。

SQL という郡論からなる美しい言語も、裏ではこの種の泥臭い"コンパイル"が走っているに違いない。