Understanding Parboiled2's '~' Combinator

Question

Looking at the parboiled2 section, Rule Combinators and Modifiers:

I don't understand the a, b, and then a ~ b diagram.

So far I've found the documentation straightforward. But I am a bit lost here.

Can you please explain each block?

Answer 1

Here's the definition of Rule:

class Rule[-I <: HList, +O <: HList]

The documentation you linked gives more explanation, but essentially I is the input to the Rule and O is the output of the Rule. The colon notation can be a little confusing. parboiled2 uses a stack to manage the state. Just remember that the types in the colon lists (HList) are produced/pushed from left to right, and consumed/popped from right to left. In the HList A:B:C, C is the top of the stack, and has to be consumed first.

~ runs one rule then the next. So in the first example a of type Rule[, A] consumes nothing and 'produces' an A, while b of type Rule[, B] consumes nothing and 'produces' a B. It makes sense then, that if you ran a followed by b, you would produce an A followed by a B. The resulting type is Rule[, A:B].

Things become much more complicated when you add inputs. You need to make sure that the types produced by a (or whatever the first rule is) are the types that b is going to consume. ~ is just like function composition. If we want to compose g and f to get g . f, we need to be sure that the output of f is the same type as the input of g.

Let's look at the third example in the table.

• a has type Rule[A, B:C]
• b has type Rule[D:B:C, E:F]

When we run a an A is consumed from the stack, a B is added to the stack, and a C is added to the stack. Then b is run, first it consumes the C, then the B, then it consumes a D off the stack. To be in the right place at the right time, that D would need to be under the A that a consumed. b would then produce an E then an F.

In total, we consumed a D and an A. The B and C don't count because they were produced and consumed internally to the rule. After consuming D and A, we leave E and F on the stack. So, the type of a ~ b is Rule[D:A, E:F].

The fourth example in the README gives an example where a produces the wrong types for b to consume. In that case a ~ b is illegal.