Name of technique for inferring type arguments of a type parameter?

Question

Setup: Let's assume we have a type called Iterator which has a type parameter Element:

interface Iterator<Element> {}

Then we have an interface Iterable which has one method which will return an Iterator.

// T has an upper bound of Iterator
interface Iterable<T: Iterator> {
    getIterator(): T
}

The issue with Iterator being generic is that we have to supply it with type arguments.

One idea to solve this is to "infer" the type of the iterator. The following pseudo-code expresses the idea that there is a type variable Element which is inferred to be the type argument to Iterator:

interface <Element> Iterable<T: Iterator<Element>> {
    getIterator(): T
}

And then we use it somewhere like this:

class Vec<Element> implements Iterable<VecIterator<Element>> {/*...*/}

This definition of Iterable doesn' t use Element anywhere else in its definition but my real use-case does. Certain functions which use Iterable also need to be able to constrain their parameters to accept Iterables which return only certain kinds of iterators, such as a bidirectional iterator, which is why the iterator returned is parameterized instead of just the element type.

---

Questions:

• Is there an established name for these inferred type variables? What about the technique as a whole? Not knowing specific nomenclature has made it difficult to search for this examples of this in the wild or learn about language specific features.
• Not all languages with generics have this technique; are there names for similar techniques in these languages?

Answer 1

I don't know if there's a particular term for this problem, but there are three general classes of solutions:

• avoid concrete types in favour of dynamic dispatch
• allow placeholder type parameters in type constraints
• avoid type parameters by using associated types / type families

And of course the default solution: keep spelling out all those parameters.

Avoid concrete types.

You have defined an Iterable interface as:

interface <Element> Iterable<T: Iterator<Element>> {
    getIterator(): T
}

This gives users of the interface maximum power because they get the exact concrete type T of the iterator. This also allows a compiler to apply more optimizations such as inlining.

However, if Iterator<E> is a dynamically dispatched interface then knowing the concrete type is not necessary. This is e.g. the solution that Java uses. The interface would then be written as:

interface Iterable<Element> {
    getIterator(): Iterator<Element>
}

An interesting variation of this is Rust's impl Trait syntax which lets you declare the function with an abstract return type, but knowing that the concrete type will be known at the call site (thus allowing optimizations). This behaves similarly to an implicit type parameter.

Allow placeholder type parameters.

The Iterable interface does not need to know about the element type, so it might be possible to write this as:

interface Iterable<T: Iterator<_>> {
    getIterator(): T
}

Where T: Iterator<_> expresses the constraint “T is any iterator, regardless of element type”. More rigorously, we can express this as: “there exists some type Element so that T is an Iterator<Element>”, without having to know any concrete type for Element. This means that the type-expression Iterator<_> does not describe an actual type, and can only be used as a type constraint.

Use type families/associated types.

E.g. in C++, a type may have type members. This is commonly used throughout the standard library, e.g. std::vector::value_type. This doesn't really solve the type parameter problem in all scenarios, but since a type may refer to other types, a single type parameter can describe a whole family of related types.

Let's define:

interface Iterator {
  type ElementType
  fn next(): ElementType
}

interface Iterable {
  type IteratorType: Iterator
  fn getIterator(): IteratorType
}

Then:

class Vec<Element> implement Iterable {
  type IteratorType = VecIterator<Element>
  fn getIterator(): IteratorType { ... }
}

class VecIterator<T> implements Iterator {
  type ElementType = T
  fn next(): ElementType { ... }
}

This looks very flexible, but note that this can make it more difficult to express type constraints. E.g. as written Iterable does not enforce any iterator element type, and we might want to declare interface Iterator<T> instead. And you are now dealing with a fairly complex type calculus. It is very easy to accidentally make such a type system undecidable (or maybe it already is?).

Note that associated types can be very convenient as defaults for type parameters. E.g. assuming that the Iterable interface needs a separate type parameter for the element type which is usually but not always the same as the iterator element type, and that we have placeholder type parameters, it might be possible to say:

interface Iterable<T: Iterator<_>, Element = T::Element> {
  ...
}

However, that is just a language ergonomics feature, and does not make the language more powerful.

---

Type systems are difficult, so it's good to take a look at what does and does not work in other languages.

E.g. consider reading the Advanced Traits chapter in the Rust Book, which discusses associated types. But do note that some points in favor of associated types instead of generics only apply there because the language does not feature subtyping and each trait can only be implemented at most once per type. I.e. Rust traits are not Java-like interfaces.

Other interesting type systems include Haskell with various language extensions. OCaml modules/functors are a comparatively plain version of type families, without directly intermingling them with objects or parameterized types. Java is notable for the limitations in its type system, e.g. generics with type erasure, and no generics over value types. C# is very Java-like but manages to avoid most of these limitations, at the cost of increased implementation complexity. Scala tries to integrate C#-style generics with Haskell-style typeclasses on top of the Java platform. C++'s deceptively simple templates are well-studied but are unlike most generics implementations.

It's also worth looking at the standard libraries of these languages (especially standard library collections like lists or hash tables) to see which patterns are commonly used. E.g. C++ has a complex system of different iterator capabilities, and Scala encodes fine-grained collection capabilities as traits. The Java standard library interfaces are sometimes unsound, e.g. Iterator#remove(), but can use nested classes as a kind of associated type (e.g. Map.Entry).

Answer 2

You might be looking for forward and backward inference. Try searching https://github.com/google/closure-compiler for these terms, in particular check out TypeInference.java:

 /**
   * We only do forward type inference. We do not do full backwards type inference.
   *
   * <p>In other words, if we have, <code>
   * var x = f();
   * g(x);
   * </code> a forward type-inference engine would try to figure out the type of "x" from the return
   * type of "f". A backwards type-inference engine would try to figure out the type of "x" from the
   * parameter type of "g".
   *
   * <p>However, there are a few special syntactic forms where we do some some half-assed backwards
   * type-inference, because programmers expect it in this day and age. To take an example from
   * Java, <code>
   * List<String> x = Lists.newArrayList();
   * </code> The Java compiler will be able to infer the generic type of the List returned by
   * newArrayList().
   *
   * <p>In much the same way, we do some special-case backwards inference for JS. Those cases are
   * enumerated here.
   */
private void backwardsInferenceFromCallSite(Node n, FunctionType fnType, FlowScope scope) {}

I'm not sure I fully get the question but my understanding is that when you infer the type, like generic type, from the type of an argument passed to function during data-flow analysis, it would be backward inference.