69

Parsec をモナドではなくアプリカティブとして使うべきだというコンセンサスがあるようです。モナド構文解析に対する適用的構文解析の利点は何ですか?

  • スタイル
  • パフォーマンス
  • 抽象化

モナドは解析していますか?

4

5 に答える 5

93

モナド構文解析と適用的構文解析の主な違いは、順次構成の処理方法にあります。アプリケーションパーサーの場合は を使用(<*>)しますが、モナドの場合は を使用します(>>=)。

(<*>) :: Parser (a -> b) -> Parser a -> Parser b
(>>=) :: Parser a -> (a -> Parser b) -> Parser b

モナドのアプローチは、2 番目の部分の文法が最初の部分の結果に依存できるため、より柔軟ですが、実際にはこの追加の柔軟性が必要になることはほとんどありません。

ある程度の柔軟性があれば問題ないと思うかもしれませんが、実際には可能です。これにより、パーサーを実行せずに、パーサーで有用な静的分析を行うことができなくなります。たとえば、パーサーが空の文字列に一致するかどうか、一致する可能性のある最初の文字は何かを知りたいとしましょう。関数が欲しい

empty :: Parser a -> Bool
first :: Parser a -> Set Char

アプリケーション パーサーを使用すると、この質問に簡単に答えることができます。(私はここで少しごまかしています。候補のパーサー「言語」に対応するデータ コンストラクターがあると想像してください) (<*>)。(>>=)

empty (f <*> x) = empty f && empty x
first (f <*> x) | empty f   = first f `union` first x
                | otherwise = first f

ただし、モナドパーサーでは、入力がわからないと、2番目の部分の文法が何であるかわかりません。

empty (x >>= f) = empty x && empty (f ???)
first (x >>= f) | empty x   = first x `union` first (f ???)
                | otherwise = first x

より多くのことを許可することで、推論を減らすことができます。これは、動的型システムと静的型システムの選択に似ています。

しかし、これのポイントは何ですか？この追加の静的な知識を何に使用できますか? firstたとえば、次の文字を各代替のセットと比較することにより、LL(1) 解析でバックトラックを回避するために使用できます。first2 つの選択肢のセットが重複しているかどうかを確認することで、これがあいまいであるかどうかを静的に判断することもできます。

もう 1 つの例は、 S. Doaitse Swierstra と Luc Duponcheel による論文Deterministic, Error-Correcting Combinator Parsersに示されているように、エラー回復に使用できることです。

ただし、通常、アプリケーション解析とモナド解析の選択は、使用している解析ライブラリの作成者によって既に行われています。Parsec などのライブラリが両方のインターフェイスを公開する場合、どちらを使用するかの選択は、純粋に文体的なものです。場合によっては、アプリカティブ コードがモナディック コードより読みやすく、逆の場合もあります。

于 2011-10-22T23:45:53.160 に答える
14

パーサーが純粋に適用可能である場合、実行前にその構造を分析して「最適化」することができます。パーサーがモナドである場合、それは基本的にチューリング完全なプログラムであり、ほとんどすべての興味深い分析を実行することは、停止問題 (つまり、不可能) を解決することと同じです。

ああ、そうです、スタイルの違いもあります...

于 2011-10-27T20:14:03.713 に答える
11

MonadicパーサーよりもApplicativeパーサーを好む主な理由は、どのような状況でも、MonadicコードよりもApplicativeコードを好む主な理由と同じです。

これは、より一般的なエンジニアリングの口実の例です。仕事を成し遂げる最も単純なツールを使用してください。台車が使用する場合は、フォークリフトを使用しないでください。クーポンを切り取るためにテーブルソーを使用しないでください。IO純粋である可能性があるときにコードを記述しないでください。単純にする。

ただし、場合によっては、の追加のパワーが必要Monadになります。これの確かな兆候は、これまでに計算されたものに基づいて計算のコースを変更する必要がある場合です。解析用語では、これは、これまでに解析されたものに基づいて、次に来るものを解析する方法を決定することを意味します。つまり、この方法で状況依存の文法を作成できます。

于 2011-10-22T23:02:08.573 に答える
4

Parsec で Applicative を使用する利点は、スタイルだけです。モナドには、より強力であるという利点があります。コンテキスト依存のパーサーを実装できます。

Doaitse Swierstra の UU 解析は、適用的にのみ使用するとより効率的です。

于 2011-10-22T19:10:16.230 に答える
3

モナドは厳密にはApplicativesよりも特徴的な抽象化です。あなたは書くことができます

instance (Monad m) => Applicative m where
  pure  = return
  (<*>) = ap

でも書き方が無い

instance (Applicative a) => Monad a where
  return = pure
  (>>=) = ???

そうです、それは本質的にスタイルの問題です。andを使用するreturnと、 andを使用してもパフォーマンスが低下apすることはないと思います。pure<*>Applicative は Monad より厳密に小さいインターフェースであるため、これは、<*>が よりも高度に最適化される場合があることを意味しますap。(しかし、巧妙な GHC 書き換えルールを使用すると、多くの場合、同じ最適化を実現できます。)

モナドは解析していますか?

モナドはアプリカティブのサブセットであるため、アプリカティブ解析はモナド解析のサブセットであると結論付けます。

于 2011-10-22T20:51:52.787 に答える