Gauche:辞書のプリミティブ

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が空だ。ここから、

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

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

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

SRFI:113set-search!とかSRFI:146mapping-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に対応するエントリを探す。

クロージャによる抽象化をうまく使って内部実装を隠してるのはいいんだけど、ややこしい。それに、ハッシュテーブルやツリーマップを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

ここで、

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

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

つまり

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

だけどこれらは高レベル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