Hacker News Reader

Comment by mrkeen | Hacker News Reader

Not a good starting type:

  type Parser<T> = (input: string) => [T, string]

This implies that it accepts a string and will return a T. Parsers might return a T.

The article also starts with the concept of a 'partial parser', from which other (non-partial?) parsers can be constructed?

  Or, and this is where the real power of partial parsers comes in: we wrap the chain up as a new parser of its own.

Nope, there's no distinction. If you combine partial parsers, you end up with a partial parser. If you combine full parsers (whatever that means) you end up with full parsers.

(Ironically there is a fitting definition of 'partial' here: the function isn't well defined on all inputs. For some inputs, T is returned, on other inputs, maybe an error is thrown, who knows..)

View on HN

Good input. Since we're working in typescript a partial parser can always throw an exception (It's what the parsimmon library does aswell I believe). I decided not to get into those technicalities too much!

> If you combine partial parsers, you end up with a partial parser.

If by partial we mean the parser can fail, not necessarily. optional(elem) and repeat(elem) are total if elem doesn't consume input on error, at least for a reasonable semantics of parser combinators (although we usually consider it a programmer error if elem matches the empty string in repeat(elem)).

No, that was my ironically landed upon definition of partial.

The article used it as in a sub-parser, which is the other thing I objected to. If you add two Integers, you get back an Integer, not a Sum. Same principle here, two parsers make a parser. You don't need to write new code to combine a partial parser with a parser, or vice versa.

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).

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.

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.

This literally makes no sense.

What makes no sense? To be useful, a Parser<T> needs to return a type that is useful for the consumer. If your Parser<T> returns, say, an Id or a unit, and then you combine that with a parser whose type is:

Parser<T> -> Parser<List<T>>

You'll leave your user with the task of filtering their list. If the implementer for the list parser had done the same bad job, you'd use a:

Parser<T> -> Parser<List<T>|()>

And your final type would be:

Parser<List<Id|()>|()>

That would be beyond horrible to use, and anyone using such a parser combinator library would, rightfully, be extremely annoyed.

    A parser for a thing
    Is a function from a string
    To a list of pairs
    Of strings and things.

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.

It's cute so I had to look it up. According to this guy [1], it's a poem from Graham Hutton's Haskell book [2]. I don't have the book so I can't check, but it sounds plausible.

[1] https://myotherpants.com/tag/test-first/

[2] https://www.amazon.com/Programming-Haskell-Graham-Hutton/dp/...

Here the list is the "flattened” ast of (Node, slice of input corresponding to the node)

The list represents the possible parses and the remaining input for each. In most cases you might prefer an unambiguous grammar, so a successful parse is a singleton list of a pair of the full parsed result with an empty input sequence.

But parser combinators build your final parser out of little bits, and sometimes those little bits might be something potentially ambiguous, like "any number of leading zeros followed by a number" which needs to parse "0" as no leading zeros and the number 0, but "00" as one leading zero and the number 0.

Non-deterministic parsers can easily blow out with backtracking much like careless recursive descent parsers, though.

Reply on news.ycombinator.com