Tociyuki::Diary RSSフィード

tociyuki による Perl・Ruby・C++・C で書き散らしたコードを中心に、日常雑記も混在 : B  F  twitter  GitHub  CPAN  本館  公開鍵
 

2018年08月17日

[]左・右再帰と Wirth VM

一個以上の項目をコンマで区切った単純なリストを、 左再帰と右再帰のそれぞれで Yacc 風に記述してみましょう。 話を単純化するため、 item の FIRST 集合はコンマを含まず、 item の FOLLOW 集合と fold_left および foldright の FOLLOW 集合には重なりがないものとします。

/*  "a,b,c" => [seq, [seq, 'a', 'b'], 'c'] */
fold_left : fold_left ',' item  { [seq, $1, $3]; }
          | item                { $1; }
          ;

/*  "a,b,c" => [seq, 'a', [seq, 'b', 'c']] */
foldright : item ',' foldright  { [seq, $1, $3]; }
          | item                { $1; }
          ;

両方ともに LL(1) 文法で書き直すことができます。 どちらの場合でも、 構文を書き直したものを使うため、 生成規則の構文木と欲しい抽象構文木が一致しなくなります。 PEG のように左辺記号で構文木を作るやりかたでは対応できません。 そこで、 相続属性・合成属性としてスタックを使うことにします。 属性文法をあからさまに記入するとうるさくなるので、 属性は暗黙のまま生成規則に渡して戻すものとします。 さらに入力記号をスタックにプッシュし続けていくものとします。 ブレースで囲んだ合成式で、 スタックの末尾から指定個数をポップして、 データ構造を作ってスタックにプッシュすることにします。 こうすることで、 LR オートマトンの reduce 動作の真似が可能になります。 ところで、 LL(1) 文法では、 FIRST 集合と FOLLOW 集合によってどの生成規則を摘要するのかが決定します。 この性質があるので、 LL(1) 文法の構文から LR 遷移表を生成すると、 必ず GOTO 遷移先が 1 つに限定されます。 これが、 スタックから記号を指定個数ポップするだけで良い理由です。

fold_left : item { $1 = pop(1); $1; } foldleft1 ;
foldleft1 : ',' item { $1, $2, $3 = pop(3); [seq, $1, $3]; } foldleft1 | ε ;

foldright : item { $1 = pop(1); $1; } foldrigh1 ;
foldrigh1 : ',' item foldrigh1 { $1, $2, $3 = pop(3); [seq, $1, $3]; } | ε ;

これを、 Wirth VM で動かしてみます。 これまでの終端記号命令 TERMINAL を SHIFT 命令に、 非終端記号命令 NONTERMINAL は APPL 命令に名称を変更します。 APPL 命令は記号ではなく番地を使って、 継続を作ってから番地へジャンプします。 EMPTY 命令はそのままで、 さらに REDUCE 命令を追加します。 命令は 3 オペランド形式です。 suc は一致中の飛び先番地、 alt は不一致中の飛び先番地です。 番地ゼロは特殊な意味をもち、 命令ポインタがゼロになると継続摘要をします。 REDUCE 命令の pop 数は、 スタックの末尾から取り除く個数、 合成ラベルは実装依存ですが、 ここでは取り除いた個数の先頭にラベルをつけたタプルにしてスタックの末尾にプッシュするという簡易動作を考えておきます。 REDUCE 命令は EMPTY 命令と同様に状態を一致状態にします。 今回は使いませんが、 空規則の際のスタック上の記号数を揃える目的で、 EMPTY 命令の第三オペランドには記号を指定できるようにして、 空規則のための記号をスタックへプッシュできるようにしておきます。

           shift     suc,   alt, 終端記号
           appl      suc,   alt, 番地
           empty     suc,     0, (ゼロまたは記号)
           reduce    suc, pop数, 合成ラベル

通常、 コンマ等の区切り記号を合成結果に残すことはないので、 合成の単純化のため、 VM にはあらかじめ shift 命令でスタックへのプッシュを除外する記号を指定できるものとしておきます。 foldright は生成規則から直訳した再帰呼び出しのままの記述です。 fold_left は末尾再帰なのでループにしています。 コンマ記号をシフト対象から除外したので、 REDUCE 命令でスタックからポップする個数が 2 個へ変わります。

