Why would the compiler leave a function's parameters generic when it's passed as a parameter?

General
1

I was reading Don Syme’s really well written comments on static abstract members on interfaces, and I saw his comments on there now being three ways to do type level abstractions.

I then realised his example for explicit function passing, i.e. this one:

let f0 add x y =
    (add x y, add y x)

is a very concise form of what I’ve been doing with records of functions as a means of function overloading. What I realised I don’t understand is, why the compiler is allowing me to do this in the first place :slight_smile:

Take this example:

// won't work for int once type of x,y i.e. 'T is resolved to string
let  adder x y = x + y

let strViaAdder = adder "str val1" "str val2"
strViaAdder.Dump("string via adder")

//let intViaAdder = adder 1 2
//intViaAdder.Dump ("int via adder")

Ignore the calls to Dump(), that’s a utility function that LinqPad provides.

Once the compiler infers the type of x and y it won’t let me call it with values of other types, but in the f0 function above, it will leave the parameters of the fAdd function as generic, so this’ll work:

let doAdd fAdd x y =
    fAdd x y
    
type MyStr = {StrVal : string}
type MyInt = {IntVal : int}

let myStr = {StrVal = "some val"}
let myStr1 = {StrVal = "another val"}

let myInt = {IntVal = 1}
let myInt1 = {IntVal = 2}

let addMyStr {StrVal = xVal}  {StrVal = yVal} = xVal + yVal
    
let addMyInt {IntVal = x} {IntVal = y} = x + y

let myStrAdded = doAdd addMyStr myStr myStr1
let myIntAdded = doAdd addMyInt myInt myInt1

myStrAdded.Dump ("added strings")
myIntAdded.Dump ("added integers")

No need to inline f0, and its parameters remain generic. I realised I didn’t notice this when using records of functions, I was just happily using them, but Don’s example made me see the gap in my understanding.
Can someone explain to my what’s going on here ?

2

Let’s simplify your second example to get some minimal code to demonstrate what you’re talking about. This doesn’t compile

let adder x y = x + y
let strViaAdder = adder "str val1" "str val2"
let intViaAdder = adder 1 2

But this does

let inline adder x y = x + y
let strViaAdder = adder "str val1" "str val2"
let intViaAdder = adder 1 2

And this does

let adder add x y = add x y
let strViaAdder = adder (+) "str val1" "str val2"
let intViaAdder = adder (+) 1 2

