Continuation Passing Style In Cee Plus Plus

Example and discussion on ContinuationPassingStyle in CeePlusPlus moved here.

Example: callcc is defined, using the methods described in FunctoidsInCpp, as a function object which takes three arguments, a value and two function objects each taking one argument. The third argument is called with an argument which is the result from the call of the second argument using the first argument, thus 

  int x = 2;
  callcc(x,f,g); // implies g(f(x))
  callcc(x,succ,succ); // will take the successor of x twice.
Incomplete calls are allowed, so that 

  callcc(x,succ);
is an object which takes a suitable function as an argument. 

  callcc(x,succ) (succ); // Allows deferred decision about last argument.
Also, the last argument in callcc can be another callcc, so that these also work. 

  callcc(x,succ,callcc(_,succ,succ));  // _ is a placeholder for the first argument.
  callcc(x,succ) (callcc(_,succ,succ));  // The second callcc is an argument to the first call.
You need to take some care here, John. You're actually passing more continuations into that porridge than you seem to be thinking: (1) A return continuation, (2) A throw continuation. The difficult part of CPS in C++ is figuring out how to remove these until you desire them explicitly. If you do not do so, CPS will break the stack - the stack cost to pass unused 'return' and 'throw' continuations is linear with program duration. There are mechanisms to avoid this... but most of them involve passing/returning a functor-object to a handler that can then execute the 'next' action, such that the stack cost is constant with the runtime duration. Unfortunately, this does make handling return values considerably more difficult (you'll end up passing continuations into continuations simply so they can be passed back to the handler after some return-value is set), and requires careful consideration of how data is stored (most will be on the heap... at least anything that needs to go from one continuation to another). Further, it requires a great deal of programming discipline.

I've only used CPS in C++ once, and it was when implementing a compiler/interpreter for a small DomainSpecificLanguage for scripting. That is a far easier place to use it, seeing as it doesn't require explaining it to the other programmers.

I am not sure quite what is so terrible in what I am doing, as nothing is being done which is not in C++. First of all, callcc is a function object rather than a function. This means that the calls of callcc are to overloads of operator() and the actual evaluation calls are being held up until the function finally returns, when all the calls are then made and return in the usual sequence. The FC++ functoids provide the means for such lazy behaviour.

Here is the actual code of callcc, which uses a template called Full3 which is part of FC++. 

  struct XCallCC
  {
      template <class T, class F, class G> struct Sig : public FunType<T,F,G,
      typename G::template Sig<typename F::template Sig<T>::ResultType>::ResultType> {};
      template <class T, class F, class G>
typename Sig<T,F,G>::ResultType
      operator()( const T& x, const F& f, const G& g) const {
return  g(f(x)) ;
      }
  };
  typedef Full3<XCallCC> XcallCC;
  XcallCC callcc;
callcc(x,succ,succ) amounts to succ(succ(x))

