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]]
______________________________________________
R-help@r-project.org mailing list -- To UNSUBSCRIBE and more, see
https://stat.ethz.ch/mailman/listinfo/r-help
PLEASE do read the posting guide http://www.R-project.org/posting-guide.html
and provide commented, minimal, self-contained, reproducible code.
