dotnet / dotnet/fsharp

Optimizing non-tail recursions for sequences

Open
#18,213 3 comments 1 reaction 0 assignees View on GitHub
Area-Compiler-Optimization Area-Compiler-StateMachines Feature Request help wanted
Dominant language
F#
Stars
4.3k
Forks
876
Avg merge
4d 22h
Merged PRs (30d)
144

Description

F# now optimizes tail recursion when generating sequences.

```fs
let rec tail b e = seq {
if b <= e then
yield b
yield! tail (b+1) e
}
```

The above [tail recursion will be successfully optimized](https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AbEAzAzgHwxgBcACWMU4gQwEsNThSZSBeU3GAR1IG8BYAFCkRpWtkakAPOxbEAFjAB2Q0WtIBPWjAwATRqvUitO3QEIqdBgApgAagCMASmZCAvkA==) and the performance will be linear.

```fs
let rec head b e = seq {
if b <= e then
yield! head b (e-1)
yield e
}}
```

At the same time, the above [`head` recursion will not be optimized](https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AbEAzAzgHwxgBcACWMUgCxgEMATU4UmUgXlNxgEdSBvALAAoUqNIBLbE1IAeDq2I0AdsLFrSAT3EwM9AITU6jZgAp4ARgCUq9aK07GMYQF8gA=), and the performance will be quadratic.

To optimize tail recursion, the [`GenerateNext`](https://fsharp.github.io/fsharp-core-docs/reference/fsharp-core-compilerservices-generatedsequencebase-1.html#GenerateNext) method can return the flag (2) to go to the next iterator and thus the tail recursion execution speed will become linear rather than quadratic.

I propose adding to this method the ability to call the next iterator and return execution to the current iterator. Flag 3 will call the next iterator and return execution to the current iterator. This will optimize the speed of all simple recursions to linear, and not just simple tail recursions.

To support the ability to call the next iterator and return to the current one, add a stack of iterators in the [`GeneratedSequenceBase` class](https://fsharp.github.io/fsharp-core-docs/reference/fsharp-core-compilerservices-generatedsequencebase-1.html). Adding a stack of iterators will allow you to optimize all types of simple recursions, not just tail ones.

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.