C++ heap CPS: Continuation Passing Style with Recursion I am willing to see how to write readable and efficient continuations on the heap in c++. I am not quite satisfied. 

The following is just an exercise: it is coded for fun. I post the code here because I am not really satisfied. I am looking for suggestions. 
I picked up the simplest algorithm: measuring the length of a list and I wrote few recursive implementations. The plain one is len(). 

Then I wrote lenK() i.e. len() in CPS. This is quite straightforward, I think this code is fine. Isn't it? 

When it comes to Kontinuations on the heap, I had to write the continuation K as a class (fine) but I had to use virtuality to let the compiler understand what I wanted (if I use templates the compiler cannot understand that my program eventually terminates and for each call create a new type). I have the strong impression that my solution is not elegant and is not efficient. Is there a better way to implement CPS on the heap? 

#include &lt;iostream&gt;
#include &lt;functional&gt;
#include &lt;memory&gt;

struct List;
bool isEnd(const List&amp; l);
double getHead(const List&amp; l);
List* getTail(const List&amp; l);


//////////////////////////////////////////////////////////////////////////////

int len(const List&amp; l, int val=0){
    if (isEnd(l))
        return val;
      return len(*getTail(l), 
                 ++val);
}

//////////////////////////////////////////////////////////////////////////////

double lenK(const List&amp; l, std::function&lt;int(int)&gt; k){
    if (isEnd(l))
        return k(0);
    return lenK(*getTail(l), [k](int a){return k(a+1);} );
}

//////////////////////////////////////////////////////////////////////////////
class IntInt{
   public:
      virtual ~IntInt()=default;
      virtual int operator()(int)=0;
};

using funcPtr = std::unique_ptr&lt;IntInt&gt;;

class IntID : public IntInt{
   public:
      int operator()(int a){ return a;}
};

class K : public IntInt{
   public:
      K( funcPtr&amp;&amp; k) : k_(std::move(k)){}
      int operator()(int a){ return (*k_)(a+1);}
   private:
      funcPtr k_;
};
//////////////////////////////////////////////////////////////////////////////

double lenKheap(const List&amp; l, funcPtr&amp;&amp; k){
    if (isEnd(l))
        return (*k)(0);
    List* myTail = getTail(l);  
    funcPtr myK = std::make_unique&lt;K&gt;(std::move(k));
    // Without tail call optimization we run out of stack space as for lenK and len. 
    return lenKheap(*myTail, 
                    std::move(myK));
}

void checkLenFunctions(const List&amp; myL){

    std::cout &lt;&lt; len(myL) &lt;&lt; std::endl;

    auto intId = [](int x){return x;};
    std::cout &lt;&lt; lenK(myL, intId ) &lt;&lt; std::endl;

    std::cout &lt;&lt; lenKheap(myL, std::make_unique&lt;IntID&gt;()) &lt;&lt; std::endl;
}


If you want to experiment without bothering with the task of implementing the List class and functions, I provide you with an implementation of it. But this is not part of the review: 

struct List{
    List(double d, List* l) : d_(d), l_(l){}
    List() : d_(0.0), l_(this){}
    double d_;
    List* l_;
};

bool isEnd(const List&amp; l){
    if (l.l_ == &amp;l)
        return true;
    return false;
}
double getHead(const List&amp; l){
    if (!isEnd(l))
        return l.d_;
    throw "EndOfList";
}
List* getTail(const List&amp; l){
    if (!isEnd(l))
        return l.l_;
    throw "EndOfList";
}

int main(){
    List myL;
    List myL1 = List(1.0, &amp;myL);
    List myL2 = List(2.0, &amp;myL1);
    List myL3 = List(3.0, &amp;myL2);
    List myL4 = List(4.0, &amp;myL3);

    checkLenFunctions(myL4);

    return 0;
}
Code Review


Use standard library data structures! In this case std::list.
Iterators are the usual way of traversing a C++ container, so use those too (they also allow us to not care which data structure is being used).
Use std::size_t or even std::container&lt;T&gt;::size_type for indexing. An int is signed, and won't necessarily cover the correct range to be indexed.
lenK and lenKheap return doubles, but should presumably return the index type.




template&lt;class IteratorT&gt;
std::size_t length(IteratorT begin, IteratorT end, std::size_t totalLength = 0) {
    return (begin == end) ? totalLength : length(std::next(begin), end, totalLength + 1);
}

using F = std::function&lt;std::size_t(std::size_t)&gt;;

template&lt;class IteratorT&gt;
std::size_t lengthK(IteratorT begin, IteratorT end, F k = [] (std::size_t a) { return a; }) {
    return (begin == end) ? k(0) : lengthK(std::next(begin), end, [k] (std::size_t a) { return k(a + 1); });
}

...

    auto list = std::vector&lt;int&gt;{ 0, 1, 2, 3 };

    std::cout &lt;&lt; length(list.begin(), list.end()) &lt;&lt; std::endl;
    std::cout &lt;&lt; lengthK(list.begin(), list.end()) &lt;&lt; std::endl;




Note that the stack overflow that happens with long lists is due to the depth of recursion. std::function may already be using the heap to allocate memory. As such, there's not much point in using unique_ptr.

In theory we could use the type hiding already present in std::function, rather than defining a separate inheritance hierarchy, and do something like this:

