Should we allow generic parser/control declarations?

[jaehyun1ee]

The current spec disallows generic parser/control declarations, in sections 13.2 and 14. For example, Section 13.2. Parser declarations states:

parserTypeDeclaration
    : optAnnotations PARSER name optTypeParameters
      "(" parameterList ")"
    ;

parserDeclaration
    : parserTypeDeclaration optConstructorParameters
      "{" parserLocalElements parserStates "}"
    ;

Unlike parser type declarations, parser declarations may not be generic---e.g., the following declaration is illegal:

parser P<H>(inout H data) { /* body omitted */ }

Hence, used in the context of a parserDeclaration the production rule parserTypeDeclaration should not yield type parameters.

Yet, it seems reasonable to amend the spec to allow generic parsers/controls because: (i) p4c accepts these as valid, and (ii) there are already other parts of the current spec that expects generic parsers/controls.

First, in p4c, this restriction does not exist. It is also reflected in some of the test programs in p4c/testdata/p4_16_samples:

• functors6.p4, functors7.p4, functors8.p4, functors9.p4
• generic.p4, generic1.p4
• issue1914-1.p4, issue1914.p4
• issue2019-1.p4, issue2019.p4
• issue2265.p4
• issue344.p4
• spec-issue1068.p4

Additionally, Section 15.1. Direct type invocation expects generic parsers and controls where it states:

directApplication
    : typeName "." APPLY "(" argumentList ")" ";"
    | specializedType "." APPLY "(" argumentList ")" ";"
    ;

This feature is intended to streamline the common case where a type is instantiated exactly once.
The second production in the grammar allows direct calls for generic controls or parsers:

control Callee<T>(/* parameters omitted */) { /* body omitted */ }

control Caller(/* parameters omitted */)(/* parameters omitted */) {
    apply {
        // Callee<bit<32>> is treated as an instance
        Callee<bit<32>>.apply(/* arguments omitted */);
    }
}

This part of the spec has been added after discussion in #1069. So following section 15.1, we can invoke generic parsers and controls, but according to section 13.2 and 14, we cannot define them at the first place, which I think is contradictory.

With these, I believe sections 13.2 and 14 don't accurately capture how P4 is used at the current state, and think that these should be revised to allow generic parsers and controls. Though I am also not aware of the initial motivations for disallowing generic parsers and controls. I believe it would be helpful to be discussed in LDWG :)

[jnfoster]

Indeed, p4c has long supported generic parsers and controls. However, if the type system uses parametric polymorphism, these are mostly useless, as any expressions whose type is a variable will have no operations on it.

There are two paths forward:

• Add some kind of type constraints so type variables are no longer useless
• Change the semantics of type parameters to be like C++ templates rather than parametric polymorphism

[jaehyun1ee]

Yes, use of variable types is quite limited in P4, as it can be only assigned via = or passed along to another generic, e.g., an extern function call. Better support for these types would definitely increase programmability.

For now, I think we should start with amending the spec to allow generic parsers and controls, as this change better reflects p4c and is consistent with other parts of the spec.

But in the broader scope, we should also think of handling variable types, which would be a big change to the language. I've thought about this for a while, and below is a short summary of my thoughts.

This is an example of how variable types can be used in current P4: assignments and calls.

extern T g<T>(in T t)

void f<T>(inout T t) {
   T x = t;
   g<T>(x);   
   return;
}

I'm not aware of the immediate benefits of using the parameter in T t in the function body, but I'll assume a case when we want to do some arithmetic on it, e.g., t + t, when T may be bit<32> or int<8>.

• C++ templates

template<T>
void f(inout T t) {
   t = t + t;
   return; 
}

// and somewhere else in code ...
bit<32> x = 1;
f<bit<32>>(x);
int<8> y = 2;
f<int<8>>(y);

This is intuitive and I believe P4 programmers would be familiar with it.

But the downside, I think, is that it would be quite complex to implement a type checker. Templates cannot be type checked as-is, and only a specific instance (when type arguments are supplied) can be type checked. So, declaration of templates and type checking of templates are decoupled. Thus, with templates, type checking cannot proceed as a linear pass over a P4 program. It should instead revisit and instantiate templates during type checking. This kind of implementation is doable, but I expect that getting it right and efficient would not be that easy.

• Type constraints

We may add type constraints, in the form T : tau where tau is some type. For instance,

void f<T : bit<32>>(inout T t) {
   t = t + t;  
   return;
}

But notice that this toy example is not useful, as it is just the same as declaring a monomorphic function void f(inout bit<32> t). To be useful, type constraints should be able to express a group of types, e.g., that T may be bit<32> or int<8>. Yet, P4 does not have inheritance and the subtype (or casting) relation between types are very simple. So, it is hard for me to imagine a crisp syntax for expressing type constraints. Maybe, one way to go is:

void f<T : bit<32>, T : int<8>>(inout T t) {
   t = t + t;  
   return;
}

where , is a logical-or of multiple type constraints.

The good part here is that generic declarations can be type checked as-is.

[jnfoster]

Generic parsers and controls were deliberately held back from the specification because, in the current form implemented by p4c they are essentially useless. I would personally recommend continuing to hold them back until further changes are made so they are not useless. It is pretty risky to add features to a language when you are not fully sure of the ramifications, unless you are happy with not-backward-compatible changes in the future. Given that there are still big questions about how to do generic controls and parsers, I see little upside and potential downside.

As far as solutions...

Adopting template-style polymorphism, like C++, is an "easy" way to address the problem that type variables are essentially useless. But abandoning parametric polymorphism would be a major philosophical change. Also, template-style polymorphism has the problem that is compilation and type checking are both anti-modular. Consider a generic control:

control C<T>(...) { 
  T t;
  ...
  t = t + t;
  ...
}

If we only instantiate C at numeric types, say C<bit<8>> everything appears to be fine. But if we instantiate C at bool, then we get a type error -- the assignment in the body of C is wrong. So code that previously appeared to type check is now rejected with an error. In general, you can never be sure that a generic declaration is type correct, as a future instance might trigger a new type error.

So I'm personally (strongly) not in favor of templates. But of course the LDWG should decide by consensus.

For type constraints, some approaches that were previously sketched (but not fleshed out into full designs) is something like Rust's traits. You could also call these type families. For example, you could have a trait/type family that captures bit-like. All types of the form bit<n> for some n belong to it. And then you could have a declaration like C<T is BitLike> so that C<bit<8>> and C<bit<16>> are well-typed but C<bool> is not. Within the body of C it would be legal to do arithmetic and bitwise operations on values of type T.

Fleshing out the latter design requires considerable work, but it seems like the nicest solution to me: principled and useful.

[ChrisDodd]

This is connected to p4c issue #5067

[rcgoodfellow]

LDWG: Something to consider for p4-next for a new major version of P4, but probably not something to put into P4-16

[jaehyun1ee]

Summary of the discussion made above:

• p4c supports generic parsers/controls, however they are mostly useless because the operations on variable-typed expressions are quite limited in P4.
  • P4 currently only allows assignment (via = or argument passing) for these expressions.
• To support better use of these, there can be two directions in extending the type system:
  • C++ template-style polymorphism
    • (Relatively) easy to implement
    • But abandons parametric polymorphism, where type checking depends heavily on how the templates are actually used (further hurts modularity)
  • Rust trait-style, bounded polymorphism
    • Better in terms of modularity
    • (Relatively) difficult to design and implement, especially on what should be the "useful" set of type families, or type classes in P4
• Given these, it seems safe to p4c as an experimental implementation of generic parsers/controls, yet leaving the specification as-is, disallowing them.