Zenn
📝

ジェネレータ＝パーサー＋ランダムネス

2022/12/12に公開
Haskell
tech

この記事はHaskell Advent Calendar 2022の12日目の記事です。

先日（12/5~10）開催された OOPSLA 2022 で "Parsing Randomness" という面白い研究が発表されていたので簡単に紹介したいと思います。

論文が取り扱っている中心的なテーマは

"A generator is a parser of randomness"

という標語で表されています。

ジェネレータというのはあるデータ構造のランダムな値を生成するプログラムのことで、例えば

data Tree a = Leaf | Node (Tree a) a (Tree a)

というデータ構造であれば

Node Leaf 5 Leaf

や

Node Leaf 5 (Node Leaf 8 Leaf)

といった値をランダムに生成してくれるといったものです。こういったジェネレータが使われる例としてはQuickCheckのようなプロパティベーステストが有名でしょう。

標語が主張しているのはこういったジェネレータはランダムネスのパーサー（構文解析器）であるということです。ジェネレータは必要に応じて乱数を使いながらデータ構造を組み立てるプログラムだと考えると、予め十分な長さの乱数列を生成しておけばジェネレータはそれを先頭から消費しながらデータ構造を組み立てるパーサーとみなすことができ、この主張は自然に感じられるかもしれません。

論文では Free Monad によって作られた1つの抽象的なプログラムから

  • ジェネレータ
  • パーサー
  • ランダムネス

それぞれへの変換を考え、 ある種のジェネレータがパーサーとランダムネスの組み合わせで表せる ことを確認することにより、標語の主張を一定の条件下で証明するということが行われています。

ジェネレータとパーサーが対応することが分かると何が嬉しいかというと、片方の世界の知識をもう片方の世界に持っていくことが出来るということです。例えばパーサーの世界では「正規言語の微分」（Brzozowski微分）という概念を考えることができますが、これをジェネレータの世界に持ってくるとどうなるでしょうか？実はこのパーサーの微分に対応する概念を使って"与えられた条件を満たす値をサンプリングするプログラム"を作ることができます。このような方法で得られるサンプリング手法は新しく、論文では 選択勾配サンプリング（Choice Gradient Sampling (CGS)） と名付けられ詳しく調べられています。

この記事では論文を参考にジェネレータがパーサーとランダムネスの組み合わせで書けることを再現してみたいと思います。

数式を表現するデータ構造

最初にジェネレータやパーサーの対象となるデータ構造を考えたいと思います。論文中では二分木とラムダ計算が例として使われていますが、同じ例を扱ってもつまらないのでここでは以下のような型で表される 四則演算を使った計算式 をデータ構造として考えたいと思います。

data Expr = C Int
          | Add Expr Expr
          | Sub Expr Expr
          | Mul Expr Expr
          | Div Expr Expr
          deriving (Show)

簡単のため今回の計算式に現れる数字は全て1桁と仮定します。つまり C に与える候補となる数字は0~9の10通りです。この制限はあくまで実装を簡単にするためなので理論的な制約によるものではありません。

このデータ構造を使って、例えば

(1 + 2) × 3

という数式は

Mul (Add (Digit 1) (Digit 2)) (Digit 3)

のように表現します。

手始めにこのデータ構造のジェネレータを作ってみましょう。

genExpr :: Int -> IO Expr
genExpr 0 = C <$> (frequency $ zip (repeat 1) [0 .. 9])
genExpr h = do
  c <- frequency [(1, '+'), (1, '-'), (1, '*'), (1, '/'), (1, 'c')]
  case c of
    '+' -> Add <$> genExpr (h-1) <*> genExpr (h-1)
    '-' -> Sub <$> genExpr (h-1) <*> genExpr (h-1)
    '*' -> Mul <$> genExpr (h-1) <*> genExpr (h-1)
    '/' -> Div <$> genExpr (h-1) <*> genExpr (h-1)
    'c' -> C <$> (frequency $ zip (repeat 1) [0 .. 9])

単純に実装するととても巨大な値を生成してしまう可能性があるので、数式のネストの深さを h として与えられるようにしています。frequency は与えられたリストの要素を重みに応じてサンプリングする関数で System.Random を用いて以下のように実装しています。

frequency :: [(Int, a)] -> IO a
frequency xs = do
  let total = sum (map fst xs)
      ys = snd $ foldr (\(n, a) (accum, ys) -> (accum+n, (accum+n, a):ys)) (0, []) xs
  n <- randomRIO (1, total)
  pure . snd . last $ takeWhile (\(i, _) -> i >= n) ys

実際に genExpr を実行すると期待通りランダムな値が生成されることが分かります。

