Bounded quantification

This article is about bounded quantification in type theory. For bounded quantification in mathematical logic, see Bounded quantifier.

In type theory, bounded quantification (also bounded polymorphism or constrained genericity) refers to universal or existential quantifiers which are restricted ("bounded") to range only over the subtypes of a particular type. Bounded quantification is an interaction of parametric polymorphism with subtyping. Bounded quantification has traditionally been studied in the functional setting of System F<:, but is available in modern object-oriented languages supporting parametric polymorphism (generics) such as Java, C# and Scala.

Overview

The purpose of bounded quantification is to allow for polymorphic functions to depend on some specific behaviour of objects instead of type inheritance. It assumes a record-based model for object classes, where every class member is a record element and all class members are named functions. Object attributes are represented as functions that take no argument and return an object. The specific behaviour is then some function name along with the types of the arguments and the return type. Bounded quantification allows to considers all objects with such a function. An example would be a polymorphic min function that considers all objects that are comparable to each other.

F-bounded quantification

F-bounded quantification or recursively bounded quantification, introduced in 1989, allows for more precise typing of functions that are applied on recursive types. A recursive type is one that includes a function that uses it as a type for some argument or its return value.[1]

Example

This kind of type constrain can be expressed in Java with a generic interface. The following example demonstrates how to describe types that can be compared to each other and use this as typing information in polymorphic functions. The Test.min function uses simple bounded quantification and does not preserve the type of the assigned types, in contrast with the Test.Fmin function which uses F-bounded quantification.

In mathematical notation, the types of the two functions are

min: ∀ T, ∀ S ⊆ {compareTo: T → int}. S → S → S
minf: ∀ T ⊆ Comparable[T]. T → T → T

where

Comparable[T] = {compareTo: T → int}
interface Comparable<T> {
  public int compareTo(T other);
}

class Integer implements Comparable<Integer> {
  @Override
  public int compareTo(Integer other) {
    //...
  }
}

class String implements Comparable<String> {
  @Override
  public int compareTo(String other) {
    //...
  }
}

class Test {
  public static void main(String[] args) {
    Comparable<String> a = min("cat", "dog");
    Comparable<Integer> b = min(new Integer(10), new Integer(3));
    String str = Fmin("cat", "dog");
    Integer i = Fmin(new Integer(10), new Integer(3));
  }
  public static <T, S extends Comparable<T>> S min(S a, S b) {
    if (a.compareTo(b) <= 0)
      return a;
    else
      return b;
  }
  public static <T extends Comparable<T>> T Fmin(T a, T b) {
    if (a.compareTo(b) <= 0)
      return a;
    else
      return b;
  }
}

See also

References

External links

Notes

  1. ↑ F-bounded polymorphism for object-oriented programming. Canning, Cook, Hill, Olthof and Mitchell. http://dl.acm.org/citation.cfm?id=99392
This article is issued from Wikipedia - version of the Sunday, March 20, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.