Allow using types to disambiguate overloaded calls

[vgurevich]

• [x] Owner: @vgurevich
• [ ] Supporters:
• [x] Design document rationale: see below
• [ ] P4 spec document written
• [ ] P4C compiler implementation provided:
• [ ] Discussed in P4 design meeting:
• [ ] Approved by LDWG
• [ ] Merged into spec
• [ ] Merged into compiler

The current version of the spec states the following in section 7.2.9.2 (Bold is mine):

Functions and methods are the only P4 constructs that support overloading: there can exist multiple methods with the same name in the same scope. When overloading is used, the compiler must be able to disambiguate at compile-time which method or function is being called, either by the number of arguments or by the names of the arguments, when calls are specifying argument names. Argument type information is not used in disambiguating calls.

I was wondering what is the rationale behind the last statement and whether it can be changed to allow the argument type(s) to be used for disambiguation, similar how it is done in at least some languages (e.g. C++).

Here are some basic use cases:

Advanced Hash

It is desirable to be able to define hash functions based on:

1. Predefined formulas (e.g. CRC-32, CRC-16, etc.)
2. CRC, based on an arbitrary polynomial, represented as CrcPolynomial() extern
3. Using a raw linear code generator matrix, represented as LcgMatrix() extern
4. Using a string with some formula, represented as a string
5. etc.

The obvious solution would be to overload the constructor, e.g.

enum HashAlgorithm_t {
    IDENTITY,
    RANDOM,
    CRC8,
    CRC16,
    CRC32,
    CRC64,
}

extern Hash<W> {
    Hash(HashAlgorithm_t algo);  
    Hash(HashAlgorithm_t algo, CRCPolynomial<_> poly); 
    Hash(HashAlgorith_t algo, LcgMatrix<_> matrix);   
    Hash(HashAlgorith_t algo, string formula);  

    W get<D>(in D data);
}

This does not work, however, because the compiler cannot disambiguate between these constructors and reports errors like this:

