Translate continuation into a closure that actually captures the scope

[mailund]

If we create closures inside a function we transform, then the enclosing environment sees the modified local variables in the loop. This breaks the illusion that we have recursive calls.

With a function like this:

library(pmatch)
tree := L(v) | T(left : tree, right : tree)
t <- T(L(1), T(L(2), L(3)))
sum_leaves <- function(t, cont = identity) {
    cases(
        t,
        L(v) -> cont(v),
        T(left,right) -> {
            call_right <- function(left_sum) {
                  sum_leaves(
                      right,
                      function(right_sum) left_sum + right_sum
                  )
            }
            sum_leaves(left, call_right)
        }
    )
}
sum_leaves(t)

we have two closures, the named call_right and the anonymous function(right_sum) ... inside it. These will capture the environment of the sum_leaves function that contains cont. If we transform the function, however, they will have access to an updated left, right and cont and nothing good will come of that.

We can fix it by capturing cont explicitly in a closure or a thunk. In the code below, I use closures.

make_call_right_closure <- function(cont, left, right) {
    force(cont)
    force(left)
    force(right)
    function(left_sum) 
        sum_leaves(right, function(right_sum) left_sum + right_sum)
}
sum_leaves <- function(t, cont = identity) {
    cases(
        t,
        L(v) -> cont(v),
        T(left,right) -> {
            call_right <- make_call_right_closure(cont, left, right)
            sum_leaves(left, call_right)
        }
    )
}

With a bit of static analysis, we should be able to automatically extract closures and capture the right environment.