Reading Gauche なメモ

gauche

進捗悪い。何が理由で停滞してるのか、というと

  • identifier って何だ
  • module って何だ

というナニ。
朝イチなので、最初らへんから再度掘ってみよう。まず GLOBAL_REF マクロの先頭らへんが以下

#define GLOBAL_REF(v)                                                   \
    do {                                                                \
        ScmGloc *gloc;                                                  \
        FETCH_OPERAND(v);                                               \
        if (!SCM_GLOCP(v)) {                                            \
            VM_ASSERT(SCM_IDENTIFIERP(v));                              \
            gloc = Scm_FindBinding(SCM_IDENTIFIER(v)->module,           \
                                   SCM_IDENTIFIER(v)->name,             \
                                   0);                                  \

v が GLOC (Global LOCation) なオブジェクトでなければ identifier である、という事がキメになっている模様。で、色々と google 先生にお伺いしていたトコロ、

というコンテンツで shiro さんがコメント投入されているのを発見。それによると

  • 束縛はモジュールのハッシュテーブルに
  • identifierはマクロ展開に使われる

との記述あり。あと Gauche のリファレンスの

とか。そういえばどっかで lisp/scheme のリフレクション云々な話をどっかで聞いて SICP でそんなナニが出てくるのをずっと待ってた記憶あり。

横道にソレた

閑話休題。とりあえず上記のソレから分かるのは

  • GLOBAL_REF に渡される引数は GLOC 又は identifier
  • GLOC でない場合、Scm_FindBinding で束縛を解決
  • Scm_FindBinding に渡すのは module と name という属性 (identifier)

で、Scm_FindBinding の中でどうしているか、というと Gauche な文書 (Gauche:グローバル変数参照の最適化) で

Gaucheでは、グローバル変数束縛はmoduleによって管理される。

とあってその直下に

グローバル変数参照は、Scm_FindBinding (module.c) によって解決される。これは指定モジュールおよびそこから可視のモジュール中から、指定された名前に束縛されているGLOC (global location) オブジェクトを探して返すもの。

という説明がある。あるいはソース上にも

  • first, search from the specified module.
  • Next, search from imported modules
  • Then, search from parent modules

というコメントがあって、これはGauche:グローバル変数参照の最適化の

1. 指定モジュール(base)
2. importしているモジュールとその親モジュール
3. 親モジュール

という記述と合致している、のかな??

ロック

Scm_FindBinding 関数では処理のアタマとケツで SCM__INTERNAL_MUTEX_{LOCK, UNLOCK} というマクロを使っている。定義は pthread.h で以下

#define SCM_INTERNAL_MUTEX_LOCK(mutex) \
    pthread_mutex_lock(&(mutex))
#define SCM_INTERNAL_MUTEX_UNLOCK(mutex) \
    pthread_mutex_unlock(&(mutex))

Gauche:グローバル変数参照の最適化によるとおそらく現在は

モジュールアクセス全てに共通するロックをひとつ作って、Scm_FindBindingはそれひとつだけをロックする

という形になっているものと思われる。ちなみに

    (void)SCM_INTERNAL_MUTEX_LOCK(modules.mutex);

な pthread_mutex_lock (unlock も) で使われている mutex は module.c の最初らへんで定義されている以下の構造体のメンバ

/* Global module table */
static struct {
    ScmObj anon_name;       /* Name used for anonymous modules.
                               Symbol '#', set by init */
    ScmHashTable *table;    /* Maps name -> module. */
    ScmInternalMutex mutex; /* Lock for table.  Only register_module and
                               lookup_module may hold the lock. */
} modules = { SCM_UNBOUND, NULL };

とりあえず Scm_FindBinding 関数では lock, unlock のみで使用されているのみ。module.c の先頭にあるコメントでも最適化なソレの記述あり。

続き

買い物から戻ったので作業続行。まず最初に引数な module から symbol なソレを検索

    v = Scm_HashTableRef(m->table, SCM_OBJ(symbol), SCM_FALSE);
    if (SCM_GLOCP(v)) {
        gloc = SCM_GLOC(v);
        if (!SCM_UNBOUNDP(gloc->value)) goto found;
    }

戻りが GLOC なオブジェクトで UNBOUND でなければ gloc が戻る。次は import された module から検索、とある。ただこの処理を通過するのは引数の flags が 0 な場合、になるのかな。ちなみに GLOC_REF マクロでは

            gloc = Scm_FindBinding(SCM_IDENTIFIER(v)->module,           \
                                   SCM_IDENTIFIER(v)->name,             \
                                   0);                                  \

という呼び出し方になってるのでこの処理は通過するはず。引数 module の import 属性は何のリストかな、ってなんだコレハ

        SCM_FOR_EACH(p, module->imported) {
            SCM_ASSERT(SCM_MODULEP(SCM_CAR(p)));
            SCM_FOR_EACH(mp, SCM_MODULE(SCM_CAR(p))->mpl) {
                ScmGloc *g;
                
                SCM_ASSERT(SCM_MODULEP(SCM_CAR(mp)));

二重なループになってるし。これは確かにコスト高いな。ちなみに import 属性は_list of imported modules_というコメントが付いている。import なリストの要素はその car も module になってる事が保証されている訳か。
ええと整理してみると

  • 引数 module の import の要素を順に取り出す
  • import の要素の car は module なオブジェクトである
  • mpl って何だ (Module Precedence List??)
  • てーか imported も mp も ((m1) (m2) (m3)) みたいなリスト??
  • 探索実績があるモジュールは searched に格納されてスルーしている模様

む。探索実績云々については以下がヒント??

    /* keep record of searched modules.  we use stack array for small # of
       modules, in order to avoid consing for typical cases. */
    ScmObj searched[SEARCHED_ARRAY_SIZE];
    int num_searched = 0, i;
    ScmObj more_searched = SCM_NIL;

今見ているバージョンだと 64 個までは searched に格納されてて、それを越えると more_searched に cons されているように見える。そのチェキが以下の手続きか

                for (i=0; i<num_searched; i++) {
                    if (SCM_EQ(SCM_CAR(mp), searched[i])) goto skip;
                }
                if (!SCM_NULLP(more_searched)) {
                    if (!SCM_FALSEP(Scm_Memq(SCM_CAR(mp), more_searched))) {
                        goto skip;
                    }
                }

ふむふむ。あるいは上記な変数の状態が以下のように操作される

                if (num_searched < SEARCHED_ARRAY_SIZE) {
                    searched[num_searched++] = SCM_OBJ(m);
                } else {
                    more_searched = Scm_Cons(SCM_OBJ(m), more_searched);
                }

で、探索の本体が以下か

                m = SCM_MODULE(SCM_CAR(mp));
                v = Scm_HashTableRef(m->table, SCM_OBJ(symbol), SCM_FALSE);
                /* see above comment about the check of gloc->value */
                if (SCM_GLOCP(v) && (g = SCM_GLOC(v))->exported
                    && !SCM_UNBOUNDP(g->value)) {
                    gloc = g;
                    goto found;
                }

ええと、冗長ですがもう一度。引数 module の imported なリストの要素を取り出しつつその要素の car の mpl 属性の要素が mp に格納されている、という事で良いのかなぁ。で、この mp の car が module なオブジェクトになっていてその table 属性についてシンボルを探索している、という事でよろしいでしょうか。
あるいは、上記の処理で (car mp) の table 属性に symbol なエントリがあった場合に

  • GLOC オブジェクトであり
    • v の exported が真で
    • v の value が unbound でない

場合に探索成功としている模様。これでも解決できなかった場合に引数 module の mpl 属性の cdr 以降の要素について探索な手続きを行なっている。あわわわ自分で書いてるんだけど意味わからん。
ってか、どんな意図があってこんなフクザツな事をしてるのだろうか。

続々

Gauche リファレンスの4.11 モジュールに以下な記述を発見。

モジュールは、シンボルを束縛へとマップするオブジェクトで、グローバル変数の解決に影響を与えます。

一応なんとなくは処理の概要が書けそうな気もしますがどうなんだろう。