vm = WirthVM.new
vm.exclude = {:COMMA => true}
label = {:fold_left => 1, :foldright => 6, :item => 12}
def insn(addr, opcode, x, y, z) WirthVM::Instruction.new(opcode, x, y, z) end
vm.program = [
  insn( 0, :trap,    0,  0, 0),
#fold_left:
  insn( 1, :appl,    2,  0, label[:item]),
  insn( 2, :shift,   3,  5, :COMMA),
  insn( 3, :appl,    4,  0, label[:item]),
  insn( 4, :reduce,  2,     2,:seq),
  insn( 5, :empty,   0,  0, 0),
#foldright:
  insn( 6, :appl,    7,  0, label[:item]),
  insn( 7, :shift,   8, 11, :COMMA),
  insn( 8, :appl,    9,  0, label[:item]),
  insn( 9, :appl,   10,  0, 7),
  insn(10, :reduce,  0,     2,:seq),
  insn(11, :empty,   0,  0, 0),
#item:
  insn(12, :shift,   0,  0, :IDENT),
]
p vm.advance(label[:fold_left], [
  [:IDENT,'a'], [:COMMA], [:IDENT,'b'], [:COMMA], [:IDENT,'c'], [:RPAREN], [:EOF]
], 0).matched #=> [:seq, [:seq, [:IDENT, "a"], [:IDENT, "b"]], [:IDENT, "c"]]
p vm.advance(label[:foldright], [
  [:IDENT,'a'], [:COMMA], [:IDENT,'b'], [:COMMA], [:IDENT,'c'], [:RPAREN], [:EOF]
], 0).matched #=> [:seq, [:IDENT, "a"], [:seq, [:IDENT, "b"], [:IDENT, "c"]]]

VM は Packrat 版を元にしています。 LL(1) 文法用としてメモライズ機構を除去し、 バックトラックによる環境戻しを簡易版にしています。 さらに、 継続とスタックを Array オブジェクトにプッシュ・ポップする方式に変更しました。

class WirthVM
  class Instruction
    attr_accessor :opcode, :x, :y, :z
    def initialize(f, a, b, c) @opcode, @x, @y, @z = f, a, b, c end
  end

  attr_accessor :exclude, :program

  def initialize()
    @program = []
    @exclude = {}
    @exp = nil
    @matched_ques = false
  end

  def matched?() @matched_ques end
  def matched() @exp end

  def advance(ip, input, tp)
    @matched_ques = matched_ques = false
    kont, exp = [], []
    while ip > 0 || ! kont.empty?
      insn = @program[ip > 0 ? ip : kont[-1]]
      x, y = insn.x, insn.y
      case insn.opcode
      when :shift
        matched_ques = (insn.z == input[tp][0])
        if matched_ques
          @exclude.member?(insn.z) or exp << input[tp]
          tp += 1
        end
      when :reduce
        e = exp.slice!(exp.size - y ... exp.size)
        e.unshift insn.z if insn.z
        exp.push e
        matched_ques = true
      when :empty
        exp.push insn.z if Symbol === insn.z
        matched_ques = true
      when :appl
        if ip > 0
          kont.push(kont, exp.size, tp, ip)
          x = y = insn.z
        elsif matched_ques
          kont, _, _, ip = kont.pop(4)
        else
          kont, ep, tp, ip = kont.pop(4)
          exp[ep ... exp.size] = []
        end
      else
        raise "instruction error #{ip} #{insn.opcode}"
      end
      ip = matched_ques ? x : y
    end
    @exp = matched_ques ? exp[0] : nil
    @matched_ques = matched_ques
    self
  end
end

2018年08月13日

[]型記述子ごとの Cheney Copying ゴミ集め (その 2)

ペア・オブジェクトやベクタ・オブジェクトのようにヒープ空間に割り当てるオブジェクトの最小単位のことを LISP の慣例にならってセルと呼ぶことにします。 セルはゴミ集めの処理単位です。 コピー方式のゴミ集め Cheney Copy 算法では、 移動元 from 空間から移動先 space 空間への複製をセル単位でおこない、 移動先空間に移動済みのセル内の全ポインタが指す子供セルをさらに移動していく処理もセル単位でおこないます。

