Zenn
🚂

Scala 3のMatch Typesでコンパイル時正規表現エンジン

2022/03/04に公開
Scala
関数型プログラミング
正規表現
tech

はじめに

Scala 3にはMatch Typesという機能がある。これはScala 2の単に型の別名を与えるだけだったtypeに対して、=の右側の型を簡約（Reduction）する機能を追加したものである。このMatch Typesを利用することでコンパイル時に様々な計算ができるので、今回の記事ではMatch Typesを利用して簡単なコンパイル時正規表現エンジンの実装を解説する。
なお、この記事の完全なソースコードは下記のGitHubリポジトリーに置かれている。

この記事を読んで分からないことや意見がある場合は気軽にコメントなどで教えてほしい。

コンパイル時正規表現の使い方

具体的な説明に移る前に今回実装したコンパイル時正規表現エンジンの使い方について説明する[1]。

EvalTest.scala
summon[
  Match[
    AST[".*abc.*"],
    "auaoeuaoeu__abc__khaoukrsao"
  ] =:= true
]

このように型Matchの第1型引数にAST[".*abc.*"]のような形で正規表現を与え、第2型引数に"auaoeuaoeu__abc__khaoukrsao"という型[2]を与え、もし第2型引数の型が正規表現にマッチした場合はtrueとなり、そうでない場合はfalseとなる。
現在この正規表現エンジンは次のメタ文字に対応している。

メタ文字 意味
. 任意の1文字
a* aの0回以上の繰り返し
(a|b) aまたはb
ab aの次にb
(a) aをグルーピング
\m メタ文字mを文字にする

これのメタ文字を使うと次のような複雑な正規表現マッチングも可能になる。

EvalTest.scala
summon[
  Match[
    AST[
      "(ab(c|.)|e*)*"
    ],
    "ab8eeeeabee"
  ] =:= true
]

実装

ここからはMatch Typesを利用したコンパイル時正規表現の実装について説明する。

正規表現パーザー

正規表現のパーザーとは文字列レベルで(ab(c|.)|e*)*のように与えられた正規表現は次のようなASTへと変換する部分である。

Alt[
  Con[
    Con[
      Lit["a"], Lit["b"]
    ],
    Alt[
      Lit["c"], Dot
    ]
  ],
  Star[Lit["e"]]
]

これには次の3つのステップが必要となる。

  1. 入力された型レベル文字列を1文字ずつ分解してトークン列へ変換する
  2. トークン列を操車場アルゴリズムで逆ポーランド記法へと変換する
  3. 逆ポーランド記法を解釈して正規表現ASTを作成する

1. トークン列への変換

文字列を1文字ずつのHListへ変換するなどの型レベルのユーティリティーは@xuwei-kさんのMatchTypeParseEval.scalaから借用した。
MatchTypeParseEval.scalaとの違いとして、正規表現の場合は次のようにトークン変換を2つのMatch Typesで行っている。

Parser.scala
type StrToEscapedToken[A <: String] =
  A match
    case "*" => Lit["*"]
    case "." => Lit["."]
    case "|" => Lit["|"]
    case "(" => Lit["("]
    case ")" => Lit[")"]
    case "\\" => Lit["\\"]
    case _ => Lit[A]

type StrToToken[A <: String] =
  A match
    case "*" => Asta
    case "." => Dot
    case "|" => VBar
    case "(" => Start
    case ")" => End
    case _ => Lit[A]

これはメタ文字を普通の文字として利用する\のため、可能な場合は2つの文字を見て判断するからである。\から始まっていなかったり、残りの文字が2文字以下などではStrToTokenを利用する。あとはこの2つを振り分けるHListToTokensを次のように定義する。

Parser.scala
type HListToTokens[A <: HList] <: HList =
  A match
    case x1 :+: x2 :+: xs =>
      x1 match
        case "\\" =>
          StrToEscapedToken[x2] :+: HListToTokens[xs]
        case _ =>
          StrToToken[x1] :+: HListToTokens[x2 :+: xs]
    case x :+: xs =>
      StrToToken[x] :+: HListToTokens[xs]
    case HNil =>
      HNil

2. 操車場アルゴリズムによる逆ポーランド記法への変換

この部分は@lotzさんのHaskellの型パズルで作るMini Interpreterを大きく参考にした。
ただ、パーズ対象が数式であれば1 + 2のように演算子+を省略しないが、一方で正規表現ではabがCon[Lit["a"], Lit["b"]]となるように、連結する場合に明示的な記号を用いない。したがって次ような戦略を取った。

  • トークンAbsorbは文字列の正規表現からは生成されないが、括弧の開始などのときにもしAbsorbがオペレータースタック[3]の先頭である場合、ここでは正規表現の連結をオペレータースタックに積まない
    • ただし、このときオペレータースタックの先頭にあるAbsorbを取り除く
  • このようにすることで(a|b)cのようにaやbの1つしかシンボルがないところで不要な連結が行なわれないように制御する

これらを踏まえた結果、次のようにかなり難解な実装となった。

Parser.scala
type ShuntingYard[In <: HList] =
  ShuntingYard0[HNil, Absorb :+: HNil, In]

