Gauche:辞書のプリミティブ

Shiro(2017/07/05 01:43:54 UTC): SRFI:146を実装してて、気づいたことのメモ。

キーと値をマップするデータ構造(<hash-table>とか<tree-map>)のAPIはどうあるべきか、ということについて。

単純に考えると、次の3つがあれば基本的な用は足りる。

  get:     Map, k -> Maybe v
  put!:    Map, k, v -> void
  delete!: Map, k -> void

ところが、実際には「エントリを探しに行って、そのエントリの有無に依存して何かをする」という操作が必要になることがちょくちょくある。例えば「エントリが既に無かった場合にのみ、追加する」という操作を、上のプリミティブだけでやろうとすると、getを呼んでその結果を見てput!を呼ぶことになるが、探索が2度行われることになる。

けれど、エントリを探しに行った時点で辞書内のデータ構造の特定の位置まで到達してるので、そこから直接操作ができると、二度めの探索の手間を省ける。

副作用前提のインタフェースでよくあるのは、put!の代わりに、値を保持する容れ物を返すようにする：

  create!:  Map, k -> Box v

既にエントリがあった場合、Boxにその値が入っているし、エントリが無かった場合はBoxが空だ。ここから、

いかなる場合でも新たな値をセットする (put!の動作)
エントリが無かった場合だけ値を追加する
エントリがあった場合だけ値を変更する
エントリに既にある値を加工する (e.g. hash-table-push! 系統)

等の操作を呼び出し側で選べる。

マップの実装がエントリごとに独立したノードを使っている場合(バケットチェイン方式のハッシュテーブルとか)は、そのノードを返せば良いのでこのインタフェースと相性が良い。自分は確かTcl/Tkがこの方式を採用してるのを見て、あちこちで真似するようになったんじゃなかったかな。

ただ、この方式は、値の容れ物が独立してない場合に使いにくい。オープンアドレス方式のハッシュテーブルとか。根本的な問題は、この方式では「値を入れる場所」というマップの内部的な情報を呼び出し側の手に委ねなければならないところにある。

SRFI:113のset-search!とかSRFI:146のmapping-searchはこの問題を継続渡しを使って解決している。マップの実装に関する情報を明かさないかわり、インタフェースはなかなかに複雑だ。

  Failure :: (v -> Map,v), (v -> Map,v) -> Map,v
  Success :: v, (k, v -> Map,v), (v -> Map,v) -> Map,v
  search: Map, k, Failure, Success

searchはマップからキーkに対応するエントリを探す。

見つからなかった場合、呼び出し側が与えるFailure手続きをコールバックする。引数は二つ、insertとignore手続きで、Failure手続きは、キーkに対する値を新たに挿入したい場合はinsertを、そうでない場合はignoreを呼ぶ。
見つかった場合、呼び出し側が与えるSuccess手続きをコールバックする。引数は三つ、kに対応する値、update手続き、delete手続き。値を置き換えたい場合はupdateを、削除したい場合はdeleteを呼び出す。

クロージャによる抽象化をうまく使って内部実装を隠してるのはいいんだけど、ややこしい。それに、ハッシュテーブルやツリーマップをSchemeだけで実装してる場合はわりと綺麗に書ける可能性があるけど、そうでない場合はちょっとオーバヘッドが気になる。特にクロージャ作成コストが高い処理系では、探索の度にクロージャを複数作るくらいなら、何度も探索する無駄をかけてもナイーブな実装の方が速くなるかもしれない。

Gaucheの場合、Cで書かれたランタイムでもハッシュテーブルやツリーマップを使うので、プリミティブなAPIはCからもアクセスしやすい必要がある。さらに、キーや値がScmObjでない場合も扱える必要がある。

そこで、低レベルAPIとしてはコンテナを返すインタフェースを用意し、

   Op = GET | CREATE | DELETE
   coreSearch : RawMap, RawKey, Op -> Entry

これをラップして、Schemeからも使えるAPIとして次のバリエーションを用意していた。

   ref  : Map, ScmObj, Option ScmObj -> ScmObj
   set! : Map, ScmObj, ScmObj, Flags -> ScmObj
   delete! : Map, ScmObj -> ScmObj

ここで、

refの第3引数はオプショナルなfallback。キーが見つからなかった場合に返す値。省略時はSCM_UNBOUNDが返されるが、これはScheme世界には存在してはいけない値で、C-Scheme界面で捕まえてエラーを投げる必要がある。
set!はキーと値の他にフラグによって動作を変える:
- フラグが無い場合: put!と同じ動作、つまり事前の状態にかかわらずキーと値の関連を挿入
- NO_OVERWRITE: 既にキーを持つエントリがあれば何もしない。無ければ新たにキーと値の関連を挿入。
- NO_CREATE: 既にキーを持つエントリが無かった場合、何もしない。
set!の戻り値は、最終的にキーに関連づけられた値。但しNO_CREATEでキーが存在しなかった場合は、SCM_UNBOUND。
delete!の戻り値は、キーに対する値が存在していた場合はその値、無かった場合はSCM_UNBOUND。

でもって、Scheme世界の方には、当面必要なサブセットの機能だけ見せていた。

  get  : Map, ScmObj, Option ScmObj -> ScmObj
  put! : Map, ScmObj, ScmObj -> Void
  delete! : Map, ScmObj -> Void

つまり

put!については必ず挿入という動作だけ
delete!について、エントリが存在したかどうかという情報は渡されない

SRFI:146を眺めているとこれだけは足りない。

mapping-adjoinは既にエントリが無い場合だけ挿入
mapping-replaceは既にエントリがある場合だけ変更

だけどこれらは高レベルC APIのフラグで対応できるな。

それとは別に、現在の高レベルC APIを眺めていて、set!をNO_OVERWRITEで呼んだ場合に、「既にエントリが存在したか否か」という情報が落ちることに気づいた (渡したvalueと戻り値を比べる方法だと、既に同じvalueを持つエントリが存在したのか、新たにエントリが挿入されたのか区別できない)。使うかどうかはわからないけれど、情報が落ちちゃうのはちと残念だ。これは、「挿入前の値」を返すことにすれば対応できる(エントリが無かった場合はSCM_UNBOUNDが返る)。非互換な変更になるが、Scm_HashTableSetとかScm_TreeMapSetの戻り値を使ってるコードってどのくらいあるかな。(Gaucheの内部で使ってるところはちょっとあるがすぐに直せる)

Last modified : 2017/07/05 10:23:57 UTC