trampoline: Make a trampoline.

In trampoline: Make Functions that Can Recurse Infinitely

Description

This function takes a call to a generator factory, created by coro::generator() and runs it as a trampoline, which allows any recursion in the generator function to recurse theoretically forever (but usually just more than can be handled by R's default call stack limits).

Usage

trampoline(call, ...)

tramampoline(call, ...)

trambopoline(call, ...)

Arguments

call

A call to a function or generator function. The function can be one defined already in the calling environment or higher or can be defined as an argument to trampoline(), see ... argument.

...

A named list of functions or generator functions. Named arguments are function or generator function definitions where the name of the argument should be the desired name of the function (that is referred to also within the function for recursion, see examples to get a clearer idea of what this means). Passing multiple named arguments is possible and allows specification of functions that can be used within the generator function that is called in call (again, the examples might make this clearer).

Value

If trm_return() or trm_tailcall() is called within the recursive generator function, trampoline() will return the final return value from the final recursion. Otherwise it will return NULL invisibly (in case the recursion is only for its side-effects). See the examples for how this works.

Examples

## standard recursive function exhausts stack:
print_numbers <- function(n) {
  if(n >= 1) {
    print_numbers(n - 1)
    print(n)
  }
}
try(print_numbers(5000))

## use trampoline with a coro generator instead
print_numbers <- coro::generator(function(n) {
  if(n >= 1) {
    yield(print_numbers(n - 1))
    print(n)
  }
})
nums <- capture.output(
  trampoline(print_numbers(5000))
)
cat(tail(nums))

## Or just use a plain function (but still use yield())
print_numbers <- function(n) {
  if(n >= 1) {
    yield(print_numbers(n - 1))
    print(n)
  }
}

trampoline(print_numbers(5))

## use an alias or another
tramampoline(print_numbers(5))
trambopoline(print_numbers(5))

## use multiple mutually recursive functions
even <- function(n) {
  if (n == 0) trm_return(TRUE) else yield(odd(n - 1))
}

odd <- function(n) {
  if (n == 0) trm_return(FALSE) else yield(even(n - 1))
}

## doesn't work (you must pass odd in because trampoline
## only converts first called function to generator by default)
try(trampoline(even(100)))

## does work
trampoline(even(100), odd = odd)

## you can specify your recursive function in the trampoline
## call if you want.
## Return a value using trm_return():
trampoline(factorial(13),
           factorial = function(n) {
             if(n <= 1) {
               return(trm_return(1))
             }
             val <- yield(factorial(n - 1))
             return(val * n)
           })

## convert to using tail call optimization by wrapping
## recursive call in trm_tailcall()
trampoline(factorial(13),
           factorial = function(n, x = 1) {
             force(x) ## necessary thanks to R's lazy evaluation
             if(n <= 1) {
               return(trm_return(x))
             }
             val <- trm_tailcall(factorial(n - 1, x * n))
             return(val)
           })

trampoline documentation built on Jan. 5, 2022, 1:07 a.m.