ECMAScript Record & Tuple polyfill はどのようにして実装されているのか

Record & Tuple とは

Record & Tuple は ECMAScript (JavaScript) に対する提案段階の機能で、構造化データのためのプリミティブ型を提供するというものです。RecordはObjectのプリミティブ版、TupleはArrayのプリミティブ版にあたります。

プリミティブとオブジェクト

JavaScriptにおける値はプリミティブとオブジェクトの2種類に分けられます。

• プリミティブはイミュータブルで、値の同等性にもとづいて比較されます。既存のプリミティブとして、null, undefined, number, string, boolean, bigint, symbol が存在しています。
• オブジェクトはデフォルトでは書き換え可能で、参照の同一性にもとづいて比較されます。

これまで、複数のスカラー値をまとめて構造化データとして扱うには、オブジェクト (主にObject / Array) を使うのが一般的でした。しかしユースケースによってはオブジェクトの持つ性質が期待に合わないことも多く、これはしばしば問題になっていました。

オブジェクトがもたらす困難

たとえば、Reactのようにリアクティブプログラミングをパラダイムとして持つフレームワークでは、状態や計算結果の変化を陽に追跡したくなる場合があります。たとえば以下のコードでは timeout という変数の変化を監視し、必要に応じて追加の処理を行っています。

useEffect(() => {
  const timer = setTimeout(() => action(), timeout);
  return () => clearTimeout(timer);
}, [timeout]);

上の例では監視対象である timeout がプリミティブであるnumber型であるため問題ありませんが、これがオブジェクトの場合は以下の2つの問題が発生しえます。

• オブジェクトがミュータブルであることによる偽陰性 (内容が変更されているのにリアクティブイベントが発火しない)
• オブジェクトが参照同一性にもとづいて比較されることによる偽陽性 (内容は同じなのにイベントが発火してしまう)

既存の解決策

前者の問題は Immutable.js や immer などのイミュータビリティーライブラリによって、また後者の問題は deep-equal などのユーザー定義の比較関数によって対応されてきましたが、これは最適な解決とはいえない状況でした。

また、既存のプリミティブ型にデータを埋め込むという方法もありました。たとえば JSON.stringify によって文字列に埋め込んでしまえば、イミュータブルで比較可能になります。しかし、キーの順序依存性やパフォーマンス、変換のための余計なコードなどを考えるとこれも最適とは言えません。

Record & Tuple が提供するもの

Record & Tuple はこれらの問題を言語の側から統一的に解決する提案です。

Record & Tuple は構造化データのためのプリミティブ型を提供します。これらは構造化データであるため、以下の特徴を備えています。

• RecordはObjectのように、複数の値に名前をつけてまとめて扱うことができる。
• TupleはArrayのように、複数の値を並べてまとめて扱うことができる。

その一方で、これらはプリミティブ型であるため、以下の特徴を備えています。

• Record & Tupleはnumberなどと同じく、イミュータブルである。
• Record & Tupleはnumberなどと同じく、値の同等性にもとづいて比較される。

これらの新しいデータ型のためには、 #{ ... } と #[ ... ] という2つの新しい構文が導入されます。これらはオブジェクト式や配列式と似たような形で使うことができます。詳しくは提案の説明を見てください。

Record & Tuple を使えるようにする

Record & Tupleは現時点 (2023-06-06) ではStage 2です。将来の標準入りを期待されているものの、まだ完成とは言えない状態で、主要ブラウザによる対応もありません。

このようにまだブラウザで使えない機能を使えるようにするために、トランスパイラとポリフィルが利用できる場合があります。Record & Tupleについても、トランスパイラとポリフィルが提供されています。

トランスパイラとポリフィルの問題領域

トランスパイラとポリフィルは、それぞれに適用可能な問題領域が異なります。

