拡張可能レコードのライブラリrecord4sについてScalaMatsuri 2024で発表しました

ScalaMasturi 2024で, 拙作の拡張可能レコードのライブラリrecord4sについて発表してきました.

発表で触れられなかった点も補足しながら, 内容を文章にしておこうと思います. とくにrecord4s以外のレコード実装との比較についてはこの記事での完全書き下ろしです.

モチベーション

たとえば, 有料記事も投稿可能なブログサービスを作っているとします. すると無料のブログ記事と, 有料部分もあるブログ記事をそれぞれ表すドメインモデルが欲しくなりそうです. 似たようなクラスを書くことになります. 下の例では有料部分の内容を表すpaidPartOfBodyの有無だけが異なります.

無料記事と共通する部分を引いてきて, 有料部分が欲しいときはそっちも引くなどすると, 詰め替えが必要になりそうです.

さらに下書き記事も扱えるようにしようと思ったら, また同じようなモデルを定義することになります.

有料・無料, 公開・下書きを問わず必要になるフィールドを追加しようと思うと, すべての定義を書き換える羽目になります. 詰め替えしてるところもすべて直して回らないといけません.

発表ではこういうふうに話しましたが, 個人的にはこの例のブログ記事のモデルはそんなによいとは思えず, そのせいでモチベーションの共有を妨げないか少し不安でした. とはいえ, 発表後に吉村さんと話していて, こういうことはプレゼンテーションモデルあるいはビューモデルというのか, バックエンドで言えばAPIとして返却すべき値のモデルを定義するときには本当によくあるという話になりました. 僕自身も経験がありますが, XxWithYyみたいなcase classが無限に生えます. そういう例だと思って見てもらうとしっくりくるんじゃないかと思います.

Scala 3の標準機能による解決

Scala 3には構造的型の機能があり, これ(と交差型(intersection type))を使えば重複なく前述のモデルの型を定義できます.

この例における

Model {
  val id: PostId
  val title: String
  val body: String
}

のようにフィールド名とその型をvalで羅列するのが構造的型です. 1行で書く場合はModel { val id: PostId; val title: String; val body: String }のように;で区切ります.

ちなみに, Scala 2までの構造的型を知っている人のために補足しておくと, Scala 3では構造的型を使ってもリフレクションは発生しなくなりました*1. 安心して使えます.

しかし, 型はすっきり書けても値の書き方が微妙になります.

構造的型の値を作成するときは左のように書くことになり, asInstanceOfしているためフィールド名を間違えてもコンパイルエラーにならず, 後からアクセスしたときに実行時エラーとなります. 型安全おじさんとしては看過できません. Optionに対してgetするのと同じくらいの罪です.

また, フィールドを追加しようと思うとだいぶ無理矢理な感じになります(右).

理想

理想としてはこんなふうに書けるといいですね.

フィールドの追加もこうだと助かります.

いや, そんな都合よく行くかいな. それがイケちゃうんです. そう, record4sならね!

record4s

実は, 「理想」として書いた例はエイリアスを適切に設定するとそのまま動きます.

もう少し具体的に使い方を見ておくと, %(...)でレコードを新規に作成でき, 構造的型が付きます. ちなみに, %はなるべく文字数短くレコードを作れるように1文字にしており, この記号はPerlの連想配列のシジルに由来します.

当然ですが, ちゃんと型が付いているので存在しないフィールドにはアクセスできません(正しくコンパイルエラーになります).

(複数)フィールドの追加もできます.

2つのレコードの結合も可能です.

フィールドの更新もできます. レコードはイミュータブルなので, 単にフィールドが置き換わった新しいレコードが作られるだけです. 更新後のフィールドは更新前と型が異なっていても構いません.

他にも機能が盛りだくさん!

Tips

メソッドの定義

拡張メソッドを定義すれば, レコードに対してメソッドを呼ぶこともできます. もう少し詳しい説明はこちら.

構造的型に対して拡張メソッドを定義した場合, その部分型に対しても同じメソッドが呼べるため, フィールドを足してもそのまま動きます. この例ではBlogPostに対してsummaryメソッドを定義しておくだけで, paidPartOfBodyフィールドが増えただけのBlogPostWithPaywallに対してもsummaryが呼べます.

例を使ってJSONをデコード

