この記事は はてなエンジニア Advent Calendar 2024 の 4 日目の記事です. 昨日は id:onk さんの コミュニティ生活で大切な三つの袋 - id:onk のはてなブログ でした.
ところで皆さん TypeScript は書いていますか書いていますよねそうですよね. そんな皆さんに TypeScript の表現力の高さを改めて実感してもらうべく, この記事では Data types à la carte という論文で紹介されている抽象データ型の拡張性に関する問題を, TypeScript ではどのように解決できるかを紹介します.
抽象データ型の拡張性の問題
まずは論文で紹介されている問題を, (元は Haskell で書かれているので) TypeScript に翻訳しながら見てみましょう.
まず A さんが以下のような数式を扱うモジュールを公開したとします. ここでは discriminated union を使って数式を表すことにしました.
/** 数式を表すデータ */ export type Expr = | { type: "lit"; value: number } // リテラル | { type: "add"; lhs: Expr; rhs: Expr }; // 足し算 /** 数式を計算する */ export function evalExpr(expr: Expr): number { switch (expr.type) { case "lit": return expr.value; case "add": return evalExpr(expr.lhs) + evalExpr(expr.rhs); } }
これを使うと, 以下のようにリテラルと足し算からなる数式を計算できます.
// 1 + 2 const expr: Expr = { type: "add", lhs: { type: "lit", value: 1 }, rhs: { type: "lit", value: 2 }, }; console.log(evalExpr(expr)); // => 3
これを見た B さんは, このモジュールを使って数式を計算するだけでなく, 文字列として表示したいと思いました. 実際に以下のようなプログラムをうまく実装できたので, B さんは満足です.
/** 数式を表示する */ function printExpr(expr: Expr): string { switch (expr.type) { case "lit": return expr.value.toString(); case "add": return `(${printExpr(expr.lhs)} + ${printExpr(expr.rhs)})`; } } console.log(printExpr(expr)); // => "(1 + 2)"
一方で C さんは, 足し算だけでなく掛け算も計算したいと考えました. そこで以下のようにデータ型の拡張を試みましたが, どうにもうまくいきません.
type MyExpr = | Expr // 元々の数式 (リテラルと足し算) | { type: "mul"; lhs: MyExpr; rhs: MyExpr }; // 掛け算 const myExpr: MyExpr = { type: "add", lhs: { type: "lit", value: 1 }, // 型エラー: 足し算の中に掛け算を含められない rhs: { type: "mul", lhs: { type: "lit", value: 2 }, rhs: { type: "lit", value: 3 }, }, }; // 型エラー: 掛け算を含む式に対応していない console.log(evalExpr(myExpr));
仕方がないので A さんにかけあって, Expr の定義に掛け算も含めてもらうことにしました.
これで C さんも満足です.
/** 数式を表すデータ */ export type Expr = | { type: "lit"; value: number } // リテラル | { type: "add"; lhs: Expr; rhs: Expr } // 足し算 | { type: "mul"; lhs: Expr; rhs: Expr }; // 掛け算 /** 数式を計算する */ export function evalExpr(expr: Expr): number { switch (expr.type) { case "lit": return expr.value; case "add": return evalExpr(expr.lhs) + evalExpr(expr.rhs); case "mul": return evalExpr(expr.lhs) * evalExpr(expr.rhs); } }
ところがこうなると困るのは B さんで, 元々特に問題のなかった実装が, 型エラーでコンパイルできなくなってしまいました.
/** 数式を表示する */ // 型エラー: case が網羅的でない function printExpr(expr: Expr): string { switch (expr.type) { case "lit": return expr.value.toString(); case "add": return `(${printExpr(expr.lhs)} + ${printExpr(expr.rhs)})`; } }
なんとかして C さんが望んだようなデータの種類の拡張を許しつつ, B さんの実装には影響を与えないようにすることはできないでしょうか?
interface と class を使った場合
ところで TypeScript には Haskell とは異なり, オブジェクト指向的な interface や class があります. これを使って問題が解決できないのかも一応見ておきましょう.
まずは A さんが以下のようなモジュールを公開したとします.
/** 数式 */ export interface Expr { /** 数式を計算する */ eval(): number; } /** リテラル */ export class Lit implements Expr { constructor(public value: number) {} eval(): number { return this.value; } } /** 足し算 */ export class Add implements Expr { constructor(public lhs: Expr, public rhs: Expr) {} eval(): number { return this.lhs.eval() + this.rhs.eval(); } }
このように interface と class を使って定義しておくと, 掛け算を扱いたかった C さんは, 以下のように独自の class を定義することができて満足です.
/** 掛け算 */ class Mul implements Expr { constructor(public lhs: Expr, public rhs: Expr) {} eval(): number { return this.lhs.eval() * this.rhs.eval(); } }
一方で数式を表示したかった B さんは, print() のようなメソッドを自分で追加することはできず, 以下のような関数を定義してもコンパイラで網羅性を検証できず, 苦労することになってしまいます.
/** 数式を表示する */ function printExpr(expr: Expr): string { if (expr instanceof Lit) { return expr.value.toString(); } else if (expr instanceof Add) { return `(${printExpr(expr.lhs)} + ${printExpr(expr.rhs)})`; } else { throw new Error("unknown expression"); } }
そこで A さんにかけあって, Expr の定義に print() メソッドを追加してもらいました.
これで B さんは満足です.
/** 数式 */ export interface Expr { /** 数式を計算する */ eval(): number; /** 数式を表示する */ print(): string; } // Lit, Add の定義は省略
ところが今度は C さんの実装がコンパイルできなくなってしまいました.
/** 掛け算 */ // コンパイルエラー: print() が未定義 class Mul implements Expr { constructor(public lhs: Expr, public rhs: Expr) {} eval(): number { return this.lhs.eval() * this.rhs.eval(); } }
このように, interface と class を使った場合は discriminated union を使った場合と比べて, データの種類の拡張は容易になっているものの, メソッドの拡張時には同様の問題が現れることがわかります.
解決方法
ここではデータ型の表現に discriminated union を使う方法をベースにしつつ, 扱う数式の種類を自由に拡張できるように定義してやることで, 問題の解決を試みます.
アイデア
まずは数式の種類ごとに, 以下のようなデータ型を定義します.
ここで最終的な数式を表す型は, 抽象化された型変数 T になっています.
// T は最終的な数式の型を抽象化したもの type Lit<T> = { value: number }; type Add<T> = { lhs: T; rhs: T };
続いて数式全体を表す型を以下のように定義できるとします.
ここでは扱う数式の種類が, 抽象化された型変数 F になっています.
// F は扱う数式の種類を拡張できるように抽象化したもの type Expr<F> = // F = F0 | F1 | ... とすると, | { type: F0; data: F0<Expr<F>> } | { type: F1; data: F1<Expr<F>> } | ...;
最終的に, どういった種類の数式を扱いたいのかを利用側で自由に (アラカルトのように!) 選んでもらって, 数式の型を完成させます.
type MyExpr = Expr<Lit | Add>; // = { type: Lit; data: { value: number } } // | { type: Add; data: { lhs: MyExpr; rhs: MyExpr } }
ここで良いニュースと悪いニュースがあります.
まず良いニュースは, TypeScript には組み込みのユニオン型があり, 上記の Lit | Add のように数式の種類を自由に選ぶときにこれが便利に使えることです.
元の論文では Haskell の言語機能を使ってこれをいかに実用的な形に落とし込むかというところに最も労力が割かれているのですが, TypeScript ではこの議論をほぼ丸ごとスキップできます.
一方で悪いニュースは, TypeScript には Haskell とは異なり組み込みの高階型がないため, 上記の Expr<F> の F のように, 型引数をとる型を抽象化する部分で行き詰まってしまうことです.
とはいえ実は TypeScript でも高階型をエミュレートする方法はよく知られているので, 次はその方法を見ていきましょう.
高階型の定義
ここでいう高階型 (higher-kinded type) というのは, 例えば「型引数をとる型 = 型コンストラクタ」を引数にとる型のことです. ちょうど関数を引数にとる高階関数の型バージョンですね.
TypeScript で高階型をエミュレートするには, まず型コンストラクタに名前をつけて, その名前を引数に取る型を定義してやるのが最も一般的です. まずはそれらの名前を登録する場所を interface として定義しましょう.
/** 型コンストラクタを登録するための interface */ export interface TypeConstructorRegistry<T> {}
TypeScript の interface には declaration merging という機能があるため, 誰でも自由に型コンストラクタを登録することができます.
例えば以下のように型コンストラクタ foo を登録してみましょう.
ここで T は型コンストラクタの引数です.
// 同じファイルの別の場所で拡張することもできるし export interface TypeConstructorRegistry<T> { foo: { data: T }; } // 別のモジュールから拡張することもできる declare module "./a" { interface TypeConstructorRegistry<T> { foo: { data: T }; } }
このように登録した型コンストラクタを適用するには, 以下のような Apply<F, T> を使います.
/** 任意の型コンストラクタのユニオン */ export type TypeConstructor = keyof TypeConstructorRegistry<unknown>; /** 型コンストラクタを適用する */ export type Apply<F extends TypeConstructor, T> = TypeConstructorRegistry<T>[F];
これを使って実際に foo を number に適用してみましょう.
type Foo = Apply<"foo", number>; // = { data: number }
うまく動きましたね.
数式を表すデータ型の定義
型コンストラクタに名前をつけて高階型を定義できるようになったところで, 実際に数式を表すデータ型を高階型として定義していきましょう.
まずはリテラルと足し算を表す型コンストラクタを登録しておきます.
export interface TypeConstructorRegistry<T> { // リテラル lit: { value: number }; // 足し算 add: { lhs: T; rhs: T }; }
続けて Expr<F> を以下のように定義します.
ここまで登場した型定義の中では一番複雑ですが, 条件型の分配と Apply を組み合わせているだけということがわかれば理解は難しくないはずです.
/** 数式を表すデータ型を作る */ export type Expr<F extends TypeConstructor> = Expr2<F, F>; export type Expr2<F extends TypeConstructor, G extends TypeConstructor> = F extends unknown ? { type: F; data: Apply<F, Expr<G>> } : never;
これに "lit" | "add" のような, 扱いたい数式の種類の組み合わせをユニオン型として与えてやると, 以下のように discriminated union の形で数式のデータ型が得られます.
type MyExpr = Expr<"lit" | "add">; // = { type: "lit"; data: { value: number } } // | { type: "add"; data: { lhs: MyExpr; rhs: MyExpr } }
もし掛け算も扱いたくなったら, そうしたい人自身が以下のように掛け算を表す型コンストラクタを追加で登録し, それを含む数式の型をその場で作ってやれば良いのです. わざわざモジュールの作者に連絡して追加してもらうこともなければ, 他の人が使っている数式の型に影響を与えることもありません.
declare module "./a" { interface TypeConstructorRegistry<T> { // 掛け算 mul: { lhs: T; rhs: T }; } } type MyExpr = Expr<"lit" | "add" | "mul">; // = { type: "lit"; data: { value: number } } // | { type: "add"; data: { lhs: MyExpr; rhs: MyExpr } } // | { type: "mul"; data: { lhs: MyExpr; rhs: MyExpr } }
数式の計算の定義
データ型を拡張可能な形で定義できたところで, 数式の計算も拡張可能な形で定義できることを確認しておきましょう.
まずは以下のような, 一般の数式を計算できるような枠組みを作っておきます.
/** 数式のうち 1 種類を計算するための関数の型 */ export type Evaluator<F extends TypeConstructor, G extends TypeConstructor> = ( expr: Expr2<F, G>, evalExpr: (expr: Expr<G>) => number, ) => number; /** 数式を計算する関数を作る */ export function makeEvalExpr<F extends TypeConstructor>( evaluators: { [F0 in F]: Evaluator<F0, F> }, ): (expr: Expr<F>) => number { const evalExpr = (expr: Expr<F>): number => { return evaluators[expr.type as F](expr, evalExpr); }; return evalExpr; }
続けて個別の数式の計算方法を定義します.
最終的にどのような組み合わせの数式を扱うかはこの時点ではわからないので, F という型引数に抽象化されていることに注目です.
/** リテラルの計算 */ export function evalLit<F extends TypeConstructor>(): Evaluator<"lit", F> { return (expr) => expr.data.value; } /** 足し算の計算 */ export function evalAdd<F extends TypeConstructor>(): Evaluator<"add", F> { return (expr, evalExpr) => evalExpr(expr.data.lhs) + evalExpr(expr.data.rhs); }
これを使って, リテラルと足し算からなるような数式は以下のように計算できます.
// リテラルと足し算からなる式 type MyExpr = Expr<"lit" | "add">; // 1 + 2 const myExpr: MyExpr = { type: "add", data: { lhs: { type: "lit", data: { value: 1 } }, rhs: { type: "lit", data: { value: 2 } }, }, }; // 関数を作って計算 const evalMyExpr = makeEvalExpr({ lit: evalLit(), add: evalAdd(), }); console.log(evalMyExpr(myExpr)); // => 3
掛け算にも対応したくなったら, まずは以下のように掛け算の計算方法を定義して,
function evalMul<F extends TypeConstructor>(): Evaluator<"mul", F> { return (expr, evalExpr) => evalExpr(expr.data.lhs) * evalExpr(expr.data.rhs); }
同じように組み合わせてやればよいですね.
// リテラル, 足し算, 掛け算からなる式 type MyExpr = Expr<"lit" | "add" | "mul">; // 1 + (2 * 3) const myExpr: MyExpr = { type: "add", data: { lhs: { type: "lit", data: { value: 1 } }, rhs: { type: "mul", data: { lhs: { type: "lit", data: { value: 2 } }, rhs: { type: "lit", data: { value: 3 } }, }, }, }, }; // 関数を作って計算 const evalMyExpr = makeEvalExpr({ lit: evalLit(), add: evalAdd(), mul: evalMul(), }); console.log(evalMyExpr(myExpr)); // => 7
数式を文字列として表示する関数の定義は読者の皆さんへの宿題とします.
おわりに
元の論文はプログラミング (特に関数型) で現れるある種の問題について, Haskell の言語機能を使うとそれなりにうまく解決できるというものでしたが, TypeScript でもそれを参考にしたテクニックが適用できて, こちらもそれなりにうまく問題を解決できるということがわかりました.
TypeScript を書くときに, TypeScript だけに注目するのではなく, 他の言語にまで視野を広げて解決策のヒントを探すのは, 自分の経験の中でもとても役に立っています. それらの言語のテクニックがそのまま TypeScript で使えるとは限りませんが, うまく TypeScript に落とし込んでパターン化できれば, 同じ TypeScript でも表現できる内容が段違いに変わってきます. やっていきましょう.
はてなエンジニア Advent Calendar 2024 の明日の担当は id:pokutuna さんです.
