Target audience: Intermediate
Estimated reading time: 4'
This post introduces and describes the concept of bounded polymorphism using self-referential type constraint.
Introduction
F-Bounded Type polymorphism or Bounded Quantification Polymorphism is parametric type polymorphism that constrains the subtypes to themselves using bounds.
Let's consider the following "classification" problem:
Let's consider the following "classification" problem:
How can we guarantee that the SharpPencils bucket contains only sharp pencils, not small pencils or erasers?
Type polymorphism
The first attempt to solve the problem is to rely on parametric type polymorphism. To this purpose, we create a Pencils trait sub-classed by as a bucket for sharp pencils, SharpPencils and a bucket for small pencils, SmallPencils.
For the sake of simplification, we assume that Pencils defines only 2 methods: add (line 4) and pop (line 5) pencils.
For the sake of simplification, we assume that Pencils defines only 2 methods: add (line 4) and pop (line 5) pencils.
1
2
3
4
5
6
7
8
9
| trait Pencils[T] {
private lazy val content = new mutable.ListBuffer[T]
def add(t: T): Unit = content.append(t)
def pop: List[T] = (content -= data.head).toList
}
class SharpPencils extends Pencils[SharpPencils]
class SmallPencils extends Pencils[SmallPencils]
|
This implementation does not guarantee that SharpPencils is the only bucket that contains the sharp pencils (line 8). Another bucket OtherPencils can be created with sharp pencils, too (line 9).
1
| class OtherPencils extends Pencils[SharpPencils]
|
The solution is to specify constraints (or bounds) on the type of elements contained in each bucket.
Bounded polymorphism
The goal is to make sure that the bucket of specific type (or containing a specific type of pencils). The first step is to make sure that a bucket does not contain other items than a Pencils. This is accomplished by using the recursive (or F-Bound) type polymorphism
trait A[T]<: ...="" a="" pre="">
The class Pencils is parameterized with one of its sub-type (line 1). None of the existing methods need to change.
1
2
3
4
5
6
| trait Pencils[T <: Pencils[T]] {
private lazy val content = new mutable.ListBuffer[T]
def add(t: T): Unit = content.append(t)
def pop: List[T] = (content -= data.head).toList
}
|
This implementation resolve the limitation raised in the previous paragraph. However there is nothing that prevent SharpPencils to contain an eraser or small pencils and SmallPencils to contain sharp pencils, as illustrated in the next code snippet.
// Won't compile!
class SharpPencils extends Pencils[Eraser]
// The following code compiles!
class SharpPencils extends Pencils[SmallPencils]
class SmallPencils extends Pencils[SharpPencils]
Self-referential polymorphism
As a matter of fact, the most effective constraint on a inherited type is the self reference (line 2) that list the type allows for the method to execute.
1
2
3
4
5
6
7
8
9
| trait Pencils[T <: Pencils[T]] {
self: =>
private lazy val content = new ListBuffer[T]
def add(t: T): Unit = content.append(t)
def pop: List[T] = (content -= data.head).toList
}
// The following code fails to compile!
class SharpPencils extends Pencils[SmallPencils]
|
The declaration of SharpPencils as containing small pencils (line 9) fails to compile because it violates the self-referential type restriction.
References
Getting F-Bounded Polymorphism into Shape B. Greenman, F. Muehlboeck, R. Tate - Cornell University