record4sとは無関係に, 一般にJSON文字列をデコードするときはデコード先の型を指定する必要があります. デコード先がcase classならクラス名を書くだけで済みますが, デコード先が構造的型だと少し面倒です. % { val name: String; val age: Int }みたいな型を長々と書くことになります.

こういうとき, 以下のdecodeByExampleを定義しておくと, インスタンス例を使ってデコード先の型を推論できます.

OpenAPIを使っている場合など, だいたい例は書くと思いますし, そうでなくとも「ここはこういう構造のJSONになってる想定」というのを書いておくと分かりやすいはずなので, オススメのやり方です*2.

内部実装

フィールドアクセス

標準ライブラリのSelectableを使うことで, Scala 3コンパイラによってフィールドアクセスはselectDynamicの呼び出しに置換されます.

この仕組みはDynamicに似ていますが, Selectableは静的に解決可能な場合のみ許すため, これだけで安全なフィールドアクセスを提供できます.

レコードの結合

内部的にはレコードの結合はMapの結合です. レコードに対して++ã‚„concatを呼ぶとMapを結合して新たなレコードを作る操作に変換されます.

返り値型はConcatという型のgivenインスタンスを探索して決めるようになっています. 構造的型を型レベル計算で生成する方法は現状(Scala 3.3.3時点)は存在しないため, givenの本体をマクロにすることでコンパイル時に構造的型の結合を計算しています. 構造的型の結合は交差型でいいと思うかもしれませんが, それだと同じフィールド名の別の型がそれぞれのレコードにある場合におかしなことになります.

重複キー問題

実は前節のレコード結合の定義には問題があります. 型が異なる同じ名前のフィールドを持つレコードが2つあり, 後者の静的型ではそのフィールドの存在を隠した場合, フィールドの型と値の不一致を発生させることが可能です.

この例では, r1.ageはIntでr2.ageはStringですが, r2の型を{ val name: String }にアップキャストしておくと, (r1 ++ r2).ageの型はIntに, 値はStringになってしまいます.

{ val age: Int }と{ val name: String }を型レベルで結合すると{ val age: Int; val name: String }なのに対し, Map("age" -> 3).concat(Map("name" -> "tarao", "age" -> "unknown"))はMap("age" -> "unknown", "name" -> "tarao")になるためです.

このため, レコードの結合は単純なMapのconcatではダメで, 右辺のレコードは静的型に表れたフィールドのみに絞る必要があります.

Scalaの他のレコード実装

発表では触れませんでしたが, 拡張可能レコードをScalaで実装した/実装しようとした例はいくつかあります. record4sの実装にあたっても大いに参考にしています.

shapelessのRecord

shapelessにはRecordがあり, これは実は拡張可能レコードです. ただし, 構造的型ではなくHListを用いた連想配列で実現しているため, フィールドの順序が異なると別の型と見なされ, またサイズが大きくなるとフィールドへのアクセスや更新がどんどん遅くなります(後ほどベンチマークのグラフで見ます). レコードの型も読みにくく書くのもかなり大変です.

scala-records

scala-recordsはある意味record4sの直接の祖先と言えます. これはScala 2向けにレコード型を提供するもので, 構造的型でレコード型を表現します. record4sと同様に内部実装はMapになっていて, Mapの操作をマクロで隠蔽することで型安全にレコードの操作ができるようになっています. ただし, 拡張可能ではありません.

実は, scala-recordsを拡張可能レコードにする試みもありました:
#104 Introduce a merge operation for joining two records.

個人的にこの議論はずっと追いかけていて機能追加を心待ちにしていたのですが, けっきょく実装されないままでした. そうこうしているうちにScala 3がリリースされ, scala-recordsではかなり大変なマクロで実現していた部分がだいぶ簡単に実装できるようになったため, scala-recordsに乗っかるより一からScala 3で書いた方が早いと判断して, 諦めて自分で実装したのがrecord4sです. 従ってrecord4sは, scala-recordsを拡張可能にしようとしたときの議論や, scala-recordsがshapelessのレコードを意識してパフォーマンスに関して配慮していた部分をすべて踏襲した上で実装しています.

Karlsson & Haller '18

Scalaで拡張可能レコードを実現する方法についてまとめた論文もあります.

