dotnet / dotnet/fsharp

[<TailCall>] does not protect against broken tail calls in nested unit-returning functions

Open
#18,667 2 comments 0 reactions 0 assignees View on GitHub
Area-Compiler-StateMachines Bug
Dominant language
F#
Stars
4.3k
Forks
876
Avg merge
4d 22h
Merged PRs (30d)
144

Description

**Repro steps**

```fs
type Expr =
| Number of int
| Add of Expr * Expr

module Evaluator =
[]
let rec private eval expr (cont: int -> unit) =
match expr with
| Number n -> cont n
| Add(left, right) ->
eval left (fun leftVal ->
eval right (fun rightVal -> cont (leftVal + rightVal)))
```

**Expected behavior**

The `TailCall` attribute should be consistent with the actual behaviour of the function. That means either:
* `eval` is actually tail-recursive, or
* `eval` is not tail-recursive and using the attribute results in a diagnostic.

**Actual behavior**

The attribute is accepted without warnings/errors, but the function is not tail-recursive. [Compilation](https://sharplab.io/#v2:DYLgZgzgPgLgngBwKYAICiAPBAnFBeFAWACgUUoUA5AVwFsAjJXAezBQEsA7GEsigQQAmglK3RZcAKnE4SJWs0HVgqNADcAhsGoaYzXHl4oVMFNiQBjFDnaaYqJJuAokElAAoLzbiA7cUALQAfCjUnOwwAJT4RmS0uhYAFi5uAO4RibHkVHSMuJyBIV7+nFkCwu4qYDAANGbsAOaJUYVZZI5axkjVHmBhXdUAap3BbWQuTvVNpu59BdiNzcPOwSjFM1UwyygA1FNLWpFHJEA) reveals two places where it is prevented:
* `eval` calls `cont` which, being a function type, returns `null : unit`, however `eval` itself is compiled as `void`-returning, and so `pop` needs to be used to get rid of the `unit` value before returning.
* The continuation calls `eval` but needs to produce a new `null` value.

**Known workarounds**

Since this is caused by the duplicity of the `unit` type, using any other type (even `_`) works, since in that case the return types match.

**Related information**

The original issue was brought up first on [StackOverflow](https://stackoverflow.com/questions/79460322/a-lambda-continuation-with-a-generic-type-does-not-produce-a-stack-overflow-but). I am not sure if this could be fixed entirely in a way that makes the tail-call optimization possible ‒ the only option seems to be to duplicate the method with an actual `Unit` return and use that version when beneficial, but in either case, this behaviour is counter-intuitive and `[]` should protect against it.

Tested on .NET 9.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.