Tuesday, May 24, 2016

Recursive Tail Calls and Trampolines in Swift

Umberto Raimondi (via Natasha Murashev):

In this post we’ll see how the lack of predictable tail call elimination in Swift could be overcome using trampolines and a few alternatives to recursion will be described.

[…]

A trampoline is not much more than a loop that executes iteratively functions that can either return the next function in the sequence (in form of a thunk or continuation, a data structure that contains the information needed to perform a specific function call) or another kind of value (in this case the content of the accumulator) to signal the end of the iteration.

[…]

And even if this implementation [is] slower than the original one for all the code needed to operate the trampoline that was added, this version solves our biggest issue related to stack exhaustion[…]

Comments RSS · Twitter

Leave a Comment