5
$\begingroup$

Motivation

I have seen many places saying that CPST (continuation-passing style transformation) can express all control flows, but the examples they give are relatively simple and do not involve any loops.

It may be because most of the languages that adopt CPS transform are functional languages, and there are no loops.

I wonder if this technique can be used for modern control flow, such as break, yield, await.

Attempt

I try to do CPS transform for the following for loop:

function iter(list: List<Integer>): Integer {
    for n in list {
        if n < 0 {
            continue
        } else if n == 0 {
            break
        } else {
           return n
        }
    }
    return -1
}

After trying, I found that adding a continuation parameter of break is enough.

  • continue is equivalent to the recursive call itself
  • break is equivalent to passing the continuation of the loop itself, that is, the statement after the loop end.
  • return is equivalent to passing the continuation of the environment function.

This is my personal understanding, I don't know if it is correct.

function cps_iter(list: List<Integer>, ret: Continuation<Integer>) {
    let cps_for = (index: Integer, br: Continuation) => {
        if (index >= list.length) {
            br()
        } else {
            let n = list[index]
            if (n < 0) {
                cps_for(index + 1) 
            } else if n == 0 {
                br()
            } else {
                ret(n)
            }
        }
    }
    loop(0, () => { ret(-1) })
}

Problem

But for the generator (function with yield), I can't figure out how to compile it, who is the continuation of yield?

function* iter(list: List<Integer>): Iterator<Integer> {
    for n in list {
        if n < 0 {
            continue
        } else if n == 0 {
            break
        } else {
            yield n
        }
    }
    return -1
}
  1. I'm wondering if my CPS form of the for loop is correct?
  2. How to compiles generators with yield and coroutines with yield*/await to CPS?
$\endgroup$
1
  • $\begingroup$ There is no such word as "Attemption" it sounds like an attempt to grab attention! $\endgroup$ Commented Jul 4, 2023 at 12:07

1 Answer 1

3
$\begingroup$

On a yield you need to do 2 things, execute the continuation that will handle the yielded value and make sure that continuation can in turn continue the loop.

So to solve that you pass the continuation of the continued loop itself.

This is a bit more involved because you also need to pass state through that makes the loop continue correctly.

This is equivalent to first transforming from a coroutine into a statemachine and on yield set the current state in a struct which gets passed to the caller and on resume check the state struct to jump to the correct place in the coroutine.

$\endgroup$
1
  • $\begingroup$ The state machine should not be necessary. I have heard in HN that the generator can be directly implemented with make-generator in the scheme without additional syntax changes. $\endgroup$
    – Aster
    Commented Jul 6, 2023 at 6:01

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .