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(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.

*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 **Lambda****Var<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

*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);

CategoryCpp CategoryFunctionalProgramming CategoryCodingConventions CategoryContinuation

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