Think Stitch
PRINCIPIA  最近の更新


LispKit Lisp 3 - ポインタ逆転アルゴリズム

ポインタ逆転アルゴリズムを実装してみました. 前回書いた再帰による mark と置き換えられます. 再帰による mark ではスタックを消費しますけど,こちらはマークするリストそのものをスタックとして使うので,リストの長さや深さに関係なく固定長のメモリ領域だけでマークできます.

これは Knuth 先生の The Art of Computer Programming で解説されている Algorithm E をそのまま C にしただけです. ラベルと goto を使ったなかなか素敵なコードです^^;

SECDR-Scheme もこのアルゴリズムを使っていたという記憶があります. 書き換えが多いので,いまの計算機だと性能は出ないかもしれませんが,メモリが少なかった時代は重宝したのでしょう.

void mark(ptr_t p)
{
    ptr_t q, t;
    if (!pair_p(p))
      return;
    t = nil;
 E2:
    mark_pair(p);
/* E3: */
    if (mark_p(p->cdr))
      goto E6;
/* E4: */
    q = (ptr_t)((intptr_t)(p->car) & ~MARK_BIT);
    if (pair_p(q) && !mark_p(q->car)) {
        mark_atom(p);
        p->car = (ptr_t)((intptr_t)t | ((intptr_t)(p->car) & MARK_BIT));
        t = p;
        p = q;
        goto E2;
    }
 E5:
    q = (ptr_t)((intptr_t)(p->cdr) & ~MARK_BIT);
    if (pair_p(q) && !mark_p(q->car)) {
        p->cdr = (ptr_t)((intptr_t)t | ((intptr_t)(p->cdr) & MARK_BIT));
        t = p;
        p = q;
        goto E2;
    }
 E6:
    if (t != nil) {
        q = t;
        if (mark_p(q->cdr)) {
            unmark_atom(q);
            t = (ptr_t)((intptr_t)(q->car) & ~MARK_BIT);
            q->car = (ptr_t)((intptr_t)p | ((intptr_t)(q->car) & MARK_BIT));
            p = q;
            goto E5;
        } else {
            t = (ptr_t)((intptr_t)(q->cdr) & ~MARK_BIT);
            q->cdr = (ptr_t)((intptr_t)p | ((intptr_t)(q->cdr) & MARK_BIT));
            p = q;
            goto E6;
        }
    }           
}
2015/03/23
© 2013,2014,2015 PRINCIPIA Limited