Raw Message

Message-ID: <etPan.57aa3591.69c463b8.1304f@birc.au.dk>
Date: 2016-08-09T19:57:05Z
From: Thomas Mailund
Subject: Continuation-parsing / trampoline / infinite recursion problem

[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


	[[alternative HTML version deleted]]