Extending Scala with Records: Design, Implementation, and Evaluation.
Olof Karlsson and Philipp Haller.
In Proceedings of the 9th ACM SIGPLAN International Symposium on Scala, New York, NY, 2018.

この論文ではshapelessã‚„scala-recordsでの実現方法に加え, この論文独自の方法も提案した上で, 各手法の特徴を比較しています. この論文の提案手法ではimplicitパラメータによって返り値型を計算していて, これはrecord4sでもやっているやり方です*3. ただし, この論文ではあくまでScalaコンパイラを拡張する前提のため, implicitに要求する型は組み込みの型であり, コンパイラが特別扱いするようになっています. それを, givenをマクロにすることでコンパイラに手を入れずに実現しているのがrecord4sです.

また, この論文が書かれた当時Scala 3の実装はある程度進んでいて, 提案手法もScala 3コンパイラを改造して実装されましたが, 設計にはScala 2時代までの課題が大きく反映されてしまっています. Scala 2ではwhiteboxマクロを使うとIDE上でうまく型推論されずコードが真っ赤になっていました. そのため提案手法では極力whiteboxマクロを使わないようになっており, その制約のためにフィールドの追加を1度に1つしかできません(複数フィールドをまとめて指定して初期化することもできません).

Scala 2のwhiteboxマクロに相当するScala 3のtransparent inlineマクロはだいぶ改善されており, この点を気にする必要はなくなりました. それゆえrecord4sでは複数フィールドまとめて追加できるようになっています. その代わり, record4sがScala 2をサポートすることはありません*4.

この論文では各実装のパフォーマンスの比較もされていて, record4sのベンチマークテストもこの論文で用いられた指標を前提としています(それ以外の指標も加えています).

record4sのArrayRecord

record4sではパフォーマンス特性の異なるArrayRecordというクラスも提供しています.

shapelessのレコードには良い点もあり, それはレコードの初期化や結合の実行速度が高速なことです. この特性に加えてフィールドアクセスの実行時間やレコード結合のコンパイル時間も抑えたのがArrayRecordです. ただし, shapeless同様, フィールドの順序を替えると別の型と見なされ, 構造的型ではありません. レコード型の書き方もやや煩雑です.

ArrayRecordはその名の通り内部のデータ表現がMapではなく配列的なもの(実際はVector)になっています. 各フィールドへのアクセスはコンパイル時に配列要素へのインデックス参照に置換されます.

Named Tuples

Scala 3.5には実験的機能としてNamed Tuplesが追加されます. (name = "tarao", age = 3)などとすると(name: String, age: Int)型の名前付きのタプルが作れる機能です. この名前は型レベルにのみ存在していて, 実行時には消去されており, 実体は普通のタプルです.

ちょうど, こちらの記事でマクロの例題として使ったNamedArrayが, 実体をタプルではなくIndexedSeqにして同じようなことをやっているものになります:

Named Tuplesは, shapelessのレコードやArrayRecordと同様に, フィールドの順序を替えると別の型と見なされます. パフォーマンス特性もおそらくArrayRecordに近いものになると思います. ただし, ArrayRecordはcase classと同等のProductのインタフェースを実装するためにフィールド名もデータとして持っており, メモリ効率はNamed Tuplesの方がよくなります. その他の特性ではおそらくNamed TuplesとArrayRecordは同等で, 固定のフィールド名だけを使う場合はNamed Tuplesが適していますが, フィールドの追加・変更をよくする場合はrecord4sの%の方が適していているはずです.

Named Tuplesが正式な言語機能として採用されれば, ArrayRecordの役目はほぼなくなる*5ため, record4sから削除する(あるいはNamed Tuplesのラッパーにする)つもりです.

他の言語での例

PureScript

言語に組み込みで拡張可能レコードが実装されている例としてはPureScriptがあります:
documentation/language/Records.md at master · purescript/documentation

実際にどう実装されているのかは知りませんが, PureScriptはaltJSなので裏側はJavaScriptのオブジェクトになっているとすると, フィールドアクセスも高速にできそうです.

TypeScript

拡張可能レコードがどういうものかを見て「それTypeScriptでできるよ」と思った人もいるかもしれませんが, 残念ながらそれは早計です. TypeScriptの場合は「重複キー問題」が発生するからです.

const r1: { age: number } = { age: 3 };
const p: { name: string, age: string } = { name: "tarao", age: "unknown" };
const r2: { name: string } = p;

