Fibonacci Summary Continued
Example 3 - Continuation Passing Style (CPS)
In order to circumvent some of the cost that is incurred by the loading of the stack with successive recursive function calls, we can implement a variation on a functional programming technique called Continuation Passing Style; which is a style of programming in which control is passed explicitly in the form of a continuation.
PHP:
// Identity Function
// https://en.wikipedia.org/wiki/Identity_function
public func id<T>(value: T) -> T {
return value
}
/// Fibonacci Numbers below ceiling value
///
/// - parameter ceiling: Ceiling value
///
/// - returns: Array of Int
/// - note: Continuation Passing Style
func fibonacci3(below ceiling: Int) -> [Int] {
func recurse(_ n: (Int, Int), cont: @escaping ([Int]) -> [Int] = id) -> [Int] {
return (n.0 + n.1 >= ceiling) ? cont([1, 1]) :
recurse((n.1, n.0 + n.1)) { r in cont(r + [n.0 + n.1]) }
}
return recurse((1, 1))
}
Basically the closure is letting us simulate lazy evaluation to do a pseudo tail-call optimisation. In Continuation-Passing style, we pass in a continuation as an extra parameter to our recursive function. Also we created a special Category theory function called an
identity function; this very basic function takes a value of any type and simply returns that value. Now that may appear stupid, but it has it's place in almost all category theory principles; in this case it's specifically used for associativity i.e. the combining of closure calls. In short we used the id function to start the process, similarly to how we use 0 and 1 for the functional
Reduce and/or
MapReduce methods. Essentially 0 and 1 are called the identity elements because they don't affect the results.
Note: In the above example the
id function is used as the default value for the closure parameter: "cont: @escaping ([Int]) -> [Int] =
id" i.e. when we call "return recurse((1, 1))" with only the tuple values (excluding the cont parameter, it utilises the default, that being the id function)
Example 4 - Trampolines
Considering many language and compilers do not adequately accommodate tail call optimisation; there are going to be scenarios where an excessive number of recursive calls will not only slow down the computation but potentially could also put us at risk of experiencing a stack overflow (insufficient resources).
First let's understand what happens when a compiler supports
tail call optimisation. Basically if the compiler during its optimisation phase detects recursion that can effectively be represented as a loop; it internally substitutes a loop or jump code for the recursion.
However as we said, not all compilers support this (because it's often impossible or very difficult to determine this). So how can we still take advantage of recursion but avoid the risk of a stack overflow -- the answer to this is to use a
trampoline. In classical recursion the call stack looks something like this:
With a trampoline, we essentially change the calls to look like this; essentially jumping from one call to the next, and for the older programmers (we're simulating the goto statement):
Here's the code for the trampoline (a generic, reusable function that is used with enum pattern matching)
PHP:
/// Trampoline Result
///
/// - Done: Associated value for completion (Accumulator)
/// - Call: Associated value for call (Element, Accumulator)
enum Result<E,A> {
case Done(A)
case Call(E, A)
}
/// Trampoline Function (Solution for lack of tail call optimization)
///
/// - parameter fn: Closure; with a Element and a Accumulator, returns a Trampoline Result<E, A)
///
/// - returns: Returns a closure, requiring an Element & Accumulator and ultimately returning the accumulator
func trampoline<E, A>(with fn: @escaping (E, A) -> Result<E, A>) -> ((E, A) -> A) {
return { (element: E, accumulator: A) -> A in
var result = fn(element, accumulator)
while true {
switch result {
case let .Done(accumulator):
return accumulator
case let .Call(number, accumulator):
result = fn(number, accumulator)
}
}
}
}
As you can see the internals of the trampoline is essentially a while loop with a switch statement, evaluating whether the next operation is either a
.Call or whether we're
.Done:
- If it's a .Call; we then retrieve the associated values (tuple + array), and wrap in a new function call, assigned to result.
- Alternatively for .Done, we simply return the accumulator; which in the case of the Fibonacci sequence is the array.
Finally here's the recursive Fibonacci function rewritten with a trampoline
PHP:
/// Fibonacci Numbers below ceiling value
///
/// - parameter ceiling: Ceiling value
///
/// - returns: Array of Int
/// - note: Recurse calling using a trampoline
public func fibonacci4(below ceiling: Int) -> [Int] {
let fibBounce = trampoline(with: { (n: (Int, Int), array: [Int]) -> Result<(Int, Int), [Int]> in
if n.0 + n.1 > ceiling {
return .Done(array)
}
return .Call((n.1, n.0 + n.1), array + [n.0 + n.1])
})
return fibBounce((1, 1), [1, 1])
}
Basically we similarly wrap the recursive part of the function internally as a variable called fibBounce, which utilises the trampoline, but with a closure signature specific to the needs of the Fibonacci algorithm:
- Tuple of the last two values in the sequence
- The array of values already calculated, to which we'll add the new one
It then, in accordance with the trampoline returns an enum Result of the tuple and the array. Internally similar to the other recursive functions, we check if our next value is below the ceiling, if not we return the array, otherwise we pass the tuple (of the last two values) and then append that sum to the array. Finally we set the enum case to reflect another
.Call() with the tuple and array.
Example of calling the 5 recursive functions
PHP:
print("\n", fibonacci(below: 1000000000))
print("\n", fibonacci1(below: 1000000000))
print("\n", fibonacci2(below: 1000000000))
print("\n", fibonacci3(below: 1000000000))
print("\n", fibonacci4(below: 1000000000))
3 and 4 are the fastest (< 0.02ms), followed by 1 and 2; the slowest in the bunch is the first fibonacci function shared (~1ms); due to the size of the recursive function and because we're recursively stacking all of the calls, i.e. compiler is unable to optimise the tail calls.
And that's it for this challenge.
Naturally I've provided a lot more than you need to complete this challenge, but I wanted to share with you a few ways of tackling this common problem, and also how to use functional constructs like CPS (Continuation Passing Style) and Trampolines to overcome the negativities of recursive calls i.e. stack loading.
Ps. the code is Swift, not PHP; just decided to use those tags to add a bit of color to the code blocks. Pity MyBB forums don't support something like Rouge or Pygments or even embedded Gists.
![[)roi(]](/forum/data/avatars/m/8/8711.jpg?1563828683){kind=avatar}
