Fun with units of measure

Since the CTP, F# has a nice feature in its type system, called units of measure. Briefly, it allows you to specify a unit with any float, and the type system checks that your uses of units are consistent. For example, you can't add a float<m> to a float<ft>, which results in, among other things, less crashes of spacecraft on Mars. I won't go into details, if you're interested but don't know what I'm talking about, read Andrew Kennedy's blog before you continue.

But anyway, using units for, well, tracking units is kind of boring - type systems are made to be abused after all. So here's my attempt to use units of measure to track the lengths of vectors, so that the compiler will for example detect that you try to add two vectors of unequal length.

How can this be achieved? The basic idea is to encode the length of the vector as an exponent to a unit, that is kept in the 'safe vector' type as a unit of measure parameter. To do this, we first need a unit of measure and a 'safe vector' type that uses it:

[<Measure>] type length

type SVec<'a,[<Measure>]'l> = 
    SVec of list<'a> * float<'l>

 

So, SVec is a vector containing elements of type 'a, and with a length encoded in 'l. We'll use the float to both encode the length of the string as a value and as a type; the idea is that SVec ([1,5], 2.0) has type SVec<int, length ^2>. Let's define some utility functions to make type safe vectors:

let nil = SVec ([],0.0)
let cons elem (SVec (xs,un:float<'l>)) : SVec<_,'l length> = 
        SVec (elem::xs, (un + 1.0<_>) * 1.0<length>)
let (=+=) = cons

let removeUnits f = f |> box |> unbox<float> 

let length (SVec (_,c)) = removeUnits c |> int 
let from_list xs (l:float<'u>) : SVec<'a,'u> = 
    if List.length xs <> int (removeUnits l) then raise <| new ArgumentException("Actual length of list is not equal to given length")
    else SVec (xs,l)

'nil' constructs an empty vector. It has type SVec<'a>,1>, denoting a list with zero elements. 'cons' adds an element to the front of the vector. To do this, it needs to do three things:

1. Add the actual element to the front of the list
2. Update the length  value by adding 1
3. Update the length type by multiplying with 1.0<length>

To get the length of a vector, we return the unit value, stripping of all static unit types. I tried this first by dividing by 1.0<'u>,  but it appears that you can't use a type argument as a unit of measure with a constant value. I'm not exactly sure why.

'from_list' takes a list and turns it into a safe vector. You need to provide a list, with the length of the list correctly encoded in both value and type. The value is tested, the type is not: as far as I can see, this is impossible to check.

Let's make a safe vector:

let l = 3 =+= (2 =+= (1 =+= nil))

The type of l is SVec<int,length^3>. Now we can define type-safe multiplication and addition:

type SVec<'a,[<Measure>]'l> = 
    SVec of list<'a> * float<'l>
        static member (+) (SVec (xs, l1): SVec<_,'l>, SVec (ys, l2): SVec<_,'l>) = 
            SVec (zip xs ys |> map (fun (x,y) -> x + y), l1)
        static member (*) (SVec (xs, l1) : SVec<_,'l>, SVec (ys, l2): SVec<_,'l>)=
            zip xs ys |> sum_by (fun (x,y) -> x*y)    

The interesting part is of course not the implementation, but the types: they statically enforce that when you add or multiply two vectors, they have the same length. So:

let sum = l + l

will typecheck fine, but

let badsum = l + nil

will give a type error!

That concludes my experiment. Some final thoughts:

• This cannot be used to make a type safe head and tail operation, as far as I can see. We'd need an additional type to represent the empty list, and somehow make a head function that can transform between the two types - the kind of overloading necessary does not seem to be possible in F#.
• Try to make a recursive function  with SVec: it's impossible, since generic recursion is impossible.

Technorati: F#,units of measure

How to invoke a method with type parameters using reflection (in F#)

Methods with type parameters arise naturally in F# code, for example:

type Example =
    static member Test l = List.rev l

'Test' has one type parameter 'a, the type of the elements of the list that is being reversed.

In F# you can call the Test method with a list of any type, and the compiler infers the type parameters for you:

let result = Example.Test [1;2;3]

The compiler infers that 'a must be an int.

Mainstream languages such as C# and VB.NET only infer the type arguments at the call site. The programmer needs to declare all the type parameters of a method explicitly. Consider the type signature of the following method:

type Example =
    static member Test2 (a,b) = (fst a = snd b)

Test2 has three type arguments: it takes two tuples a and b as its arguments, which is a total of four types. But since Test2 compares the first element of a with the second element of b, these two are inferred to have the same types. In C#, a programmer would have to infer this for herself, and write:

public static bool Test2<T, U, V>(Tuple<T, U> a, Tuple<V, T> b)
{
   return a.Fst == b.Snd;
}

(of course, assuming that a type Tuple would be defined in .NET, which is not the case if you're not using the F# core libraries)

Because it is obvious that such type annotations require much more work by the programmer, in C# and VB.NET type arguments to methods are in my experience much less common, and much less complex, than what is written without a second thought in F#.

However, recently I faced the problem of calling a number of static methods such as the above using reflection. I had the actual arguments to the method available, so for Test2 above I would have the (type-correct, of course) arguments (true,2.0) and ("whatever", false) available.

To call a method using reflection, you can use MethodInfo.Invoke, on a MethodInfo object obtained using typeof<Example>.GetMethod("Test2") or some such. Executing a non-generic method is easy - just call Invoke() with the actual arguments. However, System.Reflection refuses to call Invoke on a method with unspecified generic arguments (T,U and V for Test2) . You need to specify the actual arguments (bool, float and string for Test2 resp.) manually. So, I had to deduce these from the actual arguments given to the method. The following two functions demonstrate how to do this:

let rec resolve (a:Type) (f:Type) (acc:Dictionary<_,_>) =
    if f.IsGenericParameter then
        if not (acc.ContainsKey(f)) then acc.Add(f,a)
    else 
        Array.zip (a.GetGenericArguments()) (f.GetGenericArguments())
        |> Array.iter (fun (act,form) -> resolve act form acc)

let invokeMethod (m:MethodInfo) args =
    let m = if m.ContainsGenericParameters then
                let typeMap = new Dictionary<_,_>()
                Array.zip args (m.GetParameters()) 
                |> Array.iter (fun (a,f) -> 
                    resolve (a.GetType()) f.ParameterType typeMap)  
                let actuals = 
                    m.GetGenericArguments() 
                    |> Array.map (fun formal -> typeMap.[formal])
                m.MakeGenericMethod(actuals)
            else 
                m
    m.Invoke(null, args)

The second function, invokeMethod, can be used as a replacement for MethodInfo.Invoke that also works for methods with generic arguments. The function above only works for static methods, but taking away this restriction should be straightforward.

invokeMethod takes a MethodInfo m(which should be a static method) and the arguments you want to call the method with. First we check if m is a generic method. If not, nothing needs to be done and we can just call Invoke.

If m is a generic method, we build a a typeMap which maps the formal type arguments to their actual types, for which we can use the signature of the method on the one hand (i.e. as given by the MethodInfo), and the types of the actual arguments args. The function 'resolve' does most of the heavy lifting here, building up the typeMap by comparing actual and formal arguments in a pairwise fashion. 'resolve' needs to be called recursively, since type arguments may be nested arbitrarily deeply. For example,   the formal argument list<'a*option<'b>> should resolve with the actual argument list<int*option<bool>> by mapping 'a to int and 'b to bool.

Once we've determined the actual type arguments to the generic method, System.Reflection lets us instantiate an invoke-able method using MethodInfo.MakeGenericMethod(), which takes an array of actual types that fill in the generic type arguments to the method. If we've determined the type arguments correctly, the result of MakeGenericMethod() is another MethodInfo object that can be invoked as usual.

The interested reader can figure out the details.

Some notes:

• 'resolve' is not tail-recursive. I just didn't bother since you would need to write some extremely convoluted method arguments to blow the stack. list<list<list<list<(repeat x 1000 000)>>>> anyone? Also for the same reason I didn't worry about performance - I don't actually expect to have very deeply nested types. (if type classes were ever added to F#, I guess I would  need to start worrying about that...)
• I dislike that I used a Dictionary in there, though it seemed to be the most elegant solution. I tried using a Map, but then I had to merge maps when the recursive call to resolve returned. It seemed easier with a (non-functional) Dictionary. If anyone can do better, I'd like to hear about it.

Technorati: F#,System.Reflection