> genExpr 3
Mul (Add (Div (C 1) (C 7)) (Div (C 9) (C 3))) (Add (Div (C 9) (C 0)) (Div (C 3) (C 3)))

今度はパーサーを作ってみましょう。ここではポーランド記法で記述された数式を構文解析して Expr を組み立てるパーサーを考えます。ただしパーサーの実装を簡単にするため、通常のポーランド記法と異なり、数字の前には必ず c をつけるという約束にします。

このような記法に従うと、例えば

(1 + 2) × 3

という数式は

*+c1c2c3

という文字列で表されます。

このパーサーは以下のように実装することができます。

parseExpr :: Int -> ReadP Expr
parseExpr 0 = get >> C . read . pure <$> get
parseExpr h = do
  c <- get
  case c of
    '+' -> Add <$> parseExpr (h-1) <*> parseExpr (h-1)
    '-' -> Sub <$> parseExpr (h-1) <*> parseExpr (h-1)
    '*' -> Mul <$> parseExpr (h-1) <*> parseExpr (h-1)
    '/' -> Div <$> parseExpr (h-1) <*> parseExpr (h-1)
    'c' -> C . read . pure <$> get

ReadP は Text.ParserCombinators.ReadP として base で提供されているパーサーコンビネータの型です。

試しに parseExpr を使って文字列の構文解析を行ってみましょう。

> readP_to_S (toP (fgenExpr 3)) "*+c1c4c3"
[(Mul (Add (C 1) (C 4)) (C 3),"")]

期待通りの挙動になっていますね。readP_to_S は

readP_to_S :: ReadP a -> String -> [(a, String)]

という型の関数で ReadP a を実際に実行できる関数の型 String -> [(a, String)] に変換する役割を果たしています。

パーサー parseExpr の実装をよく見ると、ジェネレーター genExpr の実装に構造がかなり似ている事が分かると思います。

FGen a

それではこれらのジェネレータとパーサーを統一するプログラムを Free Monad を使って実装していきましょう。

実装を簡単にするため Freer Monad を使って実装します。

data Freer f a where
  Pure :: a -> Freer f a
  Bind :: f a -> (a -> Freer f b) -> Freer f b

Freer f はfに何の制約をつけること無く Functor, Applicative, Monad のインスタンスにすることができます。

instance Functor (Freer f) where
  fmap f (Pure a)    = Pure (f a)
  fmap f (Bind fa k) = Bind fa (fmap f . k)

instance Applicative (Freer f) where
  pure a = Pure a
  (Pure f)    <*> fa = fmap f fa
  (Bind ff k) <*> fa = Bind ff (\f -> k f <*> fa)

instance Monad (Freer f) where
  (Pure a)    >>= k = k a
  (Bind fa k) >>= l = Bind fa ((>>= l) . k)

なぜこのようなことが可能なのかというと裏には離散圏からの左Kan拡張があるのですが、Freer Monadの詳しい話をすると長くなってしまうので気になる人は他の文献を参照してみてください。

ジェネレータやパーサーを抽象化し統一する概念は Free Generator と呼ばれています。Free Generator を表す型 FGen a を以下の様に実装します。

type Weight = Int

type Choice = Char

data Pick a = Pick [(Weight, Choice, FGen a)]

type FGen a = Freer Pick a

Weight はサンプリングの時に考慮する重み、Choiceはパースする対象やランダムネスの出力対象となる記号列の記号、PickはChoiceの種類に合わせた分岐における選択肢、このPickを Freer Monad にしたものが FGen a となります。実は Pick の実装方法からもわかる通り今回のアプローチは有限個の記号／選択肢からなる対象にしか使うことが出来ないという暗黙の制約があります。

この FGen a を使って Expr の Free Generator である FGen Expr を実装すると以下のようになります。

fgenExpr :: Int -> FGen Expr
fgenExpr 0 = Bind
  (Pick [(1, 'c', Pure 'c')])
  (\_ -> Bind (Pick $ map (\c -> (1, c, Pure $ C (read [c]))) ['0'..'9']) Pure)
fgenExpr h = Bind
  (Pick [(1, '+', Pure '+'), (1, '-', Pure '-'), (1, '*', Pure '*'), (1, '+', Pure '+'), (1, 'c', Pure 'c')])
  (\c -> case c of
    '+' -> Add <$> fgenExpr (h-1) <*> fgenExpr (h-1)
    '-' -> Sub <$> fgenExpr (h-1) <*> fgenExpr (h-1)
    '*' -> Mul <$> fgenExpr (h-1) <*> fgenExpr (h-1)
    '/' -> Div <$> fgenExpr (h-1) <*> fgenExpr (h-1)
    'c' -> Bind (Pick $ map (\c -> (1, c, Pure $ C (read [c]))) ['0'..'9']) Pure)

