Using higher-order functions to bypass lack of structural typing

Coming from a C++ background, a pet peeve of mine in C# is how the language makes it impossible to write generic functions that use non-interface instance methods, for example the following is not legal C#:

T Foo<T>(T a, T b)
{
    return a.IsALie() ? b.Grrr(a) : a;
}

The compiler checks that this is valid for any T, and of course, that’s false because lots of Ts don’t have an IsALie() nor a Grrr(T other) method. As cool and awesome as these methods sound, we just can’t assume every type implements them. Oh well. C# does supports interface constraints though, so, assuming we have interfaces like these:

interface IIsALie { bool IsALie(); }
interface IGrrr<T> { T Grrr(T other); }

… and assuming all the concrete types we’ll ever want to use with this function do implement these interfaces, then the following works:

T Foo<T>(T a, T b) where T:IIsALie, IGrrr<T>
{
    return a.IsALie() ? b.Grrr(a) : a;
}

Is this enough? Well, the problem is that the second assumption is probably not true. What about type XYZ developed by ClosedSoftwareCorporation, which does have IsALie() and Grrr(T) methods, but doesn’t implement IIsALie and IGrrr? There’s no way for you to tell the compiler “Yeah it doesn’t explicitely implement these interfaces, but look, it has all the compatible methods with the right signatures, so just pretend it does, all right?”

The root of the problem is this: C# has a nominal type system, which doesn’t care what operations a type supports, only what specific interfaces it implements. In other words, while a type may be structurally compatible (i.e. it has all the right function signatures), C# doesn’t care, the type has to be nominally compatible (i.e. it has to say that it has the right function signatures – by implementing an interface).

And again, it’s not enough to implement any compatible interface (i.e. any interface that has an IsALie or Grrr method), you have to implement the one and only, specific interface that was used in the generic function. This, combined with lack of traits, induces lameness such as the above example.

C++ is an interesting case because although it’s also a nominal type system, templates are a blind macro system that completely ignores types, so templates actually enable static duck typing. This is what makes the STL awesome, for instance.

Also interestingly, F# provides the same feature as C++ through the inline keyword. This is more restrictive than C++ templates (abusing inlining causes code bloat), but the effect is the same.

But what can we do in the general case? What if you’re stuck with C#, or F#’s inline isn’t practical in your scenario?

It recently occured to me, and this is the reason for this blog post, that higher-order functions enable us to work around this problem. So we can turn the above function into a fully legal and generic one by:

  • Replacing methods with functions (“static methods” in OOP-lingo)
  • Having the function take the functions it uses as parameters, i.e. making it higher-order.

We end up with:

T Foo<T>(Func<T, bool> IsALie, Func<T, T, T> Grrr, T a, T b)
{
    return IsALie(a) ? Grrr(b, a) : a;
}

Now we’ve actually got a much more generic function that can work with any definition of IsALie and Grrr. However, it does have two drawbacks: it’s verbose, and it replaces two direct function calls with two delegate calls, which could be problematic in performance critical code. These may be an acceptable price to pay in many cases though.

The good news are, while C#’s limited support for functional programming won’t help us much there, F# does have you covered.

First, F# can get us rid of most of the extra verbosity through partial application. Let’s say I have “standard” implementations of “isALie” and “grrr” (in module “std” (yes this is getting silly))

let foo isALie grrr a b =
    if (isALie a) then (grrr b a) else a

// Specialize foo with the std implementations by partial application
let fooStd = foo std.isALie std.grrr

// I can then call
fooStd a b

This isn’t exactly as cool as C++ templates because I still have to declare each version of foo I want, but I can do so in just one, very simple line of code. At this point the syntactic noise has been all but eliminated. (Partial application is also possible in C#, if you have a serious case of angle bracket addiction).

Second, F# can get us rid of the performance cost, because (in Release mode at least), it’ll generate specialized code for these partially applied functions that calls the relevant functions directly rather than through an indirection. This what LINQPad gives me as optimized IL for fooStd:

fooStd@11.Invoke:
IL_0000:  nop         
IL_0001:  ldarg.1     
IL_0002:  call        Query_hiqinu+Std.isALie // look ma, direct calls!
IL_0007:  brfalse.s   IL_0011
IL_0009:  ldarg.2     
IL_000A:  ldarg.1     
IL_000B:  call        Query_hiqinu+Std.grrr
IL_0010:  ret         
IL_0011:  ldarg.1     
IL_0012:  ret 

Mind you, I’d prefer to have structural typing. Or at least traits. But, I think that with both “inline” and first-class support for higher-order functions and partial applications, we can work around the deficiencies of a strictly nominal type system in not too ugly ways most of the time. In F#. And in C#, well, gotta love those angle brackets.

Advertisements

3 thoughts on “Using higher-order functions to bypass lack of structural typing

  1. Pingback: F# Weekly #23, 2015 | Sergey Tihon's Blog

  2. Jared Hester

    Constraints are another (verbose) option –

    let inline foo (a: ^a when ^a:(member isALie : unit -> bool ))
    (b: ^b when ^b:(member Grrr : ^a -> ^a )) =
    if (^a:(member isALie: unit -> bool) a)
    then (^b:(member Grrr: ^a -> ^a) b, a)
    else a

    Reply
  3. Jared Hester

    Less verbose constraints –

    let inline isALie a = (^a: (member isALie: unit -> bool) a)
    let inline Grrr b a = (^b: (member Grrr:^a -> ^a) b, a)
    let inline foo a b = if isALie a then Grrr b a else a

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s