# tailr v0.1.0

Monthly downloads

## Automatic Tail Recursion Optimisation

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

## Readme

# tailr – Tail recursion optimisations for R programming

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.

## Installation

You can install tailr from GitHub with:

```
# install.packages("devtools")
devtools::install_github("mailund/tailr")
```

## Examples

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)
tr_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
#> }
#> }
#> })
#> }
tr_factorial(100)
#> [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
}
val
}
n <- 1000
bm <- microbenchmark::microbenchmark(factorial(n),
loop_factorial(n),
tr_factorial(n))
bm
#> 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
boxplot(bm)
```

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:

```
library(pmatch)
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) {
cases(llist,
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 {
cases(llist,
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 {
cases(llist,
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

```
tr_llength
#> 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)
}
l
}
test_llist <- make_llist(100)
bm <- microbenchmark::microbenchmark(llength(test_llist),
loop_llength(test_llist),
tr_llength(test_llist))
bm
#> 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
boxplot(bm)
```

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

## Details

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 |

suggests | covr , microbenchmark , testthat |

imports | glue , rlang (>= 0.2.0) |

depends | R (>= 3.2) |

Contributors |

#### Include our badge in your README

```
[![Rdoc](http://www.rdocumentation.org/badges/version/tailr)](http://www.rdocumentation.org/packages/tailr)
```