数日前にTwitterで, JavaScriptのオブジェクトに対する===の挙動が初心者には難しいみたいな話を見かけた. 発端や周辺の議論をちゃんと追いかけてないからとくに出典は貼らない. たぶん元々の話は「へぇ, こういう挙動なんだ, 簡単ではないね」くらいの話だったのかもしれない. 自分のタイムラインの観測範囲では「そうだそうだ, (参照の同一性ではなく)同値性にしとけばいいのに」と思っている人もそれなりにいそうに見えた.
個人的にも同値性が簡単に確認できるとよい気はするものの, 「なんでそうしないんだ, オブジェクトの中身を確認していくだけだろ!」みたいな簡単な話ではないことも知っているため, 以下のようなツイートをしたのだった.
JavaScriptのオブジェクトの同値性、再帰的な構造とか作るとぜんぜん自明じゃないんだよなぁ。リンクの構造は違うけどプロパティを辿ったときのパスはどうやっても一致する(観測上は同じに見える)やつを同じとすべき? とか。
— INA Lintaro (@oarat) 2021年8月17日
補足しとくと、x = { a: { a: x } } と x = { a: x } は同じか、みたいなやつ。(同じでいいとおもうがそれをちゃんと判定できるか。)
— INA Lintaro (@oarat) 2021年8月17日
オブジェクトの同値性を判定するメソッドや演算子を実装しようとすると, 再帰的な構造があると困ってしまう*1. なぜなら循環している可能性があるから. 同値性を判定できないと主張したいわけではなくて「同値性をどう定義したらいいか自明ではない」という話.
この記事では, オブジェクトの参照が一致するかを「(参照の)同一性」と呼び, 値が一致するかを「同値性」と呼んで区別する.
同値性の定義のパターン
どういうふうに同値性を定義したらよいか自明ではない根拠として, いくつかパターンを書いておく. 他にも変な定義はいくらでも考えられるとは思うものの, ある程度納得のいくものはこのくらいのバリエーションではないだろうか.
パターン1: 循環のない範囲でのみ同値性を定義する
たとえば, JSONとして有効な範囲内では同値性の判定が可能で, それを逸脱するものに対する判定結果は定義しない, というやり方. 定義として成立はしているものの, なに気なく書いたコードが未定義動作の可能性があって, 字面からはまったく予測できない場合もあるため, 利用者側としては嬉しくない. 個人的には絶対やめてほしい.
パターン2: 循環していたら止まらないのを許す
未定義ではないが無限ループすることがある, とするパターン.
実は同値性判定がこの仕様になっている言語もある. たとえばScala(のcase classや標準ライブラリのコレクション)がそう. Scalaはもともと==で(同一性ではなく)同値性を判定できるが, これを循環構造を持つ値に対してやると==の計算が止まらない.
循環を作るにはいくつかやり方があるが, ふつうにやっていてできるものではなくてvarとかlazy valといった黒魔術的なものを使う必要がある. varの場合はたとえばこういう感じ.
sealed trait List[+A] case class Cons[A](car: A, var cdr: List[A]) extends List[A] case object Nil extends List[Nothing] val l1 = Cons(1, Nil) l1.cdr = l1 val l2 = Cons(1, Cons(1, Nil)) val l3 @ Cons(_, _) = l2.cdr l3.cdr = l2
lazy valはより魔術性が高く, 見た感じ簡単に書ける.
sealed trait List[+A] case class Cons[A](car: A, cdr: List[A]) extends List[A] case object Nil extends List[Nothing] lazy val l1: Cons[Int] = Cons(1, l1) lazy val l2: Cons[Int] = Cons(1, Cons(1, l2))
どちらの場合もl1 == l2は止まらず, varでやった場合はスタックオーバーフローになり, lazy valでやった場合は結果が返ってこない.
Scalaの場合, もう一つ別な方法もあって, LazyListを使うと循環構造に限らず任意の無限リストを実現できる. 循環構造の場合はたとえばこう.
val l1: LazyList[Int] = 1 #:: l1 val l2: LazyList[Int] = 1 #:: 1 #:: l2
この場合もやはりl1 == l2は結果が返ってこない.
LazyListは循環なしの無限リストも表現できて, 自然数全体とかすべての素数を並べたリストみたいなものを作ることもできる.
// 自然数全体 val n = LazyList.from(0) // すべての素数 val p = { def sieve(l: LazyList[Int]): LazyList[Int] = l match { case head #:: tail => head #:: sieve(tail.filter(_ % head != 0)) } sieve(LazyList.from(2)) }
これらは値の種類がそもそも無限にあるから有限の計算で同値性を判定することが(ふつうは)できない. ここまでくるとそもそも「データ」とは言えない(値を取り出すときに計算が起こる)から, 止まらないのもやむなし. おそらく, 一般にはこういう場合もあるからあえて==が必ず止まるような仕様にはしていないのだと思う. 逆に, varもlazy valもLazyListも使っていない, 副作用のない純粋なデータであれば==は止まるはずで, 純粋なデータかどうかは静的にわかるから構わないだろう, ということではないか. そしてvarやlazy valやLazyListはそう滅多に使うものでもない. 僕だったら, 意味なくこれらを使っているコードがあったらレビューでリジェクトする.
一方で, JavaScriptではオブジェクトが副作用の影響を受けうるかどうかは(ソースコード全体をスキャンしない限りは)静的にはわからないだろうし, 破壊的代入は日常的に発生している. 普段から同値性判定が止まらないかもしれないと思いながら暮らしたくはない.
あと, 同値性を数学的な「同値関係」だと思うと, 計算が止まらない値に関しては, 関係が成り立つかどうか未定義であるとするしかなさそう. であれば, パターン1と同様に(静的に区別できるのでなければ)やめてほしい*2.
パターン3: 同じ循環の仕方の場合のみ同値と見なす
アイディアとして, 循環する場合もなんとかして循環のない場合の同値性に帰着させられないか考えてみる.
たとえば
x = { a: { a: x } } y = { a: { a: y } }
のxとyが同値かどうかで考えてみると, 自己参照しているところを●で潰すとどちらも
{ a: { a: ● } }
となり一致する(循環を考慮しない範囲の同値性で一致を確認できる). 一方,
x = { a: x } y = { a: { a: y } }
の場合は,
x = { a: ● } y = { a: { a: ● } }
となり一致しない(という定義にしようとしている).
相互再帰になっている場合, たとえば
x = { a: { a: y } } y = { a: { a: x } }
のような場合も, 自己参照がくるまで展開したらよさそうに一見おもえる. この場合はどちらも
{ a: { a: { a: { a: ● } } } }
になる. しかし実はそれではダメで,
x = { a: { a: y } } y = { a: { a: y } }
の場合にxの方は自己参照なしで延々とyが展開され続けることになる. 実際には「自己参照のところを潰す」のではなく「既に通ったオブジェクトへの参照がきたら潰す」としなければならない.
さらに, ここまでの議論だと「どのオブジェクトが潰されたか」を区別した方がよい感じがする. たとえば
x = { a: { a: y }, b: x } y = { a: { a: x }, b: y }
のときは
(1){ a: { a: (2){ a: { a: ●(1) }, b: ●(2) } }, b: ●(1) }
みたいにしないといけないはず*3.
結局これは何をしているかというと, 通ったオブジェクトを状態, オブジェクトのキーを遷移と思ったときの状態遷移グラフを描いている. グラフの(始点を揃えたときの)形が一致するかどうかが同値かどうかを決める. たとえば最後の例の状態遷移グラフは次のようになる.
これを見れば, グラフをコピーしてひっくり返して重ねるとxとyが一致することがわかる(グラフの形がxとyでちょうど対称になっていることが一目でわかる).
きちんと定義できているし, 一見これで問題ない. ただ個人的には少し気に入らない. この定義だとオブジェクト(の参照)が1対1に対応している場合しか同値と見なさないため「ある2つのオブジェクト(の参照)が同一か否か」の区別が定義に表れてしまっている. 値が一致しているかどうかで判定したいはずが, 同一性を気にしてしまっている. 具体例で言うと, 途中で挙げたこの例
x = { a: { a: y } } y = { a: { a: y } }
は, 状態遷移グラフを描くと以下のようになり
xとyは同値ではないということになる. なぜなら, xの方はx.a.aと辿るとxとは別のオブジェクトが現れるのに対して, yの方はy.a.aするとy自身が返るから, ということになる. これはつまりxとyの参照は異なるという話をしてしまっている.
別な言い方をしてみる. 循環のない
x = { a: { a: 1 } } y = { a: { a: 1 } }
だったらxとyは同値ということで誰も異論はないだろう. しかし1の部分が他のオブジェクトへの参照になった途端, 指している先は同じyなのに, それが自分自身を指しているか否かで同値かどうかが変わってしまう. これは奇妙.
定義として間違っているわけではないが, 奇妙な定義だと言ってよさそう.
パターン4: なるべく多くのものを同値と見なす
パターン3の最後の方で見たこの例
x = { a: { a: y } } y = { a: { a: y } }
は参照の同一性を考えないなら, 同値と見なしてもまったく問題ないように思える. xもyも, どちらもaのキーを辿るとずっとa → a → a → …と無限に続く. こういった場合も含めて「同値と見なして問題ないものはすべて同値と見なす」ようにできないものだろうか? 実はできる.
いったん, 循環のない場合の同値性をあらためて考え直してみる. たとえば,
x = { a: { a: 1 }, b: 2 } y = { a: { a: 1 }, b: 2 }
が同値かどうか判定するにはx.aとy.a, およびx.bとy.bが同値かどうか見ることになる. x.bとy.bはプリミティブ値なのでそのまま値が等しいか比較し, x.aとy.aはオブジェクトなのでまたその中のキーを辿った先が同値かどうか見る. 数学的にはこう定義できる.
定義 : 循環のないオブジェクトの同値性
循環のないオブジェクト中の任意のキー
について,
が存在し,
が成り立つ
中の任意のキー
が存在し,
が成り立つ
どうにかして, この定義を元に循環するオブジェクトに対しても使えるものを作れないだろうか? 実は, この定義はそっくりそのまま循環するオブジェクトに対して適用してもなんの齟齬もない. ただ循環する場合は選択肢があって, たとえば,
x = { a: x } y = { a: y }
の場合, これを同値としてもしなくても, 上に書いた定義の条件に当てはまっている. なぜなら, 同値とした場合はx.aに対してy.aは存在するし, それぞれの指す先はxとyそのもので, たったいま同値ということにしたばかりのものだから条件を満たす. 同値としない場合, x.aの指す先のxはy.aの指す先のyと同値ではないから, aについては条件を満たさず, xとyは同値ではないという結論になり辻褄が合う.
どちらでもよいのなら同値ということにしよう. その方が, 循環している場合も, 辿ったキーの並びが同じものは同値ということにできる. こうやって「同値ということにしても定義上の齟齬がないものはすべて同値とする」という定義にしてしまおう*4.
こう定義すれば, 循環のないオブジェクトに関しては従来通りの同値性となる. 循環する場合は, 同値関係の両辺とも循環し, かつキーを辿ったパスが同じ場合に同値と判定されることになる. どちらか片方が循環しない場合は循環のないオブジェクトの同値性の条件に反する(循環しない方はプリミティブ値になるのにもう片方はオブジェクトになる). どちらも循環する場合は同じキーのパスを辿れさえすれば, キーの存在の条件を満たせるから齟齬はない.
いくつか例を見よう.
x = { a: x } y = { a: { a: y } }
まずxもyもaのキーを持つのでx.aとy.aを見る. x.aは循環しているがy.aはまだ循環していないからまたaを辿る. x.a.aは(再び)循環してy.a.aも循環する. ここまで辿ってきたパスは同じ. どちらも循環しているからこの先どれだけ辿っても同じパスが現れる. だから同値でよい.
x = { a: y, b: 1 } y = { a: { a: y, b: 1 }, b: 1 }
まずx.bとy.bは値が一致する. x.aとy.aはどちらもオブジェクトだからその先を辿る. x.a.bとy.a.bは値が一致する. y.a.aは循環しているがx.a.aはまだ循環していないから先を辿る. x.a.a.bとy.a.a.bは値が一致する. x.a.a.aもy.a.a.aも循環していて, パスも一致している. だから同値でよい.
この定義なら変に参照の同一性を気にすることもなく, 値がどうなっているかだけを見て同値性を判定できているように思える.
ちなみに, Rubyはどうやらこの定義に相当する同値性判定を実装している. 偉い.
x = { a: nil, b: 1 }
y = { a: { a: nil, b: 1 }, b: 1 }
x[:a] = y
y[:a][:a] = y
x == y
# => true
理論的背景: 双模倣による定義
実は, パターン4で見た循環のないオブジェクトの同値性の定義は, オブジェクトを状態, キーを状態遷移と思ったとき*5の状態遷移システムの双模倣性(bisimulation)の定義になっている. そして「同値にしても齟齬がないものは同値とする」として広げていったものは双模倣関係*6(bisimilarity relation)になっていて, これは自動的に同値関係(反射律・対称律・推移律を満たす関係)になる.
こうやって作られた関係は, オブジェクトの同一性を最も粗く区別し, 同時にプリミティブ値はきちんとすべて区別するものになっている.
Proposition 1 yields insight in the concept of deep equality: deep equality is the
equivalence relation which makes the fewest possible distinctions among oids while at the
same time distinguishing among all different basic values such that objects and their
values are identified. Moreover the reader familiar with the theory of communication and
concurrency will have noticed the analogy with the observational equivalence concept of
strong bisimilarity [Mil89].
Deep equality revisited.
Serge Abiteboul and Jan Van den Bussche.
In Deductive and Object-Oriented Databases (DOOD 1995), Singapore, 1995.
先述の同値性のバリエーションはすべて双模倣性(bisimulation)にもなっている(はず). パターン4(双模倣(bisimilarity))はその中でも最大のもので, パターン3は最大でも最小でもない半端なものだということもわかる. 「奇妙」に思えたのはこの半端さに由来する.
双模倣はもともと, 状態遷移システムや(並行)プロセス計算体系で, 観測上の振る舞いが一致することを数学的に扱うために考え出されたもの. だから同じ概念でデータの「値としての振る舞い」の同一性を判別できることも頷ける. もしこの辺りのことをもっと詳しく知りたいなら以下の本を読むといいだろうか.
双模倣による同値性判定の実装例
実は10年くらい前に趣味で作っていたJavaScriptのライブラリ*7で, 双模倣に基づいて同値性を判定するメソッドを実装していたので紹介しておく.
sim: function(lhs, rhs, seen, axiom, transition) { if (!axiom.call(this, lhs, rhs)) return false; // detect cyclic reference if ((seen=seen.clone()).add(lhs, rhs)) return true; var states = transition.call(this, lhs, rhs); for (var i=0; i < states.length; i++) { var l = states[i][0]; var r = states[i][1]; if (!this.sim(l, r, seen, axiom, transition)) return false; } return true; }https://github.com/tarao/gnn.js/blob/5deb0f7f81020c26f13570cf135afea560524f41/gnn/base.js#L279-L291
基本的な流れは, transitionが遷移先を集めてきて, その各遷移先についてaxiom(今回の場合はプリミティブ値の場合に一致するか, 片方だけ遷移先が欠けていたりしないか)が成り立つかどうかを確認する. どちらもオブジェクトに辿りついて, 循環していたら(既に見たオブジェクトだったら)そのパスは一致したことにして探索を打ち切る. 循環していなければ再帰的にさらなる遷移先を調べていく.
循環しているかどうかの判定は, 見たオブジェクトを愚直に保存していって, 毎回線形にナメて既出かどうか調べているので効率は悪い. いまだったらWeakMapを使うとか, なんらかもっと良いやりようがありそう.
現実世界の言語処理系の実装ではどうか. たとえばRubyの処理系もだいたい同じことをしていそう. RubyのHashの同値性はeql_iという関数を再帰的に呼ぶことによって確認していそうで, その際recurというパラメータをチェックするガードが書かれていて, trueを返すようになっている.
static VALUE recursive_eql(VALUE hash, VALUE dt, int recur) { struct equal_data *data; if (recur) return Qtrue; /* Subtle! */ data = (struct equal_data*)dt; data->result = Qtrue; rb_hash_foreach(hash, eql_i, dt); return data->result; }https://github.com/ruby/ruby/blob/5e9598baea97c53757f12713bacc7f19f315c846/hash.c#L3712
このrecurがどこで真になるかと言うとこのあたり:
VALUE pair_list = rb_hash_lookup2(list, obj, Qundef); if (pair_list == Qundef) return Qfalse; if (paired_obj_id) { if (!RB_TYPE_P(pair_list, T_HASH)) { if (!OBJ_ID_EQL(paired_obj_id, pair_list)) return Qfalse; } else { if (NIL_P(rb_hash_lookup(pair_list, paired_obj_id))) return Qfalse; } } return Qtrue;https://github.com/ruby/ruby/blob/2d4f29e77e883c29e35417799f8001b8046cde03/thread.c#L5190
再帰呼び出しで渡してまわるペアに対して, どちらも以前に見たリストに含まれていればtrueが返るようになっていそう. 12年前のパッチによってサポートされた模様.
このように, 双模倣による同値性判定の実装そのものはそれほど難しくはない.
まとめ
- 循環するオブジェクトも考慮した同値性の定義はさまざまなバリエーションが考えられる
- その中でも同値になるものが最も多くなる定義を採用すると自然に思える
- 自然と思える根拠は双模倣という概念により説明できる
- ありうる定義の中で最大のものである
- 自動的に同値関係になる
- 双模倣という概念がそもそも観測上の振る舞いの一致を数学的に表現するためのものである
- 双模倣による同値性判定は, そんなに難しいところもなく実装できる
- Rubyはこの意味の同値性判定を実装していて偉い
*1:それ以外にも, 同値性判定に計算コストがだいぶかかってしまう(効率よく計算できるようにするのがたいへん)といった問題もある
*2:たとえば, PythonのdictはScalaと同様に, 循環する場合は==が無限ループするようだけど, 動的型付けの言語でこれは正直やめてほしい
*3:再帰的な参照をしている部分をなんらかの束縛関係のようなものだと思ってDe Bruijn indexのようなものを計算している, あるいはα同値性を見ている, みたいにも見えるがそう言って伝わる人には言わなくてもわかると思うのでそちらの方向の説明はしない
*4:数学的にきちんと言うと「このような条件を満たす関係のうち最大のものをとる」ということになり, 本来はそのような最大のものが存在することを証明しなければならない
*5:すべてのプリミティブ値もある唯一の状態への遷移と見なす
*6:日本語がこれでよいか少し自信がなくて, bisimilarなxとyがあったとき日本語では「xとyは双模倣である」と言うところまではよさそうだけど, このような関係のことをなんと言うのか(英語だとbisimilarity)がちょっとよくわかっていないし, 「双模倣関係」は「双模倣性」(これも関係)とたいへんまぎらわしい(英語のbisimilarityとbisimulationもたいがいまぎらわしいが)
*7:GitHubに載せていなかったのでこの機会にサルベージしてきたもので, このライブラリはけっきょく(風呂敷を広げすぎて)作りかけのまま放置していて日の目を見ることはなかった
