Thanks. So its intended to jump straight out of deeply nested calls without having to manage the unwinding.
On Sun, Mar 30, 2008 at 4:22 PM, Luke Tierney <[EMAIL PROTECTED]> wrote: > On Sun, 30 Mar 2008, Gabor Grothendieck wrote: > > > Sorry it should be as follows: > > > > fib <- function(i, a = 0, b = 1) { > > if (i == 0) b else fib(i-1, b, a+b) > > } > > > > Now, how do we transform that to use callCC? > > > > > > On Sun, Mar 30, 2008 at 1:42 PM, Gabor Grothendieck > > <[EMAIL PROTECTED]> wrote: > >> OK. Can you show code to implement the tail recursive version of > >> fib using callCC in R, say. > >> > >> Here it is transformed to tail recursive style: > >> > >> fib <- function(i, a = 0, b = 1) { > >> if (i == 0) a else fib(i-1, b, a+b) > >> > >> Now, how do I add callCC to all this so that the fib call > >> presumably does not create a new stack instance? > > What makes you think callCC has anything to contribute here? > > The Wikipedia article Hadley cited says that using CPS effectively is > difficult without tail call optimization, which R does not have and > can't, at least not without some restrictions, because the stack is > avialable via sys.xyz functions. It does _not_ say that having > explicit continuations implies having tail call optimization. > > If you want to, you can rewrite your fib in CPS, something like > > fibCPS <- function(k, i, a = 0, b = 1) { > if (i == 0) k(b) else fibCPS(k, i-1, b, a+b) > } > > and you can then use callCC to bridge between the nonCPS and CPS > world, e.g. with > > fib <- function(i) callCC(function(k) fibCPS(k, i, 0, 1)) > > This will grow the stack just like any other recursion in R. A > (minor) difference compared to your original fib is that the final > exit happens in a single jump rather than a sequence of returns. > > The point of adding the current downward-only callCC to R is to > provide a clean, lexically scoped non-local exit mechanism for exiting > from complex, possibly recursive function calls. Dylan provides this > as part of its 'block' construct (also as an exit or continuation > function); Common Lisp has 'block'/'return-from' constructs that use > lexically scoped block name symbols. > > For a slightly more realistic example than the ones currently in the > help page: Here is some code that implements a simple binary tree data > structure, and a function that visits the nodes of the tree and calls > a specified function on the value in each node: > > mkTree <- function(value, left, right) > list(isLeaf = FALSE, value = value, left = left, right = right) > mkLeaf <- function(value) list(isLeaf = TRUE, value = value) > > visit <- function(node, fun) { > if (node$isLeaf) fun(node$value) > else { > visit(node$left, fun) > visit(node$right, fun) > fun(node$value) > } > } > > A simple example tree: > > x <- mkTree(1, mkTree(2, mkLeaf(3), mkLeaf(4)), > mkTree(5, mkLeaf(6), mkLeaf(7))) > > You can use visit() to print out the node values with > > > visit(x, print) > [1] 3 > [1] 4 > [1] 2 > [1] 6 > [1] 7 > [1] 5 > [1] 1 > > > > If you want to use a function like visit() to traverse the tree but > want the traversal to stop when some condition is met then you can > either rewrite visit to allow for this, making it more complicated, or > you can use a non-local exit. That is where callCC comes in. To > print all values until you find one equal to 7 you can use > > > callCC(function(exit) { > + fun <- function(value) { > + if (value == 7) exit(NULL) > + else print(value) > + } > + visit(x, fun) > + }) > [1] 3 > [1] 4 > [1] 2 > [1] 6 > NULL > > > > One can also imagine situations where this might be useful in a > function passed to an optimizer like optim. Given that our 'break' > only breaks out of one loop level, callCC can also be useful for > breaking out of a set of nested loops. > > I first wrote this particular version of callCC when prototyping the > tryCatch mechanism in pure R code where one needs a means to jump from > a point where a condition is signaled to the point where the handler > is established. The current tryCatch implementation does things > differently because it needs to integrate with the error handling at > the C level. Currently I use callCC in the constantFold function in > codetools (which is why callCC was added when codetools became > recommended). This use is similar to the tree example. > > > luke > > >> > >> > >> On Sun, Mar 30, 2008 at 1:31 PM, Luke Tierney <[EMAIL PROTECTED]> wrote: > >>> On Sun, 30 Mar 2008, Gabor Grothendieck wrote: > >>> > >>>> I think the only relationship to that is the name since > >>>> it does not appear to allow one to leave a function > >>>> in the middle of its processing and re-enter it back > >>>> at that point -- which is what would be needed. > >>> > >>> The article conflates basic CPS with having first class continuations > >>> as in Scheme. The discussion about compilers and tail calls only > >>> requires downward-only continuations of the kind provided by R's > >>> current callCC. The user interface and coroutine discussion requires > >>> continuations that can be run outside of their creating context. The > >>> most sophisticated variant, as provided in Scheme, also allows > >>> continuations to be run more than once. I don't think any of the > >>> examples in the Wikipedia article need that, but there is some > >>> interesting work on using that to model web browsing behavior. > >>> > >>> At any rate, there is plenty of precedent for using callCC as the name > >>> for the construct here even when the continuation is no longer valid > >>> outside of the creating callCC call. So the relationship is more than > >>> just the name. > >>> > >>> luke > >>> > >>>> > >>>> On Sun, Mar 30, 2008 at 12:04 PM, <[EMAIL PROTECTED]> wrote: > >>>>> > >>>>>> Would anyone like to explain if callCC in R 2.7.0 gives > >>>>>> anything that on.exit does not already provide? > >>>>>> > >>>>>> It seems that the exit condition once defined cannot > >>>>>> be added to overridden whereas with on.exit multiple > >>>>>> on.exit's add additional on.exits rather than being ignored. > >>>>>> > >>>>>> Is this important? > >>>>> > >>>>> It facilitates a completely different style of programming - see > >>>>> http://en.wikipedia.org/wiki/Continuation-passing_style > >>>>> > >>>>> -- > >>>>> http://had.co.nz/ > >>>>> > >>>> > >>> > >>>> ______________________________________________ > >>>> R-devel@r-project.org mailing list > >>>> https://stat.ethz.ch/mailman/listinfo/r-devel > >>>> > >>> > >>> -- > >>> Luke Tierney > >>> Chair, Statistics and Actuarial Science > >>> Ralph E. Wareham Professor of Mathematical Sciences > >>> University of Iowa Phone: 319-335-3386 > >>> Department of Statistics and Fax: 319-335-3017 > >>> Actuarial Science > >>> 241 Schaeffer Hall email: [EMAIL PROTECTED] > >>> Iowa City, IA 52242 WWW: http://www.stat.uiowa.edu > >>> > >> > > > > -- > > Luke Tierney > Chair, Statistics and Actuarial Science > Ralph E. Wareham Professor of Mathematical Sciences > University of Iowa Phone: 319-335-3386 > Department of Statistics and Fax: 319-335-3017 > Actuarial Science > 241 Schaeffer Hall email: [EMAIL PROTECTED] > Iowa City, IA 52242 WWW: http://www.stat.uiowa.edu > ______________________________________________ R-devel@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-devel