[Rd] callCC in 2.7.0

[Luke Tierney]

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