Brainf*ck(bf) Interpreter

追記；

以下のインタプリターはあまりに素朴すぎることに気づいた。静的に決まる情報をぜんぜん利用できていないのだ。
さらに悪いことに、インタプリターがすべき仕事とそれ以外ですべき仕事が明確に分かれていない。
いろいろな人のコードを見たつもりだったが何も見えていなかった。Brainf*uck Compiler-Interpreter に続く。


どう書く？org の問題より。
お題は Brainf*ck (bf) コンパイラーを作るというもの。
bf は名前は何だが、シンプルなプログラミング言語で、言語処理系の入門には良い（かもしれない）。

とっくに美しい Common Lisp の回答が出ているが、
(http://ja.doukaku.org/comment/3956/)
勉強としてまずインタプリターを書いてみる。インタプリターは面白くて、

などが（あとで勉強しなおす例として）ある。将来的には

とかできると、コンピューターの知識が深まると期待している。

Brainf*ck Interpreter としては、適当な長さのメモリー配列、メモリー配列の位置を示すポインタ(ptr)、
bf のプログラム、bf のプログラムの位置を示すポインタ(pc)を持たせた CLOS のクラスを定義する。
用語が正確か自信が無いがこのクラスを vm とよんでおく。
クラスを定義したため、実行途中のメモリーの状態を表示したり（bf のデバッグなぞどう考えてもしたくないが、、）しやすいと思う。bf はプログラム中でジャンプ[]があるため、pc が必要?

  • ><+-. は処理をした後 pc を１増やす。
  • [] は pc を増減させるか、または、１増やす。
  • pc がプログラムの長さを超えたら終了。

後は定義通りに実装し、一応インタプリタとしては動くようになった。

(interpret ">+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[<++++>-]<+.[-]++++++++++." nil)
=>
Hello World!
eof

Hello World! を出力する上記 bf プログラムは、ちょっと追いかける気にはなれないが、pc がループしながら動作していることが分かる。

(defclass vm ()
  ((ptr :accessor ptr :initform 0)
   (mem :accessor mem :initform (make-array 2000 :initial-element 0))
   (prg :accessor prg :initform "")
   (pc :accessor pc :initform 0)))

(defmethod print-object ((vm vm) stream)
  (print-unreadable-object (vm stream)
    (with-accessors ((ptr ptr) (mem mem) (prg prg) (pc pc)) vm
      (format stream "pc: ~a ptr: ~a *ptr: ~a" pc ptr (aref mem ptr)))))

(defmethod init-vm ((vm vm) program)
  (setf (ptr vm) 0)
  (setf (mem vm) (make-array 2000 :initial-element 0))
  (setf (prg vm) program)
  (setf (pc vm) 0))

(defun interpret (program)
  "interpret bf program"
  (let ((vm (make-instance 'vm)))
    (init-vm vm program)
    (interpret-iter vm t)))

(defmethod interpret-iter ((vm vm) &optional debug)
  (when debug
    (format t "vm: ~a" vm))
  (with-accessors ((ptr ptr) (mem mem) (prg prg) (pc pc)) vm
    (cond
     ((>= pc (length prg)) 'eof)
     (t
      (let ((op (aref prg pc)))
	(setf pc
	  (ecase op
	    ((#\> #\< #\+ #\- #\.)
	     (ecase op
	       (#\> (incf ptr))
	       (#\< (decf ptr))
	       (#\+ (incf (aref mem ptr)))
	       (#\- (decf (aref mem ptr)))
	       (#\. (format t "~a" (code-char (aref mem ptr)))))
	     (1+ pc))
	    (#\[
	     (if (= 0 (aref mem ptr))
		 (position #\] prg :start pc)
	       (1+ pc))) ;; ignore nested []
	    (#\]
	     (if (not (= 0 (aref mem ptr)))
		 (position #\[ prg :from-end t :end pc)
	       (1+ pc)))))
	(interpret-iter vm debug))))))

次は、マクロと組み合わせてコンパイラを作ればいいのか。

いろいろな人の実装をさんざん眺めた後だが、手を動かすことで少し賢くなった気がする。


（続く）