トランスパイラは構文の追加に対応する技術です。新しい構文を使ったコードを、既存の構文を使ったコードに書き換えることで、既存の処理系でも実行できるようにします。たとえば、 Optional Chaining, Rest Spread, Async functions, Classes などはトランスパイラによって対応できる問題領域です。

ポリフィルはライブラリの追加に対応する技術です。言語定義の新しいライブラリを、ユーザー定義コードとして実現します。たとえば、 Object.fromEntries, Promise, Map, Set などはポリフィルによって対応できる問題領域です。

トランスパイラとポリフィルを使っても実現できない機能もあります。言語の意味論に手を加えないといけない場合です。たとえば、 FinalizationRegistry, WeakMap, BigInt, Symbol, Proxy などは完全な再現が難しいため、何らかの制限のもとで導入されることになります。

Record & Tuple の位置づけ

Record & Tuple は BigInt / Symbol などと同じく、プリミティブを増やす提案です。そのためポリフィル・トランスパイラだけでは完全に対応できない箇所があります。それはtypeof演算子です。

JavaScriptはtypeof演算子を含む演算子オーバーロード機構を持たないため、既存コードでtypeof演算子が使われている場合、必ず既存の結果 (undefined, number, string, boolean, bigint, symbol, object, function) のいずれかを返します。この演算子の結果を record / tuple にすることはできません。したがって、トランスパイル対象コードと既存コードを連携させようとしたとき、 Record & Tuple を完全に仕様通りに動かすことはできません。 (typeof演算子がトランスパイル対象コード内で使われる限りにおいては再現可能です)

また、 Record & Tuple にはもう1つ技術的な制約からポリフィルが仕様を満たさない動作をすることがあります。これについては後述します。

このように Record & Tuple を既存のJavaScript処理系で完全再現するのは困難ですが、ポリフィルとトランスパイラを組み合わせることで大部分は再現することができます。この方法を使って、 Record & Tuple をブラウザ上で試すこともできるようになっています。

Record & Tuple のポリフィル

そのRecord & Tupleのポリフィルは @bloomberg/record-tuple-polyfill として提供されています。

ここでは、Record & Tupleのポリフィルが仕様をどのように再現しようとしているのかを説明します。

Interning

Record & Tuple polyfillでは、オブジェクトを使ってRecord/Tupleを再現します。

すでに説明した通り、Record & Tupleの中核機能は、「イミュータビリティー」と「値の同等性による比較」の2つです。このうちイミュータビリティーはオブジェクトをfreezeすることで実現できますが、値の同等性はそう簡単ではありません。というのも、JavaScriptでは比較演算子 (===) をオーバーロードすることができないからです。

そこでrecord-tuple-polyfillではかわりに、interningという手法を使って比較結果をコントロールします。これは、同等の値を持つオブジェクトは1つしか作られないようにするというものです。

以降では話を簡単にするため、2要素からなるタプル #[x, y] に限定して説明します。

interningの簡易的な実装例は以下のようになっています。

// Intern済みのオブジェクトを格納する場所
const map = new Map();
// Intern済みのタプルを生成する
function Tuple(x, y) {
  const key = `${x}, ${y}`;
  // [x, y] の組に対応するオブジェクトがまだなければ、新たに生成する
  if (!map.has(key)) {
    map.set(key, Object.freeze([x, y]));
  }
  // 既にあれば、それを返す
  return map.get(key);
}

assertEqual(Tuple(1, 2), Tuple(1, 2));

複合キーによるinterning

先ほどの例はRecord & Tupleの仕様を満たすための実装としては足りていないところが沢山あります。そのひとつが、既存オブジェクトからの検索方法です。

先ほどの例では x と y の文字列表現を使って検索用のキーを使っていましたが、これでは異なる値が同じ文字列キーを持ってしまう可能性があり、当然それでは不十分です。

このような検索を実現するには、主に2つの方法があります。

• 自力で検索を実装する。
• 既存の検索機構を再利用する。

