Gauche:YAGHG:Introduction
0の状態からGaucheの概観を掴むところまでを簡単に。
前準備
コードを読み始める前にいろいろと用意をしておくと便利だ。
- Gaucheをデバッグ用にコンパイル
- ./configure --enable-multibyte=utf-8 CFLAGS='-g -O0'
- GNU GLOBALなどのツールのセットアップ
- CVSリポジトリをローカルにコピー
ソースコードを読むための技術も参考に。
ターゲットコード
// main.c
#include <gauche.h>
int
main()
{
ScmObj obj;
GC_INIT();
Scm_Init(GAUCHE_SIGNATURE);
obj = Scm_ReadFromCString("... s-expr ...");
Scm_Eval(obj, SCM_OBJ(Scm_UserModule()));
Scm_Exit(0);
return 0;
}
コンパイルするときにはgauche-configを使うと面倒なところを全部やってもらえるので楽なのだが、 シェル上から素で実行するとうまくいかないのでちょっと回りくどい手を使う。
$ sh -c "`gauche-config --cc` -g -O0 `gauche-config -I` -o main main.c `gauche-config -L` `gauche-config -l`"
データの内部表現
最初に見るべきはデータ構造であるので、そこから見ていこう。
ScmObj
ターゲットコードの次の部分によって、文字列で表現されていたS式がGaucheの内部表現へと変換されてobjがそのオブジェクトを指すようになる。
ScmObj obj;
obj = Scm_ReadFromCString("... s-expr ...");
Scm_ReadFromCStringが返すのは数値の内部表現かもしれないし、リストの内部表現かもしれないが、 すべて統一的にScmObj型として扱うことが出来る。
ScmObjの定義はsrc/gauche.hでされている。 src/gauche.hは各種データ型の定義、公開関数の宣言があるため最初に読み始めるファイルとして最適だろう。
137 /* 138 * An opaque pointer. All Scheme objects are represented by 139 * this type. 140 */ 141 typedef struct ScmHeaderRec *ScmObj;
301 /* A common header for heap-allocated objects */
302 typedef struct ScmHeaderRec {
303 ScmByte *tag; /* private. should be accessed
304 only via macros. */
305 } ScmHeader;
130 typedef unsigned char ScmByte;
ヒープに確保されるオブジェクト
ScmObjを一般論から理解するのはちょっと骨が折れるので、ここではまず一つの具体例 --- 文字列の表現 --- を 示すところから始めよう。
ScmObj
+--------------+ ScmString
obj | ... ------00 +------------>+----------------------+
+--------------+ | ScmHeader |
SCM_HEADER | +--------------+ | tag - 3 ScmClass
| tag | ... ------11 +-+------------------>+----------+
| +--------------+ | | |
+----------------------+ | <string> |
body | | | |
+----------------------+ +----------+
| ScmStringBody |
| +------------------+ |
initialBody | | | |
| +------------------+ |
+----------------------+
965 typedef struct ScmStringBodyRec {
966 unsigned int flags;
967 unsigned int length;
968 unsigned int size;
969 const char *start;
970 } ScmStringBody;
971
972 struct ScmStringRec {
973 SCM_HEADER;
974 const ScmStringBody *body; /* may be NULL if we use initial body. */
975 ScmStringBody initialBody; /* initial body */
976 };
977
307 #define SCM_HEADER ScmHeader hdr /* for declaration */
まず着目したいのがobjが指しているScmHeaderが、そのままScmStringの1つ目のフィールドとなっているという点。 すなわちobjをそのままScmStringにキャストできるということだ。とはいえ、上で述べたとおりScmObjはScmString以外のものも指す可能性が あるので無条件にキャストすることは出来ず、あらかじめチェックする必要がある。
if (SCM_STRINGP(obj)) SCM_STRING(obj);
それぞれのマクロの定義は次のようになっている。
986 #define SCM_STRINGP(obj) SCM_XTYPEP(obj, SCM_CLASS_STRING) 987 #define SCM_STRING(obj) ((ScmString*)(obj))
1039 SCM_CLASS_DECL(Scm_StringClass); 1040 #define SCM_CLASS_STRING (&Scm_StringClass)
314 /* Check if classof(OBJ) equals to an extended class KLASS */ 315 #define SCM_XTYPEP(obj, klass) \ 316 (SCM_PTRP(obj)&&(SCM_OBJ(obj)->tag == SCM_CLASS2TAG(klass)))
299 #define SCM_CLASS2TAG(klass) ((ScmByte*)(klass) + 3)
SCM_CLASS_STRINGは上図の<string>(Schemeから見える<string>のこと)に相当する。つまりSCM_STRINGPはScmHeader.tagが<string>を指していることを 確認しているというわけだ。
ところで、なぜクラスオブジェクトの比較を行うのにSCM_CLASS2TAGで「アドレス + 3」などということをしなくてはならないのだろうか。単純なアドレスの比較ではいけないのだろうか。その理由はScmObjが単なるポインタではない点とペアを表すScmPairの構造とにある。
特殊な形態を持つオブジェクト
「ScmObjが単なるポインタではない」のは効率性のためである。0や1といった数値を表すのにわざわざ構造体を用意して……なんてことをやるのはもったいない。 そこで、そういったオブジェクトはデータがアラインメントされるのを利用して直接ScmObjに埋め込まれるようになっている。
4の倍数バイトごとにアラインメントされると仮定すると、あるオブジェクトへのポインタの下位2ビットは常に00になる。 逆に言えばこの2ビットを00以外にしておけば残りビットを自由に扱うことが出来る。Gaucheではこれらのビットを「タグ」と呼び、 次のように割り当てている。
148 /* TAG STRUCTURE 149 * 150 * [Pointer] 151 * -------- -------- -------- ------00 152 * Points to a pair or other heap-allocated objects. 153 * 154 * [Fixnum] 155 * -------- -------- -------- ------01 156 * 30-bit signed integer 157 * 158 * [Character] 159 * -------- -------- -------- -----010 160 * 29-bit 161 * 162 * [Miscellaneous] 163 * -------- -------- -------- ----0110 164 * #f, #t, '(), eof-object, undefined 165 * 166 * [Pattern variable] 167 * -------- -------- -------- ----1110 168 * Used in macro expander. 169 * 170 * [Heap object] 171 * -------- -------- -------- ------11 172 * Only appears at the first word of heap-allocated 173 * objects except pairs. Masking lower 2bits gives 174 * a pointer to ScmClass. 175 */ 176 177 /* Type coercer */
ここでHeap objectの11に注目したい。これがSCM_CLASS2TAGの「アドレス + 3」の正体だ。コメントから特別視されていることが分かる ScmPairの定義を見てみよう。
727 /* Ordinary pair uses two words. It can be distinguished from
728 * other heap allocated objects by checking the first word doesn't
729 * have "11" in the lower bits.
730 */
731 struct ScmPairRec {
732 ScmObj car; /* should be accessed via macros */
733 ScmObj cdr; /* ditto */
734 };
このようにScmPairにはSCM_HEADERが含まれていない。一見これではobjをScmPairにキャストしてよいことを特定できないように思えるが、 objがScmPairを指しているときobj->tagはすなわち((ScmPair*)obj)->carであり、またcarはScmObjであるため絶対に11が現れない (11が現れるのはScmObjが指している先であるScmHeader.tagとしてのみ)事実を利用してSCM_PAIRPが定義できる仕組みとなっている。
747 #define SCM_PAIRP(obj) (SCM_PTRP(obj)&&SCM_TAG(SCM_OBJ(obj)->tag)!=0x03)
コンパイル
内部表現への変換が終わったところで次は評価だ。ターゲットコードの次の部分に相当する。
Scm_Eval(obj, SCM_OBJ(Scm_UserModule()));
Scm_Evalはsrc/vm.cで定義されている。
2930 ScmObj Scm_Eval(ScmObj expr, ScmObj e)
2931 {
2932 ScmObj v = SCM_NIL;
2933 v = Scm_Compile(expr, e);
...
2938 return user_eval_inner(v, NULL);
2939 }
見ての通り、評価はVMコードへのコンパイルとそれの実行という2つのステップに分けられる。
Scm_Compile
Scm_Compileを見てると面白いことが分かる。
64 ScmObj Scm_Compile(ScmObj program, ScmObj env)
65 {
66 return Scm_Apply(SCM_GLOC_GET(compile_gloc), SCM_LIST2(program, env));
67 }
Scm_ApplyはまさにSchemeのapplyだ。つまりGaucheのコンパイラはSchemeで書かれていると言うことになる。
Scm_Applyの第1引数になっているglocとはGlobal LOCation、グローバル環境での束縛を表しているもので compile_glocは次のように定義されている。
312 void Scm__InitCompaux(void)
313 {
314 ScmModule *g = Scm_GaucheModule();
315 ScmModule *gi = Scm_GaucheInternalModule();
...
326 INIT_GLOC(compile_gloc, "compile", gi);
...
331 }
これだけ分かればScm_Compileの定義をSchemeで書き直すことが出来るだろう。 goshで実際に動かしてみよう。
gosh> (apply (with-module gauche.internal compile) (list '(string? "") (interaction-environment))) #<compiled-code %toplevel@0xa156888>
コンパイラ概要
compile関数含め、Gaucheのコンパイラはsrc/compile.scmで定義されている。ファイルの先頭部分に 概要があるので眺めておこう。
src/compile.scm
42 ;;; THE COMPILER
43 ;;;
44 ;;; The main entry point is COMPILE, defined under "Entry point" section.
45 ;;;
46 ;;; compile :: Sexpr, Module -> CompiledCode
47 ;;;
48 ;;; Gauche compiles programs at runtime, so we don't want to spend too
49 ;;; much time in compilation, while we still want to generate as efficient
50 ;;; code as possible.
51 ;;;
52 ;;; Structure of the compiler
53 ;;;
54 ;;; We have 3 passes, outlined here. See the header of each
55 ;;; section for the details.
56 ;;;
57 ;;; Pass 1 (Parsing):
58 ;;; - Converts Sexpr into an intermediate form (IForm).
59 ;;; - Macros and global inlinable functions are expanded.
60 ;;; - Global constant variables are substituted to its value.
61 ;;; - Variable bindings are resolved. Local variables are marked
62 ;;; according to its usage.
63 ;;; - Constant expressons are folded.
64 ;;;
65 ;;; Pass 2 (Optimization):
66 ;;; - Traverses IFrom and modify the tree to optimize it.
67 ;;; - Limited beta-sustitution (local variable substitution and
68 ;;; inline local functions for the obvious cases).
69 ;;; - Closure optimization (generates efficient code for truly local
70 ;;; closures)
71 ;;;
72 ;;; Pass 3 (Code generation):
73 ;;; - Traverses IForm and generate VM instructions.
74 ;;; - Perform instruction combining.
75 ;;; - Perform simple-minded jump optimization.
76 ;;;
1290 ;; compile:: Sexpr, Module -> CompiledCode
1291 (define (compile program module)
1292 (let1 cenv (if (module? module)
1293 (make-bottom-cenv module)
1294 (make-bottom-cenv))
...
1307 (let1 p1 (pass1 program cenv)
1308 (pass3 (pass2 p1)
1309 (make-compiled-code-builder 0 0 '%toplevel #f #f)
1310 '() 'tail)))
1311 )))
各パスの出力結果はcompile-p1などで見ることが出来る。
gosh> ((with-module gauche.internal compile-p1)
'((lambda (x) (cons 1 (vector->list x)))
#(2)))
($call ($lambda[#f;0] (x[1;0])
($asm (CONS)
($const 1)
($call ($gref vector->list)
($lref x[1;0]))))
($const #(2)))
gosh> ((with-module gauche.internal compile-p2)
'((lambda (x) (cons 1 (vector->list x)))
#(2)))
($asm (CONS)
($const 1)
($call ($gref vector->list)
($const #(2))))
gosh> ((with-module gauche.internal compile-p3)
'((lambda (x) (cons 1 (vector->list x)))
#(2)))
args: #f
0 CONSTI-PUSH(1)
1 PRE-CALL(1) 7
3 CONST-PUSH #(2)
5 GREF-CALL(1) #<identifier user#vector->list>; (vector->list x)
7 CONS ; (cons 1 (vector->list x))
8 RET
src/compile.scmとsrc/gencompとsrc/compile.cと
ところで当然の疑問としてsrc/compile.scmはどのようにロードされているのかという話がある。 コンパイラをロードするのにコンパイラが必要という、まさに卵が先か鶏が先かという状態を 解決するのがsrc/gencompだ。
src/gencompはsrc/compile.scmをロードしVMコードの塊としてsrc/compile.cに吐き出すという ことを行う。CVSから取ってきた(src/compile.cを含まない)Gaucheをビルドするのにあらかじめ インストールされたGaucheが必要なのはこのためである。
src/compile.scmを読むに当たって
src/compile.scm中には多くのコメントがあり、コードを追うのを助けてくれる。 ゆえにここではこれ以上詳細に立ち入ることはしないが、いくつか補助的な話題に触れておく。
マクロの実行
compileのように関数として定義されたものはそのままgoshから使えるのだが、 例えばmake-bottom-cenvのようなマクロはgencompによってコンパイル時に展開されてしまい 使うことが出来ない。ダイレクトにgoshでsrc/compile.scmをロードすることも出来ないので、 ここでは安直にsrc/compile.scmをいじって対処する方法を挙げておく。
--- src/compile.scm 13 Aug 2005 06:51:52 -0000 1.33 +++ src/compile.scm 1 Apr 2006 01:18:14 -0000 @@ -33,11 +33,18 @@ ;;; $Id: compile.scm,v 1.33 2005/08/13 06:51:52 shirok Exp $ ;;; -(define-module gauche.internal +(define-module gauche.internal.test (use srfi-2) (use util.match) ) -(select-module gauche.internal) +(select-module gauche.internal.test) +(with-module gauche.internal (export-all)) +(import gauche.internal) + +(define-syntax eval-when + (syntax-rules () + ((_ (situation ...) body ...) + (begin body ...)))) ;;; THE COMPILER ;;;
次のようにロードして使う。
$ gosh -I src -l compile.scm.mod -E 'select-module gauche.internal.test' gosh> (make-bottom-cenv) #(#<module gauche.internal.test> () #f #f)
src/intlib.stub
%insert-bindingなどsrc/compile.scm中で定義されていない関数はCの関数として実装されており、 その多くはsrc/intlib.stubで宣言されている。*.stubなファイルはその名の通りスタブと呼ばれ CとSchemeの橋渡しを行うものである。あわせてsrc/genstubも見ておくとよいだろう。
src/intlib.stub 116 (define-cproc %insert-binding (mod::<module> name::<symbol> value) 117 (call "Scm_Define"))
VM
いよいよVMコードの実行だ。Scm_Compile後の動きを見てみよう。
2836 static ScmObj user_eval_inner(ScmObj program, ScmWord *codevec)
2837 {
...
2844 /* Push extra continuation. This continuation frame is a 'boundary
2845 frame' and marked by pc == &boundaryFrameMark. VM loop knows
2846 it should return to C frame when it sees a boundary frame.
2847 A boundary frame also keeps the unfinished argument frame at
2848 the point when Scm_Eval or Scm_Apply is called. */
2849 CHECK_STACK(CONT_FRAME_SIZE);
2850 PUSH_CONT(&boundaryFrameMark);
...
2869 run_loop();
...
2927 return vm->val0;
2928 }
コンティニュエーションフレーム(後述)を積むなど、いくつかの前処理をしたあとにメインループであるrun_loopを呼び出している。
735 /*===================================================================
736 * Main loop of VM
737 */
738 /*static*/ void run_loop()
739 {
...
769 for (;;) {
770 dispatch:
771 /*VM_DUMP("");*/
772 if (vm->queueNotEmpty) goto process_queue;
773 FETCH_INSN(code);
774 SWITCH(SCM_VM_INSN_CODE(code)) {
775
776 CASE(SCM_VM_CONST) {
...
780 }
781 CASE(SCM_VM_CONST_PUSH) {
...
2460 }
2461 }
ここで命令のフェッチと実行を行っているわけだ。
VMの構成
GaucheのVM構成についてはShiroさんによるドキュメントに詳しい。Gauche-0.8.6とは異なる部分もあるが本質的には変わっていない。
必要なことはすべて書かれているので、以下は蛇足である。
コンティニュエーションフレーム
コンティニュエーション、すなわち(これから呼ぶ関数が戻ってくるべき)現在の継続を保持するフレームである。RET命令と対にして考えると理解しやすいかもしれない。
... A ...
(func)
next-pc -> ... B ...
のようなSchemeコードがあるとき、func呼び出しの前にその時点での継続(次に実行すべきnext-pc)を保存する。 funcが終わりRETするときはこの継続が再開されることになる。
環境フレーム
lambdaによる新しい環境の導入に対応するフレームである。引数フレームと環境フレームヘッダ(Scheme関数の場合)からなる。 ローカル変数への参照を行うLREF(Local REFerence)命令と対にして考えると理解しやすいかもしれない。
次のコードの*1実行時のスタックを考えてみよう。
((lambda (i _)
((lambda (j)
;; *1
i j)
_))
0 1)
(次の図は実際の構造とは少し異なる)
+---------------+
: :
((lambda (i _) : :
+===============+
| 0 |
+---------------+<-----+
| | |
| ENV_HDR | |
| (ScmEnvFrame) | |
| | |
| | |
+===============+ |
((lambda (j) : : | depth/1
: : |
+===============+ |
| 1 | |
i ;; LREF10(depth/offset) +---------------+ |
j);; LREF0(depth = 0/offset) | | |
_)) | ENV_HDR | |
0 1) | | |
up | ---+------+
sp ---->+===============+
| |
| |
| |
命令コード
各命令コードの構造と意味はsrc/vminsn.scmに書かれている。動作を追いたければrun_loop中のCASE文から目的のコードを探せばよい。 実際の動作を見るには各命令コードごとにブレークポイントを仕掛けておいて、ブレークした時点でScm_VMDumpを呼び出すというのが 便利だ。ターゲットコードを対象にしたサンプルはこちら。
$ cat .gdbinit
b main
r
n
n
s
fin
s
n
n
$ grep -n CASE src/vm.c|grep -v "define"|awk -F: '{print "b vm.c:" $1}' >> .gdbinit
$ gdb main
...
(gdb) p Scm_VMDump(Scm_VM())
VM 0x8304db0 -----------------------------------------------------------
pc: 082f1d34 (00000158)
sp: 0x8306018 base: 0x8306000 [0x8306000-0x830fc40]
argp: 0x8306018
val0: #<compiled-code %internal-eval@0x834efc0>
envs:
conts:
0x8306000
env = (nil)
argp = 0x8306000[0]
pc = 0x241f84 (00000000)
base = (nil)
C stacks:
0xbfe41150: prev=(nil), cont=0x8306000
Escape points:
dynenv: ()
Code:
main_code (name=%internal-eval, code=0x82f1d30, size=4, const=1, stack=4):
args: #f
0 CONSTI-PUSH(1)
1 GREF-TAIL-CALL(1) #<identifier user#display>; (display 1)
3 RET
Gauche:YAGHG:VM:Insnも参照するとよいだろう。
動作のトレース
最後に単純なモデルを通してVMがどのように動いて結果を返すのかを見てみよう。
コード
(begin (f (g 1 2) 3) #f) 0 PRE-CALL(2) 12 2 PRE-CALL(2) 8 4 CONSTI-PUSH(1) 5 CONSTI-PUSH(2) 6 GREF-CALL(2) #<identifier user#g>; (g 1 2) 8 PUSH 9 CONSTI-PUSH(3) 10 GREF-CALL(2) #<identifier user#f>; (f (g 1 2) 3) 12 CONSTF-RET
なお、以下の話はf、gともにScheme関数である事を前提とする。
VMの初期状態
run_loopに入った直後のVMは次のようになっている。
cont ---->+=========+
| |
| C#0 |
| |
sp, argp ---->+=========+
| |
| |
env ----> NULL
pc ----> code[0]
0 PRE-CALL(2) 12
fを呼び出すのだからその前にコンティニュエーションフレームを積んでおかなければならない。 fの継続は#fを返す部分なのでそのインストラクションコードのアドレス(12)を渡している。
+=========+
| |
| C#0 |
| |
cont ---->+=========+
| |
| C#1 |
| |
sp, argp ---->+=========+
| |
| |
env ----> NULL
pc ----> code[2]
2 PRE-CALL(2) 8
今度はg呼び出しのためのコンティニュエーションフレーム。やることは上と変わらない。
+=========+
| |
| C#0 |
| |
+=========+
| |
| C#1 |
| |
cont ---->+=========+
| |
| C#2 |
| |
sp, argp ---->+=========+
| |
| |
env ----> NULL
pc ----> code[4]
4 CONSTI-PUSH(1)
gへ渡す引数を積む。CONSTI-PUSHは複合インストラクションと呼ばれるもので
の2つからなっている。
+=========+
| |
| C#0 |
| |
+=========+
| |
| C#1 |
| |
cont ---->+=========+
| |
| C#2 |
| |
argp ---->+=========+
| 1 |
sp ---->+---------+
| |
| |
env ----> NULL
pc ----> code[5]
val0 ----> 1
5 CONSTI-PUSH(2)
+=========+
| |
| C#0 |
| |
+=========+
| |
| C#1 |
| |
cont ---->+=========+
| |
| C#2 |
| |
argp ---->+=========+
| 1 |
+---------+
| 2 |
sp ---->+---------+
| |
| |
env ----> NULL
pc ----> code[6]
val0 ----> 2
6 GREF-CALL(2) #<identifier user#g>; (g 1 2)
関数gの呼び出し。これも複合インストラクションで
- Gauche:YAGHG:VM:Insn:GREF?
- gの値をval0にセット
- Gauche:YAGHG:VM:Insn:CALL
- val0を呼び出し
を行う。
これにより環境フレームヘッダENV_HDRが追加され、引数フレームとあわせて環境フレームが完成した。 pcもgのコードを指すようになり制御が移る。
+=========+
| |
| C#0 |
| |
+=========+
| |
| C#1 |
| |
cont ---->+=========+
| |
| C#2 |
| |
+=========+
| 1 |
+---------+
| 2 |
env ---->+---------+
| |
| ENV_HDR |
| |
sp, argp ---->+=========+
| |
| |
pc ----> g.code[0]
val0 ----> g
gでのRET
gはやるべき事が終わった段階で戻り値をval0にセットした状態でRETする。
これで継続が再開される。以下同じような処理が続くのでコメントは省略。
+=========+
| |
| C#0 |
| |
cont ---->+=========+
| |
| C#1 |
| |
sp, argp ---->+=========+
| |
| |
pc ----> code[8]
val0 ----> (g 1 2)
env ----> NULL
8 PUSH
+=========+
| |
| C#0 |
| |
cont ---->+=========+
| |
| C#1 |
| |
argp ---->+=========+
| (g 1 2) |
sp ---->+---------+
| |
| |
pc ----> code[9]
val0 ----> (g 1 2)
env ----> NULL
9 CONSTI-PUSH(3)
+=========+
| |
| C#0 |
| |
cont ---->+=========+
| |
| C#1 |
| |
argp ---->+=========+
| (g 1 2) |
+---------+
| 3 |
sp ---->+---------+
| |
| |
pc ----> code[10]
val0 ----> 3
env ----> NULL
10 GREF-CALL(2) #<identifier user#f>; (f (g 1 2) 3)
+=========+
| |
| C#0 |
| |
cont ---->+=========+
| |
| C#1 |
| |
+=========+
| (g 1 2) |
+---------+
| 3 |
env ---->+---------+
| |
| ENV_HDR |
| |
sp, argp ---->+=========+
| |
| |
pc ----> f.code[0]
val0 ----> f
fでのRET
cont ---->+=========+
| |
| C#0 |
| |
sp, argp ---->+=========+
| |
| |
env ----> NULL
pc ----> code[12]
val0 ----> (f (g 1 2) 3)
12 CONSTF-RET
+---------+
| |
| |
val0 ----> #f