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

24 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
  14. Yes i agree with you. I have used this app. Its really very helpful for me. I am very thankful for this. It is such a great design of post, which you have shared. I thumbs up this post. Keep it up! z medi spa

    ReplyDelete
  15. All things considered, winning does not mean you will have the capacity to win back the majority of the misfortunes.crossbow

    ReplyDelete
  16. Now pass CompTIA SY0-501 Exam on the first attempt, because Certssolution is providing most valid and updated CompTIA SY0-501 Exam Dumps with 100% money back guarantee. We are sure after using their exam practice materials you will pass your exam on the first try.Host Regions LTD

    ReplyDelete
  17. I loved this post. You describe this topic wonderfully. When hiring home contractors it is critical for pick a trusted name in construction. Experienced and efficient staff should shoot for excellence and seriously consider every detail in your home.Cape Verde Accommodation Hotel

    ReplyDelete
  18. Mind-blowing went amazed with the content posted. Containing the information in its unique format with fully loaded valid info, which ultimately grabs the folks to go through its content. Hope you to keep up maintaining the standards in posting the content further too.witneycouriers

    ReplyDelete
  19. Yes i agree with you. I have used this app. Its really very helpful for me. I am very thankful for this. It is such a great design of post, which you have shared. I thumbs up this post. Keep it up!การ์ดแต่งงาน

    ReplyDelete
  20. I recently came across your article and have been reading along. I want to express my admiration of your writing skill and ability to make readers read from the beginning to the end. I would like to read newer posts and to share my thoughts with you. witneycouriers

    ReplyDelete
  21. 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!Welcome to Jason's Holidays

    ReplyDelete
  22. I come across a blog that’s both equally educative and engaging, and let me tell you, you have hit the nail on the head. The issue is something not enough people are speaking intelligently about. I’m very happy I stumbled across this in my search for something relating to this.Cloud Consulting Services

    ReplyDelete