位置の外延的表現・内包的表現の区別と考察ノート

オブジェクトの位置の表現方法には、大きく分けて2種類ある。ここではそれを、外延的表現と内包的表現と呼びわけ、ボードゲームの駒の位置の表現を具体例にして、どのような違いがあるかを考えてみる。

今、将棋盤上においてある、王将の位置を表したい。どのような表現が考えられるか。(王将なので、手駒や成りについては考えないこととする。)

ひとつは、将棋盤を2次元配列として用意し、駒の位置に該当する要素として、駒の識別子を代入するものが考えられる。

// コード1
let 将棋盤 = Array.from({ length: 9 }, () => Array.from({ length: 9 }, () => null))
将棋盤[8][4] = "王将"

コード1を実行した結果、 将棋盤 は次のような配列になる。駒の位置は、将棋盤配列上の特定の要素として駒を表す識別子 "王将" を格納することで表現している。このような表現方法を、位置の外延的表現と呼ぶことにする。

[ [ null, null, null, null, null, null, null, null, null ],
  [ null, null, null, null, null, null, null, null, null ],
  [ null, null, null, null, null, null, null, null, null ],
  [ null, null, null, null, null, null, null, null, null ],
  [ null, null, null, null, null, null, null, null, null ],
  [ null, null, null, null, null, null, null, null, null ],
  [ null, null, null, null, null, null, null, null, null ],
  [ null, null, null, null, null, null, null, null, null ],
  [ null, null, null, null, "王将", null, null, null, null ] ]

これは 将棋盤[8][4] == "王将" である点で次の表現と大差ないので、簡潔にこちらを使って考えてもよい。

{ "8": { "4": "王将" } }

もうひとつの方法では、将棋盤を連想配列として用意し、駒に該当する要素として、駒の座標を代入する。

// コード2
let 将棋盤 = {}
将棋盤["王将"] = [4, 8]

コード2を実行した結果、 将棋盤 は次のようなオブジェクトになる。駒の位置を座標で表現するこの方法を、位置の内包的表現と呼ぶことにする。

{ "王将": [4, 8] }

位置の外延的表現と内包的表現の違いですぐ分かるのは、配列の添字と要素の関係が入れ替わっていることだ。外延的表現では、座標が添字、識別子が要素となっている。一方、内包的表現では識別子が添字、座標が要素だ。

このことは、情報へのアクセスの容易さと関わってくる。外延的表現では、位置からオブジェクトを得ることは簡単だが、オブジェクトの位置を得るには配列をスキャンしなければならない。内包的表現ではその逆で、オブジェクトの位置はすぐ分かるが、どの位置に何があるかは、オブジェクト全体をスキャンする必要がある。両方向での参照を高速に行うために、場合によっては、索引を作る必要が出てくる。

アクセスの容易さの他に、添字の空間の違いもある。外延的表現では添字が座標なので、2次元配列を使っている。一方、内包的表現では添字が識別子であるため、連想配列を使っている。つまり、添字の空間構造次第で、使うべきコンテナデータ構造が異なってくる。配列や連想配列を言語機能として備えている言語は多いが、添字空間が広大だったり連続的であるならば、R木のような構造が必要な場合もあるだろう。

オブジェクト指向のデータ表現では、オブジェクトを基準にデータが凝集されるため、素朴に設計すると内包的表現を選びがちではないかという気がする。しかし、それは空間上の現象を上手く表現することが難しいという問題がある。空間上で隣り合ったオブジェクトに作用するといった処理を書くには、将棋盤というオブジェクトを意識し、外延的表現を使う必要が出てくる。

昔作ったリポジトリがフォークされていた話

昔、SQLiteをWebAssembly向けにビルドする例をGitHubに置いていたんだけど、 github.com

先月ごろフォークされて Uno.sqlite-wasm というリポジトリができていた。 github.com

Unoは、UWPアプリをiOSAndroid, WebAssembly上で動かすプラットフォームらしい。

github.com

デモも公開されている。

https://github.com/nventive/Uno#live-webassembly-apps

練習で作ったリポジトリだったので、ドキュメントやコメントはほぼ無かったのに、よく拾い上げてハックしたな、と思った。まあ、シンプルな構成だからドキュメントがなくても理解できるとも思う。

(当のsqlite-wasm, TypeScriptで書いた部分には微妙なこだわりを出していて、普通に型を付けたらポインタが全部number型になるのを避けるために、前回紹介したPhantom property patternを使っていたりする。)