Changing a loop into a promise or task chain


If you are dealing with PPL Tasks in C++ or Promises in JavaScript, you run into the problem of having to rephrase loops in the form of callbacks. (On the other hand, if you're using Tasks in C#, then you have the wonderful await keyword to do this all for you. If you're a JavaScript programmer, you can look at the async keyword coming to ES7. If you are using C++ resumable functions, then you can use __await. More about resumable functions. Still more. )

Let's convert a loop into a promise/task chain. Here's the loop:

std::vector<std::unique_ptr<Thing>> things;

void FrobEachThing()
{
    for (auto thing : things) {
       thing->FrobAsync();
    }
}

The problem is that the Frob­Async method is asynchronous and returns a task, and we want to perform each frob operation in series, not in parallel. If we were writing in C#, this would be a piece of cake:

async Task FrobEachThingAsync()
{
    foreach (var thing in things) {
        await thing.FrobAsync();
    }
}

Similarly, if we had resumable functions:

task<void> FrobEachThingAsync()
{
    for (auto thing : things) {
       __await thing->FrobAsync();
    }
}

But we don't have that, so we will need to do the transformation ourselves.

At this point, you think back to Computer Science class and that stuff you learned about recursion and you wondered when anybody would ever want to do that. Well, we're going to do that.

The idea is that we start the asynchronous operation, and pass as a callback a function that knows how to continue the loop. Since this is a loop, the callback may end up passing itself as the next callback, and that's where we get the appearance of recursion. (It's not really recursion because the creation of the task returns immediately; the callback runs when the task completes, which is some time later.)

First, let's write out what that ranged for loop really means:

void FrobEachThing()
{
    auto first = begin(things);
    auto last = end(things);
    while (first != last) {
        (*first)->FrobAsync();
        first++;
    }
}

With this formulation, it's easier to see how to make it recursive. Actually, the important thing is that you make it tail-recursive.

typedef decltype(begin(things)) thing_iterator;

void FrobTheRestOfTheThings(
    thing_iterator first,
    thing_iterator last)
{
    if (first != last) {
        (*first)->FrobAsync();
        FrobTheRestOfTheThings(first + 1, last);
    }
}

void FrobEachThing()
{
    FrobTheRestOfTheThings(begin(things), end(things));
}

Now that we have tail recursion, we can make it into a task chain:

task<void>
FrobTheRestOfTheThingsAsync(
    thing_iterator first,
    thing_iterator last)
{
    if (first != last) {
        return (*first)->FrobAsync().then([first, last]() {
            return FrobTheRestOfTheThingsAsync(first + 1, last);
        });
    } else {
        return create_task([](){}); // null task - base case of recursion
    }
}

task<void> FrobEachThingAsync()
{
    return FrobTheRestOfTheThingsAsync(begin(things), end(things));
}

The same logic applies to JavaScript. Starting with

function frobEachThing()
{
    things.forEach(function(thing) { thing.Frob(); });
}

First, do the rewrite into an explicit loop.

function frobEachThing()
{
    var i = 0;
    while (i < things.length) {
        things[i].frob();
        i++;
    }
}

Then apply the same logic as above to convert this into a promise chain:

function frobTheRestOfTheThingsAsync(array, index, length) {
    if (index != length) {
        return array[index].frobAsync().then(function() {
            return frobTheRestOfTheThingsAsync(array, index + 1, length);
        });
    } else {
        return WinJS.Promise.wrap(); // null task - base case of recursion
    }
}

function frobEachThingAsync()
{
    return FrobTheRestOfTheThingsAsync(things, 0, things.length);
}

JavaScript captures by reference and uses garbage collection, so things are a bit easier. We can make one function local to the other and let the closures capture our state.

function frobEachThingAsync()
{
    var array = things;
    var length = array.length;
    var index = 0;

    function rest() {
        if (index != length) {
            return array[index].frobAsync().then(function() {
                index++;
                rest();
            });
        } else {
            return WinJS.Promise.wrap(); // null task - base case of recursion
        }
    }

    return rest();
}

Bonus reading: How to put a PPLTasks continuation chain into a loop.

