amazonでコンパイラ関連の本をいくつか購入。
『コンパイラの構成と最適化』はずっと欲しくてしょうがなかったんだけど、
価格があれなんでずっと我慢してた。けどやっぱり最適化のところが読みたくて、
ついにえいやっと買ってしまった・・・。結局買ってしまうんならもっと早く
手に入れるべきだったと後悔。
『Lisp In Small Pieces』 は SchemeでSchemeのインタープリタやコンパイラを作っていく
というような内容(まだほとんど読んでないのであくまで予想)。すごくおもしろそう。
今ちょうど Scheme のインタープリタを作っているので、かなり参考になると思われます。
出だしの部分はSICPの第4章でやってた超循環インタープリタの話を少し突っ込んで解説しているような
感じ。
『デバッガの理論と実装』はコンパイラとはあまり関係ないか。でも買おうと思った時に絶版に
なってたりしたらいやなので購入。
読んだらまた感想かきます。
- 作者: 中田育男
- 出版社/メーカー: 朝倉書店
- 発売日: 1999/09
- メディア: 単行本
- 購入: 3人 クリック: 42回
- この商品を含むブログ (40件) を見る
- 作者: Christian Queinnec
- 出版社/メーカー: Cambridge University Press
- 発売日: 2010/11/18
- メディア: ペーパーバック
- 購入: 2人 クリック: 61回
- この商品を含むブログ (4件) を見る
デバッガの理論と実装 (ASCII SOFTWARE SCIENCE Language)
- 作者: ジョナサン・B.ローゼンバーグ,Jonathan B. Rosenberg,吉川邦夫
- 出版社/メーカー: アスキー
- 発売日: 1998/02
- メディア: 単行本
- 購入: 8人 クリック: 108回
- この商品を含むブログ (31件) を見る
3imp ((lambda(x) x) 9) が実行される様子
3impの3章に出ているスタックベースのSchemeVMで ((lambda(x) x) 9)がどのように実行されるのかみてみた。
コンパイル結果は以下のようになった。
======================================================================== ((lambda (x) x) 9) => (frame (halt) (constant 9 (argument (close 0 (refer-local 0 (return 1)) (apply 1))))) ========================================================================
これをVMに通してみると、
[frame]
display closure と frame と next exp をスタックに順に積む
next exp は halt か return のどちらか、たぶん ←んなこたぁない。
<reg a > --- ()
<reg x > --- (frame (halt) (constant 9 (argument (close 0 (refer-local 0 (return 1)) (apply 1)))))
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr>)
<reg s > --- => 0 [ ]
ret --- (halt)
x --- (constant 9 (argument (close 0 (refer-local 0 (return 1)) (apply 1))))
<call> --- (VM a x f c (push ret (push f (push c s)))) [constant]
定数をaレジスタにセット
(9 を a にセット)
<reg a > --- ()
<reg x > --- (constant 9 (argument (close 0 (refer-local 0 (return 1)) (apply 1))))
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr>)
<reg s > --- => 3 [ ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr>) ]
obj --- 9
x --- (argument (close 0 (refer-local 0 (return 1)) (apply 1)))
<call> --- (VM obj x f c s) [argument]
aレジスタの内容をスタックに積む
(9を積む)
<reg a > --- 9
<reg x > --- (argument (close 0 (refer-local 0 (return 1)) (apply 1)))
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr>)
<reg s > --- => 3 [ ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr>) ]
x --- (close 0 (refer-local 0 (return 1)) (apply 1))
<call> --- (VM a x f c (push a s)) [close]
display closureを作ってaレジスタにセット。
n は クロージャ本体で参照される free var の数。
<reg a > --- 9
<reg x > --- (close 0 (refer-local 0 (return 1)) (apply 1))
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr>)
<reg s > --- => 4 [ ]
3 [ 9 ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr>) ]
n --- 0
body --- (refer-local 0 (return 1))
x --- (apply 1)
<call> --- (VM (closure body n s) x f c (-s n)) [apply]
aレジスタのクロージャの適用(の準備?)。
aレジスタのクロージャの本体部分をとりだしxレジスタにセット
fレジスタにスタックをセット ;; <= これはなんでだっけ？ダイナミックリンク
cレジスタにaレジスタにセットされているクロージャをセット
<reg a > --- #((refer-local 0 (return 1)))
<reg x > --- (apply 1)
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr>)
<reg s > --- => 4 [ ]
3 [ 9 ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr>) ]
n --- 1
<call> --- (VM a (closure-body a) s a s) [refer-local]
ローカル変数の参照。ｆが指すスタックポイントから0番目の要素をaレジスタにセット。
(この場合9)
<reg a > --- #((refer-local 0 (return 1)))
<reg x > --- (refer-local 0 (return 1))
<reg f > --- 4
<reg c > --- #((refer-local 0 (return 1)))
<reg s > --- => 4 [ ]
3 [ 9 ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr>) ]
n --- 0
x --- (return 1)
<call> --- (VM (index f n) x f c s) [return]
スタックの上からn個分は直前の適用で使われた引数なので不要なので、スタックポインタをn個分減らして
新しくスタックトップになった値をxレジスタにセット。トップから２つ目をfレジスタ、3つ目をcレジスタにセット
さらにスタックポインタをその下に戻しておく。
これはframeインストラクションと対になる動き
<reg a > --- 9
<reg x > --- (return 1)
<reg f > --- 4
<reg c > --- #((refer-local 0 (return 1)))
<reg s > --- => 4 [ ]
3 [ 9 ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr>) ]
n --- 1
<call> --- (let ((s (- s n))) (VM a (index s 0) (index s 1) (index s 2) (- s 3))) [halt]
aレジスタの値を結果として返す。
<reg a > --- 9
<reg x > --- (halt)
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr>)
<reg s > --- => 0 [ ]
で、最終的に9が返って処理終了。
CUnit2.1.0 libcunit.so.1が見つからない
そろそろテストも書かないといかんなー、というわけで CUnit2.1.0を導入。
早速今作っているSchemeVM用のテストを書いてみた。
gcc -o vmtest vmtest.o -L/usr/local/lib -lcunit
として、できあがったものを実行してみると、エラーがでる。
libcunit.so.1: cannot open shared object file: No such file or directory
/usr/local/libにlibcunit.so.1は確かにあるので、/etc/ld.so.conf をのぞいてみると、
include /etc/ld.so.conf.d/*.conf
となってて、*.confには /usr/local/lib の指定はみあたらない。
cd ld.so.conf.d sudo touch cunit2.1.0.conf vi cunit2.1.0.conf
として適当なファイルを作って、/usr/local/lib という１行を書き込み、sudo ldconfig として無事解決。
3imp で (+ 3 4)を実行してみる
vmで各レジスタやスタックの中身をデバッグプリントするようにしたので入力されたコードが実行される様子がわかりやすくなった。例えば以下のコードは
(run '(+ - * / cons car cdr a) (list + - * / cons car cdr 1) '(+ 3 4))
このように表示される。(日本語のコメントは後から付け加えたもの)
(+ 3 4) => (frame (halt) (constant 4 (argument (constant 3 (argument (refer-free 0 (apply 2)))))))
[frame]
display closure と frame と next exp をスタックに順に積む
next exp は frameがスタックからポップされた後に実行するコード
<reg a > --- ()
<reg x > --- (frame (halt) (constant 4 (argument (constant 3 (argument (refer-free 0 (apply 2)))))))
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1)
<reg s > --- => 0 [ ]
ret --- (halt)
x --- (constant 4 (argument (constant 3 (argument (refer-free 0 (apply 2))))))
<call> --- (VM a x f c (push ret (push f (push c s)))) [constant]
定数をaレジスタにセット
(4 を a にセット)
<reg a > --- ()
<reg x > --- (constant 4 (argument (constant 3 (argument (refer-free 0 (apply 2))))))
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1)
<reg s > --- => 3 [ ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1) ]
obj --- 4
x --- (argument (constant 3 (argument (refer-free 0 (apply 2)))))
<call> --- (VM obj x f c s) [argument]
aレジスタの内容をスタックに積む
(4を積む)
<reg a > --- 4
<reg x > --- (argument (constant 3 (argument (refer-free 0 (apply 2)))))
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1)
<reg s > --- => 3 [ ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1) ]
x --- (constant 3 (argument (refer-free 0 (apply 2))))
<call> --- (VM a x f c (push a s)) [constant]
定数をaレジスタにセット
(3 を a にセット)
<reg a > --- 4
<reg x > --- (constant 3 (argument (refer-free 0 (apply 2))))
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1)
<reg s > --- => 4 [ ]
3 [ 4 ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1) ]
obj --- 3
x --- (argument (refer-free 0 (apply 2)))
<call> --- (VM obj x f c s) [argument]
aレジスタの内容をスタックに積む
(3を積む)
<reg a > --- 3
<reg x > --- (argument (refer-free 0 (apply 2)))
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1)
<reg s > --- => 4 [ ]
3 [ 4 ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1) ]
x --- (refer-free 0 (apply 2))
<call> --- (VM a x f c (push a s)) [refer-free]
free var の参照。レジスタcのdisplay closureに入っている n 番目の値を aレジスタにセット
(この場合<reg c> の 0番目なので、#<subr +>)
<reg a > --- 3
<reg x > --- (refer-free 0 (apply 2))
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1)
<reg s > --- => 5 [ ]
4 [ 3 ]
3 [ 4 ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1) ]
n --- 0
x --- (apply 2)
<call> --- (VM (index-closure c n) x f c s) [apply]
aレジスタにセットされている関数を適用する
(この場合aはプリミティブ関数なので、schemeのapply手続きを使って適用結果を求めて、aレジスタにセットし
xレジスタに (return n)をセットする)
<reg a > --- #<subr +>
<reg x > --- (apply 2)
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1)
<reg s > --- => 5 [ ]
4 [ 3 ]
3 [ 4 ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1) ]
n --- 2
<call> --- (VM (let loop ((i (- n 1)) (lst '())) (if (< i 0) (apply a lst) (loop (- i 1) (cons (index s i) lst))))
(list 'return n) f c s) [return]
スタックの上からn個分は直前の適用で使われた引数なので不要なので、スタックポインタをn個分減らして
新しくスタックトップになった値をxレジスタにセット。トップから２つ目をfレジスタ、3つ目をcレジスタにセット
さらにスタックポインタをその下に戻しておく。
これはframeインストラクションと対になる動き
<reg a > --- 7
<reg x > --- (return 2)
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1)
<reg s > --- => 5 [ ]
4 [ 3 ]
3 [ 4 ]
2 [ (halt) ]
1 [ 0 ]
0 [ #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1) ]
n --- 2
<call> --- (let ((s (- s n))) (VM a (index s 0) (index s 1) (index s 2) (- s 3))) [halt]
aレジスタの値を結果として返す。
<reg a > --- 7
<reg x > --- (halt)
<reg f > --- 0
<reg c > --- #(body #<subr +> #<subr -> #<subr *> #<subr /> #<subr cons> #<subr car> #<subr cdr> 1)
<reg s > --- => 0 [ ]
manコマンドでCライブラリ
Ubuntu 7.04で man fprintf などで、エントリーがない、と言われてしまうことに今更ながら気づいた。
sudo apt-get install manpages-dev
として、表示されるようになった。