コピー方式では、 セル内のレイアウト情報を、 すなわち割り当てサイズ・セル内の複製範囲・セル内のポインタのありかを、 ゴミ集めが知る必要があります。 小さなセル向けのゴミ集めでは、 セルの複製範囲はセル全体として複製範囲を別に扱うことはありませんが、 大きなセルを扱うときは区別できている方が無駄な複製をせずに済みます。 こうした、 レイアウト情報はセルの型ごとに異なるため、 それを型記述子に記入しておき、 すべてのセルが自身の型記述子を参照しておくのが自然なやりかただと言えます。

組み込み型は定数として実行時に不変ですから、 それらの型記述子をヒープ領域に配置しなくても良いように思えます。 ですが、 現代の Scheme はユーザ定義型を利用でき、 ユーザ定義型の型記述子は実行時に生成されてヒープ空間に配置するのが自然です。 さらに進んで、 組み込み型とユーザ定義型の型記述子の配置場所を区別せず、 両方ともヒープ空間にいれてしまう処理系もあります。 Chibi Scheme もその一つです。

型記述子をヒープ空間にいれることにすると、 ゴミ集めが使うレイアウト情報もゴミ集めの対象になってしまいます。 Chibi Scheme のゴミ集めはマーク & スイープ方式で、 ゴミ集め中にレイアウト情報がヒープ空間内を移動しないので、 ヒープ空間外の定数置き場と同じ感覚で扱えば良いのでした。 再配置ありのコピー方式のゴミ集めでは、 ゴミ集め中にレイアウト情報が移動するのですが、 それでも前回のようなほんの少しの工夫でゴミ集めを動かすことができました。

前回の試みで用いた型記述子は Chibi Scheme のものを流用していたので、 セル内にポインタを連続して配置しなければならない制限を、 そのまま受け継いでいました。 Scheme でペアとベクタだけしか使わないときは、 それで十分ですけど、 例えば Dybvig 3imp のスタック・ベース VM のスタックのようにベクタ内の一部だけがある瞬間に有効にならない大きなオブジェクトを、 マルチ・スレッド対応でヒープ空間に複数配置するには向いていません。 さらに、 C 言語で記述した手続きのコンテキスト構造体をヒープ空間に配置するときには、 必ずしもポインタが連続できるとは限らないため、 ポインタが不連続なときもゴミ集めできるようにしておきたくなります。 そこで、 セルを固定長部分と可変長部分に分けて、 固定長部分内のポインタは不連続に格納してあっても良いことにしましょう。 可変長部分内のポインタは連続していなければなりませんが、 可変長部分内の一部分だけがポインタとして有効化できるようにしましょう。

型記述子へ、 セルのレイアウトを 3 種類に分けて記入することにします。

まず、 セルの割り当てサイズを計算するためのもので、 固定長部分のバイト数を base_size に記入します。 可変長部分は要素スロットごとのバイト数を slot_size にいれます。 セルの割り当てサイズは可変長部のスロットの上限数で決まるものとします。 同じ型でもセルごとに上限値が異なるので、 セルの capacity 欄に入れるものとします。 capacity 欄はセルの固定長部分のどこかにあり、 そのありかを capacity_offset として型記述子に記入することにします。 capacity_offset から capacity 欄の場所を求め、そこから上限値を取り出し、 上限値に slot_size を乗じて、 base_size を加えると、 セルの割り当てバイト数が得られます。 これをワード・アラインメントしてセルの割り当てワード数が求まります。

セルのコピー範囲は 2 つです。 1 つ目は固定長部分で、 固定長部分はセルの先頭側にある約束にしておきます。 よって、 セルの先頭 base_size を 1 つ目おコピー範囲とします。 2 つ目は可変長部分内の有効範囲です。 可変長部分はセルの copy_offset から始まるとします。 copy_offset がゼロのときは可変長部分がなく固定長部分だけからなる約束にしておきます。 コピー範囲は、 セルごとに異なるので、 セルの固定長部分内のどこかに offset 欄と count 欄があるものとします。 その欄のありかを型記述子の offset_offset と count_offset に記入します。 offset_offset がゼロのときは、 オフセットをゼロとして扱います。 例えば、 vector 型は offset_offset はゼロ、 count_offset と capacity_offset は同じ値になって vector-length 手続きが読み取る size 欄のありかにします。 可変長部分のコピー範囲は、 offset 欄の値から count 欄の値の個数分で、 単位は slot_size です。

