lua で Y コンビネータ
function Y(f) return function(a) return f(Y(f), a); end; end f = Y(function(f, n) if n <= 0 then return 1 else return n*f(n-1); end; end) f(10) # => 3628800
ふむふむ。
これを複数引数にするにはどうするか。とりあえず可変長引数を利用してみるがもうひとつ上手くない。もっと良い手がある気がするが、可変長引数を多値にして渡す方法がよくわからん。いったん可変長引数にしてしまうと多値にはならない気がする。
Y = function(f) return function(...) return f(Y(f), arg); end; end f = Y(function(f, tbl) local n = tbl[1]; local res = tbl[2]; if n <= 0 then return res else return f(n-1, n*res); end; end) f(10, 1) # => 3628800
うーん、もうひとつ美しくないなぁ。最大限の見積を考慮して10コくらいあらかじめ Y コンビネータ側で引数を持っておく手しかないのかな？
Y = function(f) return function(a, b, c, d, e) return f(Y(f), a, b, c, d, e); end; end f = Y(function(f, n, res) if n <= 0 then return res else return f(n-1, n*res); end; end) return f(10, 1) 3628800
引数上限5コ版。うーん美しくない。
ldo(2) 返り値
さて、 luaD_call に戻る。 firstResult が NULL でないとき、つまり C 関数のときは、各個の C 関数が適切な処理をしてくれるわけでこちらは関知しなくてよい。そうでないときは luaV_execute を実行するが、これも考えなくてよい。おおむね、 CallInfo にあるプログラムカウンタのところから実行していくだけだろうと推測されるし。
すべてが終ったら、 luaD_poscall で返り値をチェックしないといけない。
lua では多値を返すことができる。そこで、実際に「いくつの変数で結果を受けるか」という想定がないと返り値を適切に処理することができない。これが luaD_call の nResults であり、 luaD_poscall の wanted である。
void luaD_poscall (lua_State *L, int wanted, StkId firstResult) {
StkId res;
if (L->hookmask & LUA_MASKRET)
firstResult = callrethooks(L, firstResult);
res = L->base - 1; /* res == final position of 1st result */
L->ci--;
L->base = L->ci->base; /* restore base */
/* move results to correct place */
while (wanted != 0 && firstResult < L->top) {
setobjs2s(res++, firstResult++);
wanted--;
}
while (wanted-- > 0)
setnilvalue(res++);
L->top = res;
}返り値は firstResult から順に積まれているが、これを res にコピーする。 res はもともとの関数の呼出しの base である(baseは積まれるたびにインクリメントされるから、実際の始点は1だけ小さい)。あとは while ループでコピーしていくだけだ。ただ、 lua では、想定していた返り値の数よりも実際の返り値の方が少ないこともある。たとえば、
function f() return 1; end a, b = f()
みたいなケースだ。この場合には、次の while ループで nil がセットされる。
ldo にはまだあと resume や yield といったトピックもあるのだが、これはややこしそうなので後回しにしたい。次は lopcode から VM 命令を調べ、 lvm を見るかな。
しかし、スタック操作は図に書かないとわかりづらいな。
ldo
lua の関数呼出しを受け持つのが luaD_call である。しかし、細かいエラー処理を除くと、実際には luaD_precall を実行し、 luaD_poscall しているにすぎない。そのあいだに、 luaV_execute で実際の関数のコードを呼び出しているが、これは lvm のときまで待つ。
というわけで、 luaD_precall を見てみよう。この返り値から C 関数か lua 関数かを識別しているはずである。
StkId luaD_precall (lua_State *L, StkId func) {
LClosure *cl;
ptrdiff_t funcr = savestack(L, func);
if (!ttisfunction(func)) /* `func' is not a function? */
func = tryfuncTM(L, func); /* check the `function' tag method */
if (L->ci + 1 == L->end_ci) luaD_growCI(L);
else condhardstacktests(luaD_reallocCI(L, L->size_ci));
cl = &clvalue(func)->l;
if (!cl->isC) { /* Lua function? prepare its call */
/* lua 関数の処理 */
}
else { /* if is a C function, call it */
/* C 関数の処理 */
}
}全体の概形はこんなふうになっている。まず、関数呼出しのデータが関数型の値かどうかをチェックしている。そうでないときには tryfuncTM を呼び出している。メタテーブルで「関数呼出し」に相当するエントリがあるためである。
luaD_growCI は、 CallInfo のスタックが足りなかったときに realloc で伸ばしている操作。 condhardstacktests は気にしなくてよい。で、ようするに func のデータを取り出して、 isC かどうかを調べていると。 C 関数であれば適当な処理をして値を返す。 lua 関数なら NULL を返すはずである。
先に C 関数の処理を見てみる。
CallInfo *ci;
int n;
luaD_checkstack(L, LUA_MINSTACK); /* ensure minimum stack size */
ci = ++L->ci; /* now `enter' new function */
L->base = L->ci->base = restorestack(L, funcr) + 1;
ci->top = L->top + LUA_MINSTACK;
ci->state = CI_C; /* a C function */
if (L->hookmask & LUA_MASKCALL)
luaD_callhook(L, LUA_HOOKCALL, -1);
lua_unlock(L);
#ifdef LUA_COMPATUPVALUES
lua_pushupvalues(L);
#endif
n = (*clvalue(L->base - 1)->c.f)(L); /* do the actual call */
lua_lock(L);
return L->top - n;ci をひとつ進めて、新しい ci を取り出す(足りなければさっき grow_CI していたはずなのでここで足りないことはない)。で、 ci の値を初期化している。 funcr は restorestack は precall の冒頭で定義されている値で、 stack の始点と func の差を計算したもの。 restorestack はそれを再度足しているので、ようするに base を func の次のスタックとしている。で、 lua_State を引数に関数呼出しを実行しておしまい。 L->top - n というのはどういう意味かというのも後で詳しく見るが、この位置からスタックに積まれているものを、関数呼出しの返り値とするということである。つまり、 n 個の引数を持っている。
では、 lua の関数呼出しを見る。
CallInfo *ci;
Proto *p = cl->p;
if (p->is_vararg) /* varargs? */
adjust_varargs(L, p->numparams, func+1);
luaD_checkstack(L, p->maxstacksize);
ci = ++L->ci; /* now `enter' new function */
L->base = L->ci->base = restorestack(L, funcr) + 1;
ci->top = L->base + p->maxstacksize;
ci->u.l.savedpc = p->code; /* starting point */
ci->u.l.tailcalls = 0;
ci->state = CI_SAVEDPC;
while (L->top < ci->top)
setnilvalue(L->top++);
L->top = ci->top;
return NULL;Proto というのは、その lua 関数のプロトタイプ情報で、引数の数であるとか、可変長引数関数かとか、最大スタックサイズとか、そういった情報を保存している。 adjust_varargs は可変長引数のための関数である。で、
maxstacksize だけスタックを伸ばしても問題ないかチェックし、CallInfo
を取り出す。こちらは maxstacksize だけ top を加えている。で、 CallInfo には lua 関数の呼出しのための機構がいくつかある。 savedpc の pc は program counter だろうから、実行するプログラムカウンタを使う。で、 NULL を返している。
adjust_varargs も見てみる。
static void adjust_varargs (lua_State *L, int nfixargs, StkId base) {
int i;
Table *htab;
TObject nname;
int actual = L->top - base; /* actual number of arguments */
if (actual < nfixargs) {
luaD_checkstack(L, nfixargs - actual);
for (; actual < nfixargs; ++actual)
setnilvalue(L->top++);
}
actual -= nfixargs; /* number of extra arguments */
htab = luaH_new(L, actual, 1); /* create `arg' table */
for (i=0; i<actual; i++) /* put extra arguments into `arg' table */
setobj2n(luaH_setnum(L, htab, i+1), L->top - actual + i);
/* store counter in field `n' */
setsvalue(&nname, luaS_newliteral(L, "n"));
setnvalue(luaH_set(L, htab, &nname), cast(lua_Number, actual));
L->top -= actual; /* remove extra elements from the stack */
sethvalue(L->top, htab);
incr_top(L);
}nfixargs には「ふつうの引数の数」が入る。 top と base の差が実際の引数。つまり関数を呼ぶときには、まず関数オブジェクトを積み、それから引数をぜんぶ積んでから luaD_call するということになる。
ここからは、 lua のマニュアルにある次の挙動をもとに考える。
function f(a, b) end
function g(a, b, ...) end
function r() return 1,2,3 end
g(3) a=3, b=nil, ... --> (nothing)
g(3, 4) a=3, b=4, ... --> (nothing)
g(3, 4, 5, 8) a=3, b=4, ... --> 5 8
g(5, r()) a=5, b=1, ... --> 2 3まず actual が nfixargs より小さい場合。これは g(3) に対応する。このときには、通常の引数である b にも nil が入るように不足ぶんだけ top を伸ばす必要がある。
そうでない場合は actual から nfixargs を引くと、可変長引数の個数になる。が、可変長引数はテーブルとして扱う必要があるからこのままではマズい。そこで、まずテーブルを作成し、順にデータを格納していく。見直してほしいが、 luaH_new では第二引数が数値(配列)部の長さ、第三引数がハッシュの大きさなので、ほぼ配列として使っている。で、順にデータを入れていく。最後に n というキーで varargs の数を入れていた。ちょっと試す。
> function f (...) return arg.n; end > return f() 0 > return f(1) 1 > return f(1, 2, 3) 3 > return f(1, 2, 3, 4, 5) 5
なるほどそのようになっている。
テーブルができたら、可変長引数のぶんだけ top を巻戻して、作成したテーブルをスタックに積む。
ステート(続)
さて、次は ldo に進もうかと思ったが、その前に lua_State の構造の理解が必須だと思ったので先にそれを解説する。
先週は lua_State の初期化を見た。今週はまず、 lua_State の内部データを眺める。
struct lua_State {
CommonHeader;
StkId top; /* first free slot in the stack */
StkId base; /* base of current function */
global_State *l_G;
CallInfo *ci; /* call info for current function */
StkId stack_last; /* last free slot in the stack */
StkId stack; /* stack base */
int stacksize;
CallInfo *end_ci; /* points after end of ci array*/
CallInfo *base_ci; /* array of CallInfo's */
unsigned short size_ci; /* size of array `base_ci' */
unsigned short nCcalls; /* number of nested C calls */
lu_byte hookmask;
lu_byte allowhook;
lu_byte hookinit;
int basehookcount;
int hookcount;
lua_Hook hook;
TObject _gt; /* table of globals */
GCObject *openupval; /* list of open upvalues in this stack */
GCObject *gclist;
struct lua_longjmp *errorJmp; /* current error recover point */
ptrdiff_t errfunc; /* current error handling function (stack index) */
};いろいろある。 StkId というのはこれまで明示的に説明を避けてきたが、ようするに TObject* の別名である。ここではこの StkId と、 CallInfo に着目しよう。
lua はもともとスタックマシンだった。今でもスタックをもとに計算をしている(実際にはVMコードはレジスタマシン)。このスタックを意味するのが stack、stack_last、top、base、stacksizeである。
stack はスタックの始点、stack_lastはスタックの終点、 stacksize はスタックの大きさとなる。で、実際のスタックの利用を示しているのが base と top だ。コメントにもあるように、 base は「現在の関数呼出し」のときのベースになるスタック地点を保存する。それに対して top はスタックが積まれるごとに線型に増えていく値である。関数から戻るときには、 base から top までをクリアすればスタックが空になる、とかいった風情になるのだろう。
CallInfo も似たような構造を持つ。 CallInfo はそもそも関数呼出し情報を保持するデータ構造で、新しく関数が呼び出されると CallInfo にデータが積まれる。 end_ci が終点のポインタ、 size_ci がコールスタックの大きさ、 nCcalls は C 関数呼出しの回数である。
ステート
次はメモリ管理に進もうかと思ったが、読みすすめていくうちに、どうも lua_State の使い方を見ないと正しく理解できないのではないかと思った。そこで先に lstate を見て lua_State に簡単に触れる。次に ldo を見て lua のコールスタックの使い方を見る。それから lgc に進むことにする。
lstate.h にはいろんなデータ形式が保存されている。 lua_State は VM ではなく、実際には実行スレッドになっている。したがってコルーチンも lua_State である。グローバルな状態は global_State で抽象化しているので、ここを使って共有しているのだろう。
LUA_API lua_State *lua_open (void) {
lua_State *L = mallocstate(NULL);
if (L) { /* allocation OK? */
L->tt = LUA_TTHREAD;
L->marked = 0;
L->next = L->gclist = NULL;
preinit_state(L);
L->l_G = NULL;
if (luaD_rawrunprotected(L, f_luaopen, NULL) != 0) {
/* memory allocation error: free partial state */
close_state(L);
L = NULL;
}
}
lua_userstateopen(L);
return L;
}luaD_rawrunprotected がちょっと奇妙に見えるかもしれない。これは setjmp を使ってエラーが起きたときの対処をしているものなので、ようするに f_luaopen を呼んでいるのだと考えればよい。実際のメンバの初期化は preinit_state と f_luaopen で行われていて、基本的には 0 や NULL で初期化したり、グローバル変数用のテーブルを作ったり、といったことが行われている。
一方、 lua_State はコルーチンでもあった。そちらには専用の関数がある。
lua_State *luaE_newthread (lua_State *L) {
lua_State *L1 = mallocstate(L);
luaC_link(L, valtogco(L1), LUA_TTHREAD);
preinit_state(L1);
L1->l_G = L->l_G;
stack_init(L1, L); /* init stack */
setobj2n(gt(L1), gt(L)); /* share table of globals */
return L1;
}こちらは f_luaopen を使っていない。 stack_init で L を親としてスタックの初期化を行っている(f_luaopen 内でも自分自身を親にして stack_init は呼ばれている)。それからグローバルな状態を L1 にコピーして完了。 f_luaopen では実際にはグローバルな状態を初期化しているので、こちらはその処理が不要なぶん、短い。
lua_State を終了するときの関数は lua_close だ。
LUA_API void lua_close (lua_State *L) {
lua_lock(L);
L = G(L)->mainthread; /* only the main thread can be closed */
luaF_close(L, L->stack); /* close all upvalues for this thread */
luaC_separateudata(L); /* separate udata that have GC metamethods */
L->errfunc = 0; /* no error function during GC metamethods */
do { /* repeat until no more errors */
L->ci = L->base_ci;
L->base = L->top = L->ci->base;
L->nCcalls = 0;
} while (luaD_rawrunprotected(L, callallgcTM, NULL) != 0);
lua_assert(G(L)->tmudata == NULL);
close_state(L);
}基本的には、保有する様々なデータのメモリ領域を開放していくだけなのだが、ユーザデータには問題がある。というのは、ユーザデータは GC にタグつきメソッドを用意することができるからだ。つまりファイナライザである。 luaF_separateudata では所定のタグのあるユーザデータを検出し、 callallgcTM で実行している。終わったら開放しておしまいだ。
luaF_separateudata は lgc で定義されている。また callallgcTM も実体は lgc にあるから、そちらで読むことにする。
関数
lua では関数もファーストクラス値だった。型は次のようになっている。
#define ClosureHeader \
CommonHeader; lu_byte isC; lu_byte nupvalues; GCObject *gclist
typedef struct CClosure {
ClosureHeader;
lua_CFunction f;
TObject upvalue[1];
} CClosure;
typedef struct LClosure {
ClosureHeader;
struct Proto *p;
TObject g; /* global table for this closure */
UpVal *upvals[1];
} LClosure;
typedef union Closure {
CClosure c;
LClosure l;
} Closure;クロージャの実体は CClosure と LClosure 。 CClosure は C の関数呼出しを抽象化したもので、 LClosure は Lua の関数定義を抽象化している。 UpVal というのは、そのクロージャの外の環境に属するがグローバルな環境ではないところにある変数を意味している。
ClosureHeader では、 isC が「Cの関数かどうか」をチェックするフラグになっている。
Lua の関数の細かな情報は UpVal で定義されている。
typedef struct Proto {
CommonHeader;
TObject *k; /* constants used by the function */
Instruction *code;
struct Proto **p; /* functions defined inside the function */
int *lineinfo; /* map from opcodes to source lines */
struct LocVar *locvars; /* information about local variables */
TString **upvalues; /* upvalue names */
TString *source;
int sizeupvalues;
int sizek; /* size of `k' */
int sizecode;
int sizelineinfo;
int sizep; /* size of `p' */
int sizelocvars;
int lineDefined;
GCObject *gclist;
lu_byte nups; /* number of upvalues */
lu_byte numparams;
lu_byte is_vararg;
lu_byte maxstacksize;
} Proto;
typedef struct LocVar {
TString *varname;
int startpc; /* first point where variable is active */
int endpc; /* first point where variable is dead */
} LocVar;このようになっている。だいたいコメントを読めばわかるので略。
クロージャはたぶん、関数実行のときに細かく参照されるのではないかと思う。 lfunc では主に初期化等しかないので、それほど面白くない。面白いのは UpVal を探索する findupval だが、ここは実際の呼出し元がわからないと何をやっているのかわからない気がするのであとまわし。
Lua 論文について
http://www.radiumsoftware.com/0604.html#060407 で紹介されていた論文で、テーブルまわりのことはだいたい説明したように書いてあったことを付記しておく。っていうか先に論文を読めという感じですか。この先登場するであろうVM命令の説明とか、 Upval の説明とかもあってこの論文はなかなかよいです。
全体的に可搬性を上げるため、あんまりトリッキーな C のコードは使わない、という態度が興味深い。たとえば、いくつかの言語(smalltalkの処理系が挙げられていた)では、ポインタの下位ビットが0になっている(4の倍数とかなので)ことに着目してここにオブジェクトの情報を埋め込む。しかしそれはアーキテクチャによって異なるし、C言語上は本当にそうであるという保証はないので、型情報のタグとデータという構造体で表現するのだそうだ。
