Difference between type variable and type parameter in the Wild FJ paper?

In a method, foo(int x), the following terminology is used:

• The method has 1 formal parameter (int x), though that is often shortened to parameter, leading to potential confusion. int is the parameter type and x is the parameter name.

• x is a parameter variable, though that is often shortened to parameter, leading to potential confusion.

• In a call, foo(5), the value is called an argument, though that is often called a parameter value, shortened to parameter, leading to potential confusion. When clarification is needed, it is called an actual parameter.

As you can see, the shorthand use of the word parameter can mean int x, x, or 5, depending on context.

For generic types, Foo<X extends Number>, a similar naming is used:

• The type has 1 type parameter, where extends Number is the type bound, and X is the type identifier.

• X is a type variable.

• When used, Foo<Integer>, the Integer part is called a type argument. The type argument can be a wildcard.

Do not confuse a methods parameter type with a generics type parameter.

As you can see, your conclusion that ""type variable" is used to refer to wildcards specifically" is incorrect. Type variable refers to the type parameters name, regardless of whether the type parameter is bound or not.

The "actual" type of the type variable, i.e. the type argument, may or may not be a wildcard, since that is specified in the use of the generic type, not in the definition of the generic type.

A generics type variable is only referenced in the definition of the generic type, similar to how a methods parameter variable is only referenced in the body of the method.

A full text search reveals that "type variable" first occurs in section 2:

As long as the element type is known at the call site, this may be expressed with plain generics using apolymorphic method with a dummy type variable:

〈X〉void m1(List〈X〉list) { ... }

As you can see, this example doesn't use wildcards at all, contradicting your assumption that "type variable is used to refer to wildcards specifically".

So, what are type variables? Since the term is not defined in the paper itself, it must be defined in one of its references.

But which one? Since it is customary to include references before the terms are first used, the reference must be in the introduction section, and from context, this sentence looks most promising:

Parametric polymorphism — also known as genericity or generics — originated in the world offunctional programming [21]

So we are likely to find the answer in

[21] Robin Milner. A theory of type polymorphism in programming. Journal of Computer and System Sciences, 17:348–375, August 1978.

Googling the title of that paper finds a PDF with the full text, and indeed, that classic paper contains numerous examples for type variables, such as:

EXAMPLE 1.

Mapping a function over a list.

let rec map(f, m) = if null (m) then nil 
                    else cons (f(hd(m)), map (f, d(m)))

Intuitively, the function map so declared takes a function from things of one sort to things of another sort, and a list of things of the first sort, and produces a list of things of the second sort. So we say that map has type

((α → β) x α list) → β list

where α, β are type variables.

So, a type variable is just a variable (in the mathematical sense) that will contain a type. A type variable can be introduced by a type parameter, but as Milner shows, type variables can also be introduced by other means. (Notice how α and β do not show up in the definition of map?)

Something similar happens when the Java compiler performs wildcard capture. For instance, if we write:

List<?> sourceList = ...;
List<?> targetList = ...;
targetList.add(sourceList.get(0));

the compiler says:

The method add(capture#1-of ?) in the type List<capture#1-of ?> is not applicable for the arguments (capture#2-of ?)

As we can see, when reasoning about wildcard types, the compiler "captures" the value of wildcards into fresh type variables such as capture#1-of ?. Unlike type variables introduced by type parameters, these type variables never show up in the source code.

And that is why, when discussing wildcard capture, the Wild FJ paper speaks about type variables not introduced by type parameters.