Generic syntax to replace provisional $s

[josh11b]

Right now, I am using this provisional syntax in my generics proposals:

• x: T - dynamic parameter
• x:$ T - generic parameter
• x:$$ T - template parameter

In a discussion with @mconst , we thought that this alternative would be better:

• dynamic x: T - dynamic parameter
• generic x: T - generic parameter
• template x: T - template parameter
• x: T - dynamic or generic parameter based on context

The rules for determining whether x: T was dynamic or generic would be:

• For a variable declaration in the body of a function or struct: dynamic
• For a parameter in the declaration of a type or interface: generic
• For a parameter in a function signature:
  • If the parameter is used in an expression in a type position in this function signature declaration: generic
  • Otherwise: dynamic

An example of this last rule:

// Before:
fn F[T: Type, U:$ Type, N:$ UInt]
    (p: T*, a: Array(U, N), M:$ Int, V:$$ Type) -> V;

// After:
fn F[dynamic T: Type, U: Type, N: UInt]
    (p: T*, a: Array(U, N), generic M: Int, template V: Type) -> V;

Benefits of this approach:

• The unusual case of a type parameter being passed in dynamically gets highlighted.
• Any template parameter is highlighted.
• Use of : by itself is usually what you want. Particularly this syntax avoids asking the user to know that they have to do something different for type parameters.
• Use of keywords instead of symbols makes it more self-explanatory and easier to find in search engines.

The main downside of this approach is that it is context sensitive, but the scope of the context is limited to the current declaration. It also uses more characters in cases where you need to specify a keyword.

We would still need a syntax for declaring associated types and constants in an interface body, I propose const name: type, optionally followed by an = default.

// Before:
interface Addable(RHS:$ Type = Self) {
  var AddResult:$ Type = Self;
  method (me: Self) Add(rhs: RHS) -> AddResult;
}

// After:
interface Addable(RHS: Type = Self) {
  const AddResult: Type = Self;
  method (me: Self) Add(rhs: RHS) -> AddResult;
}

I'm hesitant to use var here (though we could, with a generic default) because var would have a different interpretation when implementing this interface in a struct definition, and generally elsewhere var would default to dynamic.

[josh11b]

We talked about the alternative of using & Auto or & Template to indicate that a parameter was a template, but it had two downsides:

• Only worked for type parameters, would need something else for non-type.
• It didn't seem like you would want to be able to hide an & Auto / & Template clause in an alias declaration:

alias CT = Container & Template;
fn SurpriseIHaveATemplateParam[T: CT](c: T);

That seemed to suggest that the Auto or Template keyword was not acting like other type-of-type expressions and would need special treatment.

[josh11b]

Alternate rule for the default in function declarations from @mconst (see this message in discord):

"implicit parameters and struct parameters default to generic; everything else defaults to dynamic"

This is simpler, and involves less need to carefully examine the code for readers to determine whether something is dynamic or generic when using the default.

[josh11b]

A modification of that last rule:

In function declarations:

• If it is an implicit parameter it defaults to generic.
• If it is an explicit parameter it defaults to dynamic unless that parameter is used in an expression in type position.
• Otherwise there is no default, you have to explicitly say generic or dynamic.

This way, when reading you can use the rule that all unmarked explicit parameters are dynamic, but you are less likely to accidentally make a dynamic type parameter because of the default.

[zygoloid]

I wonder how let and var fit into this. Specifically, I think we don't want to (and probably can't) support combining var with generic or template, so I think we have four different things here:

• known-before-typechecking immutable value (template)
• known-after-typechecking immutable value (generic)
• dynamic immutable value (let? or perhaps the absence of a keyword)
• dynamic mutable value (var?)

Perhaps we don't need a dynamic keyword and can use let and/or var instead?

[josh11b]

@zygoloid , are you talking about let or var in a parameter list or in a function body?

[zygoloid]

Both, but I was specifically thinking about parameter lists.

[josh11b]

I think the four categories you list make sense as mutually exclusive alternatives. "Dynamic immutable value" is a good default in a parameter list. In a function body, it makes sense to spell that let, but with one hesitation. I would also want to mark names bound to types as "dynamic immutable" when opting into dynamic dispatch, and for that case let is not as clear a match.

Thinking about this further, if we are going to allow you to declare names bound to "known-after-type-checking immutable values" inside structs and function bodies, I am tempted to suggest using the keyword const instead of generic. That term admittedly carries a lot of baggage with it, but it is still suggestive of the "compile-time constant" meaning I'd like to convey when using it.

[chandlerc]

There was some interesting discussion about this issue today in the open discussion session and I wanted to at least relay one aspect of it here (there were others but those might be better summarized by others).

Specifically, we explored a couple of alternatives to the default-with-keyword-override approach suggested above.

---

One alternative would be to make the default be indicated via syntax, and allow the syntax nesting to reflect explicit vs. deduced. This could be done with [] for example and look like:

fn F[dynamic T: Type, U: Type, N: UInt]
    (p: T*, a: Array(U, N), [M: Int, template V: Type]) -> V;

