コルーチン
Luaには「coroutine（コルーチン）」という機能があって、Lua 5.0のVMのデザインもこれを楽に実装するために採用された面もあるらしいので、VMを学ぶにあたって重要なポイントです。こんな機能。
function countUp() local n = 0 while true do coroutine.yield(n) -- 対応するcoroutine.resumeにnを返す n = n+1 end end co = coroutine.create(countUp) repeat f,a = coroutine.resume(co) -- countUp実行開始、あるいはyieldから実行再開 print(a) until a>=10
他の言語でもよくある「スレッド」に似ていますが（実際Luaではコルーチンオブジェクトの型は"thread"だったりします）、coroutine.resume と coroutine.yield を明示的に呼んだ時だけ実行コンテキストが切り替わるのがポイントです。あと、Luaのコルーチンの特徴として、resumeは移る先のコルーチンを指定できますが、yieldではresume元に「戻る」ことしかできないのもポイント。コルーチン達は対称な関係ではなくて、親コルーチンが子コルーチンを「呼び出し」て、子コルーチンは親に「returnする」という「非対称コルーチン」になってるそうです。
コルーチンの実装も、この関係を反映した感じになっています。luaV_execute でVM実行中にcoroutine.resumeを呼び出すと、別のluaV_execute関数を「呼び出し」て、coroutine.yieldで、luaV_executeからreturnして親に戻ります。Luaレベルだとコルーチンという特別な存在ですが、VMレベルだとほぼ普通の関数呼び出しになっちゃってる感じです。
lbaselib.c
第1回あたりで触れたように、コルーチン（thread）を表すデータ構造は、lua_State です。
// lstate.h struct lua_State { ... StkId top; /* first free slot in the stack */ StkId base; /* base of current function */ ... CallInfo *ci; /* call info for current function */ const Instruction *savedpc; /* `savedpc' of current function */ ... };
データスタックや、呼び出し情報スタック、PC（プログラムカウンタ）などなどが入ってます。
coroutine.* の関数の実装は、他の基本ライブラリと一緒にlbaselib.cに収まってます。
coroutine.create(fun)
// lbaselib.c static int luaB_cocreate (lua_State *L) { lua_State *NL = lua_newthread(L); ... lua_pushvalue(L, 1); /* move function to top */ lua_xmove(L, NL, 1); /* move function from L to NL */ return 1; } // lapi.c LUA_API lua_State *lua_newthread (lua_State *L) { ... L1 = luaE_newthread(L); setthvalue(L, L->top, L1); ... }
lua_newthread関数で新しいlua_Stateオブジェクトを作って、呼び出し側スレッドのtopに置きます（coroutine.createの返り値ですね）。新しく作ったスレッドでは、coroutine.createに渡された引数（関数オブジェクトなはず）をスタックに１個だけ置いておきます。
coroutine.resume (前半)
// lbaselib.c static int luaB_coresume (lua_State *L) { lua_State *co = lua_tothread(L, 1); ... r = auxresume(L, co, lua_gettop(L) - 1); ...
luaB_coresume処理の本体はauxresume関数みたいです。
// lbaselib.c static int auxresume (lua_State *L, lua_State *co, int narg) { ... lua_xmove(L, co, narg); ... status = lua_resume(co, narg); ...
lua_xmoveで、coroutine.resumeに渡された引数を呼ばれるコルーチンの方にコピーしてます。続きはlua_resumeで。
// ldo.c LUA_API int lua_resume (lua_State *L, int nargs) { ... status = luaD_rawrunprotected(L, resume, L->top - nargs); ... }
そしてresume関数へ。
// ldo.c static void resume (lua_State *L, void *ud) { StkId firstArg = cast(StkId, ud); CallInfo *ci = L->ci; if (L->status == 0) { /* start coroutine? */ lua_assert(ci == L->base_ci && firstArg > L->base); if (luaD_precall(L, firstArg - 1, LUA_MULTRET) != PCRLUA) return; }
coroutine.createで作ったばっかりのコルーチンのスタックには、関数オブジェクトが１個乗っているだけでした。そこにauxresumeで引数を積んだので、ここで、luaD_precall（OP_CALLやOP_TAILCALLの実装に使われてた補助関数）を呼ぶと、引数の個数や可変長引数などなどの準備が整って、関数の中身の実行開始準備完了状態になります。
コルーチン開始
else { /* resuming from previous yield */ lua_assert(L->status == LUA_YIELD); L->status = 0; if (!f_isLua(ci)) { /* `common' yield? */ /* finish interrupted execution of `OP_CALL' */ lua_assert(GET_OPCODE(*((ci-1)->savedpc - 1)) == OP_CALL || GET_OPCODE(*((ci-1)->savedpc - 1)) == OP_TAILCALL); if (luaD_poscall(L, firstArg)) /* complete it... */ L->top = L->ci->top; /* and correct top if not multiple results */ } else /* yielded inside a hook: just continue its execution */ L->base = L->ci->base; }
coroutine.yieldから実行再開する場合は、coroutine.resumeに渡された引数は、逆に、coroutine.yield関数の「返値」になります。なのでここは、OP_RETURNの補助関数luaD_poscallで、多値の場合の処理などをうまいことやってやります。f_isLuaはC関数からyieldした場合かな？ここは省略。
で、最後に、予告通りluaV_executeでVMのメインループに突入します。
luaV_execute(L, cast_int(L->ci - L->base_ci)); }
どん。
coroutine.yield
この luaV_execute の実行中に coroutine.yield が呼ばれた場合の処理は、親に値と制御を戻すこと。
// lbaselib.c static int luaB_yield (lua_State *L) { return lua_yield(L, lua_gettop(L)); }
lua_yieldへ。
// ldo.c LUA_API int lua_yield (lua_State *L, int nresults) { ... if (L->nCcalls > L->baseCcalls) luaG_runerror(L, "attempt to yield across metamethod/C-call boundary"); L->base = L->top - nresults; /* protect stack slots below */ L->status = LUA_YIELD; ... return -1; }
一番親のスレッドでcoroutine.yieldしようとするとエラーになるようになってます。statusをLUA_YIELDに変えて、return -1。この-1が、「yieldした」ことを意味する値です。実際、luaV_executeの値はこんな風になっていて
// lvm.c void luaV_execute (lua_State *L, int nexeccalls) { ... for (;;) { ... switch (GET_OPCODE(i)) { ... case OP_CALL: { ... switch (luaD_precall(L, ra, nresults)) { case PCRLUA: { ... } case PCRC: { ... } default: { return; /* yield */ }
関数の呼び出し（luaD_precall）でPCRLUA/PCRC以外の値が返るとluaV_executeを抜けるようになっていて、
// ldo.c int luaD_precall (lua_State *L, StkId func, int nresults) { ... else { /* if is a C function, call it */ ... n = (*curr_func(L)->c.f)(L); /* do the actual call */ if (n < 0) /* yielding? */ return PCRYIELD; ... }
luaD_precallの方は、呼んだ関数が負の値を返すとPCRYIELDを返す、と。
lua_State *L に現在のスタックの状態やPCは全て保存されているはずなので、次にluaV_executeしたときにはこの次から実行再開できます。
coroutine.resume (後半)
coroutine.yieldが呼ばれるとluaV_execute→resume→lua_resume→auxresume、とガンガンreturnしてきて、
// lbaselib.c :: auxresume(後半) if (status == 0 || status == LUA_YIELD) { int nres = lua_gettop(co); if (!lua_checkstack(L, nres)) luaL_error(L, "too many results to resume"); lua_xmove(co, L, nres); /* move yielded values */ return nres; } else { lua_xmove(co, L, 1); /* move error message */ return -1; /* error flag */ }
auxresumeで、yieldに渡された引数をauxresumeの返り値として、呼び出し元のスタックにコピーしてます。そしてさらにもう一段returnしたluaB_coresumeで、
// lbaselib.c :: luaB_coresume(後半) r = auxresume(L, co, lua_gettop(L) - 1); if (r < 0) { lua_pushboolean(L, 0); lua_insert(L, -2); return 2; /* return false + error message */ } else { lua_pushboolean(L, 1); lua_insert(L, -(r + 1)); return r + 1; /* return true + `resume' returns */ }
正常にyieldされた場合はtrue、そうでない場合はfalseとエラーメッセージをスタックに置き直す、という処理を行っています。これであとは普通に呼び出し側コルーチンの実行ループに戻ります。
まとめ
- luaV_execute = ひとつひとつのコルーチンの実行ループ
- coroutine.resume = luaV_execute呼び出し
- coroutine.yield = luaV_executeからreturn
シンプル！
Luaソースコード勉強会 (4)
今回は、割と言語のコアな部分だけれど（VMじゃなくて）ライブラリ実装になってる部分を拾っておきます。
おまけ：LuLu (3)
- 今日の成果 → http://hzkr.kokage.cc/lulu3.zip
ちょっとソースコードが酷いですごめんなさい。CALLのコードが３カ所くらいにコピペされてます。あとでちゃんとリファクタリングする。。。
今回読んだ全命令を実装（ただし、メタテーブルの処理は除く）してあります。一応 LuLu の上で動く LuLu の上でLuaのtestディレクトリにあるfib.lua（メモ化）やfactorial.lua（Yコンビネータ）などなどは動くくらいの完成度です。現時点で、１段LuLuをかませると50倍くらい遅くなります。３段くらいするとluluのロードに時間かかりすぎて実質起動しなくなります、メタテーブルちゃんとしたらさらに遅くなりそうですね。何か最適化できるかな。
実装は基本的に読んだことそのまんまですが、いくつかポイントを。ライブラリ関数はLuaそのものの関数を使い回すことにしたので、こんな感じで
function library() return { print = print, string = string, io = io, math = math, os = os, table = table, ... } end
本体のライブラリをわりとそのままLuLu上でも使えるようになりました。対象言語と実装言語が同じだとこの辺り楽でいいですね。
Upvalueについては、GCがどうこうを考えるのは難しいと思ったので、とりあえず、全部のUpvalueを無条件に閉じています。こんな感じの実装。
-- 同じ変数に対しては同じUpvalueを返すための記憶テーブル local uvcache = {} function closeupvals(from) -- upvalueをスタックから逃がす処理 from = from or 0 for k,u in pairs(uvcache) do if from<=k and not rawequal(u.base, u) then u[1] = u.base[u.idx] u.base = u u.idx = 1 uvcache[k] = nil -- 逃がし終わったらテーブルから消す end end end
uvcacheにスタック上のインデックスとUpvalueの対応関係を保持しておいて、RETURNの時にcloseupval関数でUpvalue自身の中に値を逃がしてます。「逃がし終わったらテーブルから消す」のを忘れてるバグに長いこと気づかず苦労しました。
そんなところでしょうか。ではまた次回！
VM命令：まとめ
Lua 5.1 の VM の全命令を分類すると、こうなります。
- 変数/定数コピー
- MOVE, LOADK, LOADNIL
- グローバル
- GETGLOBAL, SETGLOBAL
- 関数呼び出し
- CALL, TAILCALL, RETURN
- 演算子
- ADD, SUB, MUL, DIV, MOD, POW, UNM, NOT, LEN, CONCAT, GETTABLE, SETTABLE
- ジャンプ
- JMP, LOADBOOL, TEST, TESTSET, EQ, LE, LT
- forループ
- FORPREP, FORLOOP, TFORLOOP
- クロージャ
- GETUPVAL, SETUPVAL, CLOSURE, CLOSE
- テーブル
- NEWTABLE, SELF, SETLIST
- 可変長引数
- VARARG
今回直接触れなかった命令は・・・TAILCALLは、末尾関数呼び出しですね。CALLとRETURNをくっつけたような処理をするだけです。NEWTABLE は空テーブル {} を作るだけ、SELF は obj:method(...) 形式の式の最適化のために、テーブルアクセスと変数コピーを同時に行う命令です。SETLIST は {1,2,3} のように配列形式でテーブルに要素を設定するための命令です。かなり巨大なテーブルも書けるように工夫した命令フォーマットになっていましたが、いい加減長くなってきたので詳細は略です。
てなわけで、命令セットは見終わったので、次回はモジュールとコルーチンの辺りを見ていこうと思います。
VM命令：可変長引数
前回可変長の扱いをサボったので今回ちゃんと読むことにしました。
まず、可変長引数の関数が呼び出されたときは、luaD_precall内でその「調整」が行われます。
else { /* vararg function */ int nargs = cast_int(L->top - func) - 1; base = adjust_varargs(L, p, nargs); func = restorestack(L, funcr); /* previous call may change the stack */ }
adjust_varargsは互換性のためのコードが含まれててややこしいですが、そこを省くとこうです。
static StkId adjust_varargs (lua_State *L, Proto *p, int actual) { int nfixargs = p->numparams; ... fixed = L->top - actual; /* first fixed argument */ base = L->top; /* final position of first argument */ for (i=0; i<nfixargs; i++) { setobjs2s(L, L->top++, fixed+i); setnilvalue(fixed+i); } ... }
nfixargsは、関数定義したときの固定引数の個数（function(a,b,...) なら 2）、actualが実際に渡された引数の個数です。これ、何をしているかというと、F=nfixars, A=actualとして、普通に関数呼び出し処理をするとスタックが
base top +-------+-------+-----+-------+-----+-------+---------------------+-- | 引数1 | 引数2 | ... | 引数F | ... | 引数A | +-------+-------+-----+-------+-----+-------+---------------------+--
こうなっているのを、こう
base top +-------+-------+-----+-------+-----+-------+---------------------+-- | nil | nil | ... | nil | ... | 引数A | 引数1 | ... | 引数F | +-------+-------+-----+-------+-----+-------+---------------------+--
固定引数だけ後ろにもっていって、baseとtopもずらします。なので、固定引数へのアクセスは普通の関数の場合と同じにできて、可変長部分へのアクセスは、baseより前を見ればよいことになります。
"..." 式を実装する命令 VARARG の重要部分は以下の通りで、baseの後ろを指定されたレジスタにコピーしているのがわかります。
case OP_VARARG: { int b = GETARG_B(i) - 1; ... for (j = 0; j < b; j++) { if (j < n) { setobjs2s(L, ra + j, ci->base - n + j); } else { setnilvalue(ra + j); } } continue; }
VM命令：クロージャ
お待ちかね？のクロージャの実装です。こんなサンプル行ってみましょう。
function counter() local x = 0 local up = function() x=x+1 return x end local dn = function() x=x-1 return x end return up, dn end up,dn = counter() print(up()) -- 1 print(up()) -- 2 print(dn()) -- 1 print(dn()) -- 0
ポイントは、「upやdnに関数オブジェクトを格納するときに、変数xが外側のcounter関数で定義されてるxを指すという対応関係を保存すること」と、「counter関数が終わったあとも、変数xを壊さないようにすること」、そして、「upとdnでちゃんとxを共有すること」です。Luaでは、この例のxのような、親関数の変数のことを Upvalue と呼びます。
UpValue の構造
クロージャは、関数プロトタイプ（関数のソースコード）とUpValueのリストでできています。
// lobject.h typedef struct LClosure { ClosureHeader; struct Proto *p; UpVal *upvals[1]; } LClosure;
UpValueは、基本的には、TValueへのポインタ v です。
typedef struct UpVal { CommonHeader; TValue *v; /* points to stack or to its own value */ union { TValue value; /* the value (when closed) */ struct { /* double linked list (when open) */ struct UpVal *prev; struct UpVal *next; } l; } u; } UpVal;
valueとprevとnextについては後で考えます。実際、UpValueの値を取り出すGETUPVAL命令の実装は単にvから値を取り出すだけですし、SETUPVALもvに値を設定するだけです。
case OP_GETUPVAL: { int b = GETARG_B(i); setobj2s(L, ra, cl->upvals[b]->v); continue; } case OP_SETUPVAL: { UpVal *uv = cl->upvals[GETARG_B(i)]; setobj(L, uv->v, ra); luaC_barrier(L, uv, ra); continue; }
クロージャの作り方
クロージャを作るための命令は、OP_CLOSURE。
case OP_CLOSURE: { Proto *p; Closure *ncl; int nup, j; p = cl->p->p[GETARG_Bx(i)]; nup = p->nups; ncl = luaF_newLclosure(L, nup, cl->env); ncl->l.p = p;
まずオペランドBxでprotoオブジェクトが指定されているので、取り出します。次に、Upvalueリストを埋めます。
for (j=0; j<nup; j++, pc++) { if (GET_OPCODE(*pc) == OP_GETUPVAL) ncl->l.upvals[j] = cl->upvals[GETARG_B(*pc)]; else { lua_assert(GET_OPCODE(*pc) == OP_MOVE); ncl->l.upvals[j] = luaF_findupval(L, base + GETARG_B(*pc)); } }
CLOSURE命令の後ろには、upvalueの個数分だけ、MOVE命令とGETUPVAL命令が続いています。これは普通のMOVEやGETUPVALと違って値のコピー処理を行う命令を意味しているのではなく、CLOSUREに閉じこめるUpvalueの位置を指定するための疑似命令です。GETUPVALなら、現在実行中の関数自身のUpvalueをそのままコピーしてきます。MOVEならば、現在実行中の関数のローカル変数を指すupvalueを作ります。
スタックのB番目を指すUpvalueを作ればいいので、luaF_findupvalのやることは、要するに u.v == base+B な u を作って返すことです。ただし、同じ変数を参照するクロージャが複数あった場合にはupvalueは１つに共通化したいので、同じアドレスに対するupvalueを既に作成済みだった場合、キャッシュしておいた作成済みupvalueを返します。こんな感じ。
UpVal *luaF_findupval (lua_State *L, StkId level) {
...
while (*pp != NULL && (p = ngcotouv(*pp))->v >= level) {
...
if (p->v == level) { /* found a corresponding upvalue? */
...
return p;
}
pp = &p->next;
}
uv = luaM_new(L, UpVal); /* not found: create a new one */
uv->v = level; /* current value lives in the stack */
uv->next = *pp; /* chain it in the proper position */
...
この検索のために、作ったupvalueは検索用のチェイン(next, prev)につないでおくわけなのでした。
"閉じる"
ここまでのところ、Upvalueは単にスタック上の一カ所を指すポインタです。このままだと、親関数がreturnしたあとではそのスタックの内容が無効になってしまいます。そこで、関数から RETURN するタイミングで、Upvalueのデータをスタックから逃がしてやります。クロージャを"閉じる"処理です。
case OP_RETURN: { int b = GETARG_B(i); if (b != 0) L->top = ra+b-1; if (L->openupval) luaF_close(L, base); ... }
luaF_closeがupvalueを閉じていく処理です。
// lfunc.c void luaF_close (lua_State *L, StkId level) { UpVal *uv; global_State *g = G(L); while (L->openupval != NULL && (uv = ngcotouv(L->openupval))->v >= level) { GCObject *o = obj2gco(uv); lua_assert(!isblack(o) && uv->v != &uv->u.value); L->openupval = uv->next; /* remove from `open' list */ if (isdead(g, o)) luaF_freeupval(L, uv); /* free upvalue */ else { unlinkupval(uv); setobj(L, &uv->u.value, uv->v); uv->v = &uv->u.value; /* now current value lives here */ luaC_linkupval(L, uv); /* link upvalue into `gcroot' list */ } } }
長いですけど、値を逃がす処理はここですね。
setobj(L, &uv->u.value, uv->v);
uv->v = &uv->u.value; /* now current value lives here */
ポインタvの指すデータ（スタック）を、自分自身のvalueメンバにコピーしてから、今度はvはvalueを指すようにしてあります。これで、スタックがなくなっても大丈夫です。同じ変数に対応するUpvalueは１つしか作らないように気をつけていたので、同じ変数を2カ所に別々に逃がしてしまうようなこともありません。
ポイントはそこなんですが、これまた興味深いのが、ソースにちらちら見える "GC" や "isdead" という言葉です。作ったクロージャ自身がreturn後には使われないなら、スタックから値を逃がす必要はないんですね。なので、作成からRETURNまでの間にクロージャ自体がGC的に死んでいる判定になっていれば、もう使われないので、逃す処理を行わない、という実装になっています。なるほどー。
逃がし終わったupvalueは
unlinkupval(uv);
でリストから外しています。
なんとなくGauche VMの論文 "Efficient flonum handling on a stack-based VM for dynamically typed languages" を思い出しました。そちらは、浮動小数点数は最初は静的に確保されたメモリ領域に置いといて、関数から逃げることがわかったらヒープにメモリ確保してそっちに移動＆ポインタ差し替え、というお話だったと思います。Luaのは、最初はスタック／レジスタに置いたまま操作して、親関数内ではレジスタ演算として高速に処理できるようにしておいて、関数から逃げる時には別の領域にコピーするという感じ。ふむー。ポインタを途中で差し替えるというのが常套手段なのかな。
あとは、他にRETURN以外のタイミングで明示的に一部の変数を閉じる
case OP_CLOSE: { luaF_close(L, ra); continue; }
OP_CLOSEという命令もありました。ループで先頭に戻る時にループブロック内変数をcloseしたいような状況で呼ばれるんじゃないかと思います。
atode = {} for i=1,3 do atode[i] = function() print(i) end end atode[1]() -- 1 を表示 atode[2]() -- 2 を表示 atode[3]() -- 3 を表示
こういう。これが
... 6 [2] FORPREP 0 5 ; to 12 7 [3] GETGLOBAL 4 -1 ; atode 8 [3] CLOSURE 5 0 ; 003867E0 9 [3] MOVE 0 3 10 [3] SETTABLE 4 3 5 11 [3] CLOSE 3 12 [2] FORLOOP 0 -6 ; to 7 ...
こう。CLOSE 3 で変数 i に対するUpvalueを毎回閉じて、毎回ごとのfooが違うiを指すクロージャになる実装です。JavaScriptとかだと全部同じiを指すクロージャが出来るので違う感じですね。個人的にはこっちの方が便利だと思います。
