6.1.1 アトム
n 価のアトムとは、名前と n つの順序づいた引数を持つものであった。この処理系で は、これを名前を表す文字列と引数を保持する長さ n の配列とのペアで保持する。配列 のそれぞれの要素は、別のアトム a へのポインタと引数のインデックスを表す自然数 n のペアである。これによって、この引数に一端が接続されたリンクの他端が a の第 n 引 数に接続されていることを表現する。
6.1.2 プロセス
この処理系では、簡単のためにアトムのみからなるプロセスとルールとをそれぞれ別の データ構造で管理している。
分子を作る “,” が可換かつ結合的なので、アトムのみからなるプロセスは本質的にア
第6章 CSLMNtalの実装手法 32 トムの集合である。頻出する以下の操作：
• プロセスへのアトムの追加・削除
• プロセスにあるアトムが含まれいているかの検査
• プロセスから特定のアトム名・価数を持つアトムを次々に (それぞれ定数時間で) 取り出すイテレータを得る
を定数時間で行うため、この処理系ではプロセスを、キーがアトム名・価数のペア、値が アトムの存在表であるようなハッシュテーブルで保持する。存在表とはキーと値のペアで はなくたんにキーが存在するかどうかだけを管理するハッシュテーブルであり、特にここ で用いるのはイテレータの取得・呼び出しが定数時間で行えるようなものである。
6.1.3 存在表
“変化しない文脈の再利用” の実装のため、存在表の提供するイテレータは破壊的変更 に強くなければならない。具体的には：
• そのイテレータの生成後に追加された要素をも取り出すことができる
• そのイテレータの生成後に削除された要素はスキップする
このような存在表はハッシュテーブルと線形リストのペアとして実装することがで きる。
(define-class <set> ()
((hash :init-keyword :hash) (head :init-keyword :head) (tail :init-keyword :tail)))
(define (make-set :optional [type ’eq?]) (let1 tail-cell (cons #f #f)
(make <set>
:hash (make-hash-table type) :head (cons #f tail-cell) :tail tail-cell)))
存在表に要素を追加するときには、ハッシュテーブルにこれを追加したのち、線形リス トの末尾にも破壊的に追加する。
(define (set-add! set key) (unless (set-member? set key)
(hash-table-put! (slot-ref set ’hash) key #t) (set-car! (slot-ref set ’tail) key)
(let1 newtail (cons #f #f)
(set-cdr! (slot-ref set ’tail) newtail) (slot-set! set ’tail newtail))))
存在表から要素を除くときには、ハッシュテーブルからのみこれを削除する。
(define (set-remove! set key)
(hash-table-delete! (slot-ref set ’hash) key))
存在表のイテレータは線形リスト中のあるコンスセルへのポインタを保持し、その car 部 がハッシュテーブルに含まれていればそのオブジェクトを返し、さもなければそのコンス セルを線形リストから破壊的に除いたうえで次のコンスセルについて繰り返す。その後ポ インタを一つ進める。
(define (set-get-iterator set :optional [default #f]) (let ([last-pair (slot-ref set ’head)]
[hash (slot-ref set ’hash)]) (rec (f)
(cond [(not (cddr last-pair)) ;; 末尾に来た default]
[(hash-table-get hash (cadr last-pair) #f) (set! last-pair (cdr last-pair))
(car last-pair)]
[else
(set-cdr! last-pair (cddr last-pair)) (f)]))))
第6章 CSLMNtalの実装手法 34