interface Addable([RHS: Type = Self]) {
  let [AddResult: Type] = Self;
  method (me: Self) Add(rhs: RHS) -> AddResult;
}

Here, everything in []s is generic by default but can be overridden (either to dynamic or template) with a keyword. And to have explicit parameters, we just nest []s inside of ()s.

We could also consider replacing []s with <>s if it would more closely resemble other languages.

---

Another alternative we looked at would instead of default-and-override, have consistent syntax everywhere. This of course comes at the cost of more syntax, and maybe less obvious syntax. The best suggested syntax during our brainstorming was to use :! for generic bindings (with ! indicating the compile-time nature), and template ...:! indicating a template binding (which is also compile-time, but further is known-before-typechecking). This might look like:

fn F[T: Type, U:! Type, N:! UInt]
    (p: T*, a: Array(U, N), M:! Int, template V:! Type) -> V;

interface Addable(RHS:! Type = Self) {
  let AddResult:! Type = Self;
  method (me: Self) Add(rhs: RHS) -> AddResult;
}

Here too, we could still keep moving towards <>s in the future if needed for familiarity.

---

Both of these are really designed as a contrast to the "pick a reasonable context-based default". There is a somewhat basic tradeoff in that space -- with good defaults, most of the time things "just work" and no extra ceremony is needed. For me, the amount of noise in the [] bracketed case starts to really show this.

I personally find the last of these examples to be my favorite. There are two reasons why this works better for me. First, I find the immediate reminder of what layer at which the name is bound (which @zygoloid nicely describes the four layers of) helpful as a reader rather than relying on the context. That's probably pretty subjective, varies from person to person, and I have no strong indication of the distribution of preference here. Other than I suspect that this isn't the biggest of such subjective things.

The other thing I like about it is that it somewhat pushes towards narrowly moving from "dynamic immutable" to "known-after-typechecking" or "known-before-typechecking". For me, that seems like a good thing. Moving from "dynamic mutable" to "dynamic immutable" seems like something we should encourage widely as it just restricts usage and enables useful implementations. But when we make it known at compile-time, we actually increases where we can use the name (in addition to narrowing how it binds). As such, encouraging it to be focused, to me, seems good.

---

Some orthogonal points that came up:

