F# Recursive Objects

Question

I'm new to F#, and functional languages. So this might be stupid question, or duplicated with this Recursive objects in F#?, but I don't know.

Here is a simple Fibonacci function:

let rec fib n = 
    match n with
    | 0 -> 1
    | 1 -> 1
    | _ -> fib (n - 1) + fib (n - 2)

Its signature is int -> int.

It can be rewritten as:

let rec fib = 
    fun n ->
        match n with
        | 0 -> 1
        | 1 -> 1
        | _ -> fib (n - 1) + fib (n - 2)

Its signature is (int -> int) (in Visual Studio for Mac).

So what's the difference with the previous one?

If I add one more line like this:

let rec fib = 
    printfn "fib" // <-- this line
    fun n ->
        match n with
        | 0 -> 1
        | 1 -> 1
        | _ -> fib (n - 1) + fib (n - 2)

The IDE gives me a warning:

warning FS0040: This and other recursive references to the object(s) being defined will be checked for initialization-soundness at runtime through the use of a delayed reference. This is because you are defining one or more recursive objects, rather than recursive functions. This warning may be suppressed by using '#nowarn "40"' or '--nowarn:40'.

How does this line affect the initialization?

What does "recursive object" mean? I can't find it in the documentation.

Update

Thanks for your replies, really nice explanation.

After reading your answers, I have some ideas about the Recursive Object.

First, I made a mistake about the signature. The first two code snippets above have a same signature, int -> int; but the last has signature (int -> int) (note: the signatures have different representation in vscode with Ionide extension).

I think the difference between the two signatures is, the first one means it's just a function, the other one means it's a reference to a function, that is, an object.

And every let rec something with no parameter-list is an object rather than a function, see the function definition, while the second snippet is an exception, possibly optimized by the compiler to a function.

One example:

let rec x = (fun () -> x + 1)() // same warning, says `x` is an recursive object

The only one reason I can think of is the compiler is not smart enough, it throws an warning just because it's a recursive object, like the warning indicates,

This is because you are defining one or more recursive objects, rather than recursive functions

even though this pattern would never have any problem.

let rec fib = 
    // do something here, if fib invoked here directly, it's definitely an error, not warning.
    fun n ->
        match n with
        | 0 -> 1
        | 1 -> 1
        | _ -> fib (n - 1) + fib (n - 2)

What do you think about this?

Answer 1

"Recursive objects" are just like recursive functions, except they are, well, objects. Not functions.

A recursive function is a function that references itself, e.g.:

let rec f x = f (x-1) + 1

A recursive object is similar, in that it references itself, except it's not a function, e.g.:

let rec x = x + 1

The above will actually not compile. The F# compiler is able to correctly determine the problem and issue an error: The value 'x' will be evaluated as part of its own definition. Clearly, such definition is nonsensical: in order to calculate x, you need to already know x. Does not compute.

But let's see if we can be more clever. How about if I close x in a lambda expression?

let rec x = (fun() -> x + 1) ()

Here, I wrap the x in a function, and immediately call that function. This compiles, but with a warning - the same warning that you're getting, something about "checking for initialization-soundness at runtime".

So let's go to runtime:

> let rec x = (fun() -> x + 1) ()
System.InvalidOperationException: ValueFactory attempted to access the Value property of this instance.

Not surprisingly, we get an error: turns out, in this definition, you still need to know x in order to calculate x - same as with let rec x = x + 1.

But if this is the case, why does it compile at all? Well, it just so happens that, in general, it is impossible to strictly prove that x will or will not access itself during initialization. The compiler is just smart enough to notice that it might happen (and this is why it issues the warning), but not smart enough to prove that it will definitely happen.

So in cases like this, in addition to issuing a warning, the compiler will install a runtime guard, which will check whether x has already been initialized when it's being accessed. The compiled code with such guard might look something like this:

let mutable x_initialized = false
let rec x = 
    let x_temp = 
        (fun() -> 
            if not x_initialized then failwith "Not good!"
            else x + 1
        ) ()
    x_initialized <- true
    x_temp

(the actual compiled code looks differently of course; use ILSpy to look if you're curious)

In certain special cases, the compiler can prove one way or another. In other cases it can't, so it installs runtime protection:

// Definitely bad => compile-time error
let rec x = x + 1

// Definitely good => no errors, no warnings
let rec x = fun() -> x() + 1

// Might be bad => compile-time warning + runtime guard
let rec x = (fun() -> x+1) ()

// Also might be bad: no way to tell what the `printfn` call will do
let rec x = 
    printfn "a"
    fun() -> x() + 1

Answer 2

There's a major difference between the last two versions. Notice adding a printfn call to the first version generates no warning, and "fib" will be printed each time the function recurses:

let rec fib n =
  printfn "fib"
  match n with
  | 0 -> 1
  | 1 -> 1
  | _ -> fib (n - 1) + fib (n - 2)

> fib 10;;
fib
fib
fib
...
val it : int = 89

The printfn call is part of the recursive function's body. But the 3rd/final version only prints "fib" once when the function is defined then never again.

What's the difference? In the 3rd version you're not defining just a recursive function, because there are other expressions creating a closure over the lambda, resulting in a recursive object. Consider this version:

let rec fib3 = 
  let x = 1
  let y = 2
  fun n ->
    match n with
    | 0 -> x
    | 1 -> x
    | _ -> fib3 (n - x) + fib3 (n - y)

fib3 is not a plain recursive function; there's a closure over the function capturing x and y (and same for the printfn version, although it's just a side-effect). This closure is the "recursive object" referred to in the warning. x and y will not be redefined in each recursion; they're part of the root-level closure/recursive object.

From the linked question/answer:

because [the compiler] cannot guarantee that the reference won't be accessed before it is initialized

Although it doesn't apply in your particular example, it's impossible for the compiler to know whether you're doing something harmless, or potentially referencing/invoking the lambda in fib3 definition before fib3 has a value/has been initialized. Here's another good answer explaining the same.