sample_arch.p4(497): [--Werror=duplicate] error: Ambiguous method Hash
extern Hash<W> {
       ^^^^
sample_arch.p4(505): [--Werror=duplicate] error: Candidate is Hash
    Hash(CRCPolynomial<_> poly);
    ^^^^
sample_arch.p4(506): [--Werror=duplicate] error: Candidate is Hash
    Hash( LCGMatrix<_> matrix);
    ^^^^
sample_prog.p4(115): [--Werror=type-error] error: hash: type Hash has no matching constructor
    Hash<bit<32>>(poly) hash;
                        ^^^^^

Note that the problems start during the architecture file processing, so even if the programmer later uses the argument names for disambiguation, things still look unpleasant.

For now there is a workaround that allows us to have two choices (predefined or custom CRC polynomial, but there is no good way to extend that:

enum HashAlgorithm_t {
    IDENTITY,
    RANDOM,
    CRC8,
    CRC16,
    CRC32,
    CRC64,
    CUSTOM_POLY, 
    // CUSTOM_MATRIX, CUSTOM_FORMULA  -- of no use
}

extern Hash<W> {
    Hash(HashAlgorithm_t algo);    /* algo MUST be anything but CUSTOM_* */
    Hash(HashAlgorithm_t algo, CRCPolynomial<_> poly);  /* algo MUST be HashAlgorith_t.CUSTOM_POLY */

    /* But these still can't be added :( */
    // Hash(HashAlgorithm_t algo, LcgMatrix<_> matrix);    /* algo MUST be HashAlgorith_t.CUSTOM_MATRIX */
    // Hash(HashAlgorithm_t algo, string formula);         /* algo MUST be HashAlgorith_t.CUSTOM_FORMULA */

    W get<D>(in D data);
}

Advanced Meter Externs

There is a need to have Meter externs with some extra parameters that reflect architecture capabilities, e.g.

extern Meter<I> {
    Meter(bit<32> size, MeterType_t type);

    bit<8> execute(in I index, in MeterColor_t color, @optional in bit<32> adjust_byte_count);
    bit<8> execute(in I index, @optional in bit<32> adjust_byte_count);
}

Here the problem is that the compiler cannot figure out whether an execute() with two parameters represents the first or the second variant of the method, again, because the type is not used.

Proposal

The proposal is to allow argument type information to be used for disambiguation.

[mihaibudiu]

You are not showing the complete example that gave these errors. The solution is have indeed constructor with different argument types, but also with different argument names, and to invoke the constructor explicitly indicating the argument name:

Hash(poly = blah) x;

[vgurevich]

@mbudiu-vmw -- I was quickly checking using the existing arch, but I can construct the minimal example.

As I pointed out, the problem is that the compiler does not like the arch itself.

Also, forcing the user to always use the argument name is not nice -- the computer is fully capable figuring this out and that's what people expect.

What is the reason for not doing that? Is there a deep reason that I simply can't see or it is a matter of implementing it?

[mihaibudiu]

The architecture you submitted looks fine, the compiler should accept it. If it doesn't there's a bug. Using types for disambiguation would not be a trivial change in the compiler.

[ChrisDodd]

The main question is how much type information we want to use. I don't think we need anything as complex as C++ with its priority classes and whatnot. Perhaps just say the types are used to eliminate methods that cannot match (no conversion is possible from the argument type to the parameter type), but if there is more than one that could match (with any possible implicit conversions -- we don't have too many) then the result is ambiguous.

[vgurevich]

@mbudiu-vmw -- as you can see in the original submission, error messages are displayed against the statements in the arch file first. Let me try to create a minimal example to aid the discussion.

[mihaibudiu]

@vgurevich : you are only showing the code for the workaround, but not the original code. Supplying an argument name is not that onerous, but I agree types could be simpler. The solution with argument names is less ambiguous in the presence of implicit casts.

[vgurevich]

@mbudiu-vmw -- attached is a basic example issue884.p4.txt that uses a fake architecture. Note, that even specifying the names of the arguments explicitly doesn't help.

[ChrisDodd]

The problem in this issue884.p4 is not the overloading -- it's the missing W type parameter in the Hash constructor calls, which can't be inferred from the arguments. If you add them, it also complains about the missing type params to LCGMatrix (which it should be able to infer), and that string literals are not compile time constants...

[mihaibudiu]

The problem in your example is not with the argument types, but with the type arguments of the generic. These cannot be inferred by the compiler. If you fill them in it compiles fine. (There still one extra problem with the strings, which the compiler does not recognize as compile-time constants, but that looks like a different bug.)

[mihaibudiu]

control Ingress(inout headers_t hdr, inout meta_t meta)
{
    Hash<bit<32>>(algo=HashAlgorithm_t.CRC32)       hash1;
    Hash<bit<32>>(poly=CRCPolynomial<bit<32>>(coeff=0x107))  hash2;
    LCGMatrix<bit<8>, bit<10>>(8w4, 10w7,
        "1000100
         0100011
         0010110
         0001001") hamming;
    Hash<bit<32>>(matrix=hamming) hash3;
    Hash<bit<32>>(formula="magic_formula()") hash4;

    apply {
    }
}

[ChrisDodd]

Note that the compiler should be able to infer the type parameters to LCGMatrix from the arguments -- not sure why that is failing. Also maybe it should infer an int type parameter to CRCPolynomial as well.

[mihaibudiu]

I think that we lost this ability with a recent commit. Let me try to remember why.

[mihaibudiu]

No, it wasn't lost, the recent commit lost the ability to infer a value of "don't care" for a type parameter which is never used. Indeed, I expect we would infer the values of these type parameters. Could it be that we do it for functions but not constructors? I will file two issues with the compiler.

[jnfoster]

I think it's unwise to go down the path of allowing type information to be used in overloading until we understand precisely what the P4_16 typesystem is.

Currently neither a specification nor an algorithm for how type checking and inference should work is written down anywhere except in the C++ implementation.

-N

On Thu, Jul 30, 2020 at 7:39 PM Mihai Budiu notifications@github.com wrote:

No, it wasn't lost, the recent commit lost the ability to infer a value of "don't care" for a type parameter which is never used. Indeed, I expect we would infer the values of these type parameters. Could it be that we do it for functions but not constructors? I will file two issues with the compiler.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/p4lang/p4-spec/issues/884#issuecomment-666775602, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAOCFUVWBA6SW4T5VNKWWRDR6IADLANCNFSM4PM55VTA .

[vgurevich]

@mbudiu-vmw -- thanks for noticing the initial problem.

Attached is the simplified example issue884_1.p4.txt. If compiled "as-is" it produces the following error messages:

$ ~/trees/org/p4c/build/p4test issue884_1.p4
issue884_1.p4(14): [--Werror=duplicate] error: Ambiguous method Hash
extern Hash<W> {
       ^^^^
issue884_1.p4(15): [--Werror=duplicate] error: Candidate is Hash
    Hash(HashAlgorithm_t algo);
    ^^^^
issue884_1.p4(16): [--Werror=duplicate] error: Candidate is Hash
    Hash(CRCPolynomial<_> poly);
    ^^^^
issue884_1.p4(38): [--Werror=type-error] error: hash1: type Hash has no matching constructor
    Hash<bit<32>>(HashAlgorithm_t.CRC32) hash1;
                                         ^^^^^
issue884_1.p4(14)
extern Hash<W> {
       ^^^^
issue884_1.p4(39): [--Werror=type-error] error: hash2: type Hash has no matching constructor
    Hash<bit<8>>(my_crc) hash2;
                         ^^^^^
issue884_1.p4(14)
extern Hash<W> {
       ^^^^

If you compile it with argument names in the constructors (with -DUSE_ARG_NAMES), it compiles cleanly.

Why is this important?

Assume that initially the Hash() extern was defined with only one constructor. As a result, in 99.9% of code out there the instantiation is done without the argument name, e.g.

Hash<bit<32>>(HashLagorith_t.CRC32) hash;

Now you want to amend the architecture and add another constructor (with CRCPolynomial). If you do it with one argument, you are going to break that 99.9% of all existing programs. They will be broken because the sheer presence of an overloaded constructor in the arch file. This will be certainly wrong.

Now, imagine that you bit the bullet and decided to define the constructors like this:

enum HashAlgoritm_t {
   ...
   CUSTOM_POLY
}

Hash<T>(Hash_Algorithm_t algo);
Hash<T>(Hash_Algorithm_t algo, CrcPolynomial<_> poly);

This would preserve the backwards compatibility for a while.

Now, you want to add one more constructor, e.g. for the hash based on Linear Code Generator Matrix. You will be stuck, since the trick of adding another enum value will not work -- the compiler will not be able to distinguish between the constructor with the polynomial and the one with the matrix (since they both will have two arguments).

If all the code would be typically written with argument names this would not be a problem, but most probably it will be written without them.

Precisely the same situation happens with overloaded methods (in fact, people use argument names there even less often).

Thus the suggestion to use the names works only if most of the code would be written from scratch, but once you have a body of code out there, adding a new argument seems to be much more difficult than one would expect.

[vgurevich]

@jnfoster -- I agree that it is important to define these rules. I hope it would not be as difficult compared to C++ -- our type system is a lot simpler.

Assuming that we do that (and let's figure out what is required), would you agree that it would be a useful to use types for disambiguation of overloaded constructors/methods/functions?

[jnfoster]

Overloading is always a controversial topic. I'm not opposed to it, but there is always a danger of making things more confusing... but your example involving hash constructors is pretty compelling...

[vgurevich]

We've just hit another case, where the current rule limits us in the ability to extend an existing architecture in a backwards-compatible way. If you look at the TNA, you will see the following definition for the extern, called ActionSelector:

extern ActionSelector {
    /// Construct a selection table for a given ActionProfile.
    ActionSelector(ActionProfile action_profile,
                   Hash<_> hash,
                   SelectorMode_t mode,
                   bit<32> max_group_size,
                   bit<32> num_groups);

    /// Stateful action selector.
    ActionSelector(ActionProfile action_profile,
                   Hash<_> hash,
                   SelectorMode_t mode,
                   Register<bit<1>, _> reg,
                   bit<32> max_group_size,
                   bit<32> num_groups);
. . .

As you can see, the first (simpler) constructor takes 5 parameters and the second, more complex one takes 6.

We need to add a new, @optionalbool new_flag parameter to both constructors, but the current rules make it impossible, because once the compiler sees a constructor with 6 parameters, it cannot figure out, whether it is the first one with the optional parameter or the second one without an optional parameter.

Obviously, one can define a new (very similar) extern (e.g. ActionSelectorWithFlag, but that defeats the purpose and, in my opinion, is not a good solution.

I do propose to change the corresponding portion of the (section 7.2.9.2)[https://p4.org/p4-spec/docs/P4-16-v1.2.1.html#sec_extern] (Bold is mine):

Functions and methods are the only P4 constructs that support overloading: there can exist multiple methods with the same name in the same scope. When overloading is used, the compiler must be able to disambiguate at compile-time which method or function is being called, either by the number of arguments and their types or by the names of the arguments and their types, when calls are specifying argument names. Remove the sentence about the type info not being used

[jafingerhut]

Do you have a proposal for exactly how the compiler should use types in constructor calls to determine which of several methods might be meant, in the face of @optional constructor parameters?

e.g. should a parameter with type bit<8> be matched by a call where the parameter in the corresponding position uses a value with type enum bit<8> MyEnum_t ..., or not? What if the argument in the call is the literal -5? What if they are two differently named struct types, but they have the same corresponding field types and names? What if one is one of the new generic structs that is either already added to the spec, or is proposed to be added to the spec (I have forgotten whether it is in the spec or not yet), and the other is a struct that "looks the same" if you instantiate the type parameter of the generic struct so that field names and types look the same?

Merely saying "and their types" doesn't answer these questions, and the p4c implementation and spec seems like they need answers to at least some of those questions, if not all of them.

[mihaibudiu]

The feature being in the spec is not enough for it to be in the implementation. And usually we don't put stuff in the spec until we have an implementation. I have resisted so far using types because the phase ordering in the compiler requires the type checker to disambiguate calls in order to check them. Given the backlog of bugs, I am not sure when I would have time to modify the type checking algorithm to accommodate this feature. If there is a volunteer to tackle this feature I certainly won't object. But this is the kind of feature where I think an implementation should certainly exist before it is officially accepted.

[vgurevich]

@mbudiu-vmw -- that's precisely why I sent the "ping". I totally agree that in this case the implementation is going to drive the spec a lot more than in many other cases. I can write a detailed algorithm, but it is not going to be very useful until we make sure that it fits into the overall implementation of the type checker.

I will certainly discuss internally if this is something we can take an initiative on, but I want to make sure the issue is understood and we agree that it is important to resolve it, because it definitely holds us back.

Obviously, workaround suggestions are welcome as well.

[vgurevich]

@jafingerhut -- I agree.

Let's try, although this probably will not be a short proposal (as we can see in C++, which is one of the examples where types do play a significant role in the overloading resolution)

First, is the case without @optional parameters and without names being specified. If two or more functions/constructors have the same number of arguments, the compiler has to disambiguate, based on the types. One interesting quirk is that we have some implicit casting rules. I would think that if there are ambiguities, then the candidate with the fewer casts wins. In other words, if you have N constructors:

     c(t_1_1_t a_1_1, ..., t_1_m_t a_1_m);
     c(t_2_1_t a2_1, ..., t_2_m_t a_2_m);

     c(t_N_1_t, a_N_1, ..., t_N_m_t a_N_m);

and a constructor call

    c(t_1_t a1, ..., t_m_t a_m);

compiler needs to select the constructor S with the types t_S_1_t, ..., t_S_m_t that require the fewer number of casts from t1_t, ..., t_m_t. If more than one constructor can be selected that way (i.e., there are several constructors. that require the same (minimal) number of casts), a compilation error occurs.

For example:

/* Example 1 */
extern e_1 {
    e_1(bit<32> a_1_1, bit<16> a_1_2); /* A */
    e_1(bit<32> a_2_1, bit<32> a_2_2); /* B */
}

e1(32w11, 16w12) --> e_1(a_1_1 = 32w11, a_1_2=16w12);  /* A-0, B- */
e1(21, 16w22) --> e_1(a_2_1 = 32w21, a_2_2=16w22);     /* A-1, B- */
e1(31, 32) --> error  /* A-2, B-2 */
e1(True, 42) --> error  /* A-, B- */

enum bit<16> { VAL_1 = 51, VAL2=52 } enum_1_t;
e1(51, enum_1_t.VAL2) -> e_1(a_1_1 = 32w51, a_1_2=16w52);  /* A-2, B- */

e1(61, (bit<16>)62); /* A-1, B- */
e1(61, 16w62); /* A-1, B- */

If we think about @optional parameters without names, then you simply have more cases to choose from. Assume, that they can follow the mandatory ones (although the algorithm will work the same way even if they are in the middle). In other words, a constructor with K optional parameters:

      c(t_1_1_t a_1_1, ..., t_1_m_t a_1_m, @optional to_1_1_t oa_1_1, ..., @optional to_1_k_t oa_1_k);

is first expanded into the following K+1 constructors (I do not see that being said explicitly, but I think we should say. that if used unnamed, optional parameters cannot be skipped):

    c(t_1_1_t a_1_1, ..., t_1_m_t a_1_m); /* No optional parameters */
    c(t_1_1_t a_1_1, ..., t_1_m_t a_1_m, to_1_1_t oa_1_1); /* 1 optional parameter */
    c(t_1_1_t a_1_1, ..., t_1_m_t a_1_m, to_1_1_t oa_1_1, to_1_2_t oa_1_2); /* 2 optional parameters */
    . . . 
    c(t_1_1_t a_1_1, ..., t_1_m_t a_1_m, to_1_1_t oa_1_1, ..., to_1_k_t oa_1_k); /* K optional parameters */

After that, the previously described algorithm is applied.

For the calls with the mix of named and unnamed parameters, let's first establish some rules:

1. Unnamed parameters cannot follow named parameters.
2. All unnamed parameters in front are treated positionally
3. Named parameters cannot be used to specify anything that has already been specified positionally. For example, one cannot write c(1, 2, 3, a_1_2=5)

This basically reduces the problem of matching calls with the mix of parameters to the problems of matching parameters without names (already covered above) and matching parameters with names only (in other way, both halves of the call have to match the same variant of the constructor/function).

For the calls with the named parameters only, the names of the parameters in the call will be used to select the candidates and if there is more than one, then the type matching will be applied using the same rules as in the case of the calls with unnamed parameters. The only difference is that the compiler can "virtually" sort the parameters in the same order as their names.

What do you think?

[vgurevich]

Update: per my discussion with @jafingerhut , it might be better to have a stronger resolution rule: if there is more than one candidate that matches (regardless of the number of implicit casts) , then we'll declare an error. Given that these constructors are not arbitrary, but carefully developed by the people who define a specific architecture, this will work as well.

[jafingerhut]

Notes from discussion of this issue in 2021-May-03 LDWG meeting:

Mihai: Error if the compiler cannot narrow the list of candidates down to one certainly sounds better than "fewest casts wins", even though multiple candidates remain.

Mihai: Implementation in p4c is not easy. The p4c type checker is not a simple part of the implementation.

Chris: May require mixing type resolution and reference resolution logic.

Chris: Type variable parameters to constructors, two or more of which are the types of constructor parameters for more than one constructor call, seem like it might make source code example that could be constructed where it was impossible to narrow down a call down to one candidate constructor? Even if it was possible, the p4c implementation might be tricky.

Mihai: While this does seem useful, currently other priorities of p4c developers may hinder quick proposed implementation. If it leads to type resolution becoming much more complex in the spec, that would be a reason to push back even with a proposed implementation.

[jnfoster]

In the interest of tidying up the set of active issues on the P4 specification repository, I'm marking this as "stalled" and closing it. Of course, we can always re-open it in the future if there is interest in resurrecting it.