Comments (26)
  1. Another good option for JavaScript developers that’s available today (ES2015) is to have a generator that yields promises. That way you can have the compiler do all the awkward rewriting, and your own code is almost as clean as async/await.

  2. Bob says:

    Once you got rid of the ranged loop, don’t you miss out on frobbing the last thing? Perhaps the

    (*first)->FrobAsync();

    should be outside the if.

    1. voo says:

      No the code’s correct. Remember that end() points to one past the last element of the container.

  3. Brad Barber says:

    You can simplify the javascript version by using [].reduce – check out the collection portion of the following article: http://taoofcode.net/promise-anti-patterns/

  4. nikos says:

    Stroustrup et al are turning C++ into C#, little by little. I have stopped following them. What’s the point? All these funny constructs take more to understand than to do the equivalent in the “traditional” way. Just use a signal and wait for it. Case closed. No fuss, no headache, no room for mistakes. If you want to show off, start writing poetry :)

    1. Kevin says:

      I agree with you that adding async makes C++ more like C#. Specifically, it *simplifies* the language, by making certain things easier to express. And that does bring C++ closer to C#, because C++ has so very far to go in that department (just look at template metaprogramming, or better yet, don’t, lest your head explode).

    2. voo says:

      “All these funny constructs take more to understand than to do the equivalent in the “traditional” way. Just use a signal and wait for it.”
      The whole point of asynchronous programming is to *not* wait around and block threads. Now I’d argue that your preferred solution certainly isn’t any easier than the shown async solution, but it doesn’t matter since you’re doing something completely different.

      As someone who has written enough asynchronous code in several languages, the compiler transformations done by C# make the code vastly easier to understand and maintain than having nested callbacks everywhere. Yes C++ is taking some of C#’s features and by doing so they’re turning it into a better, safer language.

      Computing is a fast moving field, if you stop learning new things you’ll quickly become a dinosaurs who’s eclipsed by the younger generation.

      1. nikos says:

        well the particular example is about waiting so most of your comments are irrelevant

        1. voo says:

          No it’s not and understanding that basic idea is what asynchronous programming is all about. If you look at

          task FrobEachThingAsync()
          {
          for (auto thing : things) {
          __await thing->FrobAsync();
          }
          }

          the thread executing FrobEachThingAsync is *not* blocked while thing->FrobAsync() is being executed.

          It may actually be used to execute FrobAsync() or it might do some completely different task, you don’t know. But what it won’t do is being blocked waiting on a signal.

          1. nikos says:

            perhaps I need to look this up closer, but if the main thread is not blocked, what’s the point of the “await” keyword? Isn’t that waiting (blocking)?

          2. Voo says:

            There’s a pretty good introduction by Eric Lippert at https://msdn.microsoft.com/en-us/magazine/hh456401.aspx

            In the simplest terms await on a task signifies that anything following await should only be executed after the task is finished. But instead of blocking you release the thread to thread pool and allow it to do other work. As soon as the awaited task is finished a thread from the thread pool continues execution where the earlier task left off.

            This minimizes resource allocation and maximizes utilization at the cost of some extra scheduling cost.

            Nitpicker’s corner: yes vastly simplified, I do know what synchronization contexts and co are.

          3. Mason Wheeler says:

            Nikos: No, it’s *awaiting*. Essentially, the function returns at this point and execution can continue, (non-blocked,) but when the awaited task finishes, execution goes back to continue with the remainder of the function.

            If this seems strange, consider a GUI application. You click a button, and it fires off a frob() operation, which takes a long time. You don’t want to freeze the UI for a long time waiting for this to complete, so you await it, and when it finishes, it pushes a special message onto the event queue that, when handled, invokes a callback that executes the rest of your click handler.

          4. nikos says:

            so what you guys are saying is that the thing IS blocking but you get a local pump for free so that the GUI stays responsive. We all have code to do that already. But thanks for the clarification

          5. Voo says:

            Yes we already had this functionality beforehand, just as machine code can do absolutely everything that higher level languages can do.

            The point is that await makes writing asynchronous code orders of magnitudes easier. Otherwise you either end up with a state machine in your explicit message loop (and that option is right out if you’re using thread pools) or nested callbacks. Both solutions make code pretty unmaintainable.

          6. “the thing IS blocking but you get a local pump for free so that the GUI stays responsive.”

            It doesn’t run a local pump. it returns back to the main pump. The main pump then calls back into the function when the awaited operation completes. This is an important distinction, because returning back to the main pump avoids the problem of the stack with no support. It also means that if two tasks take turns running, they do not call each other recursively. The stack unwinds completely when each task pauses.

    3. McBucket says:

      C++ has always been a bit of a magpie with regards to its features (hey, it started as a better C, after all); Bjarne’s term is “multi-paradigm”. An early premise of C++ was that “you don’t pay for what you don’t use”, and so if you want to program C++ like C (or use whatever your version of the “traditional way” is), then go ahead. But some folks do value borrowings from other languages, even C# (the horror!) and find it can make programming a lot simpler, clearer and more expressive. The one feature that C++ has over the C#s and Javas of this world is, however, the automatic calling of destructors on scope exit; that one feature means that C++ won’t turn into C# any time soon, modulo major changes in C++ or C# syntax/philosophy.

      1. nikos says:

        I am all in for “progress” and increased conveniences, but all these stuff like lambdas and what this article introduced me to are not my cup of tea. For example they make debugging harder, and who knows what subtle assumptions they involve? Better the devil you know :)

        1. McBucket says:

          Simple; don’t use them, then. I’m a bit at a loss of how “they make debugging harder” or these mysterious “subtle assumptions” that you allude to; lambdas seem pretty well-defined, though like anything, you need to get used to the new syntax. But with respect to your sentiment, you’re not alone; C++ is a demonstrably larger language now, with lots more constructs and functionalities to take in, and code bases don’t automatically convert to newer, safer practices automatically. See for example: http://simpleprogrammer.com/2012/12/01/why-c-is-not-back/

          1. nikos says:

            wrt debugging: it’s like setting a breakpoint on a preprocessor macro. You can’t see clearly what’s going on. There is some opaque piece of code that you cannot examine

          2. McBucket says:

            nikos: I am able to put a breakpoint on code inside a lambda, using Visual Studio 2012. Works fine (subject to the usual release vs debug optimizations and/or inlining). It’s really just a function call, after all, and not at all like a preprocessor macro.

  5. C++ really needs syntax highlighting…

    1. McBucket says:

      Syntax highlighting isn’t part of the C++ language; it’s a part of tools that display C++ code (like code editors); many code editors/IDEs do indeed perform syntax highlighting on C++. But ok, accepting your premise, what exactly would you highlight, and how (and why)?

  6. Ben Hutchings says:

    For the C++ version, I think it would be better to use “++first” rather than “first + 1”. Using the latter adds the requirement that the iterators be RandomIterators and not just ForwardIterators.

  7. Frank says:

    Why not do the loop now and chain the asyncs?

    something like (didn’t test):

    auto task = create_task([](){});
    for (auto thing : things) {
    task = task.then([]() {
    thing->FrobAsync();
    };
    }

    1. Yeah, that seems much nicer.

  8. You can do something cooler in JavaScript to

    `return things.reduce(function(previous, current) {
    return previous.then(function() {
    return current.frobAsync();
    });
    }, WinJS.Promise.as());`

Comments are closed.

Skip to main content