似乎有共识认为应该把Parsec作为可应用的而不是单子的。在应用解析和单子解析之间,应用解析有什么好处呢?
- 风格
- 性能
- 抽象化
单子解析已经过时了吗?
似乎有共识认为应该把Parsec作为可应用的而不是单子的。在应用解析和单子解析之间,应用解析有什么好处呢?
单子解析已经过时了吗?
单子解析和应用解析的主要区别在于如何处理顺序组合。对于应用解析器,我们使用 (<*>)
,而对于单子解析器,我们使用(>>=)
。
(<*>) :: Parser (a -> b) -> Parser a -> Parser b
(>>=) :: Parser a -> (a -> Parser b) -> Parser b
单子模式更加灵活,因为它允许第二部分的语法依赖于第一部分的结果,但在实践中我们很少需要这种额外的灵活性。
你可能认为拥有一些额外的灵活性不会有任何问题,但实际上会有影响。它阻止了我们在运行解析器之前进行有用的静态分析。例如,假设我们想知道解析器是否能够匹配空字符串以及可能的匹配的第一个字符是什么。我们需要函数
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
然而,使用单子解析器,如果不知道输入内容,就无法知道第二部分的文法。
empty (x >>= f) = empty x && empty (f ???)
first (x >>= f) | empty x = first x `union` first (f ???)
| otherwise = first x
允许更多的内容,就意味着我们需要做更少的推理。这与动态类型和静态类型系统的选择类似。但是这样做有什么意义呢?我们可以利用额外的静态信息来避免在LL(1)解析中回溯,方法是将下一个字符与每个交替项的first
集进行比较。我们还可以通过检查两个备选项的first
集是否重叠,从静态上确定该语法是否存在歧义。另一个例子是它可用于误差恢复,正如S. Doaitse Swierstra和Luc Duponcheel在论文确定性、纠错组合解析器中所示。通常,然而,应用型解析和单子解析之间的选择已经由您使用的解析库的作者做出。当像Parsec这样的库公开了这两种接口时,使用哪种接口的选择纯粹是基于个人风格的。在某些情况下,应用代码比单子代码更易读,而有时则相反。(>>=)
单独暴露在类型类中的历史错误,这使得实例无法提供更优化的操作符实现,例如ap
。Applicative类避免了这个错误,并公开了<*>
(相当于ap
)的使用。 - Pi DelportApplicative
实例,而Applicative解析器通常不支持>>=
。 - dfeuer>>=
接收左侧解析器的结果并将其传递给右侧解析器,因此使得生成的解析器不可进行静态分析,因为现在解析器本身是图灵完备的。 <*>
和 <$>
不检查参数,因此,虽然解析器本身的输出是图灵完备的,因为您可以将任何东西放在 <$>
的左侧,但解析方面本身是受限的和静态可分析的。 - semicolon我能看出使用应用型解析器比单子型解析器更好的主要原因是,在任何情况下,喜欢应用程序代码胜过单子代码的主要原因是:应用程序较弱,因此使用起来更简单。
这是一种更普遍的工程法则的实例:使用最简单的工具完成工作。不要在只需要手推车时使用叉车。不要在切割优惠券时使用台锯。不要在可以使用纯代码时使用IO
。保持简单。
但有时,您需要Monad
的额外功能。如果您需要根据已计算的内容更改计算的进程,则可以确定这一点。在解析术语中,这意味着基于迄今为止已解析的内容确定如何解析接下来的内容;换句话说,您可以以这种方式构造上下文相关的语法。
option [] (anyToken >>= many . exactToken)
(这里的anyToken
和exactToken
实际上不是Parsec库的一部分,但可能应该是; 如果您不确定它们的作用,请问我)。相应的应用解析器会是什么样子? - Daniel Wagnerasum
。如果解析器的<|>
足够懒惰,我相信这将以非常低效的方式为您提供所需的语法。当然,并非所有解析器都有懒惰的<|>
。regex-applicative
肯定没有;我不知道更传统的解析器组合库是否有。 - dfeuer单子(Monads)是比应用函子(Applicatives)更丰富的抽象。你可以这样写:
instance (Monad m) => Applicative m where
pure = return
(<*>) = ap
但是没有编写的方法
instance (Applicative a) => Monad a where
return = pure
(>>=) = ???
return
和ap
,那么与使用pure
和<*>
相比,应该没有性能损失。因为Applicative是比Monad更严格的接口,这意味着<*>
有时可以比ap
更高效地优化。(但是通过巧妙的GHC重写规则,通常可以实现相同的优化。)Monadic parsing过时了吗?
由于Monad是Applicative的子集,我认为applicative parsing是monadic parsing的子集。
return
和 ap
,就不应该比使用 pure
和 <*>
有任何性能损失。但据我所知并非如此。在许多情况下(解析器只是其中之一),<*>
的性能要优于 ap
。 - semicolon
x
应用于空字符串来获取您命名为???
的值。更一般地说,您只需将空字符串提供给解析器,看看会发生什么就可以了。同样,至少可以以函数形式获得第一字符集first :: Parser a -> (Char -> Bool)
。当然,将后者转换为Set Char
将涉及对字符的低效枚举,这就是应用函子优势的地方。 - Heinrich Apfelmuslet x = pure f <*> y <*> x in empty x
。如果empty y
是False
,则计算不会终止...只是想指出,并不是那么简单。 - phadej