Wednesday, March 4, 2015

F-bounded Type Polymorphism

Target audience: Intermediate
Estimated reading time: 15'


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:

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.

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

15 comments:

  1. Nice to be visiting your blog again, it has been months for me. Well this article that i've been waited for so long. I need this article to complete my assignment in the college, and it has same topic with your article. Thanks, great share. Assam Ration Card Details

    ReplyDelete
  2. Deep learning Domain is an AI function that mimics the workings of the human brain in processing data for use in detecting objects, recognizing speech, translating languages, and making decisions. IEEE Deep learning domain Deep Learning Projects for Final Year
    mimics the workings of the human brain in processing data for use in detecting objects, recognizing speech, translating languages, and making decisions.

    Smaller than expected IEEE Final Year project centers ground for all fragments of CSE & IT engineers hoping to assemble. Final Year Projects for CSE It gives you tips and rules that is progressively critical to consider while choosing any final year project point.

    Spring Framework has already made serious inroads as an integrated technology stack for building user-facing applications. Spring Framework Corporate TRaining the authors explore the idea of using Java in Big Data platforms.
    Specifically, Spring Framework provides various tasks are geared around preparing data for further analysis and visualization. Spring Training in Chennai


    The Angular Training covers a wide range of topics including Components, Angular Directives, Angular Services, Pipes, security fundamentals, Routing, and Angular programmability. The new Angular TRaining will lay the foundation you need to specialise in Single Page Application developer. Angular Training

    ReplyDelete
  3. 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.

    ReplyDelete
  4. my Instagram followers and I’m sure they’ll enjoy it as well. It’s an amazing lighting idea.I wanna make it your idea.
    I think this amazing lighting idea could be beautified our Christmas Day.fintech software solutions

    ReplyDelete
  5. Fantastic post! Please keep sharing. I know of a roofing company if you are looking for Gamr Please get in touch! Thanks, have a good day.Game
    Game
    Game

    ReplyDelete
  6. my Instagram followers and I’m sure they’ll enjoy it as well. It’s an amazing lighting idea. I wanna make it your idea. I think this amazing lighting idea could be beautified our Christmas Day. travel

    ReplyDelete
  7. There is a possibility that the plants will be washed later in the microwave oven, do not use staples, paper clips, or other metal objects. Sometimes additional information is required to provide complete differentiation, as well as special staining techniques.Health

    ReplyDelete
  8. This web site has sports lottery contents that are run in Korea. It predicts the results of the game as well as accurate analysis of various popular sport games. It mainly provides information about popular sports games such as basketball, baseball, and soccer. Sheet mask material

    ReplyDelete
  9. There is a possibility that the plants will be washed later in the microwave oven, do not use staples, paper clips, or other metal objects. Sometimes additional information is required to provide complete differentiation, as well as special staining techniques.Monster Truck

    ReplyDelete
  10. Fantastic post! Please keep sharing. I know of a roofing company if you are looking for Gamr Please get in touch! Thanks, have a good day.visit this link

    ReplyDelete
  11. Wow! This can be one particular of the most useful blogs We’ve ever arrive across on this subject. Basically Magnificent. I’m also an expert in this topic so I can understand your hard work. gaminglight

    ReplyDelete
  12. There is a possibility that the plants will be washed later in the microwave oven, do not use staples, paper clips, or other metal objects. Sometimes additional information is required to provide complete differentiation, as well as special staining techniques.Budapest

    ReplyDelete
  13. I have read all the comments and suggestions posted by the visitors for this article are very fine,We will wait for your next article so only.Thanks!
    Himalayan Persian Cat

    ReplyDelete