2
$\begingroup$

Using continuation passing style, many common language constructs can be written in a simple language with recursion, such as loops (using trampolining), exceptions, generators and even function returns. I have found numerous examples of other language constructs, but all examples I have seen use if-statements directly. Noting the power of CPS, I got curious: Can one write an if-statement in CPS without using an if-statement directly?

The naive attempt would be something along these lines:

if_cps(condition, true_body, false_body, current_continuation)
{
    if(condition) true_body(current_continuation);
    else false_body(current_continuation);
}

but obviously this is a failure, since I used an if-statement directly.

$\endgroup$
  • $\begingroup$ This seems to be a programming question. Community votes, please: should we migrate this to Stack Overflow? $\endgroup$ – Raphael Mar 23 '16 at 9:06
  • $\begingroup$ The question might be thought of as a programming question, however I am more looking for an answer in principle rather than looking to actually write code in CPS. I have seen from your comment and the answer from @Derek-Elkins, that I might need to clarify my question a bit. I will try to do so. $\endgroup$ – 00prometheus Mar 24 '16 at 16:46
  • 2
    $\begingroup$ Do you know how to encode booleans and the conditional statement in pure $\lambda$-calculus? Like this: true = λ x y . x, false = λ x y . y, if_statement = λ condition then_body else_body . condition then_body else_body. If you now CPS transform these, you should get an answer. $\endgroup$ – Andrej Bauer Mar 24 '16 at 20:09
4
$\begingroup$

I think you are over-attributing things to CPS. First, CPS lets you model exceptions, generators, and functional calls, but it doesn't create them. For example, modeling exceptions with CPS only gives me exception-like behavior in code that is itself in CPS. I can, of course, use CPS as an implementation mechanism, an intermediate language, for exceptions or generators. Compare this to a language with first-class continuations, e.g. Scheme's call-with-current-continuation. With that, I could implement exceptions as a library.

Second, recursion gives you loops, not CPS. If you had a language which couldn't express recursion nor had built-in loops, CPS transforming would clearly not change this. You also don't need CPS to express loops as recursion, though it may be useful for things like break and continue.

To address your specific question, in some sense if is part of the definition of booleans. If you want to do anything non-trivial with a boolean, you must at some point use if. You could choose a different, non-abstract representation of booleans via their Church encoding, but converting the "native" booleans to this representation would require if, and at any rate this would just be word play. While our if-cps would not require using if in this representation, this would only be because if is represented by the identity function in this representation. Or to put it another way, we are using this representation's if.

$\endgroup$
2
$\begingroup$

OK, so following the advice given by @Andrej Bauer (in the comments to my question) and @Derek Elkins (in his answer), it seems that we can actually do if-statements in CPS!

I will attempt to write out the suggested answer:

The idea is to do booleans in pure Lambda calculus, e.g. using Church encoding. The CPS version would be like this:

true(a, b, continuation)
{
    a(continuation);
}

false(a, b, continuation)
{
    b(continuation);
}

if_cps(condition, true_body, false_body, current_continuation)
{
     condition(true_body, false_body, current_continuation);
}

To use if_cps, we would do like this:

  1. Make a closure that captures the variables needed and assign it to true_body
  2. Make a closure that captures the variables needed and assign it to false_body
  3. Assign one of the true or false functions to condition
  4. Call if_cps with the parameters above as well as the continuation.

The true_body and false_body closures need to be arity one functions, taking the continuation as a parameter.

$\endgroup$
  • $\begingroup$ Please let me know if I missed anything! $\endgroup$ – 00prometheus Mar 27 '16 at 15:08
  • $\begingroup$ Oh, BTW, obviously you can directly call condition(true_body, false_body, current_continuation), completely omitting if_cps, but this makes it clearer in my head at least. $\endgroup$ – 00prometheus Mar 27 '16 at 15:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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