Rendered at 13:52:17 GMT+0000 (Coordinated Universal Time) with Cloudflare Workers.
ArneCode 54 minutes ago [-]
I really like the animations, makes it intuitive to understand what is happening!
One disadvantage that I think parser combinators have, for example compared to parser generator libraries (where the parser is generated from a seperate grammar file), is that you have to add a lot of mapping / unwrapping code. In my opinion this makes the parsers harder to read.
As an attempt to improve this, I have been working on a parser combinator library in rust.
It adds two extra combinators (capture and bind) which can store the results of parsers in buckets (bind) and use the values stored in these buckets later to construct results (capture).
This allows you to eliminate the unwrapping / mapping code and seperate the grammar from the result contstruction.
If you have the time, I would really appreciate feedback on this!
What kind of mapping/unwrapping are you being subjected to with PCs?
marginalia_nu 3 hours ago [-]
I don't understand why this can't be on a single page. Makes it really hard to refer back to earlier "chapters" as you get new information when it's a slideshow. Can't search either.
Seems like we're needlessly reintroducing limitations from the paper medium that don't exist in digital media for weird aesthetic reasons?
creata 16 minutes ago [-]
Hey, don't blame paper. Paper packed a lot more content onto each page.
MomsAVoxell 2 hours ago [-]
Yes, I was at first discouraged to try to continue reading .. I’m glad I persisted .. but it’s as an annoyance to not know how to advance and then have to switch between scrolling and advancing instead of just scrolling ..
The user experience occludes great content though.
MattRix 1 hours ago [-]
I get your argument, but I liked it! Something about isolating each segment makes it feel more readable. Perhaps in an ideal world every article like this would allow the reader to switch between "slideshow" and "single page" view, since the same content would work for both.
testerius 43 minutes ago [-]
Yes, it would be good. However I guess even simple show/hide chapters/sections also would do good work. It could be something similar to foldable directories or code fragments in code editors (for example VS Code has this feature).
boomlinde 2 hours ago [-]
The first address should probably not be parsed as an IP address as it can also be a hostname. Might seem like a nitpick, but it creates an opportunity to demonstrate what to do when you expect either of more than one kind of construct.
The article was somewhat difficult to read due to the limited area devoted to the body of the text. I had to scroll on several pages despite the short chapters.
smusamashah 2 hours ago [-]
Thanks for sharing. This was very easy to follow on many levels. I could see it's only 17 slides and the code was simple enough to read and understand. I have read the term parser combinators many time and now I actually understand it. Kudos to the writer for making it easy to understand.
akst 2 hours ago [-]
I think this is really cool website and love this topic
But I think you might want to test this page on smaller screens, just very limited screen real estate for the content of interest, the top right half lots of padding, the scrollable content basically has 1/3 of the available screen space, the left hand side kind of has another 1/3
Look your website your vision, I get it and I respect your trying something different with the UI but if your goal here is to communicate your ideas, as a reader I'd appreciate having more screen space for the content, when I clicked on the link to see this specific post I'm just not interested in your other posts (or at least until I've read the one I went out of my way to read).
FWIW, I'm using a macbook air right now.
schindlabua 1 hours ago [-]
Thanks for the feedback. The idea was to create something between a youtube video and a blog post and something you can consume in bite-sized pieces. I'd like the visuals to do most of the talking but I guess parser combinators came out with a lot of text anway. I'll try to tighten up the UI some and get a smaller phone for testing.
doginasuit 1 hours ago [-]
I really enjoyed it and I look forward to trying out the ideas.
I think you are close to every effective presentation format, but the cramped space for the text was the biggest friction. The moving visuals, as helpful as they are, also became a little distracting as I was trying to absorb the meaning of the text. You could solve both issues with a toggle to hide or expand the visual.
monster_truck 3 hours ago [-]
I would suggest parsing my scroll wheel input and combinating it into page events
justinnk 3 hours ago [-]
Very cool visual guide! I feel it is appropriate here to recite this little poem about parsers by Fritz Ruehr that stuck with me since my first semester of CS. With this, you will never forget the type signature of a parser.
„A Parser for Things
is a function from Strings
to Lists of Pairs
of Things and Strings!“
Love me some combinators. In my earlier days it helped bridge the academic gap of CS grammars and languages to something I could not readily apply to internship dev work. I seem to recall an attempt to map or generate the from regex and in reverse, but I might be crazy this early in the morning.
Nice visuals btw. If I may be so bold: slightly smaller font and header would make scrolling through the bottom readable code snippets a little easier!
raddan 3 hours ago [-]
Yeah, the academic presentation of parsing complexity is not very useful for real-world parsing tasks. It is useful to know that regular expressions are limited (NFAs “can’t count”, so they’re not good for trying to match an unbounded number of balanced parentheses, for example). But beyond that, we largely choose capable algorithms either for ease of use or speed. Combinators, PEGs, parser generators (like lex/yacc, ANTLR) are mostly easy. For speed, almost everyone rolls a parser by hand.
I like combinator style parsers because
1) it’s really easy to think of a discrete parsing task as a function
2) tokenizing is mostly irrelevant
3) for pedagogical reasons, they make it easier for students to grasp the point of curried functions and partial application.
I even maintain a (mostly mature) parser combinator library for TypeScript for students in my research group to use.
Thanks! The site is going through a redesign so some things aren't perfect yet, I'll keep it in mind next iteration :p
Parser combinators are stronger than pure regular expressions but I'm not sure how they compare to the non-regular regexes we use in programming (PCRE etc)
mrkeen 3 hours ago [-]
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..)
schindlabua 3 hours ago [-]
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!
debugnik 2 hours ago [-]
> 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)).
mrkeen 2 hours ago [-]
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.
raddan 3 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).
rhdunn 3 hours ago [-]
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 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.
mrkeen 46 minutes ago [-]
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.
pyrale 2 hours ago [-]
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.
raddan 2 hours ago [-]
> 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.
codebje 2 hours ago [-]
A parser for a thing
Is a function from a string
To a list of pairs
Of strings and things.
mrkeen 29 minutes ago [-]
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?
rdevilla 3 hours ago [-]
[dead]
stevefan1999 3 hours ago [-]
I love parser combinators so much. Those are possible because parsing itself exhibits monadic structure, it forms transition monoid, of its more well known name as the semiautomaton in the world of CS.
prologic 2 hours ago [-]
Me too! I've written quite a few (by hand) in my time. They're awesome for writing parsers that resemble the language you're trying to parse!
rrook 2 hours ago [-]
I'm working on landing a similar feature in a language project, but in a general way, geared torward high level application flows. The general idea is that you can declare a "seam" between a function that returns a type set, and some other actor that exposes a method set that covers said typeset. The compiler can deal with the inbetween code, so the mainline of the app is just a set of typespace expansions/compressions. A callstack within a single thread domain can be expressed like:
It's a cool guide, but you kind of missed the opportunity to parse the packet metadata as arbitrary key-value pairs, i.e. for:
64 bytes from 1.1.1.1: icmp_seq=3 ttl=52 time=47.1 ms
everything after the colon is key-value data, and throwing in a generic parser for `pKeyVal()` would make an even better point of how elegant the approach is.
amelius 2 hours ago [-]
They should at least point out the limitations of the approach. For example that they cannot handle left-recursive grammars, and that they tend to backtrack a lot on ambiguous grammars leading to exponentially bad performance.
BackacheDescent 3 hours ago [-]
Just me or is clicking on share from the browser sharing the link with “example.com” instead of “t3.at”?
alfiedotwtf 34 minutes ago [-]
That was beautifully done!
mbaranturkmen 3 hours ago [-]
How does the parser decide _where_ to split the statement?
mrkeen 35 minutes ago [-]
Each parser blindly follows its own rules.
If pDigit saw "123 ", according to TFA's design, it would return (1, "23 ").
If PInt saw the "123 ", it would return (123, " ").
You could approximate pInt in terms of pDigit via:
PInt = many1 pDigit
(Ignoring negatives, int maxvalue, and many1 implies 1-or-more, not 0-or-more.)
I say "according to TFA's design" because I've been arguing elsewhere that parsers must return Either<Error,(T, Remainder)> not (T, Remainder)
TZubiri 1 hours ago [-]
looks like standard functional programming to me
adrianhqs 3 hours ago [-]
Nice design
lacoolj 3 hours ago [-]
Did you use the new Claude Motion for this?
schindlabua 2 minutes ago [-]
I used plain Opus. Will check out Claude Motion though, thanks for mentioning it!
doginasuit 47 minutes ago [-]
Not the OP, but thanks for mentioning this! Looks really useful.
One disadvantage that I think parser combinators have, for example compared to parser generator libraries (where the parser is generated from a seperate grammar file), is that you have to add a lot of mapping / unwrapping code. In my opinion this makes the parsers harder to read.
As an attempt to improve this, I have been working on a parser combinator library in rust. It adds two extra combinators (capture and bind) which can store the results of parsers in buckets (bind) and use the values stored in these buckets later to construct results (capture). This allows you to eliminate the unwrapping / mapping code and seperate the grammar from the result contstruction.
If you have the time, I would really appreciate feedback on this!
You can find it here: https://github.com/ArneCode/marser
Seems like we're needlessly reintroducing limitations from the paper medium that don't exist in digital media for weird aesthetic reasons?
The user experience occludes great content though.
The article was somewhat difficult to read due to the limited area devoted to the body of the text. I had to scroll on several pages despite the short chapters.
But I think you might want to test this page on smaller screens, just very limited screen real estate for the content of interest, the top right half lots of padding, the scrollable content basically has 1/3 of the available screen space, the left hand side kind of has another 1/3
Look your website your vision, I get it and I respect your trying something different with the UI but if your goal here is to communicate your ideas, as a reader I'd appreciate having more screen space for the content, when I clicked on the link to see this specific post I'm just not interested in your other posts (or at least until I've read the one I went out of my way to read).
FWIW, I'm using a macbook air right now.
I think you are close to every effective presentation format, but the cramped space for the text was the biggest friction. The moving visuals, as helpful as they are, also became a little distracting as I was trying to absorb the meaning of the text. You could solve both issues with a toggle to hide or expand the visual.
„A Parser for Things is a function from Strings to Lists of Pairs of Things and Strings!“
https://people.willamette.edu/~fruehr/haskell/seuss.html
Nice visuals btw. If I may be so bold: slightly smaller font and header would make scrolling through the bottom readable code snippets a little easier!
I like combinator style parsers because 1) it’s really easy to think of a discrete parsing task as a function 2) tokenizing is mostly irrelevant 3) for pedagogical reasons, they make it easier for students to grasp the point of curried functions and partial application.
I even maintain a (mostly mature) parser combinator library for TypeScript for students in my research group to use.
https://github.com/williams-cs/parsecco
Parser combinators are stronger than pure regular expressions but I'm not sure how they compare to the non-regular regexes we use in programming (PCRE etc)
The article also starts with the concept of a 'partial parser', from which other (non-partial?) parsers can be constructed?
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..)
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)).
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.
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 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.
If you always define T as some useful stuff or unit, your experience with parser combinators and their composition is going to be miserable.
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.
If it's a List, wouldn't you be forced to write the Cartesian product of two parsers instead?
bytes → (NewOrder | Cancel) → handlers → (Ack | Reject) →
https://github.com/hale-lang/hale/issues/1530#issuecomment-6...
If pDigit saw "123 ", according to TFA's design, it would return (1, "23 ").
If PInt saw the "123 ", it would return (123, " ").
You could approximate pInt in terms of pDigit via:
(Ignoring negatives, int maxvalue, and many1 implies 1-or-more, not 0-or-more.)I say "according to TFA's design" because I've been arguing elsewhere that parsers must return Either<Error,(T, Remainder)> not (T, Remainder)