[Rd] callCC in 2.7.0

Gabor Grothendieck ggrothendieck at gmail.com
Sun Mar 30 22:31:22 CEST 2008 

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 <luke at stat.uiowa.edu> 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
> > <ggrothendieck at gmail.com> 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 <luke at stat.uiowa.edu> 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,  <h.wickham at gmail.com> 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 at 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:      luke at stat.uiowa.edu
> >>> 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:      luke at stat.uiowa.edu
> Iowa City, IA 52242                 WWW:  http://www.stat.uiowa.edu
>

More information about the R-devel mailing list