5

I'm trying to figure out how to get R's callCC function for short-circuiting evalutation of a function to work with functions like lapply and Reduce.

Motivation

This would make Reduce and and lapply have asymptotic efficiency > O(n), by allowing you to exit a computation early.

For example, if I'm searching for a value in a list I could map a 'finder' function across the list, and the second it is found lapply stops running and that value is returned (much like breaking a loop, or using a return statement to break out early).

The problem is I am having trouble writing the functions that lapply and Reduce should take using a style that callCC requires.

Example

Say I'm trying to write a function to find the value '100' in a list: something equivalent to

imperativeVersion <- function (xs) {
    for (val in xs) if (val == 100) return (val)
}

The function to pass to lapply would look like:

find100 <- function (val) { if (val == 100) SHORT_CIRCUIT(val)  }
functionalVersion <- function (xs) lapply(xs, find100)

This (obviously) crashes, since the short circuiting function hasn't been defined yet.

callCC( function (SHORT_CIRCUIT) lapply(1:1000, find100) )

The problem is that this also crashes, because the short circuiting function wasn't around when find100 was defined. I would like for something similar to this to work.

the following works because SHORT_CIRCUIT IS defined at the time that the function passed to lapply is created.

callCC(
    function (SHORT_CIRCUIT) {
        lapply(1:1000, function (val) {
             if (val == 100) SHORT_CIRCUIT(val)
        })
)

How can I make SHORT_CIRCUIT be defined in the function passed to lapply without defining it inline like above?

I'm aware this example can be achieved using loops, reduce or any other number of ways. I am looking for a solution to the problem of using callCC with lapply and Reduce in specific.

If I was vague or any clarification is needed please leave a comment below. I hope someone can help with this :)

Edit One: The approach should be 'production-quality'; no deparsing functions or similar black magic.

3 Answers 3

3

I found a soluton to this problem:

find100 <- function (val) {
    if (val == 100) SHORT_CIRCUIT(val)
}

short_map <- function (fn, coll) {


    callCC(function (SHORT_CIRCUIT) {

        clone_env <- new.env(parent = environment(fn))
        clone_env$SHORT_CIRCUIT <- SHORT_CIRCUIT

        environment(fn) <- clone_env
        lapply(coll, fn)

    })
}

short_map(find100, c(1,2,100,3))

The trick to making higher-order functions work with callCC is to assign the short-circuiting function into the input functions environment before carrying on with the rest of the program. I made a clone of the environment to avoid unintended side-effects.

2

You can achieve this using metaprogramming in R. @alexis_laz's approach was in fact already metaprogramming. However, he used strings which are a dirty hack and error prone. So you did well to reject it.

The correct way to approach @alexis_laz's approach would be by wrangling on code level. In base R this is done using substitute(). There are however better packages e.g. rlang by Hadley Wickham. But I give you a base R solution (less dependency).

lapply_ <- function(lst, FUN) {
  eval.parent(
    substitute(
      callCC(function(return_) {
        lapply(lst_, FUN_)
      }), 
      list(lst_ = lst, FUN_=substitute(FUN))))
}

Your SHORT_CIRCUIT function is actually a more general, control flow return function (or a break function which takes an argument to return it). Thus, I call it return_.

We want to have a lapply_ function, in which we can in the FUN= part use a return_ to break out of the usual lapply().

As you showed, this is the aim:

callCC(
  function (return_) {
    lapply(1:1000, function (x) if (x == 100) return_(x))
  }
)

Just with the problem, that we want to be able to generalize this expression. We want

callCC(
  function(return_) lapply(lst, FUN_)
)

Where we can use inside the function definition we give for FUN_ the return_. We can let, however, the function defintion see return_ only if we insert the function definition code into this expression. This exactly @alexis_laz tried using string and eval. Or you did this by manipulating environment variables.

We can safely achieve the insertion of literal code using substitute(expr, replacer_list) where expr is the code to be manipulated and replacer_list is the lookup table for the replacement of code. By substitute(FUN) we take the literal code given for FUN= for lapply_ without evaluating it. This expression returns literal quoted code (better than the string in @alexis_laz's approach).

The big substitute command says: "Take the expression callCC(function(return_) lapply(lst_, FUN_)) and replace lst_ in this expression by the list given for coll and FUN_ by the literal quoted expression given for FUN.

This replaced expression is then evaluated in the parent environment (eval.parent()) meaning: the resulting expression replaces the lapply_() call and is executed exactly where it was placed.

Such use of eval.parent() (or eval( ... , envir=parent.frame())) is fool proof. (otherwise, tidyverse packages wouldn't be production level ...).

So in this way, you can generalize callCC() calls.

lapply_(1:1000, FUN=function(x) if (x==100) return_(x))
## [1] 100
0

I don't know if it can be of use, but:

    find100 <- "function (val) { if (val == 100) SHORT_CIRCUIT(val)  }"
    callCC( function (SHORT_CIRCUIT) lapply(1:1000, eval(parse(text = find100))) )
    #[1] 100
1
  • thanks for your answer, but evalparse is too far on the hacky side for my purposes. Deparsing a function to a string isn't always possible, and all information about the enclosing environment that the function was defined in is lost. (this will break many functions). Oct 18, 2013 at 2:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.