ちょっと前に話題になった hotscript の技法の紹介やら, ラムダ計算を TypeScript の型にコンパイルする話やらなんやら.
通常の型レベル関数
TypeScript の型エイリアスはパラメータを取れるので, これは型レベルの関数であるとみなせます.
type IsNumber<X> = X extends number ? true : false; type A = IsNumber<42>; // = true
一方でこのようにして定義された関数は第一級ではない, つまり関数そのものを他の関数の引数として渡したりすることができません.
type FilterUnion<F, X> = X extends unknown ? (F<X> extends true ? X : never) : never; // ~~~~ // ^ Error: Type 'F' is not generic. type U = FilterUnion<IsNumber, "foo" | 42 | true | null | 0 | undefined>; // ~~~~~~~~ // ^ Error: Generic type 'IsNumber' requires 1 type argument(s).
これでは上記の FilterUnion<F, X> のような高階の関数を定義することはできませんし, ラムダ計算のように関数だけを使ってプログラミングをするなんてもってのほかです.
これまでの第一級型レベル関数
第一級の関数を実現する方法の一つとして, これまでは interface が open-ended なことを利用する方法が広く知られていました[誰にとって?].
まずは以下のように関数定義のための interface Def<X> と, 関数全ての supertype Fun, 関数適用 App<F, X> を定義して,
interface Def<X> {} type Fun = keyof Def<unknown>; type App<F, X> = F extends Fun ? Def<X>[F] : never;
Def<X> の定義を拡張する形で関数を定義して, その名前自体を関数相当のものとして取り扱うことで, 第一級の関数を実現することができます.
interface Def<X> { IsNumber: X extends number ? true : false; } type FilterUnion<F, X> = X extends unknown ? (App<F, X> extends true ? X : never) : never; type U = FilterUnion<"IsNumber", "foo" | 42 | true | null | 0 | undefined>; // = 42 | 0
この方法の欠点は関数定義のスコープが単一でグローバルな Def<X> しかないことで, あるモジュール内でしか使わないような関数を定義しづらかったり, 定義するとしても他のモジュールと名前が被らないように工夫をする必要があります.
また扱いも通常の型とは異なり, 普通に export / import したりといったことができないため, 一般 (対義語: 逸般) のユーザー向けのライブラリとして提供もしづらいという懸念もありました.
(追記)
上記の方法では関数を文字列で表現していますが, 関数をカリー化するためにはオブジェクト型で表現して型引数を持ち回るなど一工夫必要そうです.
(追記終わり)
新しい第一級型レベル関数
そんな中おそらく新しい (少なくとも私は知らなかった) 第一級の関数を実現する方法が発見され, ライブラリ hotscript として公開されていました.
(追記)
特別新しいわけではなく, 遅くとも 2021 年には知られていたようだった.
(追記終わり)
hotscript で使われている方法はこれまでの方法とは異なり, interface の中で参照できる this をうまく使っています.
まずは関数全ての supertype となる interface Fun を定義して,
interface Fun { arg: unknown; ret: unknown; }
関数適用 App<F, X> を以下のように定義します.
intersection でくっつけている arg: X が interface の側からは this["arg"] として参照できてしまうのがミソ.
こんなことできちゃうんですね...
type App<F, X> = F extends Fun ? (F & { arg: X })["ret"] : never;
関数は Fun を継承した interface として定義して, 引数は this["arg"] で参照できます.
interface IsNumber extends Fun { ret: this["arg"] extends number ? true : false; } type FilterUnion<F, X> = X extends unknown ? (App<F, X> extends true ? X : never) : never; type U = FilterUnion<IsNumber, "foo" | 42 | true | null | 0 | undefined>; // = 42 | 0
この方法を使うと関数の名前空間はモジュール内に閉じているため, あるモジュールでしか使わないような関数も自由に定義できますし, また他の普通の型と同じように export / import することもできます. 便利ですね.
(追記)
カリー化された関数も, 以下のように複数の interface を使うことで表現できます.
interface Const extends Fun { ret: Const1<this["arg"]>; } interface Const1<X> extends Fun { ret: Const2<X, this["arg"]>; } type Const2<X, Y> = X;
(追記終わり)
型無しラムダ計算を TypeScript の型にコンパイルする
第一級の関数があればラムダ計算を表現してやるのがこの地方の文化, ということで型無しラムダ計算を上記の方法を使った型レベル関数に変換してみましょう.
ラムダ計算の項は以下で表されるものとします (let は本来不要ですが, 変換の都合上便利なので用意しています).
term ::= var | app | abs | let var ::= "a" | "b" | ... app ::= term term abs ::= "λ" var "." term let ::= "let" var "=" term "in" term
これをそのまま TypeScript の型に翻訳してやれば良いかというと, 実はそう一筋縄ではいきません. TypeScript の型では匿名の関数をインラインで書くことまではできないので, まずは一般の項を以下のような制限のかかった形に変換してやる必要があります (あるいは SKI コンビネータなんかに変換してやるのでも良いですが).
term ::= var | app | abs | let var ::= "a" | "b" | ... app ::= term_app term_app term_app ::= var | app abs ::= "λ" var "." term_abs term_abs ::= var | app | abs let ::= "let" var "=" term_let "in" term term_let ::= var | app | abs
変換をかいつまんで説明すると, 関数適用 app に含まれる匿名関数 abs に let で名前をつけてから, 変数のキャプチャに気をつけながら全ての関数をトップレベルに集めるといった感じです.
なんかやればできる.
あとは変換にパーサとコード生成をくっつけて, 突貫工事で完成したコンパイラがこちら.
TypeScript で書くと時間がかかりそうで (なぜなら絶対にパーサコンビネータライブラリを自作するところから始めてしまうため), 全然書いたことない Rust を書く良い機会かなと思って Rust で書きました.
コンパイラの実装言語の話はまあどうでもよくて, 実行例はこういう感じ. ここでは階乗を計算するプログラムを (ML 風の文法で) 記述していて,
let Id x = x; let Const x y = x; let Fix f = (fun x -> f (fun y -> x x y)) (fun x -> f (fun y -> x x y)); let One f x = f x; let Mul a b = fun f x -> a (b f) x; let Pred n = fun f x -> n (fun g h -> h (g f)) (Const x) Id; let True = Const; let False x y = y; let IsZero n = n (Const False) True; let Factorial n = let f = Fix (fun f n r -> (IsZero n) r (f (Pred n) (Mul n r)) ) in f n One;
コンパイルしてやるとこういう TypeScript のコードが出てきます.
interface Fun { arg: unknown; ret: unknown } type App<F, X> = F extends Fun ? (F & { arg: X })["ret"] : never; interface Id extends Fun { ret: Id$1<this["arg"]> } type Id$1<x> = x; interface Const extends Fun { ret: Const$1<this["arg"]> } interface Const$1<x> extends Fun { ret: Const$2<x, this["arg"]> } type Const$2<x, y> = x; // (中略) interface Factorial$v extends Fun { ret: Factorial$v$1<this["arg"]> } interface Factorial$v$1<f> extends Fun { ret: Factorial$v$2<f, this["arg"]> } interface Factorial$v$2<f, n> extends Fun { ret: Factorial$v$3<f, n, this["arg"]> } type Factorial$v$3<f, n, r> = App<App<App<IsZero, n>, r>, App<App<f, App<Pred, n>>, App<App<Mul, n>, r>>>; type Factorial$f = App<Fix, Factorial$v>; interface Factorial extends Fun { ret: Factorial$1<this["arg"]> } type Factorial$1<n> = App<App<Factorial$f, n>, One>;
あとは動作確認のために Church 数と通常の数値リテラル型を変換するコードを書いてやると, ちゃんと階乗が計算できていることがわかります.
type TestFactorial = ToNumber<App<Factorial, FromNumber<5>>>; // = 120
Type instantiation is excessively deep and possibly infinite. とか言われているのは本質ではないので目を瞑りましょう...
