9.2. Parametric Polymorphism

The Orc type system supports parametric polymorphism: functions, sites, and types may accept type parameters. This is the same theory that underlies Java's generics.

Parametric polymorphism occurs in three contexts: the declaration of a parametric type, the definition of a polymorphic function, or a call to a polymorphic function or site.

9.2.1. Parametric types

[50]TypeApplication::= Type TypeArguments  

Orc has a special form of type, called a type application, which applies a type operator to a sequence of type arguments. This permits the instantiation of multiple variations of the same type. The simplest example of this feature is the List type operator. For example, the list value [1,2,3] has the type List[Integer], whereas the list value [true, false] has the type List[Boolean].

Lists are not the only parametric type. The standard library includes other parametric types, such as Option, Channel, and Cell. A type alias may have type parameters, thus defining a parametric type. Similarly, a datatype declaration may also have type parameters.

9.2.2. Parametric functions

A function may be polymorphic, taking one or more type parameters. Such functions can be operate generically over different types. Consider the following definition of the append function, which appends two lists:

def append[T](List[T], List[T]) :: List[T]
def append([], l) = l
def append(h::t, l) = h::append(t,l)

The function append has a type parameter T in its signature. The type T is the type of the elements in the lists being appended. Notice that both argument lists must contain the same type of elements. The resulting list contains elements of that same type.

9.2.3. Polymorphic calls

When calling the append function, in addition to providing its normal arguments, we must also provide its type argument:

append[Integer]([1,2,3], [4,5])

However, it would be very burdensome and verbose to provide type arguments to all such calls. Fortunately, in most cases, the type checker can infer the correct type arguments, in the same way that it infers the correct type for many expressions without any additional information. So in this case, we can simply write:

append([1,2,3], [4,5])

and the typechecker infers that the parameter T is Integer, since both argument lists are of type List[Integer]. For a more thorough explanation of how this inference occurs, please refer to the typing algorithm on which the Orc typechecker is based.

Inference of type arguments will always fail on certain kinds of calls, because the typechecker does not have enough information to infer the correct type. The most common case is a site call which constructs a parametric type without taking any arguments. For example, the call Channel() will never typecheck, since there is no way for the typechecker to know what type of elements the channel should contain. In other languages such as ML, the typechecker might be able to infer this information from the rest of the program, but Orc's typechecker is based on local type inference, which must find the information locally, such as from the types of the arguments. So, to construct a channel that will contain numbers, a type argument must be given: Channel[Number]().

9.2.4. Related Links

Related Tutorial Sections