1.1 Polymorphism

Almost everything (except variables) in Felix can be polymorphic, that is, parametrised by a list of types. Here is a simple example:

  fun diag[T,U] (x:T, y:U)=> y,x;
  a := 1,"Hi";
  println$ a, diag a, diag (diag a);

C bindings can be polymorphic too:

  type vector[T] = "::std::vector<?1>";
  proc push_back[T]: vector[T] * T = "$1.push_back($2)";

In the C code ?1, ?2 represent the first and second type variables.

1.1.1 Overloading

Polymorphic functions and non-polymorphic function can be overloaded. Overload resolution proceeds by a similar algorithm to C++.

Felix first finds all the candidates. It then proceeds to compare each signature with each other signature. If one is a proper specialisation of another, the more general case is thrown out. An ambiguity exists if this process leaves more than one candidate.

  fun f[T,V] (x:T, y:V)=>y,x;               //1
  fun f[T] (x:T, y:T)=>y,x;                 //2
  fun f[A,B,C] (x: A * B, y : B *C) => y,x; //3

Here, 2 and 3 are more specialised than 1, however neither is more specialised than the other.

If the call is to a higher order function and the call applies to several arguments in turn, all the available arguments are used in an attempt to remove an ambiguity.

1.2 Advanced Type Calculus

Felix type system has several advanced features.

1.2.1 Type functions

In Felix you can specify a function which accepts and returns types:

  typefun diag1 (x:TYPE) : TYPE => x * x;
  var b: diag1 int = 1,2; // OK

Here the name TYPE is a meta-type or kind representing all types.

A type function is similar to a type index, however functions cannot be overloaded based on calculated types, unless the applications are resolved before overloading is performed.

  typedef diag2[T] = T * T;

is similar to the type function diag1, but diag2 is a polymorphic type, which is not quite the same. Polymorphic type allow overloading, and more generally unification, to deduce the index type. This cannot be done for type functions. But type functions are more general because they can be named "unapplied" and later applied. And, they can be anonymous too: type lambdas.

The syntax for type functions is the same as for ordinary functions. Type functions can also be overloaded against each other.

1.2.2 Type matches

Similar to ordinary matches, Felix has type matches:

  typedef T = int;
  val x : 
    typematch T with 
    | int => int * int  
    | _ => long 
    endmatch 
    = 1,2
  ;

A contrived example, but see the next section for a real use!

1.2.3 Type Calculus: examples

Consider the C integral promotion rules. How would we represent this in Felix?

With a type function and match of course! This is from library file int.flx:

  typefun integral_promotion: TYPE -> TYPE =
    | tiny => int
    | utiny => int
    | short => int
    | ushort => int
    | int => int
    | uint => uint
    | long => long
    | ulong => ulong
    | vlong => vlong
    | uvlong => uvlong
  ;

Note here the same short hand as for function is used, the functional form is equivalent to a function containing a match on its only argument.

The type function integral_promotion defines how each C type is promoted according to ISO C rules.

Now why would we want that? Well consider, we would like to write this code:

  fun add[T in ints, U in ints]: T * U -> arithmax (T,U) = "$1+$2";

which can add up any Felix integers the same way as C does, arithmetic promotions and all .. but what is the return type? It is the largest of the two argument types. But how can we calculate that?

Here's the answer: arithmax.flx

This file is generated by the configure script for Felix because the rule is actually platform dependent!

You can see here, we have used the previously discussed integral_promotion function to reduce the number of cases in the typematch by removing the smaller types {tiny, utiny, short, ushort} .. although the main reason is that this is how ISO C specifies the calculation be done.