• This seems like a decision we can revisit if what we use ends up significantly unpopular. This includes using <>s but also other choices. I feel like we have broad alignment on the 4 layers we're targeting semantically here and the syntax choices aren't going to really paint us into a corner excessively. (I mean, changing syntax is always hard, but I don't think this really skews our interpretation dramatically along with the basic syntax aspects.)
• Getting the <>s here seems difficult to make effective at addressing the familiarity for users. If we really want to make this more familiar, we need to spell parameterized types as Vector<Int> or some such. And that is a much more expensive syntactic location to return to <>s. It is unfortunate that the most valuable places for <>s seem also to be the most expensive. Currently, I lean toward trying to avoid <>s and seeing if programmers can make that jump, but being willing to revisit as we get broader usage data.

Definitely interested in any other feedback on these options.

[josh11b]

Upon reflection, I don't think we need to distinguish the template and generic cases for declarations inside a function or struct body.

[josh11b]

Clarifying my last comment: inside a function or struct body, the declarations require an initializer. There is very little value in requiring the user to write different keywords depending on whether the initializer is a template or generic value. I propose instead that in those cases, the user can simply write

alias <name> = <generic or template constant value>;

[josh11b]

A concern I have with the :! syntax is that it is still easy to accidentally pass in a type dynamically (the T: Type clause in the example). What do you think of this rule, independent of which proposal we go with:

Any dynamic parameter used in a type position must be must mark its declaration with a dynamic keyword.

This I think both adds clarity for the reader ("alert! this type is being passed in dynamically") and helps the compiler prevent the writer from accidentally passing in types dynamically.

An alternative, depending on the resolution of #508 , would be to say:

Any dynamic type parameter must mark its declaration with a dynamic keyword.

This rule could be written more generally to non-parameters as well.

In cases where a parameter could match either a type or non-type value, the dynamic keyword would not be required. This rule would depend on requiring that we can distinguish types and non-type values generally, which includes:

• no values are self-typed
• tuple types would be written tuple (Int, String) instead of (Int, String)

[josh11b]

Having discussed this further, I'm going to say we don't urgently need dynamic types at all. We can definitely postpone those decisions until we actually are talking about the design space of dynamic types.

[chandlerc]

FWIW, I'm pretty happy initialling rejecting the use of dynamic parameters as types (and as early as possible) so that as @josh11b indicates we can follow-up with a more cohesive design there.

I agree we shouldn't make it easy or very subtle to accidentally get something that looks like a normal type or a generic but in reality has a dynamic/runtime implementation strategy with associated overhead. While that has really interesting use cases, it should be pretty clear in the source how you got there so that the wildly different tradeoff compared to generics is clear and unsurprising.

[chandlerc]

FWIW, the leads discussions have converged here around using :! for generic bindings.

The primary rationale for not pursuing the contextual-default with override keywords approach was that we had a lot of concerns around whether the defaults would be visually consistent and easily recognized by readers. One aspect that significantly amplified these concerns is that we don't see any really good ways to make the different contexts have punctuation that directly reflects their defaults. We looked at a bunch of the options here, and none were appealing. While that wasn't the only concern with the defaults, I think it was the most clear-cut issue that pushed us away and towards a more simple but more noisy syntactic approach like the :! binding.

One concern with :! was that this might make dynamic type parameters too easily to accidentally use. But as @josh11b commented, we can just reject that for now and revisit it with a clear design to make it unsurprising if/when we need to.

Another approach that has been considered is relying on the type itself more heavily. Discussions here have ranged from using the type to key a default with override keywords (much like the prior discussion around a default-with-override-keywords) to actually embedding the generic-ness into the type system itself such that it would be possible to perfectly forward generic-ness. These options are ones that seem like they would need some significant work to fully explore (especially how far if at all to go towards embedding in the type system). Doing this seems like the right thing to do if the :! marking becomes a source of significant ergonomic problems.

But for now, we suggest using the :! approach. We can revisit it in the future if needed pretty easily, and it is a very clear-cut and readily workable approach to follow for now.

[josh11b]

I am going to restate my understanding to make sure we are all on the same page and in agreement:

• A generic parameter is written name:! TypeOfName, like KeyType:! Hashable or Size:! UInt.
• A template parameter is written template name:! Type.
• A dynamic parameter is written name: Int without the !. If the expression to the right of the : evaluates to a type-of-type, the compiler will report an error, at least for the time being.

My understanding of the alternatives considered, from most preferred to least:

• name: T would be generic if T is a type-of-type and dynamic otherwise, generic name: T would always declare name to be a generic parameter of type T
• Every type has a bit indicating whether its values are generic, with that bit defaulting to generic for type-of-types and dynamic otherwise. A generic UInt would be declared like name: Generic(UInt). Concern: would have to figure out a story for doing things like returning a pair of a dynamic value and generic value.
• Every syntactic position would have a default of generic (like deduce function parameters in [...], interface parameters, type parameters) or dynamic (ordinary function parameters in (...)), and there would be a way to override that default with a keyword. Concern: using different kinds of brackets for different parameter lists, and the default wouldn't be consistent with the kind of bracket.

[chandlerc]

I am going to restate my understanding to make sure we are all on the same page and in agreement:

• A generic parameter is written name:! TypeOfName, like KeyType:! Hashable or Size:! UInt.
• A template parameter is written template name:! Type.
• A dynamic parameter is written name: Int without the !. If the expression to the right of the : evaluates to a type-of-type, the compiler will report an error, at least for the time being.

Yep!

My understanding of the alternatives considered, from most preferred to least:

• name: T would be generic if T is a type-of-type and dynamic otherwise, generic name: T would always declare name to be a generic parameter of type T
• Every type has a bit indicating whether its values are generic, with that bit defaulting to generic for type-of-types and dynamic otherwise. A generic UInt would be declared like name: Generic(UInt). Concern: would have to figure out a story for doing things like returning a pair of a dynamic value and generic value.

I think these two were both vaguely considered together, and also including other variations on these themes. But I don't want future readers to over index on the specific, concrete expressions here, but more the overall direction. I would include in any consideration of this direction whether or not generic-ness might be fundamentally part of the type system.

• Every syntactic position would have a default of generic (like deduce function parameters in [...], interface parameters, type parameters) or dynamic (ordinary function parameters in (...)), and there would be a way to override that default with a keyword. Concern: using different kinds of brackets for different parameter lists, and the default wouldn't be consistent with the kind of bracket.

[chandlerc]

With Josh's more concrete summary (thanks!) I'm going to close this out as resolved for now.

[m13253]

(Cross posting with #1425)

In my own opinion, the first time I saw [T:! Comparable & Movable], I thought ! means negation (“not comparable”).
If we use ! here, what symbol should we use, if in the future we need to implement, for type negation?

Have we discussed other symbols on the keyboard?

[T:# Comparable & Movable]
[T:% Comparable & Movable]
[T:^ Comparable & Movable]
[T:@ Comparable & Movable]

My personal reasons:

1. The # symbol is familiar to C programmers to indicate preprocessor directives. I think it makes sense to indicate compile-time constraints.
2. The % symbol is used in printf for placeholders, which also makes sense to indicate type placeholders.
3. The ^ symbol doesn't cause ambiguity since xor operator is binary and never occurs at the beginning.
4. I don't have specific reasons for @. But it looks good.

[YagaoDirac]

Let me copy my comment from the discussion thread. Link:
#1425

Let me give you a maybe final answer. In the code
fn Partition[/Notice the scope here/T:! Comparable & Movable](s: Slice(T))
-> i64 {
}
In the scope I emphasis, it's not possible to do any "logic not", and the type has to be figured out in compile time. Or, Carbon does runtime type deduction and create types on the fly????
If I guess the correct answer, then the "!" is simply not needed.
Even if you are to retain it, in your official example, you should write it like
fn Partition[T: !Comparable & Movable](s: Slice(T))
-> i64 {
}
The space should be in front of !.

[josh11b]

I think this discussion belongs better in #1425 than here, since this issue is old and closed.