Recursive type functions subject to repeated evaluation after result is already bound
- Dominant language
- F#
- Stars
- 4.3k
- Forks
- 876
- Avg merge
- 4d 11h
- Merged PRs (30d)
- 131
Description
Variables within function bodies that are bound to the result of evaluating a recursive type function cannot be trusted to be fully evaluated, but may in fact hold delayed references to the type function that continue to reinvoke it upon future variable lookups.
This may occur regardless of whether the recursive definition group containing the type function passes the recursive safety analysis.
**Repro steps**
Copy the example from F# 4.1 spec section 10.2.3, but instead of a normal `let` definition, use a `let rec`:
``` F#
let mutable count = 1
let rec r<'T> = (count <- count + 1); ref ([] : 'T list)
// count = 1
let x1 = r
// count = 2
let x2 = r
// count = 3
let z0 = x1
// count = 3
```
Up to this point, the behavior is identical to the example in the spec. But now add a function definition that uses the type function and returns a closure:
``` F#
let foo () =
let x = r
(fun () -> x)
let bar = foo ()
bar ()
bar ()
```
**Expected behavior**
Upon evaluation of `let x = r`, the type function is evaluated once and its ultimate result value is bound to `x`, and subsequent references to `x` simply yield that value without altering `count`.
``` F#
let foo () =
let x = r
(fun () -> x)
// count = 3
let bar = foo ()
// count = 4
bar ()
// count = 4
bar ()
// count = 4
```
**Actual behavior**
The type function is re-evaluated every time the resulting closure is invoked.
``` F#
let foo () =
let x = r
(fun () -> x)
// count = 3
let bar = foo ()
// count = 4
bar ()
// count = 5
bar ()
// count = 6
```
The spec says side effects should generally be avoided in type functions, but even if a type function is referentially transparent, this can cause performance issues that are difficult to track down.
**Known workarounds**
If you own the definition of `r` and don't need to depend on it having a value signature, change it to a generic function with a unit parameter.
If you do depend on it having a value signature, but you only care that you can eventually close over a fully-evaluated value that won't force further re-evaluations, you can insert the value into a data structure and then project it back out before closing over the result:
``` F#
let foo () =
let x = (r, ())
let y = fst x
(fun () -> y)
```
With this definition, evaluating `foo ()` causes the type function to be evaluated 5 times (!) but the closure returned by `foo` will not increment `count` any further.
**Related information**
F# Interactive version 10.6.0.0 for F# 4.7 on .Net Framework 4.7.2
Contributor guide
Assessment
This issue has not been assessed yet.