FGen a からの変換

まずは Free Generator からジェネレーターへの変換を実装してみましょう。実装する前に例外ケースを取り扱うための Pattern Synonyms と補助関数を用意しておきます。

void :: FGen a
void = Bind (Pick []) Pure

pattern Void :: FGen a
pattern Void <- Bind (Pick []) _

isVoid :: FGen a -> Bool
isVoid Void = True
isVoid _    = False

これらを使って、ジェネレーターへの変換は以下のように実装することが出来ます。

toG :: FGen a -> IO a
toG Void = undefined
toG (Pure a) = pure a
toG (Bind (Pick xs) f) = do
  x <- frequency $ map (\(w, _, x) -> (w, x)) xs
  a <- toG x
  toG (f a)

このようにして作ったジェネレータへの変換を実際に動かしてみましょう。

> toG (fgenExpr 3)
Add (Sub (Sub (C 5) (C 9)) (Mul (C 9) (C 8))) (Add (Add (C 9) (C 9)) (Add (C 9) (C 8)))

期待通りの挙動になっていますね。

同様にパーサーへの変換も実装してみましょう。

toP :: FGen a -> ReadP a
toP Void = pfail
toP (Pure a) = pure a
toP (Bind (Pick xs) f) = do
  c <- get
  x <- case find (\(_, d, _) -> c == d) xs of
         Just (_, _, x) -> pure x
         Nothing -> pfail
  a <- toP x
  toP (f a)

作ったパーサーへの変換を実際に動かしてみましょう。

> readP_to_S (toP (fgenExpr 3)) "*+c1c4c3"
[(Mul (Add (C 1) (C 4)) (C 3),"")]

期待通りに動いていますね。

パーサーを使ってジェネレータを作るためには構文解析を行う対象、すなわちランダムネスを作る必要があります。ランダムネスもこれまで同様 Free Generator を変換することで作ります。

toR :: FGen a -> IO String
toR Void = undefined
toR (Pure _) = pure ""
toR (Bind (Pick xs) f) = do
  (c, x) <- frequency (map (\(w, c, x) -> (w, (c, x))) xs)
  s <- toR (x >>= f)
  pure (c:s)

このランダムネスを Expr の場合に実行すると、ランダムな数式の文字列表現を吐き出すようになっていることが分かります。

> toR (fgenExpr 3)
"**-c7c8+c6c6c5"

これまでに実装した toG, toP, toR は具体的なデータ型 Expr には依存せず、 抽象的な Free Generator FGen a からの変換になっているということが重要 です。

最後にパーサーへの変換 toP とランダムネスへの変換 toR を組み合わせることで、ジェネレータへの変換 toG を再現できることを実装して確認してみましょう。

toG' :: FGen a -> IO a
toG' g = (fst . head) <$> (readP_to_S (toP g) <$> toR g)

型の違いを吸収するためにいくつか余分な関数を適用していますが、本質的には

toG g ≅ toP g <$> toR g

という関係になっているのが分かると思います。

最後に念の為、このように実装した toG' を実際に実行してみましょう。

> toG' (fgenExpr 3)
Mul (Mul (C 7) (Mul (C 0) (C 7))) (Add (Add (C 5) (C 2)) (Add (C 3) (C 7)))

期待通りランダムな数式が生成されていますね👏

まとめ

この記事ではあるデータ構造の値をランダムに生成するジェネレータがランダムネスとそのパーサーの組み合わせで書けるということを確認しました。この記事で実装したコードはこちらのReplitで全て公開しているのでオンラインで試すことが出来ます。

Free Generator も万能ではなく再現できるジェネレータには限界があり原論文でも詳しく書かれています。こういった制限をどこまで取り払えるのかも今後の発展の一つとして楽しみですね。また今回のジェネレータ／パーサー／ランダムネスの関係はかなり実装に近いレイヤーで議論されっているので、圏論等の数学を用いてどこまで抽象化出来るのかも個人的には気になっています👀 この記事で取り上げた話に加え、原論文ではさらに Free Generator の微分を定義し、それを活用したサンプリング手法である選択勾配サンプリング（CGS）というアルゴリズムを実装し、既存のアルゴリズム（棄却サンプリング）との比較も行っていますので、気になる人は原論文もチェックしてみてください！

https://dl.acm.org/doi/10.1145/3563291

＼読んでいただきありがとうございました！／
この記事が面白かったら いいね♡ をいただけると嬉しいです☺️
バッジを贈っていただければ次の記事を書くため励みになります🙌

Discussion