5 ms·

Monadic parser combinators! There is a nice paper on the subject by Graham Hutton and Erik Meijer. It's a very good introduction to both parser combinators and

Monadic parser combinators! There is a nice paper on the subject by Graham Hutton and Erik Meijer. It's a very good introduction to both parser combinators and monads, and it's very readable even for beginners.

lomnakkus 9y ago
Hm? I don't see why these would have to be monadic. A simple type Parser t = Input -> Maybe (t, Input) or similar would be enough? Simple function composition gets you the rest of the way. (I grant you, it might be a bit tedious to write parsers this way, and monadic notation certainly makes it more pleasant in most cases.) For anyone following along at home: think function which takes input + current position and may return: "Nothing" if the parser doesn't match, or "a value of type t along with the rest of the unparsed input". (Obviously it'd have to be expanded to support errors properly, etc.) EDIT: Of course, I guess you could argue that they just are monadic by definition since chaining using function composition and parameter passing is the essence of a monad... Maybe that's what you were driving at?
- Mehdi2277 9y ago
 Yeah that type is enough to make a monad. In slightly fancy language the type you just wrote is just StateT Input Maybe. Monadic mostly makes me think of bind which is just about chaining (technically also return is needed, but here return is just always succeed and give that value) and parsers have a natural notion of run one after the other.
 - lomnakkus 9y ago
 > In slightly fancy language the type you just wrote is just StateT Input Maybe. Except the newtype -- which was kind of my point :).
 - tel 9y ago
 It's only a monad if you define it to be. It's also "just" an applicative if you like. The monadic part arises when people actually _use_ bind and then you lose some information that might be nice for optimizations.
- chombier 9y ago
 I realize I misread parent comment functions: always<A>(x: A): Parser<A> thenDependent<A, B>(a: Parser<A>, b: A -> Parser): Parser<(A, B)> as: always<A>(x: A): Parser<A> thenDependent<A, B>(a: Parser<A>, b: A -> Parser): Parser which would make a monad provided the monad laws are satisfied. Of course you don't have to write parser combinators that way, but I found it pretty practical compared to dealing with nested tuples for the sequence parser. Check out Hutton and Meijer's article for more details.
 - Tarean 9y ago
 The problem with monadic parsers is that they are too powerful. If you have two options string "foo" <|> string "for" It would be nice to automatically rewrite this as string "fo" >> (char 'o' <|> char 'r') But if we try to analyze monadic parsers like that we run into the halting problem. Applicative parsers are less powerful so we can left factor them automatically. There were some attempts to combine applicative and monadic parsers which resulted in arrow syntax but that kind of feels like the worst of both worlds for many cases.
lihaoyi 9y ago
Notably, you hardly ever need Monadic parser combinators. Applicative parser combinators work fine in almost all cases. FastParse lets you use parser combinators monadically, but that's only necessary in uncommon cases. The three I've come across are length + data-of-length constructs (more common in binary parsing than text), having your parser validate matched XML tags/closing-tags, and indentation-delimited-block parser (e.g. when parsing Python). For the vast majority of programming-language-like things, Applicative parser combinators are enough, including languages with complex syntax such as Scala.

lomnakkus 9y ago

Hm? I don't see why these would have to be monadic. A simple type Parser t = Input -> Maybe (t, Input) or similar would be enough? Simple function composition gets you the rest of the way. (I grant you, it might be a bit tedious to write parsers this way, and monadic notation certainly makes it more pleasant in most cases.) For anyone following along at home: think function which takes input + current position and may return: "Nothing" if the parser doesn't match, or "a value of type t along with the rest of the unparsed input". (Obviously it'd have to be expanded to support errors properly, etc.) EDIT: Of course, I guess you could argue that they just are monadic by definition since chaining using function composition and parameter passing is the essence of a monad... Maybe that's what you were driving at?

Mehdi2277 9y ago
Yeah that type is enough to make a monad. In slightly fancy language the type you just wrote is just StateT Input Maybe. Monadic mostly makes me think of bind which is just about chaining (technically also return is needed, but here return is just always succeed and give that value) and parsers have a natural notion of run one after the other.
- lomnakkus 9y ago
  > In slightly fancy language the type you just wrote is just StateT Input Maybe. Except the newtype -- which was kind of my point :).
- tel 9y ago
  It's only a monad if you define it to be. It's also "just" an applicative if you like. The monadic part arises when people actually _use_ bind and then you lose some information that might be nice for optimizations.
chombier 9y ago
I realize I misread parent comment functions: always<A>(x: A): Parser<A> thenDependent<A, B>(a: Parser<A>, b: A -> Parser): Parser<(A, B)> as: always<A>(x: A): Parser<A> thenDependent<A, B>(a: Parser<A>, b: A -> Parser): Parser which would make a monad provided the monad laws are satisfied. Of course you don't have to write parser combinators that way, but I found it pretty practical compared to dealing with nested tuples for the sequence parser. Check out Hutton and Meijer's article for more details.
- Tarean 9y ago
 The problem with monadic parsers is that they are too powerful. If you have two options string "foo" <|> string "for" It would be nice to automatically rewrite this as string "fo" >> (char 'o' <|> char 'r') But if we try to analyze monadic parsers like that we run into the halting problem. Applicative parsers are less powerful so we can left factor them automatically. There were some attempts to combine applicative and monadic parsers which resulted in arrow syntax but that kind of feels like the worst of both worlds for many cases.

lihaoyi 9y ago

Notably, you hardly ever need Monadic parser combinators. Applicative parser combinators work fine in almost all cases. FastParse lets you use parser combinators monadically, but that's only necessary in uncommon cases. The three I've come across are length + data-of-length constructs (more common in binary parsing than text), having your parser validate matched XML tags/closing-tags, and indentation-delimited-block parser (e.g. when parsing Python). For the vast majority of programming-language-like things, Applicative parser combinators are enough, including languages with complex syntax such as Scala.