Static Type Constraints without Inline?

Question

Recently there have been a couple questions regarding static type constraints and inline:

1. http://stackoverflow.com/questions/3754862/use-of-inline-in-f
2. http://stackoverflow.com/questions/3757126/how-does-f-compile-functions-that-can-take-multiple-different-parameter-types-in

Two statements in particular have struck me:

1. "There is no way to encode this type constraint in a first class way in compiled code on .NET. However, the F# compiler can enforce this constraint at the site where it inlines the function, so that all operator uses are resolved at compile time."

2. "...but F# can also inline between compiled assemblies because inline is conveyed via .NET metadata."

The later almost seems to contradict the former. I wonder why inlining needs to be related to the static type constraints feature at all. Couldn't the F# compiler work the way (I believe) C++ templates and .NET generics do and generate type specific, reusable functions as needed on the fly at compile time?

For example:

Polymorphic Definition:

let add (lhs:^a) (rhs:^a) = lhs + rhs

Usage:

let a = add 2 3
let b = add 2. 3.
let b = add 4. 5.

Compiler Generated add Functions:

let add_int (lhs:int) (rhs:int) = lhs + rhs
let add_float (lhs:float) (rhs:float) = lhs + rhs

Compiler Rewritten Usage:

let a = add_int 2 3
let b = add_float 2. 3.
let c = add_float 4. 5.

I am not a compiler writer nor language designer, though the topics do interest me greatly, so please point out my naivety.

Answer 1

I think that it would be technically possible to allow static member constraints without inline. Historically, I think that the feature has been used mainly with standard mathematical operators, but it has become more powerful and more useful only in recent versions.

However, there are several good reasons why you may not want to use it too often:

• Readability of type signatures if all generic methods were interpreted as methods with "hat types" then the readability of type signature would suffer, because each type parameter would have a large list of methods that need to be implemented.

• Interoperability the function/method that is declared as inline cannot be called by other .NET languages. Since interoperability is quite a concern for F#, it seems reasonable to prefer usual generic methods (that can be used from C#).

Generating specialized functions as you suggests (and as C++/CLI compiler does) would be another alternative to the F# implementation (inlining), but it would probably require more effort. In any case you would still need to mark the function somehow, so that the natural way of writing generic functions in F# is using standard generics.

And finally - to explain the contradiction in the two statements. I believe that "inline is conveyed via .NET metadata" actually means that the information about inlining is stored in some binary format in .NET resources. This means that it is a part of .NET assembly, but only F# can understand it.

Answer 2

Two bits.

First "couldn't things work this way?" Yes. "Separate compilation" is often treated as a boolean, but it is actually a continuum. Typically "separate compilation" for a statically typed language means that I only need to know the interface/signature type of a class/method to then be able to compile against that entity in another module/assembly and either succeed and generate good code, or else generate a helpful diagnostic about what the error is. The key idea is that the "type signature" is a "succinct summary of the essential constraints".

You can slide this on a scale to the other end of the spectrum, and do a duck-typing-like thing that F# inline or C++ templates do, where basically "if you plug in those data type into the code body of this method, would it compile?" This is do-able, but it typically suffers from being slower to compile and offering poorer diagnostics when things fail. These consequences fall from the lack of a "succinct summary" that is the typical artifact of "separate" in "separate compilation".

(From a completely different axis of evaluating the utility/usability, the inline/C++-template model is "extremely flexible" and "extremely complicated", whereas typical type-system stuff is "less flexible but often sufficient to express most abstractions" and "very simple".)

Anyway, so anything is possible, but if you do things "more flexibly" than a few standard well-understood mechanisms for types/generics/type-classes, you tend to fall off a cliff when it comes to compilation speed and error diagnostic quality. Thus in F#, the mechanism only kicks in when you specifically request it via inline.

Second, how does F# manage to "inline across assemblies" when .NET metadata cannot express these constraints? Simple, an F# assembly with any inline stuff contains extra F#-specific metadata (in addition to the usual .NET metadata) that basically represents the "F# code body" so it can be inlined at the call site of the referencing assembly. The F#-specific metadata is embdedded as a "resource" in the .NET assembly. In the F# PowerPack, there is a Metadata Reader module that enables you to 'reflect' on some of that extra F# metadata. (In the case of FSharp.Core, this extra metadata is broken out into FSharp.Core.sigdata and FSharp.Core.optdata files, rather than being embedded into the FSharp.Core.dll runtime assembly. This keeps the F# runtime smaller, since you only need the sigdata/optdata at design-time.)