セルの子ポインタのスキャン範囲も 2 つです。 1 つ目は固定長部分内のポインタで、 型記述子に count_fix 個のポインタのありかを fix 配列に並べます。 2 つ目の可変長部分内のポインタのある範囲は、 コピーと同じセルの offset 欄と count 欄を読みとります。 可変長部分の始まりは scan_offset に記入します。 scan_offset は copy_offset と同じ値にしますが、 可変長リテラルのセルでは scan_offset をゼロにして、 可変長部分にポインタがないことを示します。

/* 型記述子
 *
 *  type->type = <sexp_type_c 自身の型記述子>;
 *  type->ref = SEXP_TYPE;
 *  type->base_size = sizeof(struct sexp_type_c);
 *  type->slot_size = sizeof(size_t);
 *  type->capacity_offset = offsetof(struct sexp_type_c, count_fix);
 *  type->count_offset = offsetof(struct sexp_type_c, count_fix);
 *  type->copy_offset = offsetof(struct sexp_type_c, fix);
 *  他はゼロ
 */
struct sexp_type_c {
    struct sexp_type_c *type;   /* SEXP_TYPE の struct sexp_type_c 構造体へのポインタ */
    size_t ref;                 /* 型の参照値 */
    size_t base_size;           /* 固定長部のバイト数 */
    size_t slot_size;           /* 可変長部のスロットごとのバイト数 */
    size_t capacity_offset;     /* 可変長部の割り当てスロット数 */
    size_t copy_offset;         /* 可変長部の gccopy でコピーの開始場所のオフセット */
    size_t scan_offset;         /* 可変長部の gcscan する開始場所のオフセット */
    size_t count_offset;        /* 可変長部のオフセット値のあるオフセット */
    size_t offset_offset;       /* 可変長部のスロット個数値のあるオフセット */
    size_t count_fix;           /* 固定長部内の gcscan 対象のポインタ数 */
    size_t fix[];               /* 固定長部内のポインタのあるオフセットの列 */
};

コピー方式なので、 セルの割り当て可能なヒープ空間が 2 つ必要です。 space が現在利用中の、 from_space が未使用のヒープ空間とします。

struct sexp_vm_c {
    struct sexp_unknown_c *space, *hole, *top, *from_space, *from_top;
    sexp_t core;            /* 型記述子などの定数入れ */
    sexp_t a, x, f, c, s;   /* ルート集合 */
};

ゴミ集めはルート集合からコピーを開始します。 w はセル割り当て途中の作業変数をルート集合に加えるためのものです。

void
sexp_gc(struct sexp_vm_c *const vm, sexp_t *w)
{
    sexp_gcflip(vm);
    vm->core = sexp_gcscan(vm, vm->core);
    vm->a = sexp_gcscan(vm, vm->a);
    vm->x = sexp_gcscan(vm, vm->x);
    vm->e = sexp_gcscan(vm, vm->e);
    vm->r = sexp_gcscan(vm, vm->r);
    vm->s = sexp_gcscan(vm, vm->s);
    if (w != NULL) *w = sexp_gcscan(vm, *w);
}

gcflip で空間を入れ換えます。 space から hole の間が割り当て済み範囲で、 コピーが進むと hole が space から離れて、 top へ近づいていきます。 空間を入れ換えた直後の空間は空なので、 hole を space 位置にします。

void
sexp_gcflip(struct sexp_vm_c *const vm)
{
    vm->hole = vm->from_top; vm->from_top = vm->top; vm->top = vm->hole;
    vm->hole = vm->from_space; vm->from_space = vm->space; vm->space = vm->hole;
}

gcscan はルート集合の 1 要素のコピーを進めます。 その要素セルが参照しているセルも連鎖してコピーをしていきます。

#define sexp_struct_adr(t,p,f) ((t)((char *)((p).unknown)+(f)))
#define sexp_struct_val(t,p,f) ((f)>0?sexp_struct_adr(t,p,f)[0]:0)

