TypeScript 4.1による型レベルパーサコンビネーター

はじめに

これはTypeScript Advent Calendarの11日目の記事です。

TS 4.1で導入されたTemplate literal typesが世間で話題ですね。

• TypeScriptのTemplate string typesで湧き上がる界隈の様子 - Togetter
• Template String Types でパス文字列を解析してクエリする - Object.create(null)
• (ネタ) TypeScript 型パズルで作るmini interpreter by Yosuke Kurami
• TypeScriptにヤバい機能が入りそうなのでひとしきり遊んでみる - TechRacho
• Template titeral types で型上の簡易 Lisp パーサー - La Verda Luno
• Template Literal Types の基礎と .join・.split メソッドの型定義

楽しそうなので、私もTSに入門してみました！
そのような経緯で始めたため、型に呪われてしまい、型レベルプログラミングしかできなくなってしまった。

成果物: パーサコンビネータ

https://github.com/todesking/typesafe_parser

型レベル文字列操作が与えられた以上、それを使ってさまざまな文字列を解析したいわけですが、文法ごとにパーサを1から書くのはとても面倒です。特に実装が型レベルの場合は……

単純なパーサの部品を組み合わせることで、複雑な文法のパーサが定義できたら嬉しいですよね?

たとえば、文字'a'を受理するパーサp_aは

const p_a = read("a")

と書けて、文字'b'を受理するパーサp_bは

const p_b = read("b")

と書けます。この二つを組み合わせることで、'a'または'b'のどちらかを受理するパーサp_abが

const p_ab = choose(p_a, p_b)

と定義できます。このパーサを使えば、'a'または'b'の繰り返しを受理するp_ab_manyが

// rep0: 0以上の繰り返し
const p_ab_many = rep0(p_ab)

と定義できて、型レベルでも値レベルでもパーサとして機能します:

// [パース結果, 残りの文字列] が返る
const abab: [["a", "b", "a", "b"], ""] = parse(p_ab_many, "abab", {})
const a_x: [["a"], "x"] = parse(p_ab_many, "ax", {})

パース結果が一文字ごとに分解されていると面倒なので、結合する操作も欲しいですね。

// join: パース結果がstring[]であるパーサを受け取り、単一の文字列を結果とするパーサを返す
const p_ab_many2 = join(p_ab_many)
const abab2: ["abab", ""] = parse(p_ab_many_2, "abab", {})

機能

基本的な機能は以下の通りです。命令の直交性を考えるともう少し整理できそうですが、実用的な文法をパースするためにはこれくらいの機能は必要になってしまいますね。

• anyChar(): 任意の1文字を読む
• read(s1, s2, ...): 文字列s_iを読む。^[1]
• constant(p1, v): パーサp1を使ってパースし、成功したらその結果を捨てて値vを返す
• choose(p1, p2): パーサp1を使ってパースし、成功したらその結果を返す。失敗したらパーサp2でパースした結果を返す。
• not(p1, p2): 「p1で始まらない文字列」を表す。パーサp1を使ってパースし、成功したらパースに失敗する。p1が失敗した場合はp2でパースした結果を返す。
• seq(p1, p2): p1を使ってパースし、成功したら残りの文字列をp2でパースする。両方成功した場合、[p1のパース結果, p2のパース結果]を返す。
• pickFirst(p1, p2): p1を使ってパースし、成功したら残りの文字列をp2でパースする。両方成功した場合、p1のパース結果を返す。
• pickSecond(p1, p2): p1を使ってパースし、成功したら残りの文字列をp2でパースする。両方成功した場合、p2のパース結果を返す。
• rep0(p1): 失敗するまで繰り返しp1で入力をパースし続ける。成功した結果を配列で返す。
• opt(p1, default): p1でのパースに成功した場合はその結果を、失敗した場合はdefaultを返す。
• prepend(p1, p2): p2は配列を返すパーサ。p1を使ってパースし、成功したら残りの文字列をp2でパースする。[p1の結果, ...p2の結果]を返す。
• join(p1): p1はstring[]を返すパーサ。p1を使ってパースし、成功したら結果を単一文字列にして返す。
• ref()(name): 再帰的なパーサ定義に使用する(後述)

