Why is compiler ok with not closed generic?

Question

I have this code:

open System

let func<'t when 't:comparison> (a: 't[]) = a

[<EntryPoint>]
let main argv =
    let array = [||]
    let actual = func array
    printfn "array = %A, actual = %A, same objects: %b" array actual (Object.ReferenceEquals(array, actual))
    Console.ReadKey()
    0

When I try it in LinqPad5 I get a reasonlable error:

Value restriction. The value 'actual' has been inferred to have generic type val actual : '_a [] when '_a : comparison Either define 'actual' as a simple data term, make it a function with explicit arguments or, if you do not intend for it to be generic, add a type annotation.

However, when I successfully (!) compile and run it (checked for full .NET Framework and DotNetCore both Debug/Release) in Visual Studio I get this output:

array = [||], actual = [||], same objects: false

The only way I could expect this result if 't[] were a value type, but it is definitely not. So, WTF?!?

Decompiled assembly contains this code:

[CompilationMapping(SourceConstructFlags.Module)]
public static class Program
{
  public static t[] func<t>(t[] a)
  {
    return a;
  }

  [EntryPoint]
  public static int main(string[] argv)
  {
    FSharpTypeFunc fsharpTypeFunc = (FSharpTypeFunc) new Program.array\u00409();
    IComparable[] comparableArray = Program.func<IComparable>((IComparable[]) fsharpTypeFunc.Specialize<IComparable>());
    FSharpFunc<object[], IComparable[]>.InvokeFast<bool, Unit>((FSharpFunc<object[], FSharpFunc<IComparable[], FSharpFunc<bool, Unit>>>) new Program.main\u004011(ExtraTopLevelOperators.PrintFormatLine<FSharpFunc<object[], FSharpFunc<IComparable[], FSharpFunc<bool, Unit>>>>((PrintfFormat<FSharpFunc<object[], FSharpFunc<IComparable[], FSharpFunc<bool, Unit>>>, TextWriter, Unit, Unit>) new PrintfFormat<FSharpFunc<object[], FSharpFunc<IComparable[], FSharpFunc<bool, Unit>>>, TextWriter, Unit, Unit, Tuple<object[], IComparable[], bool>>("array = %A, actual = %A, same objects: %b"))), (object[]) fsharpTypeFunc.Specialize<object>(), comparableArray, object.ReferenceEquals((object) (object[]) fsharpTypeFunc.Specialize<object>(), (object) comparableArray));
    Console.ReadKey();
    return 0;
  }

  [Serializable]
  internal sealed class array\u00409 : FSharpTypeFunc
  {
    [CompilerGenerated]
    [DebuggerNonUserCode]
    internal array\u00409()
    {
    }

    public override object Specialize<a>()
    {
      return (object) new a[0];
    }
  }

  [Serializable]
  internal sealed class main\u004011\u002D2 : FSharpFunc<bool, Unit>
  {
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    [CompilerGenerated]
    [DebuggerNonUserCode]
    public FSharpFunc<bool, Unit> clo3;

    [CompilerGenerated]
    [DebuggerNonUserCode]
    internal main\u004011\u002D2(FSharpFunc<bool, Unit> clo3)
    {
      this.clo3 = clo3;
    }

    public override Unit Invoke(bool arg30)
    {
      return this.clo3.Invoke(arg30);
    }
  }

  [Serializable]
  internal sealed class main\u004011\u002D1 : FSharpFunc<IComparable[], FSharpFunc<bool, Unit>>
  {
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    [CompilerGenerated]
    [DebuggerNonUserCode]
    public FSharpFunc<IComparable[], FSharpFunc<bool, Unit>> clo2;

    [CompilerGenerated]
    [DebuggerNonUserCode]
    internal main\u004011\u002D1(FSharpFunc<IComparable[], FSharpFunc<bool, Unit>> clo2)
    {
      this.clo2 = clo2;
    }

    public override FSharpFunc<bool, Unit> Invoke(IComparable[] arg20)
    {
      return (FSharpFunc<bool, Unit>) new Program.main\u004011\u002D2(this.clo2.Invoke(arg20));
    }
  }

  [Serializable]
  internal sealed class main\u004011 : FSharpFunc<object[], FSharpFunc<IComparable[], FSharpFunc<bool, Unit>>>
  {
    [DebuggerBrowsable(DebuggerBrowsableState.Never)]
    [CompilerGenerated]
    [DebuggerNonUserCode]
    public FSharpFunc<object[], FSharpFunc<IComparable[], FSharpFunc<bool, Unit>>> clo1;

    [CompilerGenerated]
    [DebuggerNonUserCode]
    internal main\u004011(FSharpFunc<object[], FSharpFunc<IComparable[], FSharpFunc<bool, Unit>>> clo1)
    {
      this.clo1 = clo1;
    }

    public override FSharpFunc<IComparable[], FSharpFunc<bool, Unit>> Invoke(object[] arg10)
    {
      return (FSharpFunc<IComparable[], FSharpFunc<bool, Unit>>) new Program.main\u004011\u002D1(this.clo1.Invoke(arg10));
    }
  }
}

This line seems to be a culprit:

IComparable[] comparableArray = Program.func<IComparable>((IComparable[]) fsharpTypeFunc.Specialize<IComparable>());

If I remove comparison constraint Specialize uses object instead of IComparable.

Answer 1

So, as I've gathered from the comments, your actual question was this:

Why is it that returned object differs from the passed one?

First of all, the expectation of referential identity for values that are logically "equal" is vastly overrated. If your program relies on referential identity, you're doing it wrong. If you have to force referential identity to be preserved everywhere, you end up with Java.

Indeed, try this:

> obj.ReferenceEquals( 5, 5 )
it : bool = false

> obj.ReferenceEquals( [1;2;3], [1;2;3] )
it : bool = false

Huh?

Of course, you may end up with true in some special cases, for example:

> let l = [1,2,3]
> obj.ReferenceEquals( l, l )
it : bool = true

But that's merely a coincidence arising from the specific implementation that the compiler chose to represent your code. Don't rely on it.

Secondly, your function does, in fact, return the "same" (in referential identity sense) object. Try this:

   > let x =
         let array = [||]
         let typedArray : int[] = array
         let actual = func typedArray
         obj.ReferenceEquals( actual, typedArray )
   x : bool = true

See how the "malfunction" disappeared as soon as I created an intermediate typedArray? You can even replace int with IComparable, it will still be true.

The secret is that the function func is actually fine: it does return the "same" object.

The creation of a new object happens not inside func, but every time you reference array.

Try this:

> let x = 
     let array = [||]
     obj.ReferenceEquals( array, array )
x : bool = false

Huh? WTF?!

This happens, because array is not actually an object, but a function behind the scenes. Because you didn't specify what type array was, it must be generic - i.e. have any type that the user wants it to have. This must work:

let array = [||]
let a : int[] = array
let b : string[] = array

Clearly, array cannot have type int[] and type string[] at the same time, so the only way to implement such construct is to compile it as a function that takes no value parameters, but a single type parameter. Kind of like this:

static a[] array<a>() { return new a[0]; }

And then use that function to construct a and b:

var a = array<int>();
var b = array<string>();

And this is exactly what the compiler does. A function that takes only type parameters, one might call it "type function" in this context. And indeed, that's what it's called in compiled code - FSharpTypeFunc.

Answer 2

The key thing that Fyodor mentioned in his answer is that the way F# handles generic values is tricky. You can see that by looking at the following code which compiles fine:

let oops () =
  let array = [||]
  array.[0] <- 'a'
  array.[0] <- 1

Of course, you cannot put both 'a' and 1 in the same array! What happens here is that the compiler actually compiles let array = [||] as a generic function that returns a new empty array when you access it (with a specific instantiation).

Note that this is possible only for simple values that are created without any side-effects. For example, if you wanted to print a message each time the array is accessed, it would not work. The following:

let oops () =
  let array = printfn "Creating!"; [||]
  array.[0] <- 'a'
  array.[0] <- 1

Gives a type error:

error FS0001: This expression was expected to have type char but here has type int

This is because the inference engine realised that it cannot compile array as a generic function and, instead, specialized the type based on the first use.

In your case, specializing the type would not cause any problem, because you are not using the generic value with multiple different types. This means that you can make the value the same by adding a side-effect to the creation - or even just ignore a unit value () - which is enough to make the compiler specialize the type:

let func<'t when 't:comparison> (a: 't[]) = a

let same () =
  let array = (); [||]
  let actual = func array
  printfn "same: %b" (Object.ReferenceEquals(array, actual))

let notSame () =
  let array = [||]
  let actual = func array
  printfn "same: %b" (Object.ReferenceEquals(array, actual))

notSame()  // same: false
same ()    // same: true

I guess if someone ever decides to make a Wat talk about F#, this would be a good candidate! The compiler could just disallow all generic values (which is what other ML languages do), but that would remove some useful constructs like Array.empty and replace them with Array.createEmpty ().