static sexp_t
sexp_gcscan(struct sexp_vm_c *const vm, sexp_t root)
{
    sexp_t scan;
    scan.unknown = vm->hole;
    root = sexp_gccopy(vm, root);
    while (scan.unknown < vm->hole) {
        scan.unknown->type = sexp_gccopy(vm, scan.unknown->type);
        struct sexp_type_c *type = scan.unknown->type.type;
        /* 固定長部内の fix[0...count_fix] オフセットにあるポインタ */
        for (size_t i = 0; i < type->count_fix; i++) {
            sexp_t *child = sexp_struct_adr(sexp_t *, scan, type->fix[i]);
            child[0] = sexp_gccopy(vm, child[0]);
        }
        if (type->scan_offset > 0) {
            /* 可変長部の offset から size 個のポインタ */
            size_t const offset = sexp_struct_val(size_t *, scan, type->offset_offset);
            size_t const count = sexp_struct_val(size_t *, scan, type->count_offset);
            sexp_t *child = sexp_struct_adr(sexp_t *, scan, type->scan_offset);
            for (size_t i = 0; i < count; i++)
                child[i + offset] = sexp_gccopy(vm, child[i + offset]);
        }
        /* 次のセルへスキップ */
        size_t const slot_size = type->slot_size;
        size_t const capacity = sexp_struct_val(size_t *, scan, type->capacity_offset);
        scan.unknown += sexp_cell_skip(type->base_size + capacity * slot_size);
    }
    return root;
}

unknown はセルの先頭スロットの型記述子への参照を持ちます。 sexp_t はセルのスロットの内容で、 ポインタと fixnum のバリアントです。 ポインタは下位 2 ビットがゼロ、 fixnum は下位 1 ビットが 1 のビット・タグで区別します。 他に下位 3 ビットが 6 のビット・タグを失恋対識標等に使います。 組み込み型は型キャストなしで利用できるように共用体 sexp_t にしています。

enum { SEXP_BROKENHEART =  6 };

#define sexp_is_pointer(x) (((x).code&3U)==0)

struct sexp_unknown_c {
    sexp_t type;
};

typedef union {
    uintptr_t code;
    intptr_t fixnum;
    struct sexp_unknown_c *unknown;
    struct sexp_type_c *type;
    struct sexp_pair_c *pair;
    struct sexp_vector_c *vector;
    struct sexp_array_c *array;
    struct sexp_u8vector_c *identifier;
} sexp_t;

/* 型記述子
 *  type->ref = SEXP_PAIR;
 *  type->base_size = sizeof(struct sexp_pair_c);
 *  type->slot_size = sizeof(sexp_t);
 *  type->count_fix = 2U;
 *  type->fix[0] = offsetof(struct sexp_pair_c, head);
 *  type->fix[1] = offsetof(struct sexp_pair_c, tail);
 *  他はゼロ
 */
struct sexp_pair_c {
    struct sexp_type_c *type;
    sexp_t head;
    sexp_t tail;
};

/* 型記述子
 *  type->ref = SEXP_VECTOR;
 *  type->base_size = sizeof(struct sexp_vector_c);
 *  type->slot_size = sizeof(sexp_t);
 *  type->count_fix = 2U;
 *  type->capacity_offset = offsetof(struct sexp_vector_c, size);
 *  type->count_offset = offsetof(struct sexp_vector_c, size);
 *  type->copy_offset = offsetof(struct sexp_vector_c, slot);
 *  type->scan_offset = offsetof(struct sexp_vector_c, slot);
 *  他はゼロ
 */
struct sexp_vector_c {
    struct sexp_type_c *type;
    size_t size;
    sexp_t slot[];
};

struct sexp_array_c {
    struct sexp_type_c *type;
    size_t capacity;
    size_t offset;
    size_t size;
    sexp_t slot[];
};

struct sexp_u8vector_c {
    struct sexp_type_c *type;
    size_t size;
    char slot[];
};

セルは、 ポインタのバイト数でアラインメントします。

static inline size_t
sexp_cell_skip(size_t const n)
{
    return (n + sizeof(struct sexp_unknown_c) - 1) / sizeof(struct sexp_unknown_c);
}

gccopy は、 from_space 空間から space 空間へセルをコピーして、 from_space のセルがあった位置に失恋対を置いて、 どこにセルを移動したか参照できるようにします。 型記述子がコピー済みのときは、 失恋対から移動先の位置を求め、 未コピーのときは from_space 空間に残っている型記述子を求めます。

