Externs should have either a return type or at least one parameter

[erichulburd]

Looking at the spec for CALL instructions:

@syntax[:name "Extern Call Instruction"]{
    CALL @ms{Identifier} @rep[:min 1]{@group{@ms{Identifier} @alt @ms{Memory Reference} @alt @ms{Complex}}}
}

I noticed the :min 1 on call. This implicitly means EXTERN signatures should include either a return type or at least one parameter.

[macrologist]

@syntax[:name "Extern Signature Pragma"]{
    PRAGMA EXTERN @ms{Identifier} "@ms{Extern Signature}"
}

@syntax[:name "Extern Signature"]{
    @rep[:min 0 :max 1]{@ms{Base Type}} ( @ms{Extern Parameter} @rep[:min 0]{@group{ , @ms{Extern Parameter} }} ) 
}

@syntax[:name "Extern Parameter"]{
    @ms{Identifier} : @rep[:min 0 :max 1]{mut} @ms{Type}
}

Looking at the syntax for Extern Signature, it seems that they do have at least one parameter and a return type is optional. In more familiar grammar-specifying syntax, the above looks like:

ExternSignature = BaseType? ( ExternParam ExternParams?)
ExternParams = , ExternParam ExternParams

Where (, ), and , are interpreted as literal characters.

Is this what you meant?

[erichulburd]

I see, so the first ExternParam isn't optional? So this actually requires at least one non-return parameter, regardless as to whether or not there is a return value. However, I don't see what that would be the case. Why require at least one parameter?

[erichulburd]

@macrologist A few other points of clarification I think we should make:

1. Must a CALL instruction have a corresponding EXTERN instruction? Yes, is better IMO for explicitness.
2. Assuming a CALL requires a corresponding EXTERN, must the corresponding EXTERN precede the CALL instruction? i don't see a good reason to make this restriction, so I would explicitly say this doesn't matter.
3. Is it illegal to have two EXTERNs with the same name? I think it should be illegal, otherwise we have to handle overloading, which the spec currently does not cover. Should we want to support overloading in the future with sufficient detail, it's a forward compatible change.
4. Are EXTERN names case sensitive? There is no mention of this in the Quil spec. quil-rs seems to assume case sensitivity. This means you could have three different function names rng, RNG, rNg. I don't like this but it's consistent.
5. Can EXTERN names be reserved? For instance could you name the function ADD or INCLUDE? How should these collisions be enforced - case sensitive or insensitive? Again, consistency suggests case sensitive enforcement.
6. Do EXTERN signatures support variable length memory regions? The spec reads to suggest that REAL should be interpreted as a single value (ie it is legal to have a REAL return type as in EXTERN prng "REAL (seed : INTEGER)"). So what of variable length memory regions as in EXTERN choose "REAL(seed : INTEGER, choices : REAL)"? Here choices : REAL would be ambiguous. I would suggest adding syntax for variable length memory regions as REAL[].

[macrologist]

I see, so the first ExternParam isn't optional? So this actually requires at least one non-return parameter, regardless as to whether or not there is a return value. However, I don't see what that would be the case. Why require at least one parameter?

That's correct it /does/ require one parameter. About your PR, even though the grammar specifies that this is the case, it might still be a good idea to spell it out in English.

