compute-cplを読む

Gaucheのclass.cより引用．

/*
 * compute-cpl
 */
ScmObj Scm_ComputeCPL(ScmClass *klass)
{
    ScmObj seqh = SCM_NIL, seqt = SCM_NIL, ds, dp, result;

    /* a trick to ensure we have <object> <top> at the end of CPL. */
    ds = Scm_Delete(SCM_OBJ(SCM_CLASS_OBJECT), klass->directSupers,
                    SCM_CMP_EQ);
    ds = Scm_Delete(SCM_OBJ(SCM_CLASS_TOP), ds, SCM_CMP_EQ);
    ds = Scm_Append2(ds, SCM_LIST1(SCM_OBJ(SCM_CLASS_OBJECT)));

    SCM_FOR_EACH(dp, klass->directSupers) {
        if (!Scm_TypeP(SCM_CAR(dp), SCM_CLASS_CLASS))
            Scm_Error("non-class found in direct superclass list: %S",
                      klass->directSupers);
        if (SCM_CAR(dp) == SCM_OBJ(SCM_CLASS_OBJECT)
            || SCM_CAR(dp) == SCM_OBJ(SCM_CLASS_TOP))
            continue;
        SCM_APPEND1(seqh, seqt, SCM_CLASS(SCM_CAR(dp))->cpl);
    }
    SCM_APPEND1(seqh, seqt, Scm_ObjectClass.cpl);

    SCM_APPEND1(seqh, seqt, ds);

    result = Scm_MonotonicMerge1(seqh);
    if (SCM_FALSEP(result))
        Scm_Error("discrepancy found in class precedence lists of the superclasses: %S",
                  klass->directSupers);
    return Scm_Cons(SCM_OBJ(klass), result);
}

trick関係っぽいのとエラーチェックを取り除くと

/*
 * compute-cpl
 */
ScmObj Scm_ComputeCPL(ScmClass *klass)
{
    ScmObj seqh = SCM_NIL, seqt = SCM_NIL, ds, dp, result;
    ds = klass->directSupers;

    SCM_FOR_EACH(dp, klass->directSupers) {
        SCM_APPEND1(seqh, seqt, SCM_CLASS(SCM_CAR(dp))->cpl);
    }
    SCM_APPEND1(seqh, seqt, ds);

    result = Scm_MonotonicMerge1(seqh);
    return Scm_Cons(SCM_OBJ(klass), result);
}

こんな感じ？
SCM_APPEND1はgauche.hに，Scm_Delete，Scm_Append2，Scm_MonotonicMerge1はlist.cに定義されている．
直接スーパークラスのCPLのリストに直接スーパークラスのリストをappendしてmerge．mergeの挙動は大まかにこんな感じ．

(monotonic-merge '((a b) (c d))) ; => (a b c d)
(monotonic-merge '((a b) (c b))) ; => (a c b)
(monotonic-merge '((a c) (b c))) ; => (a b c)
(monotonic-merge '((a b) (b a))) ; => #f

このmergeがアルゴリズムの核な気がする．そしたらMonotonic Mergeのコメントの所に

 *  The algorithm is used in C3 linearization of class precedence
 *  calculation

と書いてあった．Scm_MonotonicMerge1 の中身はややこしそうである．うーむ．