Comment by raddan
14 hours ago
Combinators are functional—they always return something. But if you want to return nothing, fine; T is any type. Just return something like unit (ie, the singleton type that has nothing as a value).
14 hours ago
Combinators are functional—they always return something. But if you want to return nothing, fine; T is any type. Just return something like unit (ie, the singleton type that has nothing as a value).
T is not any type, T is a type defined at compile time, and usually checked against the parser’s implementation.
If you always define T as some useful stuff or unit, your experience with parser combinators and their composition is going to be miserable.
> T is not any type, T is a type defined at compile time,
This is a distinction without a difference. In a static, type-safe language, T always has to be instantiated with a type. But that does not change the fact that, from the perspective of the function definition, T is any type. T must be a specific type for the function call.
From the function's point of view it may be asked to return any type T. That is not the same thing as it being able to return any type that is convenient for its implementation.
2 replies →
There are three return states that a parser (or partial parser) can return:
1. an item (`T`) for a successful parse;
2. an error (`ParseError`) for an unrecoverable parse error;
3. a partial item (`T with ParseError`) for a recoverable parse error or warning (known statically).
You may also want to differentiate between:
1. leaf nodes (numbers, identifiers, string literals, etc.);
2. composite/nested nodes (addition, multiplication, variable assignment, etc.).
You don’t need 2 and 3. You can express them just with with T. For example, you could use an Either type for “good, here’s your value/bad, here’s your error.” If you want to get more sophisticated, you can add a type with extra error cases. In my own combinator libraries, I also include extra failure information to make diagnosing failed parses easy (and to generate pretty output). This does not change the fact that T is sufficient.
No. The parser code (in a library that everyone depends on) will branch on success/fail internally. It has nothing to branch on if it only sees T, because T may not have a success/fail nature.
You could take a step back and make sure T has a fail case, e.g. T-extends-Either<A, B>, but what is to be gained?
* Firstly, what the hell is A?
* The user would need to type Parsers of T=Cat and T=Dog instead as Parsers of T=Either<Error,Dog> and T=Either<Error,Cat>. If everyone has to do it, pull the common abstraction back into the library itself! Also the caller would receive a successful parse of T=Either and would then need to check to see if it was success(success) or success(fail).
* You also mix abstractions in the same way as newlines in string literals. You could no longer represent a successful parse of a failed Either, since the failed Either would look like a parse error.
1 reply →
If you use an Either instead of a List, then you can write an or combinator, which accepts two parsers and tries the second if the first fails. It branches on the Left/Right of the Either.
If it's a List, wouldn't you be forced to write the Cartesian product of two parsers instead?
You’re going to write a monad and alternative instance for whatever structure you use. A list is a Cartesian product, but that’s just the join of parser B over each remaining input of parser A, it’s still a one-liner.
The question is capabilities. Either gives you an error result that might be useful. List gives you backtracking and, depending on your grammar, multiple parses. Maybe is like a weaker Either. Other monads might do other interesting things, but from the perspective of accepting strings satisfying a grammar, List is the choice that supports non-determinism.
(Laziness strongly recommended.)
The poem is not mine, I believe it is Conor McBride’s.
[dead]