[R] Delayed evaluation / lazy expression evaluation

[Thomas Mailund]

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]]