Distributors - Unifying Parsers, Printers & Grammars

Show and Tell
1

First post here. I’d like to show my distributors library. This library builds on Profunctors and optics from the lens library, particularly Prisms. Distributors generalize the story about parsing being the prototype example of Functors with the Applicative, Alternative and Monad interfaces, to a story about grammar being the prototype example of Profunctors with Monoidal, Distributor, Alternator and Monadic interfaces. Distributors provides

  • correct-by-construction invertible parsers
  • extensible – define new parser generators or other generators from grammars
  • type-safe subtype hierarchy for regular, context-free & context-sensitive grammar
  • grammar string generators
    • regular expressions for regular grammar
    • and BNF for context-free
  • algebraic RegEx and BNF combination and pattern matching
  • some related optics

The entry module for grammar Control.Lens.Grammar has lots of examples. And all of the documentation has links to papers and posts from which ideas have been used.

Distributors is dedicated to the memory of Jean Bénabou.

26 Likes
2

I like invertable syntax combinators but I personally found them too hard to use cleanly. Do your generalization fix some of their issues? Do you still need to use binary tuples and isomorphism functions to actually parse things? Do you still need a lot of helper functions to swap the parsed input order into the AST order? I’ve never really used lens so I can’t really understand the documentation.

1 Like
3

I think the issues about tuples are ameliorated by the use of generated optics. Distributors provides a Template Haskell function makeNestedPrisms which when applied to a datatype, makes the appropriate conversion functions between the datatype and tuples in the form of a Prism or Iso. The documentation of distributors compares how to translate between the usual style of Applicative parsing to Profunctors to help. But familiarity with optics is definitely helpful.

1 Like
4

I’m not sure if you’re aware, but your CtxGrammar goes far beyond “context sensitive grammars”. In fact the Filtrator combinator satisfied allows you to take an arbitrary (computable) subset of the language, which lands you in the class of “all recursively enumerable languages” (equivalently “unrestricted grammars”), which technically does contain all context-sensitive languages, but calling this “context-sensitive” would be a poor name.

1 Like
5

which lands you in the class of “all recursively enumerable languages”

I’m confused then. Including Filtrator in the definition of CtxGrammar doesn’t make it any stronger. That’s because Alternator & Monadic already imply Filtrator with a default definition of filtrate = mfiltrate like how MonadPlus implies Filterable with filter = mfilter. So I guess MonadPlus also generates recursively enumerable languages? I think the name’s ok. I’ll add a note on it to the docs if we can settle my confusion. I should also note that RegGrammars actually allow you to define context-free grammars since they’re hosted in Haskell and Haskell already allows general recursion.

6

MonadPlus generates all recursively enumerable languages yes. Let L be a language accepted by a computable predicate p :: String -> Bool. Then

parseL = many anyChar >>= \xs -> if p xs
  then pure ()
  else mzero

Of course, we don’t get actually “parse” any notion of a parse tree in this way, but this accepts exactly the language L.

1 Like
7

Cool, thanks for explaining! I will add notes to the documentation to help clarify.