TypeShape: Practical Generic Programming in F#

Last week I announced a new library, TypeShape, with claims that it provides a practical way of doing generic programming in F#. I’m following up with this blog post to elaborate why I believe this to be genuinely useful, and how it could benefit the day-to-day life of the working .NET developer.

The pain of Reflection

Almost everybody who has worked with .NET will at some point need to dabble in the murky ways of reflection. Reflection is needed in scenaria where we need to access data in an indirect fashion, or where circumvention of the type system is necessary.

For example, assume that we have defined the following static method

type Foo =
    static member Bar<'T>(?optionalParam : 'T) : unit =
        printfn "Invoked with parameter %A" optionalParam

Assume now that we would like invoke that method, with a value whose type cannot be known at compile time. In other words, we want to define a function

val invokeUntyped : obj -> unit

which takes an input of type obj and invokes the generic method using the underlying type of the object instance. How do we do this? By using reflection of course!

open System.Reflection

let invokeUntyped (value:obj) =
    // Step 1: get the underlying System.Type for the value
    let t = value.GetType()
    // Step 2: locate the required method and apply the type argument
    let methodInfo =
        typeof<Foo>
            .GetMethod("Bar", BindingFlags.Public ||| BindingFlags.Static)
            .MakeGenericMethod [|t|]

    // Step 3: since the parameter is optional, it must be wrapped
    let optTy = typedefof<_ option>.MakeGenericType [|t|]
    let optCtor = optTy.GetConstructor [|t|]
    let optVal = optCtor.Invoke [|value|]

    /// Step 4: invoke the method with constructed optional parameter
    methodInfo.Invoke(null, [|optVal|]) :?> unit

This is cumbersome code to implement and is highly susceptible to breakage; even minor changes to the method signature will result in runtime errors. What’s more, reflection-based implementations are known to be significantly slower than their IL counterparts.

Using TypeShape

The TypeShape library can be used to implement the same functionality, but in a significantly safer and easy-to-read fashion:

open TypeShape

let invokeUntyped' (value:obj) =
    let shape = TypeShape.Create (value.GetType())
    shape.Accept { new ITypeShapeVisitor<unit> with
        member __.Visit<'T> () = Foo.Bar(value :?> 'T)}

Let’s have a look at the code, line by line.

The first line takes the underlying type of the input value and uses that to create an object of type TypeShape. This object encapsulates essential information on the type of the object.

The second line accepts an object expression of type ITypeShapeVisitor, which in turn invokes the method Foo.Bar. The second line is an instance of what is known as the visitor pattern, a design pattern commonly found in object-oriented programming. In this case, our visitor takes no arguments other than a type variable 'T. Passing this visitor to the TypeShape instance will have it invoked using the object type as argument, hence the downcast is expected to be successful. Importantly, the invocation is performed normally, thus any disagreement in the method signature will be picked up by the compiler.

In other words, TypeShape lets us introduce type variables into scope using the relatively concise approach of F# object expressions.

Nothing magical

The implementation of TypeShape is surprisingly simple to define:

open System

type ITypeShapeVisitor<'R> =
    abstract Visit<'T> : unit -> 'R

[<AbstractClass>]
type TypeShape() =
    abstract Type : Type
    abstract Accept : ITypeShapeVisitor<'R> -> 'R

type TypeShape<'T>() =
    inherit TypeShape()
    override __.Type = typeof<'T>
    override __.Accept v = v.Visit<'T>()

type TypeShape with
    static member Create(t : Type) =
        let tsTy = typedefof<TypeShape<_>>.MakeGenericType [|t|]
        Activator.CreateInstance tsTy :?> TypeShape

In essence, TypeShape uses a minimal amount of reflection to bootstrap typed instances, then takes advantage of the ordinary .NET type system to access type information on-demand. TypeShape instances encapsulate and bear witness to types that may not be known at compile time.

Going Further

Let’s take a look at a different application: suppose we have a tuple whose precise type cannot be known at compile time. A common example of this is the object returned by the ShapeCombination active pattern in the F# quotations module. Suppose we would like like to extract either or both of the items contained in the tuple. Here’s how it could be done using reflection:

let extractTupleElements (value:obj) =
    let t = value.GetType()
    if not t.IsGenericType || t.GetGenericTypeDefinition() <> typedefof<_ * _> then
        invalidArg "value" "not a tuple type!"
    let m_Item1 = t.GetProperty("Item1")
    let m_Item2 = t.GetProperty("Item2")
    m_Item1.GetValue(value), m_Item2.GetValue(value)

