On the road to understanding F-Bounded Polymorphism

Question

Before even getting to F-bounded Polymorphism there is construction that underpin it that i already have a hard time to understand.

trait Container[A]
trait Contained extends Container[Contained]

That construction which seem to be a trivial object oriented thing to do as it also exist in java, is already slightly puzzling me.

The issue is that when i see this trait Contained extends Container[Contained] it feels like an infinite type recursion to me.

When we define the type List even tho we have Cons[A](a:A, tail:List[A]), we also have case object Nil. So the recursion can end with Nil.

But here, i don't understand how we are not in an infinite recursion ? And why it works.

Can someone care to un-confused me about it ? Or if there is any documentation, blog, or whatever can explain how this works, or maybe is implemented.

Answer 1

I think your question is driven by confusion about the meaning of the term recursive type and the difference between kind, type, and class.

Lets first address the recursive type. Sometimes people mis-use recursive type to actually mean that this type corresponds to a data structure which recursively contains itself.

Following Tree is a recursive data strcuture but not a recursive type,

trait Tree[+A]

case class NonEmptyNode[A](value: A, left: Tree[A], right: Tree[A]) extends Tree[A]
case object EmptyNode extends Tree[Nothing]

Whereas, something like following is not a recursive data strcuture but it's a recursive type.

trait Mergeable[+A]

class A(val i: Int) extends Mergeable[A]

---

Interestingly, this is also related to the "importance" of some debated features of many modern languages - null and mutability.

