学習計画 - 後戻り

教材ではちゃんと AST (Abstract Syntax Tree) を基本的なデータ構造として使っているが、自分は手抜きで S 式を使っていた。このため理解がこんがらがっている、と分かった。本を後ろから前に向かって読むのは良くない。

http://d.hatena.ne.jp/cranebird/20080302/1204430344

Common Lisp の構造体で AST を表現してみる。defstruct を使う。list があるのにツリーを自分で作るのは無駄な気もするが勉強。

(defstruct ast
 op val left right)

op には num, plus-op, minus-op が入る。num の場合は val に数値が入る。演算子 plus-op, minus-op の場合は、left, right のスロットに別の ast か nil が入る。make-ast,ast-p などの関数が自動的に作成される。

この構造体をそのまま使ってもいいが、ちょっと細かくコンストラクタも一緒に作成することにする。

;; 改良版
(deftype operators () `(member num plus-op minus-op))
(defstruct (ast
	    (:constructor make-ast-num (val))
	    (:constructor make-ast-op (op left right)))
  (op 'num :type operators);; NUM PLUS-OP MINUS-OP
  val ;; value for num
  left right)

この定義にすると、make-ast-num と make-ast-op の二つのコンストラクタが作成される。
(deftype を使っているが、type check は実装依存でしたりしなかったり？らしい。)

cl-user(3): (make-ast-num 13)
#S(ast :op num :val 13 :left nil :right nil)
cl-user(4): (make-ast-op 'plus-op (make-ast-num 4) (make-ast-num 3))
#S(ast :op plus-op
       :val nil
       :left #S(ast :op num :val 4 :left nil :right nil)
       :right #S(ast :op num :val 3 :left nil :right nil))

ちゃんとできているみたいだけど、表示が冗長。なので print-object を定義する。

(defmethod print-object ((ast ast) stream)
  "print ast"
  (ecase (ast-op ast)
    (num
     (princ (ast-val ast) stream))
    ((plus-op minus-op)
     (format stream "(~a ~a ~a)" (ast-op ast) (ast-left ast) (ast-right ast)))))

num のときは値のみ、演算子のときは (演算子 left right) という風に表示する。

cl-user(7): (make-ast-op 'plus-op (make-ast-num 4) (make-ast-num 3))
(plus-op 4 3)
cl-user(8): (make-ast-op 'minus-op
			 (make-ast-op 'plus-op (make-ast-num 4) (make-ast-num 3))
			 (make-ast-num 5))
(minus-op (plus-op 4 3) 5)

まるで list で作られた S式そのものに見えているけど、これはれっきとした構造体。

cl-user(10): (describe *)
(minus-op (plus-op 4 3) 5) is a structure of type ast.  It has these slots:
 op                 minus-op
 val                nil
 left               (plus-op 4 3)
 right              5

前回は S 式をコンパイルしていたのを、この AST をコンパイルするようにする。ついでに、マシン語用にも構造体を定義。

(defstruct code
  opcode operand)

(defmethod print-object ((code code) stream)
  "print code"
  (princ "[" stream)
  (princ (code-opcode code) stream)
  (when (code-operand code)
    (princ " " stream)
    (princ (code-operand code) stream))
  (princ "]" stream))

(defvar *max-codes* 100)

(defun compile-ast (ast)
  (compile-ast-iter ast (make-array *max-codes* :element-type 'code :fill-pointer 0)))

(defun compile-ast-iter (ast codes)
  "compile ast"
  (ecase (ast-op ast)
    (num 
     (vector-push (make-code :opcode 'push :operand (ast-val ast)) codes))
    ((plus-op minus-op)
     (let ((inst (ecase (ast-op ast)
		   (plus-op 'add)
		   (minus-op 'sub))))
       (compile-ast-iter (ast-left ast) codes)
       (compile-ast-iter (ast-right ast) codes)
       (vector-push (make-code :opcode inst) codes)
       codes))))

• Lisp のリストの要素も、AST の op ように型情報を持っているはず。シンボルテーブルを参照している？恐らく。
• deftype ってあまり使われていないのだろうか。
• AST とコンスセルの関係は？lisp ではプログラム自体がコンスセルからなるリスト。AST はいらない？
• read. 内部構造を AST、表示を S式っぽくした。次はASTを作る部分。でもそれはほとんど read 関数そのものか？Common Lisp はコンパイラそのものを分解しているのだろう。