Template literal types で型上の簡易 Lisp パーサー

Tech
Share

TypeScript に Template literal types というかなりヤバい革新的な新しい機能の PR が出された。
Template literal types and mapped type ‘as’ clauses

体を慣らすのを兼ねて簡易 Lisp パーサーを型上で実装してみた。正直なところ Lisp でプログラミングはほぼしないが、文法が簡単に見え Template literal types で処理できそうだったため若気の至りでやってしまった。さすがに実行はできない（数値演算が無理ゲー）。意外と Lisp が興味深い言語に感じた。

有名どころの Lisp 派生言語の共通項を実装すると実装時間がやばそうなので、構文は最小限にした。
[Try it on the Playground] -> Parse<`'(try your code)`>

Template literal types

Template literal types は、TypeScript 4.1 に向けて PR として提出された新しい機能だ。Template literal types and mapped type ‘as’ clauses #40336
（途中で挙動が変わったり名称が変わったりしたため、PR を読み進めるときは気を付けるとよい。）

Template literal types の内容をつかむには PR のコメントを読む必要があるが、端的に言えば以下（抜粋）の書き方が可能になる。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 文字列の結合
type ConcatNeo<S1 extends string, S2 extends string> = `${S1}|||${S2}`;
type Join<T extends (string | number | boolean | bigint)[], D extends string> =
    T extends [] ? '' :
    T extends [unknown] ? `${T[0]}` :
    T extends [unknown, ...infer U] ? `${T[0]}${D}${Join<U, D>}` :
    string;
    
type T1 = ConcatNeo<`abc`, `def`>; // "abc|||def"
type T2 = Join<[`hoge`, `fuga`, `piyo`], `-`>; // "hoge-fuga-piyo"

// 文字列の分割
type MatchPair<S extends string> =
    S extends `[${infer A},${infer B}]`? { 0: A, 1: B } : unknown;
type Split<S extends string, D extends string> =
    string extends S ? string[] :
    S extends '' ? [] :
    S extends `${infer T}${D}${infer U}` ? [T, ...Split<U, D>] :
    [S];

type T3 = MatchPair<`[1,'2']`>; // { 0: "1", 1: "'2'" }
type T4 = Split<`foo->bar->baz`, `->`>;  // ["foo", "bar", "baz"]

文字列の分割、文字の変換（変換先の型を問わない）と結合を組み合わせることで、文字列の変換や構造体へのパースなど様々なことができる。
infer との組み合わせが協力で、Conditional Type でネストしてやるとほぼ関数型プログラミングみたいなことができる（再帰回数制限内においては）。

1
2
3
4
5
6
7
8
type Mask<S extends string, Result extends string = ``> =
    S extends `${infer C}${infer R}` ?
        C extends `0` | `1` | `2` | `3` | `4` | `5` | `6` | `7` | `8` | `9` ?
            Mask<R, `${Result}*`> :
        Mask<R, `${Result}${C}`>
    : Result;

type T5 = Mask<`p1a2s3s`>; // "p*a*s*s"

応用

リンクをたどれた奴だけ。

Lisp パーサー

[Try it on the Playground]（再掲）

Lisp で以前から素人ながら知っている程度の構文は実装している。 (+ 1 2.3e4 "hoge") とか '((-fuga- . '1) piyo) ; comment とか。ほかに Common List や Scheme の有名どころでは # には対応していない。

メモ書き程度の解説

関数型プログラミングのやり方みたいになってる。

  • 再帰かつ “関数” を超えて状態を保持できないので、すべての状態を引数として受け渡す。
  • 大体 1 文字の処理が終わると SExpression に戻る（文字列・コメントは例外的に一括マッチ）。
  • InitExprs にリスト内の項目を積み、リストの終わりでポップし上位の InitExprs にこれを積む。
  • . の扱いが鬼門で、それが理由で条件分岐が多くなっている。
  • 数値の判定もまた難しい。
  • infer を駆使して “関数” の戻り値を取得（パターンマッチ）する。
  • InitExprs extends [unknown, unknown] で特定のリスト件数にマッチする。
  • 1 文字にマッチし、次いでその文字の種類でマッチする。

型レベル文字列プログラミングの辛かったところ

  • 再帰回数上限ですぐエラーになる。下記を参考にできるだけ誤魔化す。
    TypeScript、型レベルプログラミングエラー抑制テクニック | Tkr Blog
  • ある文字の集合が現れるまで一括で取得、という処理が不可能だ。例えば、正規表現っぽく記号文字までの部分を取得する、など。
    1 文字ずつしか処理できない部分が多くなり、上の再帰上限がよりシビアになる。
  • 単体テストはできそうな予感はあるが、デバッグがかなり難しい。
    上のパーサーでは ParseError を定義・利用・伝搬して確認しやすい工夫はしている。