So, lets say you were one of the designers of an Java language (back in early 2000's) and wanted to empower your users by adding support for generic programming.

You expect your users to be able to define generic contracts for their classes. For example, a contract for mergable classes.

public abstract class Mergable<A> {
    public A merge(A other)
}

Which is perfectly fine. But, this also opens the door for something like following

public abstract class HasBrother<A> {
    public A brother;
}

public class Human extends HasBrother<Human> {
    public Human brother;

    public Human(Human brother) {
        this.brother = brother;
    }
}

And this is where the problem starts. How will you ever be able to create an instance of Human ?

But they had an "awesome" solution for it. Just use null and keep the brother mutable (don't use final).

Human h1 = new Human(null);
Human h2 = new Human(null);

h1.brother = h2;
h2.brother = h1;

But scala.collection.immutable.List (and the Tree created above) data strcuture in Scala is very similar to this. And we don't like null and mutability.

This is possible in Scala only due to support for type parameter variance and the special bottom type called Nothing.

---

Now, lets talk about kind, type and class.

type can be thought as a defined contract.

class can be thought as the runtime implementation of the above contract.

kind is actually a type constructor. It needs a type parameter to construct the type.

Lets take following List as an example,

trait MyList[+A]

class MyNil extends MyList[Nothing]
class MyCons[A](val value: A, val tail: MyList[A]) extends MyList[A]

Note :: I am intentionally not using case object or case class to avoid the confusions caused by companion objects.

Here,

kind for MyList is F[+A].

kind for MyCons is F[+A].

kind for MyNil is A.

MyList has no corresponding type, but it has a corresponding class MyList.

MyCons has no corresponding type, but it has a corresponding class MyCons.

MyNil has a corresponding type MyNil and a corresponding class MyNil.

These corresponding type (available at only compile-time in most languages) and class (which exist at run-time) are bound to variables when they are created.

In val l: MyCons[Int] = new MyCons(1, new MyNil), l will have type MyCons[Int] and runtime class MyCons (which will be an instance of Class[_ <: MyCons[Int]]).

But, in val l: MyList[Int] = new MyCons(1, new MyNil), l will have type MyList[Int] and run-time class MyCons (which will be an instance of Class[_ <: MyList[Int]]).

---

Now, lets talk about the actual recursive types? We said earlier that a recursive type looks like following,

trait Mergeable[+A]

class Abc extends Mergeable[Abc]

But saying that the above is a recursive type is kind of wrong. It is more accurate to say that Mergeable is a kind which can result in recursive types.

val abc: Abc = new Abc
// type - Abc; class - Abc (Class[_ <: Abc])

val abc: Mergeable[Abc] = new Abc
// type - Mergeable[Abc]; class - Abc (Class[_ <: Mergeable[Abc]])

val abc: Mergeable[Mergeable[Abc]] = new Abc
// type - Mergeable[Mergeable[Abc]]; class - Abc (Class[_ <: Mergeable[Mergeable[Abc]]])

// ... and so on to Infinity

But, if we remove make that A invariant then this kind can not result in recursive types.

trait Mergeable[A]

class Abc extends Mergeable[Abc]

val abc: Abc = new Abc
// type - Abc; class - Abc (Class[_ <: Abc])

val abc: Mergeable[Abc] = new Abc
// type - Mergeable[Abc]; class - Abc (Class[_ <: Abc])

val abc: Mergeable[Mergeable[Abc]] = new Abc
//                                   ^
// error: type mismatch;
// found   : Abc
// required: Mergeable[Mergeable[Abc]]
// Note: Abc <: Mergeable[Abc] (and Abc <: Mergeable[Abc]), but trait Mergeable is invariant in type A.
// You may wish to define A as +A instead. (SLS 4.5)

---

These recursive types are different from F-Bound polymorphism.

The following is F-Bound but not recursive

trait Fruit[A <: Fruit[A]]

class Apple extends Fruit[Apple]

Here, kind of Fruit is F[A <: iw$Fruit[A]]. And we are adding an upper bound on A that says A has to be sub-type of Fruit[A] (which is an F). This is where the name F-Bound comes from.

The following is both F-Bound and recursive.

trait Fruit[+A <: Fruit[A]]

class Apple extends Fruit[Apple]

Here, kind of Fruit is F[+A <: iw$Fruit[A]].

Now, I can specify the type of any Apple at many recursive depths.

val f: Apple = new Apple
// type - Apple; class - Apple (Class[_ <: Apple])

val f: Fruit[Apple] = new Apple
// type - Fruit[Apple]; class - Apple (Class[_ <: Fruit[Apple]])

val f: Fruit[Fruit[Apple]] = new Apple
// type - Fruit[Fruit[Apple]]; class - Apple (Class[_ <: Fruite[Fruit[Apple]]])

// ... and so on to Infinity

Any language which does not support higher kinds can not have F-bound types.

---

Now, we can finally come to your doubt where you are thinking about the infinite loop.

Like we said earlier, a type can be thought to be like a label used to refer to a certain contract. So, that eager looping actually does not happen.

(I think) Scala compiler uses the implicit evidences (=:=, <:< constraints) for type comparisions. These evidences are lazily generated by the compiler by using the type bounds on type parameters. So, the compiler has the capabilty of recursilvely generating the evidences for type of any depth among these recursive types.

So, if you have code

val f: Fruit[Fruit[Fruit[Fruit[Apple]]]] = new Apple

Only then will the compiler require to "think" about this type Fruit[Fruit[Fruit[Fruit[Apple]]]] and it's comparision with type Apple.

It will then be able to generate evidence Apple <:< Fruit[Fruit[Fruit[Fruit[Apple]]]] by using the type relation Apple <: Fruit[Apple] (provided by inheritence) and Fruit[T2] <: Fruit[T1] for any T2 <: T1 (prvided by co-variance of A in kind Fruit[A]). And thus the above code will successfully type-check.

And in case, if this implicit evidence generation somehow encounters a loop, it actually will not be an issue because this is already taken care of in implicit resolution/generation rules.

If you look at the implicit resolution rules at https://www.scala-lang.org/files/archive/spec/2.13/07-implicits.html, you will find following

To prevent infinite expansions, such as the magic example above, the compiler keeps track of a stack of “open implicit types” for which implicit arguments are currently being searched. Whenever an implicit argument for type TT is searched, TT is added to the stack paired with the implicit definition which produces it, and whether it was required to satisfy a by-name implicit argument or not. The type is removed from the stack once the search for the implicit argument either definitely fails or succeeds. Everytime a type is about to be added to the stack, it is checked against existing entries which were produced by the same implicit definition and then,

• if it is equivalent to some type which is already on the stack and there is a by-name argument between that entry and the top of the stack. In this case the search for that type succeeds immediately and the implicit argument is compiled as a recursive reference to the found argument. That argument is added as an entry in the synthesized implicit dictionary if it has not already been added.
• otherwise if the core of the type dominates the core of a type already on the stack, then the implicit expansion is said to diverge and the search for that type fails immediately.
• otherwise it is added to the stack paired with the implicit definition which produces it. Implicit resolution continues with the implicit arguments of that definition (if any).

Here, the core type of TT is TT with aliases expanded, top-level type annotations and refinements removed, and occurrences of top-level existentially bound variables replaced by their upper bounds.

A core type TT dominates a type UU if TT is equivalent to UU, or if the top-level type constructors of TT and UU have a common element and TT is more complex than UU and the covering sets of TT and UU are equal.

So, the moment Scala compiler finds a loop in implicit constrant search, it will choose that constraint and avoid going into infinite loop.

Answer 2

Instead of thinking in terms of recursion perhaps looking at it purely from the perspective of quantification and bounds might help. For example let's interpret

trait Container[A]

as saying

trait Container[A >: Nothing <: Any]

that is, type constructor Container accepts all types A as argument. Since it takes all types, then it will also take our yet-to-be-defined type Contained, as whatever we define it must end up somewhere between Nothing and Any, hence, without thinking about recursion, we can admit the following is legal

trait Contained extends Container[Contained]

Next let's just tighten one of the bounds such that

trait Container[A <: Container[A]]

is interpreted as

trait Container[A >: Nothing <: Container[A]]

that is, type constructor Container accepts all types A between Nothing and Container[A] as argument. Now our yet-to-be-defined type A = Contained will indeed end up as a subtype of Container[A] since that is what we explicitly tell the compiler with

trait Contained extends Container[Contained]

so without thinking about recursion too much we can admit above is legal.

---

As a side note, regarding term "recursive type", as with many terms in computer science, I doubt there is a universally accepted definition what exactly it means. For example, paper F-Bounded Polymorphism for Object-Oriented Programming calls

class Point(val x: Double, val y: Double) {
  def move(t: (Double, Double)): Point
  def equal(p: Point): Boolean
}

a "recursive type" because Point declares computations that take and return Point values.

Answer 3

This is how I look at it:

1. First you're creating a type function Container[_] which can be applied to any type A. Note that A and Container[A] are two different types.

2. Next you're creating a new type Contained. At this point Contained is just a label.

3. Finally, you're telling Scala that Contained will extend another type: Container[Contained].

Using extends has several consequences, for example:

• You get an automatic conversion Contained => Container[Contained] for free