Intermediate and return values in continuation-passing style

Question

I am coming from a OOP, non-functional background, so I am having trouble fully visualizing several online examples regarding continuation passing. Also, functional languages like Scheme don't have to specify types of arguments or return values, so I am unsure whether I got the idea correctly.

Since C# supports lambdas, I took the first example from the Wikipedia article and tried to port it to C# with strong typing, to see how the pattern would apply:

// (Scheme)

// direct function
(define (pyth x y)
 (sqrt (+ (* x x) (* y y))))

// rewriten with CPS 
(define (pyth& x y k)
 (*& x x (lambda (x2)
          (*& y y (lambda (y2)
                   (+& x2 y2 (lambda (x2py2)
                              (sqrt& x2py2 k))))))))

// where *&, +& and sqrt& are defined to 
// calculate *, + and sqrt respectively and pass the result to k
(define (*& x y k)
 (k (* x y)))

So, rewriting the CPS pyth& version in C# resulted in:

// (C#6)

// continuation function signature
delegate double Cont(double a);

// *&, +& and sqrt& functions
static double MulCont(double a, double b, Cont k) => k(a * b);
static double AddCont(double a, double b, Cont k) => k(a + b);
static double SqrtCont(double a, Cont k) => k(Math.Sqrt(a));

// sqrt(x*x + y*y), cps style
static double PythCont(double x, double y, Cont k) =>
    MulCont(x, x, x2 =>
        MulCont(y, y, y2 =>
            AddCont(x2, y2, x2py2 =>
                SqrtCont(x2py2, k))));

I could have used generics instead of double, but signatures would be longer. Anyway, what I am not sure is:

1. Is the Cont signature above correct (i.e. Func<double, double>)? Should the continuation fn. accept the parameter, process it, and then return the value of the same type back?

2. When I first started reading about continuations, I got the feeling that this continuation function will get invoked for each step in the call stack, but in the example above it's only passed to sqrt&, and all other calls get lambdas which don't really "pass" intermediate values to the original continuation. The code above in the function above is basically analogue to k(Math.Sqrt(x * x + y * y)), so does this mean my assumption about intermediate "hooks" is wrong?

Temporize

It looks fine to me. The only problem is that it should use tail calls. While fine for this example, your stack will blowup very quickly with a bit more code. – Jemappes

It's hard to answer this question without knowing what your intuition about hooks is. With CPS, the callee can call the continuation multiple times, or not at all, or save it somewhere to be invoked later. This example is fairly simple so each continuation just calls the next stage but they don't have to in general. – Manta

@Lee: Thanks, perhaps these examples are simplified so some important points are lost, but they leave me completely clueless about how the continuation could be an abstract representation of the control state, since to me it just looks like a plain old callback function. – Temporize

@Lousy It's not a callback, since callbacks are usually called asynchronously while the main code continues running. With CPS, the main code is never returned to. So all your lambdas are being called in tail position, in Scheme at least. – Armelda

@Jemappes I only see tail calls. C# compiler (csc) doesn't support TCO so even tail calls will blow the stack in C# until a new version use the VM opcodes for TCO – Mosher

@Mosher That's as good of an advertisement as there is for IronScheme, which I'm sure uses the tailcall opcode. Right, leppie? – Armelda

@ChrisJester-Young It needs to since Scheme relies on it to work. I think the requirement of call/cc is more difficult to support than tail calls. – Mosher

@ChrisJester-Young: Well, Lee's comment was that "the callee can call the continuation multiple times, or not at all, or save it somewhere to be invoked later", and furthermore, wikipedia's article on continuations states async/await as continuation examples for C# (in C#, continuations are used pretty much exclusively in the context of async tasks). – Temporize

@Sylwester: I wasn't actually interested in tail-calls (my intent is not to replicate this in C#, but to use C# to get a better image of the pattern in a language I am more familiar with). My question was more related to what continuation is supposed to do within a program, apart from transforming the code for tail-call optimization. – Temporize

@Mosher Well, if you internally implement continuations via CPS-transformation, things like tail calls and multiple values are trivially implemented in terms of CPS. ;-) (Again, not sure how IronScheme does it, and I'd love to hear from leppie on this.) – Armelda

@Lousy That's continuations in general, not CPS. In normal CPS-transformed code, the lambdas are indeed tail-called just once (except in looping contexts and such like), sequentially, never returning to the caller (they're always passed a continuation which they then tail-call). – Armelda

@Lousy The purpose of CPS-transformation is indeed to enable things like tail calls (and general continuations) and various other control flow optimisations, but continuations in general can be used to snapshot call-flow states (which is what is meant by being able to save and invoke continuations later on, multiple times). – Armelda

@Lousy A Continuation like you are referring to is what call/cc is for. It's a way to get the rest of the computation as a function you can indeed choose not to call, call once or several times. CPS is what languages that support call/cc to do with the code in order to facilitate that one can write code in a more normal fashion but get the benefits of continuations without having to write code in CPS style themselves. It's quite difficult to follow even the simple example of pythagoras so imagine a complex program in the same form. – Mosher