Again, the same application could be simplified using the TypeShape library:

let extractTupleElements' (value : obj) =
    match TypeShape.Create (value.GetType()) with
    | Shape.Tuple2 (s : IShapeTuple2) ->
        s.Accept {
            new ITuple2Visitor<obj * obj> with
                member __.Visit<'T, 'S>() =
                    let t,s = value :?> 'T * 'S
                    box t, box s
        }

    | _ -> invalidArg "value" "not a tuple type!"

In this case, we use the included Shape.(|Tuple2|_|) active pattern that checks against our shape being a 2-tuple. If successful, it returns an instance of type IShapeTuple2 that accepts a different visitor, ITuple2Visitor, which introduces the tuple element types in scope.

Similarly, here’s how we can check whether an unknown F# map contains a particular key:

let mapContainsKeyUntyped (key:obj) (map:obj) =
    match TypeShape.Create(map.GetType()) with
    | Shape.FSharpMap (s : IShapeFSharpMap) ->
        s.Accept {
            new IFSharpMapVisitor<bool> with
                member __.Visit<'K,'V when 'K : comparison> () =
                    (map :?> Map<'K,'V>).ContainsKey(key :?> 'K)
        }

    | _ -> invalidArg "map" "not an F# map!"

Generic Programming

TypeShape active patterns can be used to orchestrate what could be considered as generic programming. For instance, take this value printer generator:

let rec mkPrinter<'T> () : 'T -> string = mkPrinterUntyped typeof<'T> :?> _
and private mkPrinterUntyped (t : Type) : obj =
    match TypeShape.Create t with
    | Shape.Unit -> box(fun () -> "()")
    | Shape.Bool -> box(sprintf "%b")
    | Shape.Int32 -> box(sprintf "%d")
    | Shape.String -> box(sprintf "\"%s\"")
    | Shape.FSharpOption s ->
        s.Accept {
            new IFSharpOptionVisitor<obj> with
                member __.Visit<'T> () =
                    let tp = mkPrinter<'T>()
                    box(function None -> "None" | Some t -> sprintf "Some (%s)" (tp t))
        }

    | Shape.Tuple2 s ->
        s.Accept {
            new ITuple2Visitor<obj> with
                member __.Visit<'T, 'S> () =
                    let tp = mkPrinter<'T>()
                    let sp = mkPrinter<'S>()
                    box(fun (t : 'T, s : 'S) -> sprintf "(%s, %s)" (tp t) (sp s))
        }

    | Shape.FSharpList s ->
        s.Accept {
            new IFSharpListVisitor<obj> with
                member __.Visit<'T> () =
                    let tp = mkPrinter<'T>()
                    box(fun ts -> ts |> List.map tp |> String.concat "; " |> sprintf "[%s]")
        }

    | Shape.FSharpSet s ->
        s.Accept {
            new IFSharpSetVisitor<obj> with
                member __.Visit<'T when 'T : comparison> () =
                    let tp = mkPrinter<'T>()
                    box(fun (s:Set<'T>) -> s |> Seq.map tp |> String.concat "; " |> sprintf "set [%s]")
        }

    | _ -> failwithf "unsupported type '%O'" t

The implementation can be used to generate printers for anything within the prescribed algebra of types:

let printer = mkPrinter<(bool * string) option * Set<int * string list option>>()

More importantly, any reflection code will only be executed at generation time, meaning that generated printers execute very efficiently:

// Real: 00:00:00.561, CPU: 00:00:00.562, GC gen0: 32, gen1: 0, gen2: 0
for i = 1 to 1000 do ignore <| sprintf "%A" value
// Real: 00:00:00.010, CPU: 00:00:00.000, GC gen0: 1, gen1: 0, gen2: 0
for i = 1 to 1000 do ignore <| printer value

This technique is being utilized in libraries such as FsPickler and FSharp.AWS.DynamoDB, and is an important contributor to their performance.

Conclusion

If your project relies heavily on reflection, you should consider giving TypeShape a try. It could improve readability and maintainability of your code, and may in some cases lead to better performance. Check it out at https://github.com/eiriktsarpalis/TypeShape and please submit your feedback and/or bug reports!