tailr v0.1.0


Monthly downloads



Automatic Tail Recursion Optimisation

Implements meta-programming functions for automatically translating recursive functions into looping functions or trampolines.


tailr – Tail recursion optimisations for R programming

Project Status: Active – The project has reached a stable, usable
state and is being actively
developed. Last-changedate lifecycle Licence

Travis build
status Appveyor build
status Coverage
status Coverage

minimal R
version packageversion CRAN\_Status\_Badge

Recursive functions are the natural way to express iterations in a functional programming langauge, but in R, they can be significantly slower than loop-versions and for moderately long sequences or moderately deep trees, recursive functions will reach a limit imposted on them by the stack limit.

There are known solutions to these problems, as long as functions are written to be tail-recursive, meaning that the return value of a function is either a base value or another recursive call, but where we do not call recursively to then do something with the result.

The goal of tailr is to automatically transform tail-recursive functions into loops or trampolines.


You can install tailr from GitHub with:

# install.packages("devtools")


We can take a classical recursive function and write it in a tail-recursive form using an accumulator:

factorial <- function(n, acc = 1) {
    if (n <= 1) acc
    else factorial(n - 1, acc * n)

We can then, automatically, translate that into a looping version:

tr_factorial <- tailr::loop_transform(factorial)
#> function (n, acc = 1) 
#> {
#>     .tailr_n <- n
#>     .tailr_acc <- acc
#>     callCC(function(escape) {
#>         repeat {
#>             n <- .tailr_n
#>             acc <- .tailr_acc
#>             if (n <= 1) 
#>                 escape(acc)
#>             else {
#>                 .tailr_n <<- n - 1
#>                 .tailr_acc <<- acc * n
#>             }
#>         }
#>     })
#> }

#> [1] 9.332622e+157

We can then compare the running time with the recursive function and a version that is written using a loop:

loop_factorial <- function(n) {
    val <- 1
    while (n > 1) {
        val <- n * val
        n <- n - 1

n <- 1000
bm <- microbenchmark::microbenchmark(factorial(n), 
#> Unit: microseconds
#>               expr      min        lq      mean   median       uq      max
#>       factorial(n) 1060.171 1549.4740 1913.4090 1713.880 1944.354 8509.096
#>  loop_factorial(n)   58.790   84.8125  146.6675  102.599  106.656 5168.802
#>    tr_factorial(n)  188.604  273.1550  418.8421  388.853  446.079 2951.480
#>  neval
#>    100
#>    100
#>    100

There is some overhead in using the automatically translated version over the hand-written, naturally, and for a simple function such as factorial, it is not hard to write the loop-variant instead of the recursive function.

However, consider a more complicated example. Using the pmatch package, we can create a linked list data structure as this:

llist := NIL | CONS(car, cdr : llist)

A natural way to process linked lists using pattern matching is to write recursive functions that matches different patterns of their input. A function for computing the length of a linked list can look like this:

llength <- function(llist, acc = 0) {
          NIL -> acc,
          CONS(car, cdr) -> llength(cdr, acc + 1))

It is reasonably simple to understand this function, whereas a looping version is somewhat more complicated. An initial attempt could look like this:

loop_llength <- function(llist) {
    acc <- 0
    repeat {
              NIL -> return(acc),
              CONS(car, cdr) -> {
                  acc <- acc + 1
                  llist <- cdr

This version will not function, however, since it tries to return from inside a call to cases, and return only works inside the immediate scope.

Instead, we can use callCC to implement a non-local return like this:

loop_llength <- function(llist) {
    callCC(function(escape) {
        acc <- 0
        repeat {
                  NIL -> escape(acc),
                  CONS(car, cdr) -> {
                      acc <<- acc + 1
                      llist <<- cdr

Notice that we have to use the <<- assignment operator here. This is for the same reason that we need a non-local return. The expression inside the call to cases is evaluated in a different environment than the local function environment, so to get to the actual variables we want to assign to, we need the non-local assignment operator.

It is possible to avoid cases using other functions from the pmatch package, but the result is vastly more compliated since pattern matching and expressions that should be evaluated per case needs to handle scoping. We can automatically make such a function using tailr, however:

tr_llength <- tailr::loop_transform(llength)

The function we generate is rather complicated

#> function (llist, acc = 0) 
#> {
#>     .tailr_llist <- llist
#>     .tailr_acc <- acc
#>     callCC(function(escape) {
#>         repeat {
#>             llist <- .tailr_llist
#>             acc <- .tailr_acc
#>             if (!rlang::is_null(..match_env <- pmatch::test_pattern(llist, 
#>                 NIL))) 
#>                 with(..match_env, escape(acc))
#>             else if (!rlang::is_null(..match_env <- pmatch::test_pattern(llist, 
#>                 CONS(car, cdr)))) 
#>                 with(..match_env, {
#>                   .tailr_llist <<- cdr
#>                   .tailr_acc <<- acc + 1
#>                 })
#>         }
#>     })
#> }

but, then, it is not one we want to manually inspect in any case.

The automatically generated function is complicated, but it actually outcompetes the hand-written loop version.

make_llist <- function(n) {
    l <- NIL
    for (i in 1:n) {
        l <- CONS(i, l)
test_llist <- make_llist(100)
bm <- microbenchmark::microbenchmark(llength(test_llist),
#> Unit: milliseconds
#>                      expr      min       lq     mean   median        uq
#>       llength(test_llist) 68.07866 76.34487 89.97757 81.73584  89.41849
#>  loop_llength(test_llist) 73.21940 81.79118 98.12486 89.10334 102.31499
#>    tr_llength(test_llist) 43.32049 49.75380 57.50893 54.22610  59.83531
#>       max neval
#>  331.3670   100
#>  267.8227   100
#>  200.1066   100

It is, of course, possible to write a faster hand-written function to deal with this case, but it will be about as complicated as the automatically generated function, and you don’t really want to write that by hand.

As you have no doubt noticed about llength, it is not in fact tail-recursive, from the look of it, since the final recursion is enclosed by a call to cases. The function is only tail-recursive because it can be translated into one by rewriting the cases function call to a sequence of if-statements. The tailr package doesn’t handle cases from pmatch by knowing about this package. Instead, it has a mechanism that lets you provide re-writing rules.

If you set the attribute “tailr_transform” on a function, and set this attribute to a function, then that function will be called when tailr sees the function, before it attempts any other processing. The attribute must be a function that maps an expression to another, re-written, expression. The one for cases looks like this:

tailr_transform_call <- function(expr) {
    stopifnot(rlang::call_name(expr) == "cases")

    args <- rlang::call_args(expr)
    value <- args[[1]]
    patterns <- args[-1]
    eval(rlang::expr(cases_expr(!!value, !!!patterns)))
attr(cases, "tailr_transform") <- tailr_transform_call

You can use this mechanism to support tail-recursion for non-tail-recursive functions that can be rewritten to be tail-recursive.

Functions in tailr

Name Description
can_loop_transform_body Tests if a function, provided by its name, can be transformed.
can_transform_rec Recursive call for testing if an expression can be transformed into a looping tail-recursion.
simplify_returns Remove return(return(...)) expressions
simplify_returns_call Removes return(return(...)) cases.
handle_recursive_returns Handle the actual recursive calls
handle_recursive_returns_call Handles the actual recursive returns
translate_recursive_call Translate a return(<recursive-function-call>) expressions into a block that assigns the parameters to local variables and call `next`.
user_transform Apply user transformations depths-first.
make_returns_explicit_call Make exit points into explicit calls to return.
returns_to_escapes Make calls to return into calls to escapes.
returns_to_escapes_call Make calls to return into calls to escapes.
simplify_nested_blocks Simplify nested code-blocks.
build_transformed_function Construct the expression for a transformed function body.
can_call_be_transformed Tests if a call object can be transformed.
user_transform_rec Apply user transformations depths-first.
make_returns_explicit Make exit points into explicit calls to return.
No Results!

Last month downloads


License GPL-3
Encoding UTF-8
Language en-GB
LazyData true
ByteCompile true
RoxygenNote 6.0.1
NeedsCompilation no
Packaged 2018-02-28 13:03:47 UTC; mailund
Repository CRAN
Date/Publication 2018-02-28 17:07:02 UTC

Include our badge in your README