type ShuntingYard0[Out <: HList, Op <: HList, In <: HList] <: HList =
  (Op, In) match
    case (HNil, HNil) =>
      ReverseHList[Out]
    case (sym :+: op, HNil) =>
      ShuntingYard0[sym :+: Out, op, HNil]
    case (Absorb :+: op, Start :+: in) =>
      ShuntingYard0[Out, Absorb :+: Start :+: op, in]
    case (Absorb :+: op, sym :+: in) =>
      ShuntingYard0[sym :+: Out, op, in]
    case (Plus :+: op, Start :+: in) =>
      ShuntingYard0[Plus :+: Out, op, In]
    case (Plus :+: op, End :+: in) =>
      ShuntingYard0[Plus :+: Out, op, In]
    case (Start :+: op, VBar :+: in) =>
      ShuntingYard0[Out, VBar :+: op, in]
    case (sym :+: op, VBar :+: in) =>
      ShuntingYard0[sym :+: Out, op, In]
    case (_, Asta :+: in) =>
      ShuntingYard0[Asta :+: Out, Op, in]
    case (_, Start :+: in) =>
      ShuntingYard0[Out, Absorb :+: Start :+: Plus :+: Op, in]
    case (Start :+: op, End :+: in) =>
      ShuntingYard0[Out, op, in]
    case (VBar :+: op, End :+: in) =>
      ShuntingYard0[VBar :+: Out, op, in]
    case (sym :+: op, End :+: in) =>
      ShuntingYard0[sym :+: Out, op, End :+: in]
    case (VBar :+: op, sym :+: in) =>
      ShuntingYard0[sym :+: Out, Op, in]
    case (_, sym :+: in) =>
      ShuntingYard0[sym :+: Out, Plus :+: Op, in]

3. ASTの作成

ASTの作成は次のようなナイーブなコードで完了した。

type RPN[Symbols <: HList] =
  RPN0[HNil, Symbols]

type RPN0[Stack <: HList, Symbols <: HList] =
  (Stack, Symbols) match
    case (x :+: HNil, HNil) =>
      x
    case (x1 :+: xs, Asta :+: ys) =>
      RPN0[Star[x1] :+: xs, ys]
    case (x1 :+: x2 :+: xs, VBar :+: ys) =>
      RPN0[Alt[x2, x1] :+: xs, ys]
    case (x1 :+: x2 :+: xs, Plus :+: ys) =>
      RPN0[Con[x2, x1] :+: xs, ys]
    case (xs, y :+: ys) =>
      RPN0[y :+: xs, ys]

これにより型レベルの正規表現ASTが得られる。

正規表現エンジン

ここまでで正規表現ASTを得たので、ここからは正規表現を型レベル文字列にマッチングするエンジンの実装となる。正規表現エンジンの実装方法にはいくつかやり方があるが、Match Typesのような簡約と相性がよさそうと個人的に思った微分（Derivative）[4]を使う方法を採用した。微分というと難しそうであるが、アルゴリズムの詳細は下記の記事にある通りかなり簡単なパターンマッチングで記述することができる。

ほとんどこの記事のパターンマッチを型レベルへ持ってくるだけであった。ほぼ同じなので、詳細を知りたい場合はEval.scalaのソースコードを紹介するだけとする。

まとめ

このように実は正規表現エンジンそのものよりも、型レベル文字列からASTを得る実装に数倍手間がかかっている。実はScala 3の最新の3.1.2-RC1においてはMatchsという型レベル文字列に対する型レベルのマッチングが標準で用意されているので、このような面倒な実装をする必要はない。
また@oaratさんはラムダ計算のコンパイル時インタープリターを実装しており、このMatch Typesがチューリング完全であることが明らかとなった。

参考文献

脚注

  1. ここでA =:= Bとあったとき（1）AはBのサブタイプ（A <: B）かつ（2）BはAのサブタイプ（B <: A）の両方が満された場合に=:=のインスタンスが存在する。この記事での用途はこれを利用して、主に左側のコンパイル時正規表現が型レベル簡約の結果、右辺の型と等しくなったことをsummonによる=:=のインスタンスの取得ができるかどうかに帰着させている。 ↩︎

  2. ここで型の中に表われるtrueや".*abc.*"やなどは一般的には「Booleanの値」や「文字列型の値」に見えるが、Scala 3には文字列やtrueなど一部のリテラル値をそれにのみ対応する型へと昇格させる機能がある。もう少し詳細に説明すると、たとえばIntという型に対してその型の値は1や-10などたくさんある。一般的な型はIntのようにその型の値から型は一意であるが、逆に型から値は一意に定まらない。しかしここで型Unitについて考えるとUnit型の値となるのは()ただ1つであるため、Unit型については型から値・値から型の両方が一意に定まることになる。そこで改めてtrueや".*abc.*"という型は、さきほど説明したUnitのように1つだけの真偽値trueであったり、あるいは文字列値".*abc.*"に対応する型となる。この記事ではこのような型として表われた特定の文字列を型レベル文字列などと呼称する。 ↩︎

  3. @lotzさんの記事では「演算子用のスタック」などと呼称されていたものを、この記事ではこう呼ぶことにする。 ↩︎

  4. 正規表現を微分するとはどういうことなのかというと、文字列wがあるとして文字列をリストのような構造と考えるとc :: wsのように先頭からどんどん取り出していくことができる。このように文字列においては「先頭と残りを分離する」という操作ができるが、この操作を正規表現に対して行うのが正規表現の微分となる。文字列w @ c :: wsに対する正規表現rのマッチングを、文字cをマッチさせた残りの正規表現rsを残りの文字列であるwsに対し再帰的に微分し、最終的に残りの文字列が尽きたときに残った正規表現が空を受理するという問題に帰着させている。 ↩︎

Discussion