Should nested types capture type parameters?

Should nested types capture type parameters?

Yes No
type Map(K,V) {
counters: List(Count)
elements: List(Pair)

type Count {
key: K
count: Int
}
type Pair {
key: K
value: V
}
}

let c: Map(Int,Int).Count = ...
let e: Map(Int,Int).Entry = ...

type Map(K,V) {
counters: List(Count(K))
elements: List(Pair(K,V))

type Count(K) {
key: K
count: Int
}
type Pair(K,V) {
key: K
value: V
}
}

let c: Map.Count(Int) = ...
let e: Map.Entry(Int,Int) = ...


Some observations:

• "Yes" is more concise in the type definitions.
• "No" is more concise when the type parameters aren't necessary (second-to-last line).
• "Yes" feels more natural to me right now, whatever that means.
• Java chose "No".
• Maybe a nested type can opt-in to capture?

I'm working on a data description language and can't decide which way to go on this. I'm hoping someone here has information or opinions that might tip me one way or the other.

Comment viewing options

Java chose "yes and no"

Should nested types capture type parameters? ... Java chose "No"
Java's non-static inner classes do capture type variables. The following is legal.
class Map<K,V> {
class Pair {
K key = null;
V value = null;
}

// etc
}

On the other hand, Java's static inner classes don't capture type variables. Their nesting is purely for name space purposes so they don't capture anything. The difference gives a hint to answering your question. What are the semantics of your nesting? Does each individual Map have its own unique type of Pair, or is the nesting more shallow than that?

That helps.

Ah, that's a good way of looking at it. My nested types are like Java's "static" inner classes. (The language is a simple tree-structured data definition language, like JSON, so I don't think it even has enough expressive power for a non-static nesting to even be useful.)

However, I neglected to mention a feature of the language that makes the "No" choice a little messier. Sometimes, types are implicitly defined. For example:

type Thing(K,V) {
Leaders: {    // type is specified inline
Key1: K
Key2: K
}
OtherKeys: List(K)
OtherValues: List(V)
}


This desugars into:

type Thing(K,V) {
OtherKeys: List(K)
OtherValues: List(V)

// compiler automatically generates this
Key1: K
Key2: K
}
}


I like that the type specified inline automatically captures the type environment. So when desugaring, the generated type definition needs to be type-parameterized. Not a huge deal, but this is where the type-capturing option comes out a little cleaner.

I don't particularly have

I don't particularly have any technical reason for preferring one over the other, but the latter uses don't even make sense to me. Map isn't a type by itself, so Map.Count doesn't make sense (to me.) The way it is written suggests that it should be Map(Int,Int).Count(Int) and that Map(Int,Int).Count(Bool) should be just as legal. Note, that this is what you get if you view the if the answer was Yes to each of them. So personally, the No response is completely nonsensical to me and the Yes response is the correct one.

my "type" is more of a "type" + "namespace"

I do agree that the capturing option is more intuitive given the syntax I used. But another way to look at it is that my "type" construct actually defines a type and a namespace of the same name. So:

type Map(K,V) {
elements: List(Pair(K,V))
type Pair(K,V) {
key: K
value: V
}
}


Could be seen as a condensed form of:

name Map {
type (K,V) {
elements: List(Pair(K,V))
}
name Pair {
type (K,V) {
key: K
value: V
}
}
}


Again, I agree the capturing option is conceptually simpler. But for many uses, it ends up being slightly redundant (i.e. when the nested type doesn't use the outer type parameters).

the nested type doesn't use the outer type parameters

Is that not similar to the problem of variables captured by a closure? You want to capture only the variables used in the closure.

Closures can't be "built" from the outside

Yes. For references to Count within Map, it works like variable capture in closures. No matter how many type parameters are actually captured, they are all currently in scope and so they don't show up in Count's type parameter list.

But for references to Count from outside of Map, those captured type parameters are no longer in scope and thus must be specified. One way of doing this is to be uniform and plug in type arguments for the outer type: "Map(Int,Int).Count".

The disadvantage of doing that is that we must provide arguments for all of Map's type parameters even though Count doesn't use all of them. That's why something like something like "Map.Count(Int)" is attractive.

Yes personally

1) In the No-version, you end up with the confusing possibility of declaring incompatible types (or was that your intention) e.g. per your example:
 let c: Map.Count(String) = ... let e: Map.Entry(Int,Int) = ... 
or perhaps:
 let c: Map(Int,Int).Count(String) = ... 

2) In the No-version, within the inner classes each type parameter has been declared twice. If the V in type Map(K,V) is exactly the same as the V in type Pair(K,V), then why redeclare it in the inner class? If they can be different then I would think that would leave scope for mistakes. I prefer the Yes-version for having only one place where the type parameter is "defined".

3) The Yes-version does just feel better to me :)

The only corner case might be if you want to allow the user to use a subclass for the inner type e.g.
 type Map(K,V) { type Count(J <: K) { key: J count: Int } ... 
Finally, is "Entry" a synonym for "Pair"?