[Haskell-cafe] Alternative instance for non-backtracking parsers

[Doaitse Swierstra]

> Op 24 aug. 2018, om 7:33  heeft Paul <aquagnu at gmail.com> het volgende geschreven:
> 
> >  Of course the example above can be mitigated by moving the char '-' outside the alternative.
> 
> Right, this works fine:
> 
>   pq :: Parsec Void String Bool
>   pq = do
>     char '-'
>     (q <|> p)
> 
> which for me, means that Haskell has not real backtracking.

You are confusing the language “Haskell” with the library “Parsec”. Parsec is just one of the many parser combinator libraries. 

> Btw, `Alternative` is not backtracking (as well as List permutations).

The class “Alternative” does in no way specify how parsers should behave; it defines an interface. One might expect <|> to be associative, but even that is in no way guaranteed.

> After "do" should happen context saving. I think it's possible to be implemented manually... As workaround, may be to pick char '-', but don't consume it (and to fail if it is not expecting '-') ? Or to switch to another parser libs: arrow based, happy, bindings to good known libs... For me, parsers combinators absolutely ever are big problem: a lot of tricks, low performance, may be it's typical for any "elegant" approach.

 - Some libraries do not need “try” constructs to set backtrack points, but may be a bit slower; other libraries are more greedy and a bit faster. 
 - Some parsers keep track of where you are in the input at some cost, others just parse as fast as possible without having to update line and position counters (handy when you know the input is correct since it was machine-generated). 
 - Some libraries provide nice error messages about what was expected at some cost, other libraries just report that they did not find a parse. 
 - Some libraries try to “repair” the input and continue parsing when they cannot proceed otherwise, some others just stop when they get stuck. 
 - Some libraries hang on to the input so they may backtrack to a point far back, some libraries work in an online way and pursue all parses “in parallel”, i.e. they perform a breadth first search for a successful parse. 
 - Some libraries analyse the grammar before parsing starts and warn for non-sensical parsers, others just do not. 
 - Some libraries already return part of the computed result during the parsing process -and thus exhibit online behaviour-, other libraries (usually the monadic ones) construct a huge closure describing the result, which only becomes available when a succesful parse was found. 
 - Some libraries analyse a grammar for left-recursion and transform them into an equivalent non-left-recusrive one at some costs. 
 - Some libraries memoise the parsing, and may be faster, but in return cannot handle real monadic constructs. 
 - Etc., Etc.

My impression is that with respect to parser combinators you just jump a bit too fast to a conclusion.

Doaitse


> 
> 
> 23.08.2018 22:41, Olaf Klinke wrote:
>> Dear Cafe,
>> 
>> can anyone explain the use of an Alternative instance for a parser monad where the parser (p <|> q) does not backtrack automatically when p fails?
>> Consider megaparsec for example. When p is a parser that does not backtrack automatically, then (p <|> q) never succeeds with q. While I do understand that fine-grained control of backtracking is desirable for performance reasons in general, it escapes me why such an Alternative instance could be useful. See also "A note on backtracking" in the parser-combinators package documentation [1].
>> 
>> Minimal code example and context below.
>> 
>> Thanks,
>> Olaf
>> 
>> [1] http://hackage.haskell.org/package/parser-combinators-1.0.0/docs/Control-Applicative-Combinators.html
>> 
>> import Text.Megaparsec
>> import Text.Megaparsec.Char
>> import Data.Void
>> 
>> p :: Parsec Void String Bool
>> p = do
>>   char '-'
>>   string "True"
>>   return True
>> q :: Parsec Void String Bool
>> q = do
>>   char '-'
>>   string "False"
>>   return False
>> 
>>>>> parseTest (p <|> q) "-True"
>> True
>>>>>  parseTest (p <|> q) "-False"
>> 1:2:
>> unexpected "Fals"
>> expecting "True"
>> -- Since q can parse "-False", I would expect (p <|> q) to parse "-False", too.
>> 
>> Context:
>> Of course the example above can be mitigated by moving the char '-' outside the alternative. But we might not have control over whether the two parsers share a common prefix. I am trying to write some code generic in the parser monad and I am having difficulties making my code work for both backtracking and non-backtracking parsers. If possible, I'd like to keep my parser type class devoid of a 'try' combinator, which would be the identity function for parser monads that always backtrack.
>> _______________________________________________
>> 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.
> 
> _______________________________________________
> 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.