Add some safe optional prefix parser

[ogregoire]

In the AGENTS.md, you write:

Use anyOf() to split the rule into two choices for an optional prefix:

anyOf(
    sequence(accidental, note, (a, n) -> n.withAccidental(a)),  // with prefix
    note)  // without prefix

My issue with this is that it's hard to use, and unintuitive, and yet it's documented as totally safe. I'm using this structure several times, unfortunately, and in this way:

anyOf(
  sequence(
    prefix,
    here()
      .I()
      .construct()
      .a()
      .quite()
      .long()
      .parser(),
    (pref, suff) -> ...),
  here()
    .I()
    .construct()
    .a()
    .quite()
    .long()
    .parser()
    .map(suff -> ...))

This leads to a lot of redundancy. Moving the pain point on the user. Okay, I could move my long parser to another variable, fair point:

Parser<X> quiteLongParser = here()
    .I()
    .construct()
    .a()
    .quite()
    .long()
    .parser();

anyOf(
  sequence(
    prefix,
    quiteLongParser,
    DomainObject::new),
  quiteLongParser
    .map(suff -> new DomainObject(DEFAULT_VALUE, suff))
)

The clear issue here becomes the duplication of the lambda. A lesser issue is the indenting that is not the same because of the sequence.

What if we could have a static <T, U, V> Parser<V> optionalPrefix(Parser<T>, Parser<U>, BiFunction<Optional<T>, U, V>? Even as a wrapper around that anyOf?

In my example, the only lambda I get is (Optional<T> t, U u) -> new DomainObject(t.orElse(DEFAULT_VALUE), u)), which is probably better looking and shows the intent more than the anyOf(sequence(), ) structure.

It's just a wrapper around the totally safe structure you provide that is easier to use than the current recommended structure. So I don't see any trouble in regards to the safety.

Do I miss anything? Would this be possible to implement?

[fluentfuture]

Yeah, I can definitely see that suporting sequence(OrEmpty, Parser) helps. You don't even need to accept Optional, just do this:

sequence(prefix.orElse(DEFAULT_VALUE), theLongParser, DomainObject::new);

The main reason sequence(OrEmpty, Parser) isn't added is due to the fear that it could make left recursion less obvious.

Today, if you run into a StackOverflowError by mistake, and you realize left-recursion isn't supported, you can eyeball the code and left recursion should be explicit because you do have a recursive parser that looks like Parser.define(self -> sequence(self, ...)), where self literally shows up as the "leftmost" subrule.

If OrEmpty is allowed, we lose the explicitness because the code still looks innocent as in sequence(prefix, self, ...). And you may run into code that require more debugging-in-the-head until you realize: "Silly me! Of course prefix's type is OrEmpty!".

So here it's design trade-off: it's useful, but it may also be risky and cause unintended surprises.

There may also be other ways to support it. Say, what if we add an instance method to Parser?

Parser<T> optionallyPrecededBy(Parser<L> prefix, Function<T, L, T> prefixFunction);

Then, instead of sequence(), you use this new method that tries not as hard to hide left recursion:

longParser.map(DomainObject::new)
    .optionallyPrecededBy(foo, DomainObject::withFoo);

It'll require a "wither" for the prefix.

The upside of this design is that it's symmetric to optionallyFollowedBy().

The downside is that the method call order doesn't mirror the grammar order.

Or, could there be a 3rd way (like, coming up with a method name other than sequence() such that the leftmost rule being optional is obvious?)

I think one way or another it probably should be supported. It just hasn't been obvious which is the optimal design.

Which of these options would work better for your use case?

[ogregoire]

I don't like the downside of a Parser.optionallyPrecededBy. It's counter-intuitive. This is why I thought about static method in my original post. I think that static methods are the way to go because there is no way that appending a method that speaks about a prefix is intuitive. If there is an instance method, what would be the perfect parameter order? (optionalPrefix, normalParser, (prefix, parser) -> {...}) or (normalParser, optionalPrefix, (parser, prefix) -> {...})? Are we really getting the prefix after? That's nonsense. Are we getting the prefix before? That's against all the other methods' logic.

So to me, the static method is the only way to support this feature, no instance at all. Naming it sequence is actually completing the overload coverage. Nowadays, we're all using tools, be it an IDE, an agent or something else. It's obvious if a prefix is a Parser or an OrEmpty.

If you want to be explicit and avoid sequence one might name the method optionalPrefixFollowedBy(OrEmpty, Parser, BiFunction), but I'm not a native English speaker, there are probably better names out there.

[fluentfuture]

Yeah. I agree that the order isn't intuitive.

