1
\$\begingroup\$

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 <iostream>
#include <functional>
#include <memory>

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

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

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

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

double lenK(const List& l, std::function<int(int)> 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<IntInt>;

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

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

double lenKheap(const List& l, funcPtr&& k){
    if (isEnd(l))
        return (*k)(0);
    List* myTail = getTail(l);  
    funcPtr myK = std::make_unique<K>(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& myL){

    std::cout << len(myL) << std::endl;

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

    std::cout << lenKheap(myL, std::make_unique<IntID>()) << 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& l){
    if (l.l_ == &l)
        return true;
    return false;
}
double getHead(const List& l){
    if (!isEnd(l))
        return l.d_;
    throw "EndOfList";
}
List* getTail(const List& l){
    if (!isEnd(l))
        return l.l_;
    throw "EndOfList";
}

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

    checkLenFunctions(myL4);

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ It's continuation passing style \$\endgroup\$ – papagaga Oct 12 '18 at 14:30
  • \$\begingroup\$ I'd be glad to review this but I'm not sure how. What's the point of continuations on the heap? std::function might allocate some memory on the heap for all we know; having a unique_ptr handle instead doesn't seem to be a step forward. On the contrary that leads to very obfuscated a code. \$\endgroup\$ – papagaga Oct 12 '18 at 14:36
  • \$\begingroup\$ @papagaga thanks for the name. This is just a case-study. I think that heap-based CPS is useful when stack is limited and recursion is deep. Especially in algorithms based on double recursion. I hope this does make sense. \$\endgroup\$ – jimifiki Oct 12 '18 at 15:47
2
\$\begingroup\$

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<T>::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<class IteratorT>
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<std::size_t(std::size_t)>;

template<class IteratorT>
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<int>{ 0, 1, 2, 3 };

    std::cout << length(list.begin(), list.end()) << std::endl;
    std::cout << lengthK(list.begin(), list.end()) << 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<class IteratorT>
std::size_t lengthKHeap(IteratorT begin, IteratorT end, std::unique_ptr<F>&& k = std::make_unique<F>([] (std::size_t a) { return a; })) {
    return (begin == end) ? (*k)(0) : lengthKHeap(std::next(begin), end, std::make_unique<F>([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<class F>
auto make_copyable_function(F&& f) {
    auto spf = std::make_shared<std::decay_t<F>>(std::forward<F>(f));
    return [spf] (auto&&... args) -> decltype(auto) { return (*spf)(decltype(args)(args)...); };
}

template<class IteratorT>
std::size_t lengthKHeap(IteratorT begin, IteratorT end, std::unique_ptr<F>&& k = std::make_unique<F>([] (std::size_t a) { return a; })) {
    return (begin == end) ? (*k)(0) : lengthKHeap(std::next(begin), end, std::make_unique<F>(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<void()>;

struct Then {

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

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

private:

    std::vector<NodeT> m_nodes;
};

...

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

    auto then = Then();

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

    then();

    std::cout << i << 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.


Full Code

#include <functional>
#include <memory>

template<class IteratorT>
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<std::size_t(std::size_t)>;

template<class IteratorT>
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<class F>
auto make_copyable_function(F&& f) {
    auto spf = std::make_shared<std::decay_t<F>>(std::forward<F>(f));
    return [spf] (auto&&... args) -> decltype(auto) { return (*spf)(decltype(args)(args)...); };
}

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

#include <functional>
#include <vector>

using NodeT = std::function<void()>;

struct Then {

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

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

private:

    std::vector<NodeT> m_nodes;
};

#include <list>
#include <vector>
#include <iostream>

int main() {

    {
        auto const list = std::vector<int>{ 0, 1, 2, 3 };

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

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

            auto then = Then();

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

            then();

            std::cout << i << std::endl;
        }
    }
}
\$\endgroup\$

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.