callcc(x,succ) (callcc(_,succ,succ) ) is FC++ currying and amounts to succ(succ(succ(x))

The power is that callcc(x,succ) is a C++ object which can be passed e.g. as an argument and then further processed.

callcc(x,succ) will be instantiated by FC++ as an object of type binder1and2of3 which looks like this. It holds the parameters of the call until the time when the call is complete when the operator() is called. 

 template <class Ternary, class Arg1, class Arg2>
 class binder1and2of3 {
   const Ternary f;
   const Arg1 a1;
   const Arg2 a2;
 public:
   template <class Arg3>
   struct Sig 
   : public FunType<typename Ternary::template Sig<Arg1,Arg2,Arg3>::Arg3Type,
                    typename Ternary::template Sig<Arg1,Arg2,Arg3>::ResultType> {};
   binder1and2of3(const Ternary& w, const Arg1& x, const Arg2& y) : 
     f(w), a1(x), a2(y) {}
   template <class Arg3>
   typename Sig<Arg3>::ResultType 
   operator()(const Arg3& z) const { return f(a1,a2,z); }
 };

Further, it requires a great deal of programming discipline.

I agree with this, and this is what the original authors of FC++, Brian McNamara and Yannis Smaragdakis, teach by the thoroughness of their code. A full set of binders is supplied for 1, 2 and 3 parameter objects and I have been replicating this code for 4 and 5 argument objects. The beauty is that it supplies a good foundation for extension to different problems, which is what I have been doing here. -- JohnFletcher

I was only suggesting you take care. It's easy to implement badly.

Your approach to callcc above is unlikely to suffer the stack problem at the immediate level since it follows the pattern of acquiring a result then passing the result to another function, which can (if fully optimized for removal of unnecessary temporaries) avoid stack growth issues... essentially by avoiding recursion. Of course, elimination of unnecessary temporaries is an absolute must. So long as the continuation you wish to pass can be determined statically by the programmer, it would be a fine means of composing programs in a manner that optimizes easily. I'm fairly certain it's less useful than function composition, but it certainly isn't useless.

Where it might break is if optimization is insufficient... TailRecursion is an optimization that makes a language well suited for callcc, but C++ lacks TailRecursion. Your implementation requires that C++ perform very good temporary elimination, which can be difficult given that C++ now defines temporary elimination happening only after End of Full Expression (basically after the semicolon) to avoid wiping out things like temporary 'std::string' objects and the inner 'const char*' one can access with '.c_str()'. Further, the approach isn't entirely suited for CPS where branching occurs (multiple continuations)... it does not naturally extend to the broader spectrum of CPS. You'll need to ensure no other CPS things you implement will break the C++ stack due to the C++ calling convention.

Consider that with CPS, the goal of passing the continuation is to control program flow... possibly for a very large application. E.g. you might pass in two continuations, the first to be followed in the event an integer is parsed, and the second in the event a string is parsed. Or you might pass in a third continuation, to be followed in the event an exceptional condition occurs. The continuations that won't ever be followed can be discarded, along with any data that only they continue to depend upon. In a fully CPS program, the stack can be eliminated entirely, though some equivalent may exist for program areas that perform a great number of 'upwards' continuations.

If you wish to consider ContinuationPassingStyleInCeePlusPlus, it's these other uses of continuations that are essential for you to cover. Branching, Looping, Co-Functions (that, e.g., 'yield' a different value on each call), and Exception handling are necessary.) And all of these must be done without potentially breaking the stack. I think it could be done, and would be interesting to do, just not in a manner similar to your current approach. Have any ideas for cpWhile, cpFor, cpIf, cpIfElse?

On a lesser note, the signature on your callcc description is likely broken... you need to use a composed signature if you're going to return a composed value; the return type is: typename G::template Sig<typename F::template Sig<T>::ResultType>::ResultType, not T. - accepted and implemented.

Further, incrementing x when x is const will probably fail. - this is now clarified.

Note that succ is another functoid with the following guts. It is called inc in FC++ which is deliberately following HaskellLanguage, where side effects are not allowed. I have made succ a synonym for inc and prev a synonym for dec. 

    template <class T>
    T operator()(const T& x) const { T y = x; return ++y; }
Thanks for the comment on the return type, you are quite right. This would all go away using FunctoidsInCppWithConceptCpp. I agree that compiler optimisation is important for run time efficiency. On the wider issue of handling problems where there are choices of processing see ContinuationPassingStyleInCppQuadraticEquationExample which is a first attempt at this, although the implementation is not (yet) a continuation. (Sorry for the long page name.) The example could be reimplemented using the Lambda language below. -- JohnFletcher

The comments on extensions take this into another league. FC++ has a lambda language with placeholders, which is described in CppTemplateMetaprogramming, p.244 etc. Here is an example in the current context. X, F and G are placeholders of type LambdaVar<int>. 

  LambdaVar<1> X;
  lambda(X,F,G) [ callcc [X,F,G] ] (35,succ,succ);
  lambda(C,X,F) [ C [X,F,C [_,F,C [_,F,F] ] ] ] (callcc) (45,succ);
  //The last example is equivalent to 
  callcc(45,succ,callcc(_,succ,callcc(_,succ,succ)));
The lambda language does have structures for IF and various other things. See examples below. -- JohnFletcher

Being unfamiliar with the syntax used here, I don't quite follow the example. However, having the structure for the "if" conditional isn't entirely sufficient to make it practical at runtime in production code.

A couple of examples from working code of for IF. For more details on this refer to the FC++ web page referenced on FunctoidsInCpp. 

 // Minimum
 lambda(X,Y) [ if0[ X %less% Y, X, Y ] ] (2,10);
 // Factorial n.
 lambda(X) [ letrec [ F == lambda(Y)[ 
                      if1[ Y %equal% 0,
                           1,
                           Y %multiplies% F[Y%minus%1] ] ]
       ].in[ F[X] ] ] (n);
Note: This code depends upon a combination of OverloadingCommaOperator with ArgumentDependentNameLookup. -- JohnFletcher

JuneZeroSeven

CategoryCpp CategoryFunctionalProgramming CategoryCodingConventions CategoryContinuation

EditText of this page (last edited July 9, 2010) or FindPage with title or text search