[Caml-list] ANN: angstrom

[Caml-list] ANN: angstrom

[Spiros Eliopoulos]

[-- Attachment #1: Type: text/plain, Size: 1817 bytes --]

Hey List,

It is with great pleasure that I announce the initial release of angstrom,
a parser-combinator library that I have been developing over the past
several months:

  https://github.com/inhabitedtype/angstrom
  http://opam.ocaml.org/packages/angstrom

Angstrom exposes monadic and applicative interfaces for composition, and
supports incremental input through buffered and unbuffered interfaces. Both
interfaces give the user total control over the blocking behavior of their
application, with the unbuffered interface enabling zero-copy IO. Parsers
are backtracking by default and support unbounded lookahead.

Whereas many OCaml parser combinator libraries claim heritage from the
Parsec[0] Haskell library, angstrom instead follows the design and
semantics of attoparsec[1], hence the name[2]. For a high-level comparison
of Angstrom's features to other parser-combinator libraries, see the table
included in the README:

  https://github.com/inhabitedtype/angstrom#comparison-to-other-libraries

The source distribution ships with a JSON parser, which I've benchmarked
against ezjsonm and yojson. Yojson wins hands down (it benefits greatly
from not having to support non-blocking incremental input), though the
angstrom-based parser comes in second both in terms of latency and
allocations. The results can be found here:

  https://gist.github.com/seliopou/7487875d36914efe74f736aaa3fbed16

There are several more performance improvements in the pipeline, which
should further reduce allocation rates, in some cases dramatically so. More
on that in the next release, along with other developments.

As always, issues and pull requests are welcomed.

-Spiros E.

[0]: https://hackage.haskell.org/package/parsec
[1]: https://github.com/bos/attoparsec
[2]: https://en.wikipedia.org/wiki/%C3%85ngstr%C3%B6m

[-- Attachment #2: Type: text/html, Size: 2598 bytes --]

Re: [Caml-list] ANN: angstrom

[Daniel Bünzli]

Looks cool.

Le vendredi, 22 juillet 2016 à 15:35, Spiros Eliopoulos a écrit :  
> For a high-level comparison of Angstrom's features to other parser-combinator libraries, see the table included in the README:
>  
> https://github.com/inhabitedtype/angstrom#comparison-to-other-libraries
Do you have a story for precise line-column and byte count tracking ? It's quite important in practice to be able to give good error reports.  

Also does the API easily allow to do best-effort decoding (after reporting an error allow to resync input by discarding and restart the parsing process) ?  
  
> Yojson wins hands down (it benefits greatly from not having to support non-blocking incremental input),

I guess it also benefits of not implementing the standard at all, e.g. it won't check the validity of the underlying character stream.  

Also regarding benchmarks it would be more interesting to have benchmarks on real world examples where you convert json input to concrete ocaml data types. E.g. it would be cool if you could provide a jsonm-like streaming interface with angstrom and then use angstrom's combinators to parse the stream of json lexeme into OCaml data structures.

Best,  

Daniel

Re: [Caml-list] ANN: angstrom

[Spiros Eliopoulos]

[-- Attachment #1: Type: text/plain, Size: 2694 bytes --]

On Fri, Jul 22, 2016 at 5:38 PM, Daniel Bünzli <daniel.buenzli@erratique.ch>
wrote:

> > For a high-level comparison of Angstrom's features to other
> parser-combinator libraries, see the table included in the README:
> >
> > https://github.com/inhabitedtype/angstrom#comparison-to-other-libraries
> Do you have a story for precise line-column and byte count tracking ? It's
> quite important in practice to be able to give good error reports.
>

Angstrom's targeting the use case of network protocols and serialization
formats, a use case where line/column numbers are of dubious value, and
doesn't really make sense when dealing with binary formats. So it will
likely never support line/column tracking. It will however at some point
report character position on failure. I have a local branch that implements
it, though it's untested.


> Also does the API easily allow to do best-effort decoding (after reporting
> an error allow to resync input by discarding and restart the parsing
> process) ?


From what I understand, this would require users to modify input rather
than putting any correction logic into the parser itself. Angstrom does not
support this functionality, and likely won't. In principle the only change
necessary would be to simply surface the success continuation on failure.
Everything else is accessible to the user (except for failure position, see
above). Why it's valuable to do this outside of the parser is unclear to me
though.

> Yojson wins hands down (it benefits greatly from not having to support
> non-blocking incremental input),
>
> I guess it also benefits of not implementing the standard at all, e.g. it
> won't check the validity of the underlying character stream.
>
> Also regarding benchmarks it would be more interesting to have benchmarks
> on real world examples where you convert json input to concrete ocaml data
> types. E.g. it would be cool if you could provide a jsonm-like streaming
> interface with angstrom and then use angstrom's combinators to parse the
> stream of json lexeme into OCaml data structures.


Doing that would seem to muddle application and library performance
measurements within the benchmark. Arguably, constructing a generic
in-memory representation is doing the same in essence. At least this way
it's an "application" that's easy for benchmarks to standardize on (more or
less) and implement, so that one can use the benchmark results to compare
different libraries.

But anyways, there's nothing in principle preventing it from happening.
There parser would look something like this:

  skip_many (token >>| (handler : json_token -> unit))

-Spiros E.

[-- Attachment #2: Type: text/html, Size: 3564 bytes --]

Re: [Caml-list] ANN: angstrom

[Daniel Bünzli]

Le vendredi, 22 juillet 2016 à 23:46, Spiros Eliopoulos a écrit :
> Angstrom's targeting the use case of network protocols and serialization formats, a use case where line/column numbers are of dubious value,

Well when you are dealing with large malformed json streams it's nice to know where they error… But if you target binary data only a byte count should suffice.
  
> From what I understand, this would require users to modify input rather than putting any correction logic into the parser itself.

No the parser itself is in charge of performing this. A very simple example of this is when you get an UTF-8 decode error. You want to be able to report the error and let the client restart the decode which is easy to do by finding a synchronization byte in the input. But again this may not be useful for binary protocols, it is however useful for decoding text and parsing languages.
  
> Doing that would seem to muddle application and library performance measurements within the benchmark. Arguably, constructing a generic in-memory representation is doing the same in essence.

Not really, it can completely change the outcome of your benchmarks. For example jsonm allows you to completely eschew going through a generic in-memory representation before being able to extract the data.  

Best,  

Daniel

Re: [Caml-list] ANN: angstrom

[Cole Brown]

[-- Attachment #1: Type: text/plain, Size: 1951 bytes --]

it seems like such a pedantic critique would be most productively presented off
the main band, no?

congrats on the release! exciting to see something like this in the ocaml
world. i look forward to its continued improvement.

cole

On Friday, July 22, 2016, Daniel Bünzli <daniel.buenzli@erratique.ch> wrote:

> Le vendredi, 22 juillet 2016 à 23:46, Spiros Eliopoulos a écrit :
> > Angstrom's targeting the use case of network protocols and serialization
> formats, a use case where line/column numbers are of dubious value,
>
> Well when you are dealing with large malformed json streams it's nice to
> know where they error… But if you target binary data only a byte count
> should suffice.
>
> > From what I understand, this would require users to modify input rather
> than putting any correction logic into the parser itself.
>
> No the parser itself is in charge of performing this. A very simple
> example of this is when you get an UTF-8 decode error. You want to be able
> to report the error and let the client restart the decode which is easy to
> do by finding a synchronization byte in the input. But again this may not
> be useful for binary protocols, it is however useful for decoding text and
> parsing languages.
>
> > Doing that would seem to muddle application and library performance
> measurements within the benchmark. Arguably, constructing a generic
> in-memory representation is doing the same in essence.
>
> Not really, it can completely change the outcome of your benchmarks. For
> example jsonm allows you to completely eschew going through a generic
> in-memory representation before being able to extract the data.
>
> Best,
>
> Daniel
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs

[-- Attachment #2: Type: text/html, Size: 2429 bytes --]

Re: [Caml-list] ANN: angstrom

[Daniel Bünzli]

Le samedi, 23 juillet 2016 à 08:41, Cole Brown a écrit :
> it seems like such a pedantic critique would be most productively presented off the main band, no?

Do you think that asking for a compelling story at the error reporting level is a *pedantic* critique ?  

If that is the case then I hope I won't ever in my life have to use any software produced by you.

Beyond correctness, how you deal with error conditions along the whole computing chain is precisely what distinguishes mediocre software from excellent one, both from a programmer and end user perspsective. If the foundations you build on do not provide the facilities that allow you to do so then, by transitivity, you are only bound to produce mediocre software.

Now it seems that I was misguided in what Angstrom is providing, I thought it was a general combinator parsing library that I could eventually use to write my decoders and parsers in either binary or text formats, but given that it doesn't seem to care too much about error reporting, it may not be.

> congrats on the release! exciting to see something like this in the ocaml world. i look forward to its continued improvement.
It seems such pointless congratulations would be most productively presented off the main band, no ?  

Best,  

Daniel

Re: [Caml-list] ANN: angstrom

[Spiros Eliopoulos]

[-- Attachment #1: Type: text/plain, Size: 2807 bytes --]

> Le vendredi, 22 juillet 2016 à 23:46, Spiros Eliopoulos a écrit :
> > Angstrom's targeting the use case of network protocols and serialization
> formats, a use case where line/column numbers are of dubious value,
>
> Well when you are dealing with large malformed json streams it's nice to
> know where they error… But if you target binary data only a byte count
> should suffice.
>

Most text editors give users the ability to seek to a byte position. That
should be sufficient to debug parse errors for both binary data and those
intended for human consumption.


> > From what I understand, this would require users to modify input rather
> than putting any correction logic into the parser itself.
>
> No the parser itself is in charge of performing this. A very simple
> example of this is when you get an UTF-8 decode error. You want to be able
> to report the error and let the client restart the decode which is easy to
> do by finding a synchronization byte in the input. But again this may not
> be useful for binary protocols, it is however useful for decoding text and
> parsing languages.


Seems like this would be just as easily accomplished by writing a parser
that does the appropriate error recovery while accumulating descriptions of
the error. The value of handing restart control to the client seems dubious
to me, though. If the client will always abandon a parse if there's a
correctable parse error, then the parser should just fail with the first
error (no accumulation). If the client will always accept any parse
correction from the parser, then it should accumulate all errors and return
them along with the parse result. If the client selectively picks which
parse errors it will accept corrections for, then the parser can be
parameterized on those choices. Inverting control in the failure case
doesn't really seem to offer any benefits, especially if the client is just
going invoke the continuation (or not) without modification.


> > Doing that would seem to muddle application and library performance
> measurements within the benchmark. Arguably, constructing a generic
> in-memory representation is doing the same in essence.
>
> Not really, it can completely change the outcome of your benchmarks. For
> example jsonm allows you to completely eschew going through a generic
> in-memory representation before being able to extract the data.


The point of a benchmark is to offer some comparison between different
systems by subjecting them to identical (as possible) test loads. The more
and varied test loads involved in a benchmark, the better. But absence of a
multitude does not invalidate the one, especially when the one is
representative of how most web applications deal with JSON data.

-Spiros E.

[-- Attachment #2: Type: text/html, Size: 3468 bytes --]

Re: [Caml-list] ANN: angstrom

[Daniel Bünzli]

Le lundi, 25 juillet 2016 à 16:15, Spiros Eliopoulos a écrit :
> If the client will always accept any parse correction from the parser, then it should accumulate all errors and return them along with the parse result.

No, in practice you want to be able to report errors before having seen all the input.  

> But absence of a multitude does not invalidate the one, especially when the one is representative of how most web applications deal with JSON data.
I personally find generic JSON representations rarely useful, I prefer to work with proper OCaml data structures.
  


Best,  

Daniel

Re: [Caml-list] ANN: angstrom

[Spiros Eliopoulos]

[-- Attachment #1: Type: text/plain, Size: 1014 bytes --]

On Mon, Jul 25, 2016 at 11:44 AM, Daniel Bünzli <daniel.buenzli@erratique.ch
> wrote:

> Le lundi, 25 juillet 2016 à 16:15, Spiros Eliopoulos a écrit :
> > If the client will always accept any parse correction from the parser,
> then it should accumulate all errors and return them along with the parse
> result.
>
> No, in practice you want to be able to report errors before having seen
> all the input.


So in this situation, the main parse succeeds with errors corrections that
are going to be logged somewhere. If something besides logging would be
done with the errors, it would fall into one of the other cases described
above. The latency difference is on the order of milliseconds, maybe
seconds, depending on the application. It's not nearly enough time to make
a difference in whatever log analysis process they would be fed into,
whether it's inspection by a human (certainly) or some other automated
process (they all typically include a ton of latency already).

-Spiros E.

[-- Attachment #2: Type: text/html, Size: 1390 bytes --]

Re: [Caml-list] ANN: angstrom

[Daniel Bünzli]

Le lundi, 25 juillet 2016 à 18:07, Spiros Eliopoulos a écrit :

> So in this situation, the main parse succeeds with errors corrections that are going to be logged somewhere. If something besides logging would be done with the errors, it would fall into one of the other cases described above. The latency difference is on the order of milliseconds, maybe seconds, depending on the application. It's not nearly enough time to make a difference in whatever log analysis process they would be fed into, whether it's inspection by a human (certainly) or some other automated process (they all typically include a ton of latency already).

You are making a lot of assumptions about how the client should use the library or what humans are supposed to tolerate… Giving back control to the client in case of error and allow it to restart the process allows to lift the constraints you put on the client.

Best,  

Daniel

Re: [Caml-list] ANN: angstrom

[Spiros Eliopoulos]

[-- Attachment #1: Type: text/plain, Size: 3205 bytes --]

On Mon, Jul 25, 2016 at 12:21 PM, Daniel Bünzli <daniel.buenzli@erratique.ch
> wrote:

> You are making a lot of assumptions about how the client should use the
> library or what humans are supposed to tolerate…

Nope, just one or two that seem pretty reasonable. First, there's not much
else a client of a parser can do with those errors without breaking
conceptual abstraction boundaries. Any action that a client would want to
take that wasn't logging properly belongs in the parser itself. A design to
the contrary would require the client of the parser to embody knowledge of
the parsing process itself, which defeats modularity, reuse, and ultimately
kills compositionality. So the only client assumption is that the client
finds these sorts of properties desirable.
Second, I'm well aware of human tolerances for feedback latency. Such
topics have been making the rounds in The New York Times, pop design books,
and the blogosphere for more than a decade now, so it's hardly an obscure
topic. I've also built and commercialized systems for application
performance management, which required a deep understanding of end-user
experience, business use cases, and operational practices.

The design I described has worst case failure reporting latency not
exceeding the latency of a successful parse. If you're exceeding those
latency tolerances at the parsing step, there is no hope of redemption for
the latency of the rest of your pipeline. And these aren't even
catastrophic failures. As you describe them they're, more or less, warnings.


> Giving back control to the client in case of error and allow it to restart
> the process allows to lift the constraints you put on the client.

While such a design sometimes benefits the system _as a whole_, it
certainly comes at a cost. In the case where clients are meant to
explicitly handle parse errors and restart the parse _through control
inversion_, the cost is the compositionality. That may be a worthwhile cost
to pay in some cases, but those cases have not yet revealed themselves to
me. On the other hand, Angstorm allows you to construct parsers
compositionally, and reuse them in just the same way. It even allows users
to design parsers that will report parse warnings, or even receive certain
kinds of errors are return a decision (that the parser is designed to
understand) about how to proceed. Whether or not that's a worthwhile design
is another question. I would say it's not but there's no accounting for
taste. For supporting composition, it's certainly better than control
inversion.

To bring it back, I think this discussion is focusing a bit too much on the
implementation of a single Angstrom parser, rather than the capabilities of
the library as a whole. Angstrom can suit the needs of many architectural
styles, whether its a "direct" style or "streaming" style, or that leads to
parsers that give clients fine-grained control over error recovery. It's a
parser combinator library, after all. Your parsers can do whatever you
design them to do, take whatever parameters they need to, and following a
few rules of thumb, still deliver good performance.

-Spiros E.

[-- Attachment #2: Type: text/html, Size: 3869 bytes --]

Re: [Caml-list] ANN: angstrom

[Daniel Bünzli]

Le lundi, 25 juillet 2016 à 21:37, Spiros Eliopoulos a écrit :

> While such a design sometimes benefits the system _as a whole_, it certainly comes at a cost. In the case where clients are meant to explicitly handle parse errors and restart the parse _through control inversion_, the cost is the compositionality.

[…]
> For supporting composition, it's certainly better than control inversion.

The point is that clients are usually parsers themselves. You are not actually loosing compositionnality by supporting what you call "control inversion", you are increasing it by allowing the parsers to be used differently according to the context.  

A simple example is contrasting parsing gigabytes of geojson data where I might not consider an error of the underlying character stream as a catastrophic error and opt to continue the decode versus an implementation of the JOSE framework in which I really want to treat any sort of error as a catastrophic one.  

Best,

Daniel

Re: [Caml-list] ANN: angstrom

[Anil Madhavapeddy]

On 22 Jul 2016, at 14:35, Spiros Eliopoulos <seliopou@gmail.com> wrote:
> 
> Hey List,
> 
> It is with great pleasure that I announce the initial release of angstrom, a parser-combinator library that I have been developing over the past several months:
> 
>   https://github.com/inhabitedtype/angstrom
>   http://opam.ocaml.org/packages/angstrom
> 
> Angstrom exposes monadic and applicative interfaces for composition, and supports incremental input through buffered and unbuffered interfaces. Both interfaces give the user total control over the blocking behavior of their application, with the unbuffered interface enabling zero-copy IO. Parsers are backtracking by default and support unbounded lookahead.
> 
> Whereas many OCaml parser combinator libraries claim heritage from the Parsec[0] Haskell library, angstrom instead follows the design and semantics of attoparsec[1], hence the name[2]. For a high-level comparison of Angstrom's features to other parser-combinator libraries, see the table included in the README:
> 
>   https://github.com/inhabitedtype/angstrom#comparison-to-other-libraries

I just wanted to thank Spiros for a great recent OCaml Workshop 2016 talk on his work on the webstack and point to his talk:
https://www.youtube.com/watch?v=tTqqu4xh4UY&list=PLnqUlCo055hVHS08n-Po_T4K2eNNahkg9&index=13
(livenotes as it happened: http://icfp2016.mirage.io/OCaml/improving-the-ocaml-webstack-.md )

And also one by Romaine on using Angstrom in his Mr MIME email parsing library:
https://www.youtube.com/watch?v=kQkRsNEo25k&index=12&list=PLnqUlCo055hVHS08n-Po_T4K2eNNahkg9
(livenotes: http://icfp2016.mirage.io/OCaml/whos-got-your-mail-mr-mime.md )

I've (along with the rest of the MirageOS team) have started discussing the integration of Angstrom (and its companion serialisation library Faraday) into the Cohttp stack to simplify its parsing and reduce our dependency on allocation-heavy patterns such as regular expressions, and expect to make progress on this in the next few months (as well as try out Angstrom on low-level libraries such as Mirage TCP/IP and DNS)

If you are interested, please get in touch with me and I can redirect you to the appropriate issue repository for your desired features for those protocol libraries.

regards,
Anil

Re: [Caml-list] ANN: angstrom

[Hendrik Boom]

On Fri, Jul 22, 2016 at 04:35:18PM +0300, Spiros Eliopoulos wrote:
> Hey List,
> 
> It is with great pleasure that I announce the initial release of angstrom,
> a parser-combinator library that I have been developing over the past
> several months:
> 
>   https://github.com/inhabitedtype/angstrom
>   http://opam.ocaml.org/packages/angstrom

Is it the case that Angstrom will parse only streams of characters, 
and not streams of other kinds of tokens?

-- hendrik

Re: [Caml-list] ANN: angstrom

[Spiros Eliopoulos]

[-- Attachment #1: Type: text/plain, Size: 985 bytes --]

That's correct, angstrom is specialized to parse character-based inputs.
You can use it generate a stream of tokens, but processing that token
stream is up to the user.

-Spiros E.

On Fri, Feb 3, 2017 at 2:37 PM, Hendrik Boom <hendrik@topoi.pooq.com> wrote:

> On Fri, Jul 22, 2016 at 04:35:18PM +0300, Spiros Eliopoulos wrote:
> > Hey List,
> >
> > It is with great pleasure that I announce the initial release of
> angstrom,
> > a parser-combinator library that I have been developing over the past
> > several months:
> >
> >   https://github.com/inhabitedtype/angstrom
> >   http://opam.ocaml.org/packages/angstrom
>
> Is it the case that Angstrom will parse only streams of characters,
> and not streams of other kinds of tokens?
>
> -- hendrik
>
> --
> Caml-list mailing list.  Subscription management and archives:
> https://sympa.inria.fr/sympa/arc/caml-list
> Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
> Bug reports: http://caml.inria.fr/bin/caml-bugs
>

[-- Attachment #2: Type: text/html, Size: 2017 bytes --]