Reimplemented parsers from the ground up.
Reimplemented parsers from the ground up.

The types for parsers are now based on Hutton and Meijer's monadic parser combinators.

Their type is (in pseudo-Haskell):

   Parser(T) = String -> Maybe(String, T)

this is fine for non-streaming parsing, but for streaming we need to allow parsing to
ask for more data:

   Parser(T) = String -> ParseResponse(T)

   data ParseResponse(T) = Backtrack(String) | Done(String,T) | Continue(Parser(T))

but this has another problem -- this allows backtracking at any point, not just on
the first character of input, which requires arbitrary buffering for combinators such
as sequencing.

We restrict attention to LL(1) grammars, which resolve all choices based on the first
character of input. Choice is of the form:

   \Sigma_{c \in C} c.P_c

that is, we only allow guarded sums. For this purpose, we have a type:

   GuardedParser(T) = String -> GuardedParseResponse
   Parser(T) = String -> ParseResponse(T)

   data GuardedParseResponse(T) = Backtrack(String) | Done(String,T) | Continue(Parser(T))
   data ParseResponse(T) = Done(String,T) | Continue(Parser(T))

that is, you can only backtrack on the initial move, not on subsequent moves.

The other change is to ensure that all method calls can be statically dispatched.
In the above, there's a case Continue(Parser(T)) which requires dynamic dispatch.
We change this to make being a parser a trait that ensures that the continue case
uses the same type, so doesn't require any dynamic dispatch:

   class Parser P where
     parse: (P T) -> String -> ParseResponse(P,T)

   data ParseResponse(P,T) = Done(String,T) | Continue(P(T))

Note that the type doesn't change. In Rust, this allows method dispatch to be performed
statically.

The down-side of static dispatch is that parsers form an applicative functor rather than
a monad, for the usual reason that applicative functors allow for more static analysis.

asajeffrey/parsell