[R] Delayed evaluation / lazy expression evaluation
Thomas Mailund
thomas.mailund at gmail.com
Mon Apr 24 14:35:20 CEST 2017
Hi, I’m playing around with ways of implementing lazy evaluation of expressions. In R, function arguments are evaluated as promises but expressions are evaluated immediately, so I am trying to wrap expressions in thunks—functions with no arguments that evaluate an expression—to get something the resembles lazy evaluation of expressions.
As an example, consider this:
lazy <- function(value) {
function() value
}
f <- lazy((1:100000)[1])
If we evaluate f we have to create the long vector and then get the first element. We delay the evaluation to f so the first time we call f we should see a slow operation and if we evaluate it again we should see faster evaluations. If you run this benchmark, you will see that this is indeed what we get:
library(microbenchmark)
microbenchmark(f(), times = 1)
microbenchmark(f(), times = 1)
microbenchmark(f(), times = 1)
microbenchmark(f(), times = 1)
Now, I want to use this to implement lazy linked lists. It is not particularly important why I want to do this, but if you are interested, it is because you can implement persistent queues with amortised constant time operations this way, which is what I am experimenting with.
I have this implementation of linked lists:
list_cons <- function(elem, lst)
structure(list(head = elem, tail = lst), class = "linked_list")
list_nil <- list_cons(NA, NULL)
empty_list <- function() list_nil
is_empty.linked_list <- function(x) identical(x, list_nil)
You can implement it simpler using NULL as an empty list, but this particular implementation lets me use polymorphism to implement different versions of data structures — the reasoning is explained in chapter 2 of a book I’m working on: https://www.dropbox.com/s/qdnjc0bx4yivl8r/book.pdf?dl=0
Anyway, that list implementation doesn’t evaluate the lists lazily, so I am trying to wrap these lists in calls to lazy().
A simple implementation looks like this:
lazy_empty_list <- lazy(empty_list())
lazy_cons <- function(elm, lst) {
lazy(list_cons(elm, lst()))
}
Now, this works fine for adding an element to an empty list:
lst <- lazy_cons(2, lazy_empty_list)
lst()
It also works fine if I add another element to an expression for constructing a list:
lst <- lazy_cons(1, lazy_cons(2, lazy_empty_list))
lst()
I can construct lists as long as I want, as long as I explicitly give the lazy_cons() function an expression for the list:
lst <- lazy_cons(1, lazy_cons(2, lazy_cons(3, lazy_empty_list)))
lst()
However, if I save intermediate lists in a variable, it breaks down. This code:
lst <- lazy_cons(2, lazy_empty_list)
lst <- lazy_cons(1, lst)
lst()
gives me this error:
Error in lst() :
promise already under evaluation: recursive default argument reference or earlier problems?
Now, I am particularly dense today, it being Monday and all, so there is likely to be something very obvious I am missing, but I would think that the “lit” variable, when passed to lazy_cons(), would be interpreted as a promise to be evaluated in the parent environment, so I don’t see why it is considered a circular definition of it.
If I force the list to be evaluated, it all works, and the first evaluation is more expensive than the following:
lazy_cons <- function(elm, lst) {
force(lst)
lazy(list_cons(elm, lst()))
}
lst <- lazy_cons(1, lazy_empty_list)
lst <- lazy_cons(2, lst)
lst <- lazy_cons(3, lst)
microbenchmark(lst(), times = 1)
microbenchmark(lst(), times = 1)
microbenchmark(lst(), times = 1)
But if I do the exact same thing in a for-loop, it breaks again—this does not work and I get the same error as earlier:
lst <- lazy_empty_list()
for (e in 1:3) {
lst <- lazy_cons(e, lst)
}
microbenchmark(lst(), times = 1)
microbenchmark(lst(), times = 1)
microbenchmark(lst(), times = 1)
I really can’t see what the difference is between the loop version and the explicitly unwrapping of the loop, but R certainly sees a difference…
I would really love to hear if any of you guys have any insights to what is going on here...
Cheers
[[alternative HTML version deleted]]
More information about the R-help
mailing list