As to the why, I think the concern had to do with the two ways that externs are being used. To recap (correct me if I'm wrong):

1. via a CALL: To act on, read, and possibly mutate some classical memory that has been declared in the quil program
2. in a numerical expression: To return a value when an extern appears in Quil instruction parameter positions (e.g. CPHASE(my_extern(10)) 0 1)

Recalling also that there is an equivalence between

PRAGMA EXTERN moo "INT (x: INT)" 

and

PRAGMA EXTERN moo "(y : mut INT, x : INT)"

from the perspective of a CALL instruction. And indeed, there is no reason to CALL something if it isn't going to be altering declared memory somehow. B/c how else will the rest of the quil program make use of the call?

If you want to relax this so that calls are just calls to external functions, including those with no named references to any other parts of quil programs, then tat seems like a good agenda item for a quil meeting.

I want to make clear with an example what the "zero arity externs" would permit:

CALL foo 
CALL bar
CALL baz 
CALL moo
...

I.e. quil would end up being able to support a very underwhelming batch procedural language such that all of these calls would be invisible to the rest of the quil program itself. I know that this is an extreme example, but I just wanted to highlight what would be possible.

As for your 6 items:

1. yes. Any function mentioned in a CALL must be declared in an EXTERN instruction. On my reading, the spec does assert this requirement, but perhaps it could be clearer.
2. The spec doesn't say, but Im open to pinning this down if there's a good reason to. I don't know if human beings are looking at your quil source files, but if they are, it might be nice if EXTERNs appear at the top of the file. Just a personal take: I can see reasons to do it both ways, which might mean it is best left unspecified. Open to discussion on it for sure.
3. The spec doesn't say. If you're declaring dozens of EXTERNs and doing so intersperesed throughout a quil source file, then I see the utility of making this stritctly illegal. It is unspecified right now.
4. I think it should be up to the control architecture to which externs are native. Since externs are by their very nature tied to some specific external environment, different environments may find different case conventions more or less convenient.
5. I would prefer to NOT allow externs to be named with quil reserved words, but it would not be impossible to support - just annoying. I think the principle of flexibility is not always worth defending prima facie, but there may be real need. If there is, we should talk about it more.
6. If I recall correctly, we punted this ask to a later discussion. This may be the time to open that discussion. Another good agenda topic would be "sequential memory in externs? + structured memory declarations at all?" or something.

[erichulburd]

The parameter requirements are good with me. There is one slight idiosyncrasy that I think probably bears explicit mention. According to the grammar, a user would have to write:

 EXTERN foo "(ret : mut INTEGER)"

# instead of:

EXTERN foo "INTEGER"

So I think we could either:

1. Relax the grammar so no parameters would be required, but mention that either a return value or at least one parameter is required in the signature.
2. Spell out this idiosyncrasy explicitly.

I'm fine with either option; I probably prefer the first.

---

For items 1-5, my general tact would be to favor explicitness and consistency, so I think we're generally on the same page. I will update my PR to:

1. Explicitly require a corresponding EXTERN declaration for each CALL. These must match case sensitively on name.
2. State that the spec leaves unspecified the ordering of EXTERN declarations with respect to any corresponding CALL. (this seems more like a lint / format thing, than a spec level requirement). 3-4. Explicitly require uniqueness of every EXTERN name, case sensitive.
3. Explicitly require that EXTERN names not infringe on reserved words, case sensitive.

---

For item 6, I'm not sure why I punted on this, but it's somewhat of a requirement for our first use case which involves choosing a random element from a memory region. We could go lower level and just replace this function with MOD, and then index into the memory region with a LOAD, but this is less efficient in stack instructions.

I'd definitely like to get something like REAL[] into the spec. We can discuss tomorrow at the meeting.

[erichulburd]

One more item for the list: mut is lowercase, whereas almost every other keyword in Quil is uppercase. Should it be treated case sensitively? And should it be added to the list of reserved words. I lean yes and yes.

[macrologist]

One more item for the list: mut is lowercase, whereas almost every other keyword in Quil is uppercase. Should it be treated case sensitively? And should it be added to the list of reserved words. I lean yes and yes.

Hmm this is a tricky one since it isn't actually a Quil keyword.

It only ever appears inside of the string content of a PRAGMA, and it happens that the string must belong to this micro language that the standard also defines, along side Quil.

I.e. A Quil parser is 100% free to ignore pragmas, as such mut isn't really a Quil keyword at all.

With that perhaps pointless exercise in pedantry out of my system, I don't think it is unreasonable to make a choice and stick with it. The spec presently does insist that it is case sensitive. I.e. mut but not MUT or Mut or muT etc.

If you'd prefer to make it more keyword like, that's probably fine.

[macrologist]

As for item 6. Ahh I didn't realize it was the actual ask. I think it is OK so long as these array types do not appear in return positions.

[erichulburd]

With that perhaps pointless exercise in pedantry out of my system, I don't think it is unreasonable to make a choice and stick with it. The spec presently does insist that it is case sensitive. I.e. mut but not MUT or Mut or muT etc.

Great, we'll roll with that. I think lowercase definitely adds to readability, even if it is inconsistent. For that reason, I'd say let's keep it out of reserved words until it moves out of a pragma into its own instruction (if ever).

I think it is OK so long as these array types do not appear in return positions.

Yup, I understand your thinking on that.

---

I'll have a spec update in my PR touching on all of these points early next week.