Skip to content

Continuation-parsing / trampoline / infinite recursion problem

18 messages · Thomas Mailund, Bert Gunter, William Dunlap +1 more

Original
Thomas Mailund
# 
[I?m really sorry if you receive this mail twice. I just noticed I had sent it from a different account that the one I signed up to the mailing list on and I don?t know if that means it will be filtered; at least I haven?t received it myself yet.]


I am playing around with continuation-passing style recursions and want to use the trampoline approach to avoiding too deep recursions. I want to do recursions on a tree so I cannot simply simulate a tail-recursion with a loop and need something else, and rather than simulating my own stack I want to use the method that solves this in general.

I cannot seem to get out of problems with the

  Error: evaluation nested too deeply: infinite recursion / options(expressions=)?
  Error during wrapup: evaluation nested too deeply: infinite recursion / options(expressions=)?

error, so I reduced the problem to just computing factorials to see if I could at least get it to work there, but here I get the problem as well, and in the example below I am completely stumped as to why.

trampoline <- function(thunk) {
    while (is.function(thunk)) thunk <- thunk()
    thunk
}

thunk_factorial <- function(n, continuation = identity, acc = 1) {
    force(continuation) # if I remove this line I get an error
    cat("call: ", n, " : ", acc, "\n") # same for this line
    if (n == 1) {
        continuation(acc)
    } else {
        make_thunk(thunk_factorial, n - 1, continuation, n * acc)
    }
}
trampoline(thunk_factorial(10000))

This version works for me. If I remove the ?force(continuation)? it doesn?t ? even though I never modify the contination in this function (in the tree I want to do recursion on I will have to). I get all the way down the simulated recursion to the final call of the continuation and then I get the error. So as far as I would expect I should just get the identity of the final accumulator at the end, but instead I get the error.

If I remove the cat-call I also get the error. That *really* puzzles me. What is cat doing that lets me complete the function when it is involved but not when I comment out that line?

There is clearly something about this infinite recursion error I am completely missing. Any help would be greatly appreciated.

Cheers
Thomas
Thomas Mailund
# 
?
Oh, I see that the make_thunk function is missing in my example. It is just this one

make_thunk <- function(f, ...) f(...)
On 9 August 2016 at 21:57:05, Thomas Mailund (mailund at birc.au.dk(mailto:mailund at birc.au.dk)) wrote:

            

      
      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Thomas Mailund
    

    

      
      #
    

  


  

          

      
      
      
    

        
Doh!  It is of course this one:

make_thunk <- function(f, ...) function() f(?)

It just binds a function call into a thunk so I can delay its evaluation.

Sorry
	Thomas

  
  


  


      

    

    

      
      

        


  

        

      Thomas Mailund
    

    

      
      #
    

  


  

      
An alternative implementation, closer to what I need when I have more than one recursion in each step, but still using factorial as the example, is this one:

