ひとり勉強会

ひとり楽しく勉強会

VM命令：クロージャ

LUA

お待ちかね？のクロージャの実装です。こんなサンプル行ってみましょう。

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を指すクロージャが出来るので違う感じですね。個人的にはこっちの方が便利だと思います。