他の部品はこれらを組み合わせることで構成されています。たとえばpの1回以上の繰り返しであるrep1(p)はprepend(p, rep0(p))、区切り文字sepを挟んだpの1回以上の繰り返しrep1sep(p, sep)はprepend(p, rep0(pickSecond(sep, p))となります。

refを使うことでパーサの再帰的な定義が可能です。

// expr := num | '(' expr ')'
// という文法のパーサ

// "expr" と言う名前のパーサへの参照
const expr_ref = ref("expr")
const num = read("0", "1", ...)
const expr = choose(num, pickSecond("(", pickFirst(expr_ref, ")")))

// 名前とパーサの対応付け
const env = {expr: expr}

const x = parse(expr, "((1))", env)

実装

「結果がTのサブクラスになるパーサ」をParser<T>とします。
名前とパーサの対応付けRecord<string, Parser<unknown>>を環境と呼びます。
「パーサPおよび環境Eにより文字列Sをパースした結果」の型を Parse<P, S, E>とします:

export type Parse<
  P extends Parser<unknown>,
  S extends string,
  E extends Record<string, Parser<unknown>>
> = ...

各種類のパーサも型として表現しておきます:

export type Read<P extends string> = {
  type: "read";
  pattern: P[];
  _result: P[number];
};
export type Constant<T, P extends Parser<unknown>> = {
  type: "constant";
  parser: P;
  value: T;
  _result: T;
};
// ...

ここまで準備できたらナイーブに実装するのは簡単です。渡されたパーサの種類に応じてconditional typesを使って処理を分岐し、template literal typesを使って文字列の一致判定をし、子パーサを使う際はParseを再帰的に呼び出せばよい。

type  Parse<P, S, E> =
    P extends Read<infer T> ?
      S extends `${T}{infer S1}` // 実際はTがunionになるのでもうちょっと複雑
      ? [T, S1]
      : ParseError
   : P extends Constant<infer P1, infer T> ?
     // パーサP1でSをパースし、パース結果V1と残りの入力S1を得る
     Parse<P1, S, E> extends [infer V1, infer S1]
     ? [T, S1] // V1を捨て、TとS1を返す
     : ParseError
   // ...

そんなことをしたら、悪名高い Type instantiation is excessively deep and possibly infinite(2589)で死ぬのでは? という疑問を持った方は鋭い。実際死にます。

型の再帰制限を突破する

そう、ナイーブな実装だと、入力がちょっと長くなっただけで型の再帰上限に達して死んでしまうのです。幸いなことに、通常40-50くらいしかない再帰上限を大幅に緩和できるテクニックが知られています。

このテクニックは、｢型の構造に制約を加えることで再帰制限を無効化する方法」と「ネストした型から対数オーダーで目的の要素を取り出す方法」の二つから成ります。

まず、辞書型の内部での再帰は制限を受けないことを利用して、

type Rec<X> =
{__rec: /* Recを使った定義 */ }

という形式で再帰を扱うことで、{__rec: {__rec: ... {__rec: 目的の型}}} を得ます。

ここから目的の型を得るためには、ナイーブな方法だと線形オーダーの再帰が必要になりますが、一度に半分ずつ剥がすことで対数オーダーの再帰回数で済ませることができます。

type UnwrapAux<T> =
  T extends never ? never
  : T extends { __rec: { __rec: infer U } } ? { __rec: UnwrapAux<U> }
  : T extends { __rec: infer U } ? U
  : T;

type Unwrap<T> =
  T extends { __rec: unknown } ? Unwrap<UnwrapAux<T>> : T;

二つのテクニックを組み合わせることで、めでたく目的を達成することができます:

type F<X> = Unwrap<Rec<X>>

良かったですね。

というのが基本的な話なのですが、パーサに応用するのはそう単純な問題ではなかったのです。
さいしょにP1でパースし、失敗したらP2のパース結果を返すパーサChoose<P1, P2>について考えてみましょう。このパーサを評価するためには、まずP1を使ってパースし、その結果に応じてP2でパースするかどうか制御する必要があります。

type Parse<S, P> = {__rec:
  P extends Choose<infer P1, P2> ?
    Parse<S, P1> の結果に応じた分岐...
}

ところがParse<S, P1>の結果は不明個の{__rec: }に包まれているため、これを剥がさないと結果がわからないのです。
再帰制限を突破するためには、巨大なネストを一気に剥がすことで再帰回数を対数オーダーにするというテクニックが必要でした。Parseを呼ぶたびにネストを剥がしていては、結局線形オーダーで再帰呼び出しが発生してしまいます。
再帰制限を突破するためには、型を

type Rec<State> =
  Stateが終了条件を満たしている ? State
  : {__rec: Rec<次の状態<State>> }

という構造に帰着させる必要があるのです^[2]。

しばらくの間はTCO…… CPS…… とブツブツうわごとを言っている状態になっていたのですが、｢いままでのパース結果」や「次に実行すべき処理」を状態として管理すればよさそうなので、そのようなVMを実装することにしました。

まず、状態をこのように定義します:

type State<
  S extends string,        // 入力
  Vs extends unknown[],    // 値スタック
  Is extends Insn[],       // 次に実行する命令の列
  IStack extends Insn[][], // 命令のスタック
  Env extends Record<string, Insn[]> // 名前とパーサの対応付け
> = ...

そして、VMの命令列を以下のように定義します。擬似言語で書いてあるので、雰囲気で読んでください。

IAnyChar:
  [S1, V1] <- read(S, /./)
  Vs.push(V1)
  S <- S1

IRead<T>:
  [S1, V1] <- read(S, T)
  Vs.push(V1)
  S <- S1

ICall<Is2>:
  IStack.push(Is)
  Is <- Is2

IRef<Name>:
  IStack.push(Is)
  Is <- Env[Name]

IAbort:
  if Vs.top is error:
    Is <- IStack.pop()

長いので略

IPush<V>:
  Vs.push(V)

IPop:
  Vs.pop()

IPushS:
  Vs.push(S)

IPopS:
  S <- Vs.pop()

ISeq:
  V1 <- Vs.pop()
  V2 <- Vs.pop()
  Vs.push([V1, V2])

IChoose<Is2>:
  if Vs.top is error:
    Vs.pop()
    IStack.push(Is)
    Is <- Is2

INot:
  if Vs.top is error:
    Vs.pop()
    S <- Vs.pop()
  else:
    Vs.pop()
    Vs.pop()
    Vs.push(error)

IRep<Is2>:
  if Vs.top is error:
    Vs.pop()
  else:
    V1 <- Vs.pop()
    V2 <- Vs.pop()
    Vs.push([...V2, V1])
    Is <- [ICall<Is2>, IRep<Is2>, ...Is]

IOpt<V>:
  if Vs.top is error:
    Vs.pop()
    Vs.push(V)

IPrepend:
  V1 <- Vs.pop()
  V2 <- Vs.pop()
  Vs.push([V2, ...V1])

IJoin:
  V1 <- Vs.pop()
  Vs.push(V1.join(''))

たとえばP1のパースに成功したらVを返すパーサConstant<V, P1>の場合は

ICall<Compile<P1>> # P1でパース
IAbort             # 失敗したら抜ける
IPop               # パース結果を捨てる
IPush<V>           # Vを結果としてpush

という命令列になり、Choose<P1, P2>は

ICall<Compile<P1>> # P1でパース
IChoose<Compile<P2>>        # 値スタック先頭がエラーだったら、値を捨ててからP2を呼ぶ

となり、P1のパースに失敗する前提でP2でのパース結果を返すNot<P1, P2>は

IPushS         # 現在の入力を待避
...Compile<P1> # P1でパース
INot           # パース結果が成功なら失敗を積む。失敗なら待避した入力を復帰
IAbort         # 失敗が積まれていたら抜ける
...Compile<P2> # P2でパース

となります^[3]

あとはStateから次のStateを得るNextState<S>を書き(これはナイーブに命令の種類で分岐するだけ)、先ほどの再帰上限突破テクに組み込めばよろしい:

type Run<St extends TopState> =
  St extends State<infer S, [infer V, ...unknown[]], [], [], Record<string, Insn[]>>
  ? V extends Fail<unknown>
    ? V
    : [V, S]
  : { __rec: Run<NextState<St>> };

これで完璧ですね…… と思いきや、なぜか再帰回数が300回程度でTS2589が出てしまいました。原因がよくわからないのですが、内部の処理が複雑すぎると何らかの再帰回数バジェットを消費するのでしょうか?
とりあえず再帰回数を減らせばいいということで、一回の再帰で状態を10ステップ計算するという方法でどうにか逃げました……

// 再帰の際にNextStateではなくこれを呼ぶ
type FutureState<St extends TopState> =
  NextState<NextState<NextState<NextState<NextState<
  NextState<NextState<NextState<NextState<NextState<
    St
  >>>>>
  >>>>>

値レベルの実装

これはやるだけなのであまり面白くありませんが、関数のreturn typeとして例のVM処理系が登場して、とにかく何をやっても絶対に型が合わないという状況になったため、関数シグネチャのオーバロード(?)で解決したということがありました。TypeScriptはanyを使わなくても危険なキャストをする方法がいくらでもある。

export function parse<...>(p: P, s: S, env: E): ParseVM<P, S, E>;
function parse<...>(p: P, s: S, env: E): [unknown, string] {
  // 戻り値の型が単純なので合わせられる
}

型が合わない理由というのは色々あるのですが、Template literal typesのサポートがまだ弱いことも一因としてあります。単純な例としては:

// strがprefixで始まっている場合はprefix部を除いて返す。そうでなければstrをそのまま返す
function rm_prefix<S extends string, P exteds string>(str: S, prefix: P)
: S extends `${P}${infer Rest}` ? Rest : S {
  // どうやっても絶対に型が合わない！！！！！！！
}

「まだ」と言ってみたものの、これに型がつけられる時代は来ないのではという気がしますね……

結果

なんかJSONっぽい文法を定義してやって、

  // json = array | dict | num | str
  // array = '[]' | '[' json (',' json)* ']'
  // dict = '{}' | '{' str ':' json (',' dict_key ':' json)* '}'
  // num = [0-9]+
  // str = '"' ([^"] | '//"')* '"'
  const self_ref = ref<unknown>()('json')
  const str_body = join(rep0(choose(read('\\"'), not(read('"'), anyChar()))))
  const str = wrap(read('"'), str_body, read('"'))
  const num = join(rep1(number))
  const array = wrap(read('['), rep0sep(self_ref, read(',')), read(']'))
  const dict_kv = seq(str, pickSecond(read(':'), self_ref))
  const dict = wrap(read('{'), rep0sep(dict_kv, read(',')), read('}'))
  const json = choose(dict, choose(array, choose(num, str)))
  const env = {json}

無事型レベルでパースすることができました！！！

  const content = '{"num":123,"str":"abc","arr":[1,"a",[]],"dict":{"k1":1}}'
  const ok: [
    [
      ['num', '123'],
      ['str', 'abc'],
      ['arr', ['1', 'a', []]],
      ['dict', [['k1', '1']]]
    ],
    '']
  = parse(json, content, env)

本当は元のJSONと同じような型をつけたかったのですが、時間の問題で割愛されました。技術的には可能だと思われます。

デバッグ技術

型レベル例外や型レベルコンパイルエラー(評価結果にCompileError<T>が出現したらコンパイルエラーになるような型)などは存在しないため、デバッグにとても苦しみました。

type Bug<T> = {bug: T} を定義しておき、｢このパスは絶対に通らない」という場所に埋め込み、Tにデバッグ情報を詰めることで簡易printfデバッグ的なことをするというテクニックは割と便利。

パースに失敗すると例外を投げるようなAPIにしたので、失敗時の型は当然neverにすべきなのだが、そうするとエラー時の型レベル情報量がゼロになってしまうためtype Fail<Msg> = {fail: Msg}型にしました。never & {msg: "parse error"}とかやってみたけど、当然ながらneverに縮退してしまいました……

まとめ

• 型レベルで動作するパーサコンビネータが書けた
  • https://github.com/todesking/typesafe_parser
• 汎用的な実装はオーバヘッドが大きすぎるため、実用的型レベルパーサ(?)が必要な場合は文法ごとに手動で最適化した実装を使った方がいいです
• 俺は何をしているんだ

脚注

1. 複数のs_iがマッチした場合は未定(そのような状態がありうることにいま気づいた……)

2. 再帰の場所に制限を加えることで最適化できるという点で、末尾再帰最適化に似ていますね

3. Notが微妙にバグってる気がしてきました……