thunk_factorial <- function(n, continuation = identity) {
  force(continuation) # if I remove this line I get an error
  cat("call: ", n, "\n") # same for this line
  if (n == 1) {
    continuation(1)
  } else {
    new_continuation <- function(result) {
      cat("thunk: ", result, "\n?) # remove this line and it fails, keep it and it works
      make_thunk(continuation, n * result)
    }
    make_thunk(thunk_factorial, n - 1, new_continuation)
  }
}
trampoline(thunk_factorial(10000))

Here I am making a continuation instead of passing along an accumulator, which I need to do for more complex cases, and with that continuation I can also get it to complete without errors if I output the text inside it. Removing the `cat` line and I get the recursion error?

Cheers
	Thomas

            

      
      
      
    

        

      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Duncan Murdoch
    

    

      
      #
    

  


  

      
On 10/08/2016 12:53 PM, Thomas Mailund wrote:

            

      
      
      
    

        
I haven't looked closely at the full set of functions, but this comment:

force(continuation) # if I remove this line I get an error

makes it sound as though you're being caught by lazy evaluation. The 
"make_thunk" doesn't appear to evaluate ..., so its value can change 
between the time you make the thunk and the time you evaluate it.  I 
think you could force the evaluation within make_thunk by changing it to

make_thunk <- function(f, ...) { list(...); function() f(?) }

and then would be able to skip the force() in your thunk_factorial function.

Duncan Murdoch

  
  


  


      

    

    

      
      

        


  

        

      Thomas Mailund
    

    

      
      #
    

  


  

      
That did the trick! 

I was so focused on not evaluating the continuation that I completely forgot that the thunk could hold an unevaluated value? now it seems to be working for all the various implementations I have been playing around with.

I think I still need to wrap my head around *why* the forced evaluation is necessary there, but I will figure that out when my tired brain has had a little rest.

Thanks a lot!

	Thomas

            

      
      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Bert Gunter
    

    

      
      #
    

  


  

      
make_thunk is probably unnecessary and apparently problematic. I think
you could use do.call()  instead, as do.call(f,list(...))  .



-- 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 Wed, Aug 10, 2016 at 9:53 AM, Thomas Mailund <mailund at birc.au.dk> wrote:

            

      
      
      
    

        

      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Thomas Mailund
    

    

      
      #
    

  


  

      
But wait, how is it actually changing? And how did calling `cat` make the problem go away? 

Ok, I will go think about it?

Thanks anyway, it seems to do the trick.

            

      
      
      
    

        

      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Thomas Mailund
    

    

      
      #
    

  


  

      
On 10 Aug 2016, at 19:15, Bert Gunter <bgunter.4567 at gmail.com<mailto:bgunter.4567 at gmail.com>> wrote:

        
make_thunk is probably unnecessary and apparently problematic. I think
you could use do.call()  instead, as do.call(f,list(...))  .

Yes,

make_thunk <- function(f, ...) function() do.call(f, list(...))

also works as far as I can see, yes. I do need to turn it into a thunk, though, as far as I can see.

Thanks
Thomas

  
  


  


      

    

    

      
      

        


  

        

      Duncan Murdoch
    

    

      
      #
    

  


  

      
On 10/08/2016 1:10 PM, Thomas Mailund wrote:

            

      
      
      
    

        
The original version

make_thunk <- function(f, ...) function() f(?)

says to construct a new function whose body evaluates the expression 
f(...).  It never evaluates f nor ... , so they don't get evaluated 
until the first time you evaluate that new function.

My version containing list(...) forces evaluation of ... .  It would 
have been even better to use

make_thunk <- function(f, ...) { list(f, ...); function() f(?) }

because that forces evaluation of both arguments.

I suspect you would have problems with

make_thunk <- function(f, ...) function() do.call(f, list(...))

for exactly the same reasons as the original; I'm surprised that you 
found it appears to work.

Duncan Murdoch

            

      
      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Thomas Mailund
    

    

      
      #
    

  


  

      
?
I am not sure I can see exactly how the parameters are changing at all, regardless of which of the versions I am using. Nowhere in the code do I ever modify assign to a variable (except for defining the global-level functions).

I think my problem is that I don?t really understand ... here.

I would expect these two cases, with and without a thunk, to give me the same output, but they clearly do not.

x <- function(...) eval(substitute(alist(...)))
x(a = 2, b = 3)
x(c = 4, d = 5)

xx <- function(...) function() eval(substitute(alist(...)))
xx(a = 2, b = 3)()
xx(c = 4, d = 5)()

The first gives me the parameters and the second just ? back.

How is the thunk actually seeing ... and why does it work with do.call and not with direct call?

library(pryr)
xxx <- function(...) function() do.call(eval %.% substitute %.% alist, list(...))
xxx(a = 2, b = 3)()
xxx(c = 4, d = 5)()

gives me the same results as the xx case, so it is not the do.call that does it, even though that works in my examples.

With

xxxx <- function(...) { list(...) ; function() eval(substitute(alist(...))) }
xxxx(a = 2, b = 3)()
xxxx(c = 4, d = 5)()

it is the same.


Explicitly naming the parameters, of course works fine

y <- function( ...) { params <- list(...) ; function() params }
y(a = 2, b = 3)()
y(c = 4, d = 5)()

Here I get the expected lists out.

I guess I just shouldn?t be using ... in an inner function that refers to the parameters in an outer function. I?m not even sure what that should be expected to do and I certainly do not understand what is happening :)

Explicitly remembering the parameters seems to work fine, though.

Cheers
	Thomas

        
On 10 August 2016 at 19:28:43, Duncan Murdoch (murdoch.duncan at gmail.com(mailto:murdoch.duncan at gmail.com)) wrote:

        

            

      
      
      
    

  
  


  


      

    

    

      
      

        


  

        

      William Dunlap
    

    

      
      #
    

  


  

      
You may gain some understanding of what is going on by adding
the output of sys.nframe() or length(sys.calls()) to the cat() statement.

Bill Dunlap
TIBCO Software
wdunlap tibco.com

        
On Wed, Aug 10, 2016 at 9:59 AM, Thomas Mailund <mailund at birc.au.dk> wrote:

        

            

      
      
      
    

        

      
      
    

            

      
      
      
    

        

      
      
    

            

      
      
      
    

        

      
      
    

        

  
  


  


      

    

    

      
      

        


  

        

      Thomas Mailund
    

    

      
      #
    

  


  

      