template&lt;class IteratorT&gt;
std::size_t lengthKHeap(IteratorT begin, IteratorT end, std::unique_ptr&lt;F&gt;&amp;&amp; k = std::make_unique&lt;F&gt;([] (std::size_t a) { return a; })) {
    return (begin == end) ? (*k)(0) : lengthKHeap(std::next(begin), end, std::make_unique&lt;F&gt;([k = std::move(k)](std::size_t a) { return (*k)(a + 1); }));
}


However, this doesn't compile. Although lambda capture by move was added in C++14, std::function is still required to be copyable. We can use a dodgy work-around storing the parameters in a shared pointer like this:

// hideous hack from here: https://stackoverflow.com/a/20846873/673679
template&lt;class F&gt;
auto make_copyable_function(F&amp;&amp; f) {
    auto spf = std::make_shared&lt;std::decay_t&lt;F&gt;&gt;(std::forward&lt;F&gt;(f));
    return [spf] (auto&amp;&amp;... args) -&gt; decltype(auto) { return (*spf)(decltype(args)(args)...); };
}

template&lt;class IteratorT&gt;
std::size_t lengthKHeap(IteratorT begin, IteratorT end, std::unique_ptr&lt;F&gt;&amp;&amp; k = std::make_unique&lt;F&gt;([] (std::size_t a) { return a; })) {
    return (begin == end) ? (*k)(0) : lengthKHeap(std::next(begin), end, std::make_unique&lt;F&gt;(make_copyable_function([k = std::move(k)](std::size_t a) { return (*k)(a + 1); })));
}


But as mentioned, this doesn't help avoid the stack overflow.



Deviations

Things become much more interesting if we stop using recursion and store a vector of functions instead. This allows us to make the control flow explicit (which appears to be one of the main points of using continuations). e.g.:

using NodeT = std::function&lt;void()&gt;;

struct Then {

    void add(NodeT node) {
        m_nodes.push_back(std::move(node));
    }

    void operator()() const {
        for (auto&amp; n : m_nodes)
            n();
    }

private:

    std::vector&lt;NodeT&gt; m_nodes;
};

...

    auto i = 0;
    auto increment = [&amp;] () { ++i; };

    auto then = Then();

    for (auto _ : list)
        then.add(increment);

    then();

    std::cout &lt;&lt; i &lt;&lt; std::endl;


Counting the elements in a list isn't a good example, but I've actually found this pattern of composing functions very helpful for writing lexers / parsers. By defining some more classes to go with Then (Or, ZeroOrOne, ZeroOrMore, etc.) and some operator overloading, it's possible to build up an entire tree of parsing / lexing functions with code that's very close to a simple statement of the language grammar. Which is pretty cool (if not technically continuations).



Of course, there's also asychronously oriented composition stuff using std::future, but I've not been keeping up with what's going on in the C++ standard with that lately.


facebook version.
blog series on avoiding allocations.




Full Code

#include &lt;functional&gt;
#include &lt;memory&gt;

template&lt;class IteratorT&gt;
std::size_t length(IteratorT begin, IteratorT end, std::size_t totalLength = 0) {
    return (begin == end) ? totalLength : length(std::next(begin), end, totalLength + 1);
}

using F = std::function&lt;std::size_t(std::size_t)&gt;;

template&lt;class IteratorT&gt;
std::size_t lengthK(IteratorT begin, IteratorT end, F k = [] (std::size_t a) { return a; }) {
    return (begin == end) ? k(0) : lengthK(std::next(begin), end, [k] (std::size_t a) { return k(a + 1); });
}

// hideous hack from here: https://stackoverflow.com/a/20846873/673679
template&lt;class F&gt;
auto make_copyable_function(F&amp;&amp; f) {
    auto spf = std::make_shared&lt;std::decay_t&lt;F&gt;&gt;(std::forward&lt;F&gt;(f));
    return [spf] (auto&amp;&amp;... args) -&gt; decltype(auto) { return (*spf)(decltype(args)(args)...); };
}

template&lt;class IteratorT&gt;
std::size_t lengthKHeap(IteratorT begin, IteratorT end, std::unique_ptr&lt;F&gt;&amp;&amp; k = std::make_unique&lt;F&gt;([] (std::size_t a) { return a; })) {
    return (begin == end) ? (*k)(0) : lengthKHeap(std::next(begin), end, std::make_unique&lt;F&gt;(make_copyable_function([k = std::move(k)](std::size_t a) { return (*k)(a + 1); })));
}

#include &lt;functional&gt;
#include &lt;vector&gt;

using NodeT = std::function&lt;void()&gt;;

struct Then {

    void add(NodeT node) {
        m_nodes.push_back(std::move(node));
    }

    void operator()() const {
        for (auto&amp; n : m_nodes)
            n();
    }

private:

    std::vector&lt;NodeT&gt; m_nodes;
};

#include &lt;list&gt;
#include &lt;vector&gt;
#include &lt;iostream&gt;

int main() {

    {
        auto const list = std::vector&lt;int&gt;{ 0, 1, 2, 3 };

        {
            std::cout &lt;&lt; length(list.begin(), list.end()) &lt;&lt; std::endl;
            std::cout &lt;&lt; lengthK(list.begin(), list.end()) &lt;&lt; std::endl;
            std::cout &lt;&lt; lengthKHeap(list.begin(), list.end()) &lt;&lt; std::endl;
        }

        {
            auto i = 0;
            auto increment = [&amp;] () { ++i; };

            auto then = Then();

            for (auto _ : list)
                then.add(increment);

            then();

            std::cout &lt;&lt; i &lt;&lt; std::endl;
        }
    }
}