Consider adding recoverability to the vocabulary of parser combinators
(sorry for repost, seems GMail's html processing on my last email has rendered it barely readable, so again with plain text here) Dear Cafe, I'm still not fully clear about the confusion regarding megaparsec's behavior that I posted lately here. But now comes to my mind that it may have some problem rooted in the lacking of recoverability semantic with respect to parser combinators, some quoting from http://hackage.haskell.org/package/parser-combinators/docs/Control-Applicati... The *A note on backtracking* section
Combinators in this module are defined in terms Applicative and Alternative operations.
This parser fails unconditionally without providing any information about
And `empty`'s doc: the cause of the failure. Clearly `empty` is used to express failure, but there is seemingly no device to explicitly express whether a failure is recoverable. Then I observed megaparsec's implicit rule as currently implemented is like: *) a failure with no input consumed can be recovered by rest parsers *) a failure with some input consumed can not be recovered by rest parsers This works to great extent, but I would think the expressiveness can be further extended for a parser from the application, to tell the library that some input induces recoverable failure. I have no expertise to suggest whether `MonadPlus` and/or `MonadFail` are suitable devices to be considered, but as megaparsec has implemented instances for them, I do feel some tweaks would be possible and meaningful. Best regards, Compl
Hi Compl, At least, for the example you gave on this list, it can be fixed by returning Nothing instead of using the facility for failure baked into (mega)parsec. (Proposed diff for reference: https://github.com/complyue/dcp/pull/3) "Returning Nothing" can be seen as adding a new channel for errors, turning the Parser monad into `MaybeT Parser`. Then `return Nothing` is how `empty` is defined by `MaybeT`, allowing that error to be caught and recovered from at the point where it was thrown, no backtracking. (And the original failure mode of Parser becomes `lift empty`.) Does that address your problem? Cheers, Li-yao On 10/28/2020 5:18 AM, Compl Yue wrote:
(sorry for repost, seems GMail's html processing on my last email has rendered it barely readable, so again with plain text here)
Dear Cafe,
I'm still not fully clear about the confusion regarding megaparsec's behavior that I posted lately here. But now comes to my mind that it may have some problem rooted in the lacking of recoverability semantic with respect to parser combinators, some quoting from http://hackage.haskell.org/package/parser-combinators/docs/Control-Applicati...
The *A note on backtracking* section
Combinators in this module are defined in terms Applicative and Alternative operations.
And `empty`'s doc:
This parser fails unconditionally without providing any information about the cause of the failure.
Clearly `empty` is used to express failure, but there is seemingly no device to explicitly express whether a failure is recoverable. Then I observed megaparsec's implicit rule as currently implemented is like:
*) a failure with no input consumed can be recovered by rest parsers *) a failure with some input consumed can not be recovered by rest parsers
This works to great extent, but I would think the expressiveness can be further extended for a parser from the application, to tell the library that some input induces recoverable failure.
I have no expertise to suggest whether `MonadPlus` and/or `MonadFail` are suitable devices to be considered, but as megaparsec has implemented instances for them, I do feel some tweaks would be possible and meaningful.
Best regards, Compl
_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.
Hi Li-yao,
I appreciate your help especially the PR as a working fix.
But personally I don't like the overall method of your solution, I can see
Monad Transformers are powerful enough to tackle similar problems, but I'm
not satisfied by the ergonomics in composing monads with transformers.
`ParsecT` had already caused me much pain to get started in the beginning,
and I'm still not fluent (comfortable) in transforming monads, especially
I'm afraid I will have to transform much of the standard combinator
functions, in order to get the real case parser working, as its resulting
AST is much more complex.
I still have faith in the improvement of megaparsec as a well known parser
combinator library (I regard it as the best for engineering needs among
other libraries), and I must admit megaparsec already elegantly works 99%
out of my current use cases, and the very issue we are talking about is a
nice-to-have rather than must-to-have, so I would think we still have time
to anticipate more options to come out.
And I particularly like to see parser combinators have this issue addressed
in its own design space.
Thanks again with best regards,
Compl
On Wed, Oct 28, 2020 at 8:19 PM Li-yao Xia
Hi Compl,
At least, for the example you gave on this list, it can be fixed by returning Nothing instead of using the facility for failure baked into (mega)parsec. (Proposed diff for reference: https://github.com/complyue/dcp/pull/3)
"Returning Nothing" can be seen as adding a new channel for errors, turning the Parser monad into `MaybeT Parser`. Then `return Nothing` is how `empty` is defined by `MaybeT`, allowing that error to be caught and recovered from at the point where it was thrown, no backtracking. (And the original failure mode of Parser becomes `lift empty`.)
Does that address your problem?
Cheers, Li-yao
On 10/28/2020 5:18 AM, Compl Yue wrote:
(sorry for repost, seems GMail's html processing on my last email has rendered it barely readable, so again with plain text here)
Dear Cafe,
I'm still not fully clear about the confusion regarding megaparsec's behavior that I posted lately here. But now comes to my mind that it may have some problem rooted in the lacking of recoverability semantic with respect to parser combinators, some quoting from
http://hackage.haskell.org/package/parser-combinators/docs/Control-Applicati...
The *A note on backtracking* section
Combinators in this module are defined in terms Applicative and Alternative operations.
And `empty`'s doc:
This parser fails unconditionally without providing any information about the cause of the failure.
Clearly `empty` is used to express failure, but there is seemingly no device to explicitly express whether a failure is recoverable. Then I observed megaparsec's implicit rule as currently implemented is like:
*) a failure with no input consumed can be recovered by rest parsers *) a failure with some input consumed can not be recovered by rest
parsers
This works to great extent, but I would think the expressiveness can be further extended for a parser from the application, to tell the library that some input induces recoverable failure.
I have no expertise to suggest whether `MonadPlus` and/or `MonadFail` are suitable devices to be considered, but as megaparsec has implemented instances for them, I do feel some tweaks would be possible and
meaningful.
Best regards, Compl
_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.
(sorry I forgot the text color again, maybe https://darkreader.org is
to blame, anyway plain text mode I should use)
Hi Li-yao,
I appreciate your help especially the PR as a working fix.
But personally I don't like the overall method of your solution, I can
see Monad Transformers are powerful enough to tackle similar problems,
but I'm not satisfied by the ergonomics in composing monads with
transformers. `ParsecT` had already caused me much pain to get started
in the beginning, and I'm still not fluent (comfortable) in
transforming monads, especially I'm afraid I will have to transform
much of the standard combinator functions, in order to get the real
case parser working, as its resulting AST is much more complex.
I still have faith in the improvement of megaparsec as a well known
parser combinator library (I regard it as the best for engineering
needs among other libraries), and I must admit megaparsec already
elegantly works 99% out of my current use cases, and the very issue we
are talking about is a nice-to-have rather than must-to-have, so I
would think we still have time to anticipate more options to come out.
And I particularly like to see parser combinators have this issue
addressed in its own design space.
Thanks again with best regards,
Compl
On Wed, Oct 28, 2020 at 8:19 PM Li-yao Xia
Hi Compl,
At least, for the example you gave on this list, it can be fixed by returning Nothing instead of using the facility for failure baked into (mega)parsec. (Proposed diff for reference: https://github.com/complyue/dcp/pull/3)
"Returning Nothing" can be seen as adding a new channel for errors, turning the Parser monad into `MaybeT Parser`. Then `return Nothing` is how `empty` is defined by `MaybeT`, allowing that error to be caught and recovered from at the point where it was thrown, no backtracking. (And the original failure mode of Parser becomes `lift empty`.)
Does that address your problem?
Cheers, Li-yao
On 10/28/2020 5:18 AM, Compl Yue wrote:
(sorry for repost, seems GMail's html processing on my last email has rendered it barely readable, so again with plain text here)
Dear Cafe,
I'm still not fully clear about the confusion regarding megaparsec's behavior that I posted lately here. But now comes to my mind that it may have some problem rooted in the lacking of recoverability semantic with respect to parser combinators, some quoting from http://hackage.haskell.org/package/parser-combinators/docs/Control-Applicati...
The *A note on backtracking* section
Combinators in this module are defined in terms Applicative and Alternative operations.
And `empty`'s doc:
This parser fails unconditionally without providing any information about the cause of the failure.
Clearly `empty` is used to express failure, but there is seemingly no device to explicitly express whether a failure is recoverable. Then I observed megaparsec's implicit rule as currently implemented is like:
*) a failure with no input consumed can be recovered by rest parsers *) a failure with some input consumed can not be recovered by rest parsers
This works to great extent, but I would think the expressiveness can be further extended for a parser from the application, to tell the library that some input induces recoverable failure.
I have no expertise to suggest whether `MonadPlus` and/or `MonadFail` are suitable devices to be considered, but as megaparsec has implemented instances for them, I do feel some tweaks would be possible and meaningful.
Best regards, Compl
_______________________________________________ Haskell-Cafe mailing list To (un)subscribe, modify options or view archives go to: http://mail.haskell.org/cgi-bin/mailman/listinfo/haskell-cafe Only members subscribed via the mailman list are allowed to post.
participants (2)
-
Compl Yue -
Li-yao Xia