さてこの「自力で検索を実装する」についてですが、ハッシュテーブルを実装するにはハッシュ値が必要ですし、探索木を実装するには全順序が必要です。しかし、JavaScriptにはこれらを計算するための都合のいい仕組みがなく、特にSymbolとオブジェクトに関しては実現が困難です。したがって、もし自力で検索を実装するとなると、基本的には線形探索ということになってしまいます。

そこでここでは、かわりの方法として、既存の検索機構であるMapを再利用して、配列をキーとしたMapを作ることを考えます。

ここでのアイデアは簡単です。配列の要素数だけ、Mapをネストさせます。TypeScriptの型でいうと Map<K1, Map<K2, Map<K3, V>>> のようなものを考えます。たとえば2要素の簡易的なinternであれば以下のような実装になります。

// Intern済みのオブジェクトを格納する場所
const map = new Map();
// Intern済みのタプルを生成する
function Tuple(x, y) {
  if (!map.has(x)) map.set(x, new Map());
  const map1 = map.get(x);
  if (!map1.has(y)) map1.set(y, Object.freeze([x, y]));
  return map1.get(y);
}

assertEqual(Tuple(1, 2), Tuple(1, 2));

基本的なアイデアがわかれば再帰を丁寧に実装するだけですが、このとき注意が必要な点があります。それは要素削除の実装です。

要素削除時には、内部で使っているMapが不要になる場合があります。不要になったMapは積極的に削除するようにしておかないと、「対外的には要素は少ないのに、内部では大量のMapを持っている」という状態 (一種のメモリリーク) になる可能性があります。

Recordのinterning

RecordはObjectのイミュータブル版と説明しましたが、そのキーは常に辞書順でソートされた状態で入るという違いがあります。そのため、Recordの同等性は [k1, v1, k2, v2, ...] のようなリストの同等性で考えることが可能です。こうすればTupleと同じようにinterningできることになります。

実際の実装ではこのようにフラット化せずに、[[k1, v1], [k2, v2], ...] の形で保持しているようです。

ゴミ回収

JavaScriptの処理系は通常、使われなくなったデータを自動で回収します。さもなくば、長期にわたって実行されるプログラムは(実際には常に一定量のデータしか使っていなくても)メモリを徐々に利用し尽くしてしまいます (メモリリーク)。

同じことがRecord & Tuple polyfillにも期待されますが、interningしている都合上自動的にはゴミが回収されません。そこで、メモリリークが起きないようにするために明示的な処理が必要です。

JavaScriptでメモリリーク対策をするにあたって使える道具には以下があります。

• WeakMap / WeakSet
• WeakRef
• FinalizationRegistry

特にWeakRef / FinalizationRegistryはゴミ回収の挙動に依存する高度なAPIで、できるなら避けるべきとされています。しかし実は、今回のケースで適切にメモリリークを回避するには、この2つはどうしても必要になります。

• 検索用のMapはプリミティブ値をキーに持つため、WeakMapで代替できません。そのため、これらのMapのテーブルサイズの節約は自力で行う必要があります。これにはゴミ回収に対して能動的にアクションを取る必要があり、FinalizationRegistryが不可欠です。
• intern処理本体がintered objectへの強参照を保持してしまうと、どうやってもinterned objectを回収することはできません。そのため、interned objectの保管には必然的にWeakRefを使うことになります。WeakMap / WeakSet はゴミ回収の挙動を観測できないように設計されているため、この目的では使えません。

interningが正しく機能するために、interned objectが生きている限りはMap経由で到達可能でなければいけません。これを保証するには以下の2つのアプローチが考えられます。

• 途中のMapは全てグローバルからの強参照で繋ぎ止めておき、FinalizationRegistryのイベントに応じて削除する。
• 途中のMapは弱参照で持つが、かわりにinterned objectからMapへの逆向きの参照を強参照で保持しておく。要らなくなった要素の削除はFinalizationRegistryのイベントに応じて行う。