@Sylwester: so this is difficult to follow even for programmers seasoned in functional programming? That's good news. :) – Temporize

@Sylwester: The calls are indeed in the tail position, but C# will not emit the tail. prefix to allow tail recursion (which the CLR just does fine). You could use something like post process the IL though. – Jemappes

@ChrisJester-Young: The CLR supports tail calls. It is just a tail. prefix bytecode in IL for the call in the tail position. – Jemappes

@Jemappes Right, my question is about whether IronScheme already generates that tail. prefix without having to postprocess like you say you have to for C#. – Armelda

@ChrisJester-Young: It does emit it where required to have proper tail recursion as required. Cases it does not is where TCE can be applied, or the called function is is known not to be recursive (as tail calls are expensive on the CLR), for example functions like primitives car/cdr and (maybe) even things like length (which is tail recursive in itself, but cannot recurse more). Edit: car/cdr is a bad example as I only emit field getters for them anyways, but arithmetic is probably better example. – Jemappes

Answer 1

1. Yes, unless you want to do anything non-numerical with the outermost continuation, it is correct. You would only need more "Cont"s when your original expression involves more types, e.g.

   (define (foo x) (if (= x 0) 1 0))

in which case it might look like this (sorry I write in scheme for brevity):

(define (foo& x k)
  (=& x 0 (lambda (r1)
            (if r1 (k 1) (k 0)))))

-- now the outermost continuation has a number (let's say an int) as input, while the one provided to "=&" has bool->int type.

2. You are almost right (up to duality) -- each step on the call stack is now a call to some continuation. In general you might be confusing first-class continuations with cps -- the former is a language feature (as in scheme where you can access the current continuation with call/cc operator), the latter is a technique you can use anywhere. You actually can convert expressions to cps without even having higher-order functions in your language (by just representing them somehow).

Another thing you asked is how cps relates to control flow. Well, notice that in applicative, functional language (like scheme) the only thing you have specified is that in case of application, you first evaluate the operands and the operator, and then apply the latter to the former. It does not matter in what order you evaluate the operands -- you might do it left-to-right, right-to-left [or perhaps in some crazy way]. But what if you're not using purely functional style, and the operands cause some side effects? They might e.g. print something to stdout, and later return some value. In that case, you would like to have control over the order. If I remember well, programs compiled with gambit-C evaluate arguments right-to-left, while interpreted with gambit's interpreter left-to-right -- so the problem really exists ;). And precisely then the cps might save you [actually there are other means as well, but we're about cps right now!]. In the scheme example you posted it is forced that the arguments of "+" are evaluated left-to-right. You might alter that easily:

(define (pyth& x y k)
 (*& y y (lambda (y2)
          (*& x x (lambda (x2)
                   (+& x2 y2 (lambda (x2py2)
                              (sqrt& x2py2 k))))))))

And that's the thing.

Of some further applications, as guys already said in the comments, transformation to CPS moves every application to tail-position, so the call stack is being replaced with lambdas, and further if you defunctionalize them, what you get is a data structure representing the control flow -- a neat form to be converted to, say C, or some other imperative language. Fully automagicaly! Or, if you'd like to implement some monad mumbo-jumbo, say Maybe monad, in CPS it's easy, just prepend to each continuation-lambda the test on whether the received value is "Just something" (in which case do the job and push the result to your continuation), or "Nothing", in which case you just push Nothing (to the continuation-lambda). Of course rather by another program or macro, not by hand, as it might be tedious -- the most magic behing cps is that it's so easy to automate the transformation to cps.

Hope I didn't make it unnecessarily complicated.

Gabrielagabriele

Answer 2

I have created a very comprehensive introduction to the Continuation monad that you can Find Here Discovering the Continuation Monad in C#

Also you can find a.Net Fiddle here

I Repeat it in summary here Starting from an initial Function

int Square(int x ){return (x * x);}

2. Use Callback and remove return type

    public static void Square(int x, Action<int> callback)
    {
    callback(x * x);
    }

3. Curry the Callback

    public static Action<Action<int>> Square(int x)
    {
     return (callback) => { callback(x * x); };
    }

4. Generalize the returned Continuation

    public static Func<Func<int,T>,T> Square<T>(int x)
    {
         return (callback) => { callback(x * x); };
    }

5. Extract the Continuation Structure Also Known As the Return Method of the monad

       delegate T Cont<U, T>(Func<U, T> f);

    public static Cont<U, T> ToContinuation<U, T>(this U x)
    {
       return (callback) => callback(x);
    }

    square.ToContinuation<Func<int, int>, int>()

6. Add The bind Monadic method and thus Complete the Monad

    public static Cont<V, Answer> Bind<T, U, V, Answer>(
    this Cont<T, Answer> m,
    Func<T, Cont<U, Answer>> k, 
    Func<T, U, V> selector)
    {
     return (Func<V, Answer> c) => 
    m(t => k(t)(y => c(selector(t, y))));
    }

Unfriendly