?
Well, they stay at 3 when I call cat (except for the final step going down in they recursion where `identity` is called, where they are 4). They do that both when I evaluate ... in the `make_thunk` function and when I don?t. But then, when I call `cat` it also worked before. I cannot keep `cat` in there and still get the error, something that is *really* puzzling me.

        
On 10 August 2016 at 19:48:47, William Dunlap (wdunlap at tibco.com(mailto:wdunlap at tibco.com)) wrote:

        

            

      
      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Thomas Mailund
    

    

      
      #
    

  


  

      
?
Ok, I think maybe I am beginning to see what is going wrong...

Explicitly remembering the thunk parameters in a list works fine, as far as I can see.

make_thunk <- function(f, ...) {
? remembered <- list(...)
? function(...) do.call(f, as.list(remembered))
}

thunk_factorial <- function(n, continuation = identity) {
? if (n == 1) {
? ? continuation(1)
? } else {
? ? new_continuation <- function(result) {
? ? ? make_thunk(continuation, n * result)
? ? }
? ? make_thunk(thunk_factorial, n - 1, new_continuation)
? }
}

trampoline <- function(thunk) {
? while (is.function(thunk)) thunk <- thunk()
? thunk
}

trampoline(thunk_factorial(100))


But if I delay the evaluation of the parameters to thunk I get an error

make_thunk <- function(f, ...) {
? remembered <- eval(substitute(alist(...))) # not evaluating parameters yet
? function(...) do.call(f, as.list(remembered))
}

thunk_factorial <- function(n, continuation = identity) {
? if (n == 1) {
? ? continuation(1)
? } else {
? ? new_continuation <- function(result) {
? ? ? make_thunk(continuation, n * result)
? ? }
? ? make_thunk(thunk_factorial, n - 1, new_continuation)
? }
}

trampoline(thunk_factorial(100))

Running this version I am told, when applying the function, that it doesn?t see variable `n`.


As far as I can see, the thunk remembers the parameters just fine. At least this gives me the parameters I made it remember

x <- 1
f <- make_thunk(list, a = 1 * x, b = 2 * x)
g <- make_thunk(list, c = 3 * x)
f()
g()

Here I just get the parameters back in a list because the wrapped function is `list`. (The reason I have `x` as a global variable and use it in the arguments is so I get call objects that needs to be evaluated lazily instead of just values).

These values contain the expressions I gave the `make_thunk` function, of course, and they are not evaluated. So in the factorial function the missing `n` is because I give it the expression `n - 1` that it of course cannot evaluate in the thunk.

So I cannot really delay evaluation.

Does this sound roughly correct?

Now why I can still get it to work when I call `cat` remains a mystery?

Cheers
	Thomas

        
On 10 August 2016 at 19:12:41, Thomas Mailund (mailund at birc.au.dk(mailto:mailund at birc.au.dk)) wrote:

        

            

      
      
      
    

        

      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Duncan Murdoch
    

    

      
      #
    

  


  

      
On 10/08/2016 2:39 PM, Thomas Mailund wrote:

            

      
      
      
    

        
Where that will fail is in a situation like this:

thunklist <- list(thunk_factorial, thunk_somethingelse)
for (i in seq_along(thunklist))
   thunklist[[i]] <- make_thunk(thunklist[[i]])

The problem is that the first time thunklist[[1]] is evaluated, it will 
call the function thunklist[[2]] (or something else if i has been 
modified in the meantime), and things will go bad.  That's why it's 
important to force both f and ... in make_thunk.

Duncan Murdoch

            

      
      
      
    

        

      
      
    

        

      
      
    

  
  


  


      

    

    

      
      

        


  

        

      Thomas Mailund
    

    

      
      #
    

  


  

      
Yes, I am aware of this situation and I agree that it is better to force f. I was simply trying to figure out why it was necessary in this particular program where the only repeated assignment anywhere in the code is in trampoline, in a scope none of the thunks can see.

What ever my problem was, it was not that the binding of f changes. The code works correctly if I output info with cat, so unless cat could affect this it can't be.

I still don't quite understand that but I suspect it is ... that is doing something I don't understand. Either that or my understanding of in which scope lazy parameters get evaluated is completely wrong.

Anyway, that being said, you are of course right that it is better to force f in my actual program, and I will.


Thanks

        
On 10 August 2016 at 22:22:32, Duncan Murdoch (murdoch.duncan at gmail.com<mailto:murdoch.duncan at gmail.com>) wrote:

        

        
On 10/08/2016 2:39 PM, Thomas Mailund wrote:

        
Ok, I think maybe I am beginning to see what is going wrong...

Explicitly remembering the thunk parameters in a list works fine, as far as I can see.

make_thunk <- function(f, ...) {
remembered <- list(...)
function(...) do.call(f, as.list(remembered))
}

Where that will fail is in a situation like this:

thunklist <- list(thunk_factorial, thunk_somethingelse)
for (i in seq_along(thunklist))
thunklist[[i]] <- make_thunk(thunklist[[i]])

