Unable to reduce over collection of closures

help
1

I'm exploring FP / parser combinators in Rust, and trying to follow along based on some other examples I've seen in a tutorial in F#. I have the following code:

struct ParseError(String);

trait Parser<T>: Fn(&str) -> (Result<T, ParseError>, &str) {}

impl<T, F> Parser<T> for F where F: Fn(&str) -> (Result<T, ParseError>, &str) {}

fn or_else<T>(parser1: &impl Parser<T>, parser2: &impl Parser<T>) -> impl Parser<T> {
    move |input| {
        let (result1, remaining1) = parser1(input);

        match result1 {
            Ok(token1) => (Ok(token1), remaining1),
            Err(_) => parser2(remaining1),
        }
    }
}

fn choice<T>(parsers: &[&impl Parser<T>]) -> impl Parser<T> {
    move |input| {
        let parser = parsers
            .iter()
            .reduce(|parser1, parser2| &&or_else(*parser1, *parser2));

        parser.unwrap()(input)
    }
}

I defined Parser<T> the way it is because I don't believe there is any other way to have a type alias for a closure type like I have here; this seems to be the closest equivalent. If there is a more idiomatic way, it would be good to know. The parsers are passed by reference as I don't want the combinator to render the parsers passed to it unusable after they are composed (as they don't rely on other state).

My goal is to be able to take a collection of parsers and apply them in sequence until one passes. Building this (playground link), though, I get this error:

   Compiling playground v0.0.1 (/playground)
error[E0308]: mismatched types
  --> src/lib.rs:22:40
   |
 7 | fn or_else<T>(parser1: &impl Parser<T>, parser2: &impl Parser<T>) -> impl Parser<T> {
   |                                                                      -------------- the found opaque type
...
18 | fn choice<T>(parsers: &[&impl Parser<T>]) -> impl Parser<T> {
   |                          -------------- expected this type parameter
...
22 |             .reduce(|parser1, parser2| &&or_else(*parser1, *parser2));
   |                                        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected type parameter `impl Parser<T>`, found opaque type
   |
   = note: expected reference `&&impl Parser<T>` (type parameter `impl Parser<T>`)
              found reference `&&impl Parser<T>` (opaque type at <src/lib.rs:7:70>)
   = help: type parameters must be constrained to match other types
   = note: for more information, visit https://doc.rust-lang.org/book/ch10-02-traits.html#traits-as-parameters

For more information about this error, try `rustc --explain E0308`.
error: could not compile `playground` (lib) due to 1 previous error

I don't see where the mismatch is, and reading through the book doesn't really clarify to me how I'd go about solving this either. My current understanding is that as each return of or_else is an impl Parser<T>, an opaque type, each version of it is different and they can't be passed in as a parameter in further calls to or_else, which use impl Parser<T> in the parameter position, which expects a specific concrete type. However, I don't think my understanding is on the right track.

In all honesty, I'm not even sure I'm going about this idiomatically. How should I go about structuring this code to model what I stated above? How can I go about fixing this / what is the error actually saying?

2

this signature is equivalent to:

fn choice<T, P: Parser<T>>(parsers: &[&P]) -> impl Parser<T>;

all the elements of the input slice have the same type P. then Iterator<Item = T>::reduce() takes a reducer function of type (T, T) -> T. because the slice parsers is of type &[&P], parsers.iter() returns an iterator that is impl Iterator<Item = &&P>, which means your reducer function should have the type (&&P, &&P) -> &&P. in other words, you are supposed to return references to a Parser of the same P, which is impossible with static (but opaque) typed closures.

also, returning a reference of a temporary value for Iterator::reduce() will never work (except for 'static promoted constants).

for this example, you can implement choice by replacing Iterator::reduce() with a "regular" loop. or, you can try to erase the static type and use dynamic dispatch, if you want to stick to Iterator::reduce().

3 Likes
3

To further explain impl Trait, they mean different things when they are arguments to functions (APIT) or in the return type of functions (RPIT). The signature of or_else roughly corresponds to

fn or_else<'p1, 'p2, T, P1, P2>(
    parser1: &'p1 P1,
    parser2: &'p2 P2
) -> OrElseParser<'p1, 'p2, T, P1, P2>
where
    P1: Parser<T>,
    P2: Parser<T>,

where every APIT corresponds to a generic type on the function (albeit unnameable), and the RPIT corresponds to a type alias. The type alias is also unnameable, invariantly parameterized by the generics which are in scope, refers to some type determined by the function body, and is not normalizable.

Then in choice...

fn choice<'outer, 'inner, T, P>(
    parsers: &'outer [&'inner P]
) -> ChoiceParser<'outer, 'inner, T, P>
where
    P: Parser<T>,

...your closure has the signature (ignoring lifetimes):

|(&&P, &&P)| -> &&OrElseParser<'_, '_, T, P, P>

That's where the type mismatch comes from.

Some sort of fold isn't an option either, as after each fold you'll get a recursively expanding type.

// Parser from `or_else::<T, P, P>`
OrElseParser<'_, '_, T, P, P>
// Then passing that to `or_else` along with another `P` results in:
OrElseParser<'_, '_, T, OrElseParser<'_, '_, T, P, P>, P>

Using dyn Parser<T> would remove this problem (that's the "erase the static type" route). You'd need some sort of boxing.

Side note: Because all of the parsers passed to choice have the same type, they can't be distinct closure types. It would be possible, but probably surprising, if the same closure succeeded with the same input after some number of failures. So choice may not be as useful as you hoped.

However, all of the parsers could be fn(..) pointers or otherwise erased parsers (Box<dyn Parser<T>>, Box<dyn Fn(..)>). So choice is also not useless.

You don't need to reuse the parsers within or_else, so this signature will do:

fn or_else<T>(parser1: impl Parser<T>, parser2: impl Parser<T>) -> impl Parser<T> {

If F: Fn(..), then &F: Fn(..) too, so callers can pass in &some_parser if they need to.

(And actually, even if you needed to reuse them in or_else, you could use &parser1 in or_else yourself.)

Similarly, provided you deal with the other problems, you could have

fn choice<T>(parsers: &[impl Parser<T>]) -> impl Parser<T> {
2 Likes
4

This clarifies a lot. Didn't realize the distinction between the impl Trait in argument vs. return position. The code example you show also makes a lot of sense. Some follow-up questions, though.

  1. Given the restrictions with each closure having a distinct type, does that mean there is no way to implement choice using or_else, whether as a loop or using iterators?
  2. If I Boxed the function trait (so created a trait object), would it be possible to implement this in terms of or_else (even if using a loop)? I'm trying different things but still getting all sorts of lifetime errors (closure not living long enough, or not being able to take the reference of a closure) / compilation errors. I'm not sure how I'd go about creating a type-erased version like you describe.
5

The restriction is more that in order to call choice with that signature (no matter the function body), you need a slice of parsers that all have the same type (elements of a slice have the same type). That's still possible, though how ergonomic or ideal it is for your use case, I am less certain about. Example.

And you can use such type erasure to call or_else from choice as well...

pub fn choice<T>(parsers: &[impl Parser<T>]) -> impl Parser<T> {
    move |input| {
        // There may be a way to fold so that you have ~ 1/2 as many boxes;
        // I didn't attempt it.
        let parser = parsers
            .iter()
            .map(|p| Box::new(p) as Box<dyn Parser<T>>)
            .reduce(|parser1, parser2| Box::new(or_else(parser1, parser2)));

        parser.unwrap()(input)
    }
}

...but this almost surely has a performance impact (which seems undesirable if you care enough to have all this copyless parsing infrastructure).

1 Like
6

There are funny tricks you could do with choice<T: CursedTrait>(opts: T) where CursedTrait is implemented via a macro for tuples of up to (traditionally) 12 members, all of which implement Parser. And then you build a chain of or(opt.1, or(opt.2, or(... etc.

1 Like
7

You may also want to consider other implications of the boxing approach. Say you passed in 4 parsers. Effectively you build...

c1 = or_else(&p[0], &p[1])
c2 = or_else(&c1, &p[2])
c3 = or_else(&c2, &p[3])

Then you call c3

  • which calls c2
    • which calls c1
      • which calls p[0]
      • then potentially p[1]
    • then potentially p[2]
  • then potentially p[3]

You could refactor so that you only potentially recurse, but you still may recurse. And the Box destructors will also recurse the whole way regardless. So if you pass in too many parsers, you're going to blow the stack.

You could build some linked list or tree something something to iterate in place, maybe, but ugh. That's a ton of work and headaches just so you can use or_else.

Maybe consider having an or_else somewhere different, like on your return type.

1 Like
8

Extremely helpful. Thanks for all the examples. And you’re right, it’s extremely wasteful to just create all these boxes for no reason; my goal was just to understand what is possible as a whole with closures.

1 Like