前者の場合、FinalizationRegistryにはinterningの元となった値のリストを保持しておき、interned objectが無くなった時点で対応するキーを削除するという実装になります。

// Intern済みのオブジェクトを格納する場所
const map = new ArrayKeyedMap();
// Intern済みのタプルを生成する
function Tuple(x, y) {
  const stored = map.get([x, y])?.deref();
  if (stored) {
    return stored;
  }

  const interned = Object.freeze([x, y]);
  // 弱参照を登録しておく (interned objectが使われなくなった時点で破棄される)
  map.set([x, y], new WeakRef(interned));
  // interned objectの破棄後にmap自体のクリーンアップをするための登録処理
  reg.register(interned, [x, y]);
  return interned;
}
const reg = new FinalizationRegistry((values) => {
  const weak = map.get(values);
  // 競合条件で、キー自体が消滅していたり、キーが消滅したところに新たに同じキーが登録されている可能性がある
  // これらの可能性は除外し、「期限切れの弱参照がある」というときだけ安全にクリーンアップできる。
  if (weak && !weak.deref()) {
    map.delete(values);
  }
});

assertEqual(Tuple(1, 2), Tuple(1, 2));

後者はもう少し複雑です。WeakMapを使ってinterned objectからMapへの逆向きの参照を保持しておきます。あるMapで管理されていたinterned objectが全て無くなった時点でMapは自動消滅しますが、そのMapの親Mapにエントリは残されたままになります。それを消すためにinterned objectの削除フックをFinalizationRegistryに登録しておきます。

では実際の実装はというと、基本的には前者のようにグローバルからの強参照を使うのですが、ゴミ回収のために逆向きの参照も保持し、明示的に参照カウントを管理する実装になっているようです。このようになっている理由は謎です。

ポリフィルの限界

Unsupported Featuresでも触れられている通り、interningによる実装は完全ではなく、どうしても仕様を満たせない部分があります。

まず代表的なのが浮動小数点数の扱いです。JavaScriptの比較には SameValue, SameValueZero, IsLooselyEqual, IsStrictlyEqual の4種類がありますが、このうちSameValue, SameValueZero, IsStrictlyEqualにおいてオブジェクトはその同一性で比較されます。つまり、interningのアプローチを取る以上は、この3種類の比較の結果は全て同じになってしまうことになります。しかし、Record & Tupleの提案仕様では浮動小数点数を含むRecord / Tupleの比較は同じサブルーチンで再帰的に定義されるため、どの比較関数を使ったかによって異なる結果になることが期待されます。interningではどうしてもこの齟齬を回避することができません。

また前述の通り、typeof演算子もオーバーロードできないため、結果は仕様通りにはなりません。

他にも記載されていない違いはあります。たとえば、 Object(value) はプリミティブ値valueをラップした別のオブジェクトを返すはずですが、ポリフィルを使う限りにおいてはvalueが元からオブジェクトであるため結果は同じままです。

とはいえ、Record & Tupleの中核機能である「イミュータビリティー」と「値の同等性による比較」は実現されているため、仮に今から使い始めても大きな問題はないのではないかと思います。とはいえ、提案はまだStage 2ですし、TypeScriptのサポートもないため、実用するのはもう少し後のほうがよいでしょう。

まとめ

• Stage2提案であるRecord & Tuple が入ると、構造化データをプリミティブ値として扱うことができるようになる。
• プリミティブ値はイミュータビリティーと値の同等性による比較という2つの特徴を持つため、リアクティブプログラミングをはじめとする様々なユースケースでより素直なプログラムが書けるようになることが期待される。
• トランスパイラとポリフィルを使うことにより、既存の処理系でも部分的にこの提案の動作を再現することができる。
• ポリフィルでは比較演算の挙動を調整するためにinterningが使われており、そのinterningの実装にはMapのネストやGCの高度な制御などのテクニックが使われている。