The problem is that the first time thunklist[[1]] is evaluated, it will
call the function thunklist[[2]] (or something else if i has been
modified in the meantime), and things will go bad. That's why it's
important to force both f and ... in make_thunk.

Duncan Murdoch


thunk_factorial <- function(n, continuation = identity) {
if (n == 1) {
continuation(1)
} else {
new_continuation <- function(result) {
make_thunk(continuation, n * result)
}
make_thunk(thunk_factorial, n - 1, new_continuation)
}
}

trampoline <- function(thunk) {
while (is.function(thunk)) thunk <- thunk()
thunk
}

trampoline(thunk_factorial(100))


But if I delay the evaluation of the parameters to thunk I get an error

make_thunk <- function(f, ...) {
remembered <- eval(substitute(alist(...))) # not evaluating parameters yet
function(...) do.call(f, as.list(remembered))
}

thunk_factorial <- function(n, continuation = identity) {
if (n == 1) {
continuation(1)
} else {
new_continuation <- function(result) {
make_thunk(continuation, n * result)
}
make_thunk(thunk_factorial, n - 1, new_continuation)
}
}

trampoline(thunk_factorial(100))

Running this version I am told, when applying the function, that it doesn?t see variable `n`.


As far as I can see, the thunk remembers the parameters just fine. At least this gives me the parameters I made it remember

x <- 1
f <- make_thunk(list, a = 1 * x, b = 2 * x)
g <- make_thunk(list, c = 3 * x)
f()
g()

Here I just get the parameters back in a list because the wrapped function is `list`. (The reason I have `x` as a global variable and use it in the arguments is so I get call objects that needs to be evaluated lazily instead of just values).

These values contain the expressions I gave the `make_thunk` function, of course, and they are not evaluated. So in the factorial function the missing `n` is because I give it the expression `n - 1` that it of course cannot evaluate in the thunk.

So I cannot really delay evaluation.

Does this sound roughly correct?

Now why I can still get it to work when I call `cat` remains a mystery?

Cheers
Thomas

        
On 10 August 2016 at 19:12:41, Thomas Mailund (mailund at birc.au.dk(mailto:mailund at birc.au.dk)) wrote:

        
That did the trick!

I was so focused on not evaluating the continuation that I completely forgot that the thunk could hold an unevaluated value? now it seems to be working for all the various implementations I have been playing around with.

I think I still need to wrap my head around *why* the forced evaluation is necessary there, but I will figure that out when my tired brain has had a little rest.

Thanks a lot!

Thomas

        
On 10 Aug 2016, at 19:04, Duncan Murdoch wrote:

        

        
On 10/08/2016 12:53 PM, Thomas Mailund wrote:

        
On 10 Aug 2016, at 13:56, Thomas Mailund wrote:

        
make_thunk <- function(f, ...) f(...)

Doh! It is of course this one:

make_thunk <- function(f, ...) function() f(?)

It just binds a function call into a thunk so I can delay its evaluation.

I haven't looked closely at the full set of functions, but this comment:

force(continuation) # if I remove this line I get an error

makes it sound as though you're being caught by lazy evaluation. The "make_thunk" doesn't appear to evaluate ..., so its value can change between the time you make the thunk and the time you evaluate it. I think you could force the evaluation within make_thunk by changing it to

make_thunk <- function(f, ...) { list(...); function() f(?) }

and then would be able to skip the force() in your thunk_factorial function.

Duncan Murdoch



______________________________________________
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.
______________________________________________
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.

  
  


  


      

    

    

      
      

        


  

        

      Duncan Murdoch
    

    

      
      #
    

  


  

      
On 10/08/2016 1:28 PM, Duncan Murdoch wrote:

            

      
      
      
    

        
I have done some experimentation, and am unable to reproduce the 
behaviour you described.  Using do.call() doesn't affect things.

Duncan Murdoch

  
  


  


      

    

    

      
      

        


  

        

      Thomas Mailund
    

    

      
      #
    

  


  

      
I don?t know? that was the behaviour I had yesterday, but on the laptop where I was doing the experiments I updated R from 3.2 to 3.3 earlier today and now the original make_thunk

make_thunk <- function(f, ?) function() f(?)

also works for me.

I don?t know what else I can say to that :)

Cheers
Thomas

        
On 11 August 2016 at 23:05:29, Duncan Murdoch (murdoch.duncan at gmail.com<mailto:murdoch.duncan at gmail.com>) wrote:

        

        
On 10/08/2016 1:28 PM, Duncan Murdoch wrote:

            

      
      
      
    

        
I have done some experimentation, and am unable to reproduce the
behaviour you described. Using do.call() doesn't affect things.

Duncan Murdoch