const r = { ...r1, ...r2 };
const age: number = r.age;
console.log(age);

"unknown"

本来はconst age: number = r.age;の行でコンパイルエラーになってほしいですが, 素通りしてしまっています. TypeScriptが型安全ではない要素は他にもたくさんありますが, こうも簡単に型安全性を破壊できてしまうのは驚きです. これでは流石に「拡張可能レコードを実現できている」とは言いがたいと思います.

TypeScriptに拡張可能レコード相当の使い方を期待するなら, スプレッド構文(ã‚„Object.assign)でレコードを結合するのを封印して, { ...r1, f1: v1, f2: v2}の形のみ許すように制限する必要があります. (ではlinterでそこを制限すればそれでいいかと言うと, レコードの結合ができないため「拡張可能レコードを実現」という意味では片手落ちだと思います.)

Haskell

Haskellには拡張可能レコードのライブラリがいくつかあります:
Extensible record - HaskellWiki

あまり詳しく知らないのでどれがどういう特徴かというのはよく知りません. ただ, レコード型はどの言語でも記法が独特になりがちな中, Haskellはとくに記号がどういう意味で使われるかしっかり覚えないと使えない印象があります.

パフォーマンス

record4sはパフォーマンスについても十分に気をつかっています. 詳細はこちらを見てください. ここでは発表で紹介した部分だけ触れておきます.

レコード作成の実行時間

レコードの作成にかかる時間はサイズが大きくなるにつれて線形に増えます. Mapと同じです.

一方, ArrayRecordã‚„shapelessのレコードは作成の実行時間は短く済みます. ハッシュマップのハッシュ値を計算する必要がないためです.

フィールドアクセスの実行時間

フィールドアクセスにかかる時間はフィールドのインデックスやレコードのサイズによりません. ハッシュ値の計算で上下はしますが, 実質定数時間です. shapelessのレコードだとフィールドを前から順に探索するため線形時間かかってしまうのとは対照的です.

レコード結合のコンパイル時間

グラフからは少し読み取りづらいですが, Scala 3コンパイラ自体の構造的部分型の検査がになっているため, レコード結合のコンパイル時間はサイズの2乗に比例します. しかしshapelessのレコードと比べるとずっとましです.

ベンチマークの実装

基本的にJMHで計測し, Seabornで可視化しているだけです. 計測対象(shapelessやscala-records)のScalaバージョンを分ける必要もあるためScalaのバージョンごとにsbtプロジェクトを分けています.

[Karlsson & Haller '18]のベンチマーク実装がそのまま使えるとよかったのですがそのままではビルドできず, 変にコード生成していて何を計測しているのかも分かりにくかったため, 素朴なコードで再実装しています.

Scala 2ã‚‚Scala 3ã‚‚, コンパイラをライブラリとして呼び出すことが可能で, コンパイルされるコードから呼び出し元のクラスファイルにアクセスする(例)ことも可能なため, 特定部分のコンパイルにかかる時間を計測するのも非常にやりやすかったです.

ベンチマークに関するコードは以下にあります.

• script/benchmark.sh
• script/benchmark
• modules/benchmark_3
• modules/benchmark_2_13
• modules/benchmark_2_11

まとめ

• record4sはScala 3で拡張可能レコードを提供するライブラリ
• モデリングにおいて有用な場合がある
• マクロとインラインの機能を使って注意深く設計されている
• これまでのレコード実装をふまえた設計になっている
• パフォーマンスについても十分に配慮されている

*1:より正確に言うと, リフレクションを用いるものは構造的型そのものとは別の仕組みに切り離されました.

*2:このやり方はid:Windymeltくんに「型を書くのは面倒だからインスタンスから推論する方法はないか」と訊かれて思いつきました.

*3:shapelessでも頻出のよくある手法ではあります.

*4:もしかしたらこれがscala-recordsを拡張可能にする試みが進まなかった一番の理由かもしれません.

*5:もともとはJSONに変換する都合上, Productのインタフェースを備えたレコード型があると都合がよかったために実装したものでしたが, Productを介さない変換を後から実装したため不要になっていました. パフォーマンス特性として%とは違った利点があったため残してあったのが, Named Tuplesの登場でいよいよ本当に不要になるということです.