[R] Delayed evaluation / lazy expression evaluation

Bert Gunter bgunter.4567 at gmail.com
Mon Apr 24 16:59:57 CEST 2017


There is no way that I have the tenacity to wade through your verbiage
(maybe other hardier souls will). However, it sounds like you are
trying to reinvent wheels. I think you want: ?substitute.

> f <- function(exp)substitute(exp)
> f(1:100)
1:100

see also ?delayedAssign for direct manipulation of promises. You may
also wish to check out Hadley Wickham's book on advanced R (available
over the web also, I think) or other resources (e.g. see the R
Language Reference that ships with R) for "computing on the language"
resources.

If all this misses your point, sorry. As I said, others may have
greater initiative with your missive.

Cheers,
Bert

Bert Gunter

"The trouble with having an open mind is that people keep coming along
and sticking things into it."
-- Opus (aka Berkeley Breathed in his "Bloom County" comic strip )


On Mon, Apr 24, 2017 at 5:35 AM, Thomas Mailund
<thomas.mailund at gmail.com> wrote:
> 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 at 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.



More information about the R-help mailing list