The reason why is the bottom example and the middle example are using two different F# features. The bottom example is just using generics. I can see the type of adder is
add: ('a -> 'b -> 'c) -> x: 'a -> y: 'b -> 'c. So I can call adder with any type for each of 'a, 'b, and 'c as long as I can provide an add function along with them.

The middle example needs more than generics. It’s type signature is

val inline adder:
  x:  ^a -> y:  ^b ->  ^c
    when ( ^a or  ^b) : (static member (+) :  ^a *  ^b ->  ^c)

You can see it uses ^ instead of ' to introduce a type variable, and we can no longer just use any ^a, ^b, or ^c - specifically we need ^a or ^b to have this static member (+) defined. This is outside the scope of what generics can do for us so we turn to another F# feature called SRTP. But one of the costs of SRTP is that it can only be used with inline functions, otherwise it ends up just taking a “guess” at the types involved (usually that means just “locking in” the types the first time you try to use it). The differences between SRTP and generics are somewhat historical, since generics are a part of all .NET languages since forever ago, and SRTP is an F#-specific feature.

Now SRTP is a fairly advanced feature of F# and has some gotchas, and hard-to-understand errors, and very weird syntax, but the good news is that you’ll probably only “accidentally” bump into SRTP specifically for the arithmetic operators (+, -, *, /), and anywhere else you’ll only bump into them if you’re intentionally using them. So just remember that if you’re doing anything with arithmetic operators, and you want to leave them “generic,” you probably need to add inline to whatever function you’re working with.

Aside:
It’s also worth noting that generics work with some constraints - it doesn’t always have to be any type whatsoever. Generics allow you to constrain on inheritance (like 'a when 'a :> IMyInterface), as well as equality/comparison (like 'a when 'a : comparison). But since there’s no interface for IAddable, you have to use SRTP, which allows for a lot more powerful constraints, like any type that defines a (+) operator.

Hope that helps with understanding the difference! Let me know if that didn’t make sense or if there’s more I can try to clear up.

3

Thanks Nathan, I appreciate the time you’ve taken to respond.

I think I need to rephrase my question slightly. Let me use the examples you’ve kindly provided.

let adder add x y = add x y
let strViaAdder = adder (+) "str val1" "str val2"
let intViaAdder = adder (+) 1 2

As you’ve also written, the compiler infers the type of adder as:

add: ('a -> 'b -> 'c) -> x: 'a -> y: 'b -> 'c
This is the automatic generalisation kicking in, i.e. adder<'a,'b,'c> being defined in the background.
When adder is called with (+) with string typed parameters, its type parameters ('a, 'b, 'c) remain generic. They’re constrained to string for the call site, i.e. "str val" + 3 would not work, but the constraint is applied only at the call site. intViaAdder can pass (+) 1 2 and the type parameter constraints introduced due to previous call (type inference) are not applied here. Instead, the types are inferred again, they’re consistent (both ints) and the call works.

Things are different here though:

let adder x y = x + y
let strViaAdder = adder "str val1" "str val2"
let intViaAdder = adder 1 2

Once the first call to adder resolves the type of x and y to string, the second call won’t be allowed.

Given + in x + y is just another function (an operator), why is the inference triggered from the call site fixing the type parameters for a larger scope (second example above) compared to the inference triggered from the call site when using a higher order function (first example above) ?

It looks like the use of an operator introduces stronger constraining of inferred types than function application, but that’s just me speculating :slight_smile:

In fact, the first example above is the second one refactor to parameterise the + operator, and in that case the compiler leaves the type parameters of adder generic, it only constrains them during the call to adder. I’d like to understand the reason for this difference in behaviour, i.e. why the type inference is treating operator application and function application differently, if that’s what’s happening here of course :slight_smile:

4

In this case, because generics just don’t cut it (ultimately because (+) uses SRTP). In the code snippet

let adder x y = x + y

you can’t define the type signature of adder with just generics. You could try to say that it’s 'a -> 'a -> 'a or 'a -> 'b -> 'c, but that would let you write nonsense programs like

let dt : DateTime = adder (DateTime(2022,07,18)) (DateTime(2022,07,19))

and the problem there is that you can’t add two DateTimes together. So adder would need to be able to carry some additional constraint that it’s input types are “addable.”

You say “Given + in x + y is just another function,” but realize that + is defined using SRTP. + is not just your typical generic function. You can mouse over the + operator in your IDE to see what F# makes of it:
image

SRTP can be thought of kind of like a 2nd way to do generics in F# that can do more powerful things, but only work on “inline” functions (you can see it says “inline” in the definition of +). If you use SRTP in a function that isn’t inline, F# can’t “leave it generic” so it has to decide on one single type, which is going to be whatever the first type used is.

So this is all very much specific to the fact that you’re using + in your example, and + is using SRTP. If I choose some other “normal generic” operator like <, then everything works like you expect:

let lessThan x y = x < y
let a = lessThan 5 1
let b = lessThan "hi" "hello"

(in this case because generics support constraining on comparison. The type signature is
lessThan: x: 'a -> y: 'a -> bool when 'a: comparison
which is just using generic type 'a and not the SRTP type ^a like you can see in the + operator).

There’s even a little “gotcha” on F# For Fun And Profit on this very issue
here if you scroll down to the “Quirks of generic numeric functions” section.

Does that help?

2 Likes
5

This is very helpful @ntwilson , thanks a lot!.

If I understanding the mechanics correctly, the fact that (+) is defined using inline is indeed the reason for not being able to leave the parameters of add function generic. Expanding on what you said:

So inline causes the compiler to do what it’s told and generate the code at the location of its use, i.e. within the body of add function, using the inferred type, which, then fixes the type of the parameters of the function that wraps to call to inline function. Since the wrapping/calling function itself is not inline, the types get constrained to whatever is inferred. The example with < is very useful in explaining the difference between inline and non-inline functions, so thanks for that!

This logic begs another question though: when an inline function is passed as a parameter to a higher order function, as you did with adder, is the compiler then ignoring the inline semantics, but keeping the SRTP checks? That’s the only explanation I can think of for the following code to work:

let adder add x y = add x y
let strViaAdder = adder (+) "str val1" "str val2"
let intViaAdder = adder (+) 1 2

Type checking would not allow us to use (+) for types for which the operator is not defined, and since (+) is defined based on SRTP, that’s what’s used here.
However, the type of add parameter in adder’s signature remains generic, and the only explanation based on my understanding above is that the inline function (+) is called without inlining, so there’s at least one case in which an inline function would not be actually inlined :slight_smile: Did I get it right?

Once again, thanks for all the time to help, much appreciated.

6

I’m glad that clarified things for you!
For the higher-order function though, I don’t think there’s any issues with keeping the same “inlining” logic as for the normal function. So the inlining happens at compile-time, as soon as the compiler knows the types involved. This is grossly inaccurate, I’m sure, but as a mental model, you can imagine the compiler making a pass at the end where it swaps in any occurrences of an inline SRTP function with a version with the types “locked in”. So you could imagine, e.g., that the code

let x = 1 + 5 
let y = "hi" + " there"

would get transformed into

let x = plus_int_int 1 5
let y = plus_str_str "hi" " there"

Now let’s go back to our example in question

let adder add x y = add x y
let strViaAdder = adder (+) "str val1" "str val2"
let intViaAdder = adder (+) 1 2

You can just imagine the compiler making a pass to transform it into

let adder add x y = add x y
let strViaAdder = adder (plus_str_str) "str val1" "str val2"
let intViaAdder = adder (plus_int_int) 1 2

So it actually does the inlining before it passes it into the adder function. And it’s actually passing a different “version” of the + function in on the two separate calls. One way to illustrate this is to show that you can’t partially apply + in this case:

> let adder add x y = add x y
- let adderViaPlus = adder (+)
- let strViaAdder = adderViaPlus "str val1" "str val2"
- let intViaAdder = adderViaPlus 1 2;;

  let intViaAdder = adderViaPlus 1 2;;
  -------------------------------^

stdin(20,30): error FS0001: This expression was expected to have type
    'string'
but here has type
    'int'

because then there’s only a single “version” of + that gets passed in, and the inliner doesn’t have an opportunity to swap in different versions on the two different calls.

7

That’s brilliant. I can see how strong the emphasis on static in SRTP can be now :slight_smile:

Your explanation makes perfect sense, and I don’t think its accuracy matter that much in this context, what matters is that what’s possible at compile time. Very helpful point:

and your example with partial application (or the inability to do it to be precise) proves that inlining is indeed taking place.

You may find this interesting. I fed the example code to sharplab:

let adder add x y = add x y
let strViaAdder = adder (+) "str val1" "str val2"
let intViaAdder = adder (+) 1 2

and got back this (in C#, presumably after F# → MSIL → C# process takes place:)

using System.Diagnostics;
using System.Reflection;
using System.Runtime.CompilerServices;
using <StartupCode$_>;
using Microsoft.FSharp.Core;

[assembly: FSharpInterfaceDataVersion(2, 0, 0)]
[assembly: AssemblyVersion("0.0.0.0")]
[CompilationMapping(SourceConstructFlags.Module)]
public static class @_
{
    [CompilationMapping(SourceConstructFlags.Value)]
    public static string strViaAdder
    {
        get
        {
            return $_.strViaAdder@3;
        }
    }

    [CompilationMapping(SourceConstructFlags.Value)]
    public static int intViaAdder
    {
        get
        {
            return $_.intViaAdder@4;
        }
    }

    [CompilationArgumentCounts(new int[] { 1, 1, 1 })]
    public static c adder<a, b, c>(FSharpFunc<a, FSharpFunc<b, c>> add, a x, b y)
    {
        return FSharpFunc<a, b>.InvokeFast(add, x, y);
    }
}
namespace <StartupCode$_>
{
    internal static class $_
    {
        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        internal static readonly string strViaAdder@3;

        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        internal static readonly int intViaAdder@4;

        [DebuggerBrowsable(DebuggerBrowsableState.Never)]
        [CompilerGenerated]
        [DebuggerNonUserCode]
        internal static int init@;

        static $_()
        {
            strViaAdder@3 = string.Concat("str val1", "str val2");
            intViaAdder@4 = 3;
        }
    }
}

based on this, the compiler is a lot more aggressive than inlining in advance. It seems to run the actual code during compile time and create constant values (at least for the integers), not leaving it to runtime. If my understanding of the C# above is correct, strViaAdder is not even computed via passing an inlined plus_str_str, it’s a pre-computed field with the actual value!

This has been a fantastic exchange Nathan, thanks a lot for taking the time to respond.

1 Like