I was hoping that in concrete use cases the domain model would look more intuitive, if for example you've got a Noun type, and the prefix natually feels like an optional add-on of the domain object.

In that context, would it read more intuitive? What's your use case?

book.optionallyPrecededBy(prelude, Book::withPrelude);

Nowadays, we're all using tools, be it an IDE, an agent or something else. It's obvious if a prefix is a Parser or an OrEmpty.

This is the part I'm not against (I'm hoping to be convinced that it is the case and then it'll make the API more complete). What gets me hung up so far, is that when you have hundreds of of lines of parser code, with a dozen sequence(a, b, ...), it becomes less clear which one may hide a conditional left recursion. The "conditional" is particularly nasty because the code may only blow up when the first OrEmpty happens to consume no input under the specific edge case. It may work well for your test cases but fail in production, and unpredictably.

And I worry that AI code generation can make it worse. AI already tends to trip at the presence of OrEmpty, which means that if we didn't have OrEmpty, AI generated code could have produced subtle infinite loops.

The anyOf(sequence(prefix, subject, ...), subject), while not as intuitive at write-time, at read-time is still intutive, and left recursion is always explicit.

[fluentfuture]

Actually that sequence(OrEmpty, Parser) static method already exists. It's just package-private due to the left recursion concern.

Can you share what your domain type is so it'll be easeir for me to understand whether the wither idea can apply?

Assuming the optionallyPrecededBy() idea doesn't look right, we may just need a good method name that can more clearly show to the readers that the leftmost expression may be empty and the second-in-place parser may introduce left recursion when used in Parser.define().

Your original suggestion of optionalPrefix() does meet the requirement of explicitness. Does it read fluent though? Or does it read redundant when you have optionalPerfix(prelude.optional(), book) with two optional in the expression? Again, this is where your concrete use case may help.

[ogregoire]

My use case is structured English sentences. A specific subset of English instructions that are structured enough for mechanical interpretation.

This specific scenario is about the subject of actions.

Act.
Planner acts.
Planner and Executor act.

The action "act" can have a subject, that is optional. When the subject is absent, the subject must be parsed as "you".

That is my sole use case for this scenario. But it repeats for a dozen actions.

[fluentfuture]

Okay. Let me know if I'm misunderstanding the use case.

1. There is a subject grammar, which may be empty and default to "You".
2. There are a bunch of actions, like "eat", "walk", "pay", "smile". Each will have their own grammar, and produce a different domain model like Eat, Walk, Pay, Smile.

Just thinking out loud, I may have a subject parser of type Parser<String>.

And all of these act domain models share an optional String subject, and then with their own properties (for example Walk may include a distance like "walked a mile", and Eat will have a target like "ate brunch").

The domain types may look like::

record Eat(String who, String what) {}

record Walk(String who, int distance) {}

record Pay(String who, String whom, int howMuch) {}

Currently, you may be forced to do:

Parser<Eat> eat = anyOf(
    sequence(word(), string("eat").then(word()), Eat::new),
    string("eat").then(word()).map(what -> new Eat("You", what));

Parser<Walk> walk = anyOf(
    sequence(word(), string("walk").then(digits().map(Integer::parseInt)(, Walk::new),
   string("walk").then(digits()).map(distance -> new Walk("You", Integer.parseInt(distance)));

Parser<Pay> pay = anyOf(
    sequence(word(), string("pay").then(word()), digits().map(Integer::parseInt), Pay::new),
    sequence(
        string("pay").then(word()),
        digits().map(Integer::parseInt),
        (whom, howMuch) -> new Pay("You", whom, howMuch)));

And that's clearly a lot of duplication.

With sequence(OrEmpty, Parser), I suppose you can simplify it to:

Parser<Eat> eat =
    sequence(word().orElse("You"), string("eat").then(word()), Eat::new);

Parser<Walk> walk =
    sequence(word().orElse("You"), string("walk").then(digits().map(Integer::parseInt), Walk::new);

Parser<Pay> pay = anyOf(
    sequence(word().orElse("You"), string("pay").then(word()), digits().map(Integer::parseInt), Pay::new);

That's clearly a lot better (let's temporarily not worry about left recursion since you don't have a recursive grammar).

Although, that you still have to repeat the .orElse("You") for each act still feels redundant.

What if (without the new overload), you create a helper that wraps the subject parsing separately?

<A> Parser<A> act(Function<String, Parser<A>> action) {
  return anyOf(word().flatMap(action),  action.apply("You"));
}


Parser<Eat> eat =
    act(who -> string("eat").then(word()).map(what -> new Eat(who, what));

Parser<Walk> walk =
    act(who -> string("walk").then(digits().map(d -> new Walk(who, Integer.parseInt(d)));

Parser<Pay> pay =
    act(who -> sequence(
        string("pay").then(word()),
        digits().map(Integer::parseInt), 
       (whom, howMuch) -> new Pay(who, whom, howMuch)));

It allows to reuse the act() function and centralize the entire optional subject issue.

Would that work?

[ogregoire]

That would work, yes. But that means that the parser is re-created everytime I parse an action where the subject matches. If I write an action parser with anyOf wrapping all those actions, I will definitely re-create useless objects again and again.

This approach is very smart and fits my specific use-case, but I guess, I'd rather have a static (as opposed to dynamic) parser.

[fluentfuture]

Do all your act parsers return a single value (as opposed to the speculated pay example that produces both the "whom" and "howmuch"?).

Since it's unlikely that we can support all combinations of Parser+OrEmpty overloads of sequence() anyways, another alternative is to change the act() helper to support the single-return case better:

<A, R> Parser<R> act(
    Function<String, Parser<A>> action, BiFunction<String, ? super A, ? extends R> combiner) {
  return anyOf(sequence(word(), action, combiner),  action.map(a -> combiner.apply("You", a)));
}

Then your call sites won't be dynamic:

Parser<Eat> eat =  act(string("eat").then(word()), Eat::new);

Parser<Walk> walk =  act(string("walk").then(digits().map(Integer::parseInt), Walk::new);

[ogregoire]

No, my action parsers all return domain-specific AST, just like you correctly thought with your action examples. However each action has its own subject. While I'm lenient about "act"/"acts", I'm not lenient with the subject. Though, "you" is the only common subject to all actions whether explicit or implicit.

I don't think it's needed to support all combinations of Parser/OrEmpty since they're combinable using the lower number of sequence. But if you were to do that, I suppose there are 3+7+15, yeah that's a lot.

Slightly tengent to this, what is the best way to parse sequences of words: string("see you tomorrow"), sequence(word("see"), word("you"), word("tomorrow")), something else? My AI agent keeps doing the latter, but I think string/caseInsensitive are best for this job...

[fluentfuture]

I see. So the subject part isn't reusable, neither is the act part. They both have their specific grammar rules.

So the best you could achieve (if sequence(OrEmpty, Parser, BiFunction) were public), is to be able to call sequence(fooSubject.orElse("You"), fooAction, (s, a) -> ...).

The pattern of using anyOf(sequence(fooSubject, fooAction, FooAction::new), fooAction.map(FooAction::new)) depends on the FooAction having two overloaded constructors supporting the with- and without-subject cases. Not sure if that works for you. If it does, then with the fooAction being extracted to a variable, it's still relatively compact?

string("see you tomorrow");

There is no off-the-shelf sentence() combinator, but it's easy to create one. A few options to consider:

1. I prefer using Substring since it's easy to use and most efficient:

       import com.google.mu.util.Substring;
   
       Parser<?> sentence(String s) {
         return Substring.consecutive(Character::isWhitespace).repeatedly().split(s)
             .map(Parser::word)
             .reduce(Parser::then)
             .orElseThrow();
       }
   
       Parser<?> caseInsensitiveSentence(String s) {
         return Substring.consecutive(Character::isWhitespace).repeatedly().split(s)
             .map(Parser::caseInsensitiveWord)
             .reduce(Parser::then)
             .orElseThrow();
       }

   Substring lives in mug core so it's already in your transitive dependency closure.

2. If you'd rather stick to the Parser API itself, then:

       Parser<?> sentence(String s) {
         return Parser.word().skipping(Character::isWhitespace).parseToStream(s)
             .map(Parser::word)
             .reduce(Parser::then)
             .orElseThrow();
       }
   
       Parser<?> caseInsensitiveSentence(String s) {
         return Parser.word().skipping(Character::isWhitespace).parseToStream(s)
             .map(Parser::caseInsensitiveWord)
             .reduce(Parser::then)
             .orElseThrow();
       }

   For this particularly case, it's almost as succinct. And since it runs at parser construction time, the performance difference between Substring and Parser probably doesn't matter much.

[fluentfuture]

Fwiw, I've added left recursion guard that will now report at time of parser construction (as opposed to at parsing time).

This in turn makes the left recursion errors not as scary as they used to be, and I don't think it's bad enough to warrant keeping the sequence(OrEmpty, Parser) OrEmpty.then(Parser), OrEmpty.followedBy(Parser) package private.

[ogregoire]

Do you know how great you are? Do you actually know that?

Thank you very much! This is great news. I sure hope that you still had your content of sleep while making this possible.

Edit: sorry, sent too fast