static sexp_t
sexp_gccopy(struct sexp_vm_c *const vm, sexp_t const x)
{
    union sexp_gccopy_src_c src; 
    sexp_t dst;
    struct sexp_type_c *type;

    if (! sexp_is_pointer(x) || x.unknown < vm->from_space || vm->from_top <= x.unknown)
        return x;
    src.code = x.code;
    if (src.forwarding->tag == SEXP_BROKENHEART)
        return src.forwarding->address;
    if (src.unknown->type.forwarding->tag == SEXP_BROKENHEART)
        type = src.unknown->type.forwarding->address;
    else
        type = src.unknown->type.from;
    size_t const slot_size = type->slot_size;
    size_t const capacity = sexp_struct_val(size_t *, src, type->capacity_offset);
    size_t const offset = sexp_struct_val(size_t *, src, type->offset_offset);
    size_t const count = sexp_struct_val(size_t *, src, type->count_offset);
    dst.unknown = vm->hole;
    /* 割り当てワード数分をスキップ */
    vm->hole += sexp_cell_skip(type->base_size + capacity * slot_size);
    /* 固定長部のコピー */
    memcpy(dst.unknown, src.unknown, type->base_size);
    if (type->copy_offset > 0 && count > 0) {
        /* 可変長部のコピー */
        char *const t = sexp_struct_adr(char *, dst, type->copy_offset);
        char *const s = sexp_struct_adr(char *, src, type->copy_offset);
        memcpy(t + offset * slot_size, s + offset * slot_size, count * slot_size);
    }
    src.forwarding->tag = SEXP_BROKENHEART;
    src.forwarding->address = dst;
    return dst;
}

ゴミ集めのときにだけ、 from_space 内で失恋対が意味を持ち、 space へ移動した先のアドレスを失恋対で追いかけられるようにしておきます。 ゴミ集めが使う型記述子もゴミ集めがコピーをしていくので、 型記述子の移動先を追跡できるようにします。

union sexp_gccopy_src_c {
    struct {
        union {
            struct sexp_type_c *from;
            struct {
                uintptr_t tag;
                struct sexp_type_c *address;
            } *forwarding;
        } type;
    } *unknown;
    struct {
        uintptr_t tag;
        sexp_t address;
    } *forwarding;
    uintptr_t code;
};

2018年08月09日

Oberon システムのゴミ集め

Oberon システムのゴミ集めは完全なマーク & 一括スイープ方式です。 ゴミ集めは協調型タスクとしてスケジュールされ、 ゴミ集め中に他のタスクのスタックは空なので、 全ロード済み MODULE のグローバル変数のポインタをルート・セットに選ぶだけで済んでいて、 スタック走査がない分シンプルです。

ゴミ集めは翻訳器とローダの助けを借りて、 どこがポインタかを追跡していきます。 MODULE のグローバル変数領域中の全ポインタのオフセットのベクタと、 各構造体中のポインタのオフセット・ベクタを翻訳子がローダブル・バイナリに書き込みます。 後者は構造体型記述子に書き込まれます。 ローダがメモリ割り当て領域に合わせて、 これらのアドレスを解決してゴミ集めに備えます。 手続き NEW が構造体型記述子を使って構造体にヒープから領域を割り当てると同時に、 隠しフィールドを 2 つ初期化します。 一方に構造体記述子のアドレスを格納し、 もう一方をマーク・フィールドとしてゼロにします。 これで、 ゴミ集めの仕掛けと準備が整います。

⇒ 構造体記述子の生成部 ORG.Mod PROCEDURE BuildTD

⇒ トップ・スコープのポインタ位置の書き出し部 ORG.Mod PROCEDURE FindPtrs

⇒ 手続き NEW のコード生成 ORG.Mod PROCEDURE New

⇒ ローダ PROCEDURE Load の pointer references が大域変数のポインタベクタのアドレス計算部分、 同 fixup of type descriptors が構造体記述子のアドレス計算部

⇒ 手続き NEW の実行部 Kernel.Mod PROCEDURE New

⇒ ゴミ集めタスク Oberon.Mod PROCEDURE GC

⇒ ゴミ集めマーク・フェーズ Kernel.Mod PROCEDURE Mark

