RSS 2.0 | Atom 1.0

Sign In


# Sunday, August 31, 2008
Statically typed duck typing in F#
Many times when I talk to a pro-dynamic typing person, they bring up duck typing. And when I say that duck typing could be resolved statically, I usually get wierd looks, or worse. Well F# exposes static duck typing to users. At least, using the definition that C# uses for duck typing of foreach and collection initalizers. (Yes, of course its a compiler feature and not true CLR/runtime checking.) I'm not promoting this, just pointing it out for fun.

F# allows inline values to accept "statically resolved type variables". The F# specification says (§5.1.2):
A type of the form ^ident is a statically resolved variable type. A fresh type inference variable is created and added to the type inference environment (see §14.6). This type variable is tagged with an attribute indicating it may not be generalized except at inline definitions (see §14.7), and likewise any type variable with which it is equated via a type inference equation may similarly not be generalized.
At the end of this post I have a simple example to help understand this kind of type variable. But more interesting is a another constraint you can apply to such type variables. § Member Constraints: "A constraint of the form (typar or ... or typar) : (member-sig) is an explicit member constraint." But, inside the the F# library, this form is used with function application! For example, the char function is defined:

let inline char (x: ^a) =
    (^a : (static member ToChar: ^a -> char) (x)) // Function application!
     ...<snip /> --
I removed all the special case and inline IL code as its irrelevant for this post

Well, if we have member constraints with function application... we have "statically typed duck typing":

let inline speak (a: ^a) =
    let x = (^a : (member speak: unit -> string) (a))
    printfn "It said: %s" x
    let y = (^a : (member talk: unit -> string) (a))
    printfn "Then it said %s" y

type duck() =
    member x.speak() = "quack"
    member x.talk() = "quackity quack"
type dog() =
    member x.speak() = "woof"
    member x.talk() = "arrrr"

let x = new duck()
let y = new dog()
speak x
speak y


It said: quack
Then it said quackity quack
It said: woof
Then it said arrrr

The restriction is that you have to use inline to get generalization*. If it's not inline, then it'll add additional constraints based on usage. If you removed inline in this case, you'd get the following:

warning FS0064: This construct causes code to be less generic than indicated by the type annotations. The type variable 'a has been constrained to be type 'duck'.
error FS0001: The type 'dog' is not compatible with the type 'duck'.

Inline is as it sounds - the IL code is emitted inline, which is obviously a drawback in many cases. But that's the only way it can work - it has to statically know what types and compile the right method info into the binary. I suppose it'd be possible for the CLR to support this intrinsically. That way, the JIT could emit much more optimized code, versus creating a new method for reach type. I don't know dynamic languages well enough to know if this would be at all a help for interop.

*Here's a simple example to demonstrate the difference between 'a and ^a type parameters generalization.

> let id (a : 'a) = a;;
val id : 'a -> 'a

> id 1, id "hi";;
val it : int * string = (1, "hi") // Good, it's generic

> let id (a : ^a) = a;;
  let id (a : ^a) = a;;
stdin(8,14): warning FS0064: This construct causes code to be less generic than indicated by the type annotations. The type variable 'a has been constrained to be type 'obj'.

val id : obj -> obj

> id 1, id "hi";;
val it : obj * obj = (1, "hi") // Constrained to obj - not generic

> let inline id (a : ^a) = a;;
val inline id :  ^a ->  ^a

> id 1, id "hi";;
val it : int * string = (1, "hi") // Since it's inline, it's generic

Sunday, August 31, 2008 1:14:34 AM UTC  #    Comments [4]  |  Trackback

Saturday, September 13, 2008 2:50:35 AM UTC
You know what's really annoying?

I had proposed this feature for C# 4:


I called them "generic static member constraints," and the purpose was to allow the use of operator overloading from generic methods, but otherwise it's the same basic idea: instead of constraining on types, constrain on members, and then any type that implements that "interface" can be used.

Pity it wasn't accepted...
Sunday, September 14, 2008 10:36:53 PM UTC
I think the reason it wasn't accepted was that this requires the method to be inlined. This has versioning issues and the C# team is very wary about allowing such things to be created. Another is that the CLR has no support for this at all, so exposing it to other languages doesn't work well.

F# can do it because the assumption is that if you use F#, you aren't a total idiot and can handle yourself and understand the impact of certain features. Perhaps that's phrased harshly, but I think it does capture quite a bit of the end result.
Monday, September 15, 2008 12:33:46 AM UTC
And the obvious response is that YES the CLR should natively support this. It's the CLR that supports generic parameter contstraints to begin with, and this seems like an "obvious" enhancement...

The downside is that this removes nearly any ability to have generic code sharing for any such constrained methods. So thus we'd have different native code generated for (1) all reference types, (2) each value type, and (new) (3) each different static member constraint type.

Given the recommendations against value types to begin with, the additional code (2) requires isn't likely to be too significant in practice, but (3) could be a killer, which would be why they don't want to add such support...
Monday, September 15, 2008 1:56:27 AM UTC
>The downside is that this removes nearly any ability to have generic code sharing for any such constrained >methods. So thus we'd have different native code generated for (1) all reference types, (2) each value >type, and (new) (3) each different static member constraint type.

(1) by itself isn't that bad. Since the rest of the types are the same, it'd only require a quick method lookup. To start, they could probably store the lookups right inline, then with tracing support, re-JIT to only keep the most common types inline or something?

(3) Could possibly make things get more complicated, true.

But I like the idea of having a "StructurallyEquivalentAttribute" in addition to enabling a way to tell the CLR that a certain type implements a certain interface. So for instance, if I create a member constrained type, when I compile, I'll generate a specially marked interface and require that on the generic parameter. So far, so normal.

Next, when I use a type I don't own, I'll emit some new metadata (new CLR feature) to say "[mscorlib]System.String implements __IAutoGen<>0". When the CLR loads my assembly, it'll first "join" [myasm]__IAutoGen<>0 to the normalized implementation (i.e., a global set of interface types that share the same signature) -- this is the structurally equivalent attribute in action. Then, it'll see if it needs to re-JIT the System.String class to add this interface implementation. (This final part, I'm not sure of the difficulty or performance issues).

At any rate, this would allow code reuse just like with an interface.

The bigger question is if this is actually worth it. I'd much rather they worked on making F#-type allocations a top-scenario and getting performance up to spec...
Please login with either your OpenID above, or your details below.
Home page

Comment (HTML not allowed)  

Enter the code shown (prevents robots):

Live Comment Preview