⇒ ゴミ集めスイープ・フェーズ Kernel.Mod PROCEDURE Scan

Oberon-07 は、 これらの仕掛けを簡便に実現するため、 ポインタ型の基本型を構造体型に制限しています。 NEW 手続きで構造体に領域を割り当てると、 先頭に 2 つの隠しフィールドをつけます。 構造体のポインタは先頭フィールドを指し、 隠しフィールドは負のオフセットで参照します。 -8 のオフセットには構造体型記述子のアドレスが格納され、 -4 はマーク用フィールドでゼロに初期化します。 構造体型記述子のオフセット 16 以降に構造体中のポインタ・フィールドのオフセットが並びます。 この並びは -1 で終端されています。 次の例では、 +8 オフセットのフィールドと、 +16 オフセットのそれがポインタ・フィールドであることを表しています。

RECORD
  INTEGER f1;           (*  +0 *)
  INTEGER f2;           (*  +4 *)
  POINTER TO Foo f3;    (*  +8 *)
  INTEGER f4;           (* +12 *)
  POINTER TO Foo f5;    (* +16 *)
END;

        -8    -4    +0    +4    +8    +12   +16
      | tag |mark | f1  | f2  | f3  | f4  | f5  |
         |
         v
        +0                +16   +20   +24
      | NEW 用のヘッダ  |  +8 | +16 |  -1 |

ゴミ集めのマーク・フェーズは、 Deutsch-Schorr-Waite ポインタ反転算法をアレンジして、 マーク・スタックなしでの深さ優先探索マークをおこなっています。 この算法は、 2 つのポインタ current と previous を使います。 リンクを深く潜っていくときは、 current に辿ったポインタを入れ、 元の current の値を previous に入れます。 その際、 辿ったポインタの内容を逆向きに書き直していくので、 ポインタ反転法と呼ばれています。 なお、 Oberon の Kernel.Mark 手続きでは、 previous は変数 q、 current は変数 p としています。

Kernel.Mark のアレンジで巧みなのは、 mark 隠しフィールドの使い方です。 まだ訪れていないときは値がゼロになっており、 訪れた後は、 current ポインタが辿ったフィールドに対応する構造体型記述子中のアドレスを格納してあります。 例えば、 上の構造体の例を複数割り当てて、 f3 フィールドで順にリンクしているとします。 R2.f3 を辿って current を R3 に移したとき、 R2 の mark フィールドが T1 になり、 R2.f3 のポインタが反転して R1 に書き直されます。 mark フィールドには着目しているフィールドのオフセットの入っているタグのアドレスへ順に更新していくので、 ゼロから T1、 T2、 T3 と順に変化していきます。

                    R1
      | tag |  T1 | f1  | f2  | R0  | f4  | f5  |
                     ^
                     +----------+
                                |
                 previous (q)   |
                    v           |
                    R2          |
      | tag |  T1 | f1  | f2  | R1  | f4  | f5  |

                 current (p)
                    v
                    R3
      | tag |   0 | f1  | f2  | nil | f4  | nil |


  tag                T1    T2    T3  
| NEW 用のヘッダ  |  +8 | +16 |  -1 |

mark フィールドは current を一段元に戻すときに使います。 例えば、 R3 のポインタ・フィールドは両方とも nil なので、 ここから深く潜ることはできません。 そこで、 R2 に戻ることにします。 まず、 R3 の mark フィールドへ T3 を書きこみます。 previous の R2 の mark フィールドに T1 が入っているので、 T1 からオフセット +8 を得て、 R2.f3 のアドレスを得ます。 R2.f3 のポインタの値 R1 を戻った後の previous にします。 R2.f3 に current の値を書き込んで、 ポインタ・フィールドの値を復帰させ、 current を R2 にすると一つ浅い段階に戻ります。

                 previous (q)
                    v
                    R1
      | tag |  T1 | f1  | f2  | R0  | f4  | f5  |

                 current (p)
                    v
                    R2
      | tag |  T1 | f1  | f2  | R3  | f4  | f5  |
                                |
                    +-----------+
                    v
                    R3
      | tag |  T3 | f1  | f2  | nil | f4  | nil |


  tag                T1    T2    T3  
| NEW 用のヘッダ  |  +8 | +16 |  -1 |