Callback ordering

[briancavalier]

I had this issue come up recently while discussing tick conflation algorithms with when.js contributor @Twisol. Given this:

var p, f, g, h;
p = // let p be an already-fulfilled promise
f = g = h = function() {}; // Note: no additional asynchrony introduced

p.then(f).then(g);
p.then(h);

In what order should f, g, and h be called? Promises/A+ currently says that f must be called before h, and that f must be called before g. It doesn't say anything about the relationship between g and h, so currently, afaict, both sequences, fgh and fhg, are correct.

I quickly tested current implementations of when.js, avow, and Q, and all 3 do breadth-first: fhg.

Anyone have any thoughts on this? I'm not necessarily saying we should (or even could) specify anything, but more just opening up the discussion to see where it leads.

[Twisol]

Glad to see that this was raised for discussion. 😄 Just to throw my own argument into the pot...

I argue that the fgh order is the correct one. Conceptually, f and g are two adjacent parts of a single pipeline of data. Allowing h to intercede creates a form of pre-emptive multitasking: code may inject itself between any two handlers. But if fg is allowed to fully evaluate before h, then the only locations where code may be injected is where a promise is explicitly named. This makes it much easier to analyze the behavior of a stimulus as it traverses the dependency tree, because you can simply follow the named promises and their then handlers.

Naturally, if f returns a promise that won't resolve until later, g won't execute until after h. But that's explicitly part of f's semantic contract, and dependencies must be able to handle that. It's all much more explicit.

[lsmith]

The relationship between f and g is user-defined, not structural to the promise code. Each promise establishes an individual contract for its then() "subscribers", unrelated to other promises.

The order of f before h is guaranteed, and f before g is guaranteed, but there is no relationship between g and h.

I translate the code to the following English statements:
"I promise that when p resolves to a value, I'll call g."
"I promise that when g is called and resolves to a value, I'll call h."
"I promise that when p resolves to a value, I'll call h."

[novemberborn]

Interesting!

I was going to argue for fhg because it'd be easier to implement, until I tried with Legendary:

var legendary = require("legendary");
var p = legendary.fulfilled();
function f(){ console.error("f"); };
function g(){ console.error("g"); };
function h(){ console.error("h"); };

p.then(f).then(g);
p.then(h);

Which actually outputs fgh!

This happens because the internal promise for p.then(f) is resolved synchronously after f has returned. That's nice and all but does lead to a stack overflow when chaining > 4656 promises (in Node). Which brings me full circle to arguing that fhg is easier to implement, if I'd resolve promises asynchronously.

[Twisol]

I'm going to sit out of the argument for a bit, but FWIW...

Which brings me full circle to arguing that fhg is easier to implement, if I'd resolve promises asynchronously.

I've implemented it in my own branch of when.js, and it's actually quite simple. Feel free to peruse if you want to compare and contrast the implementations.

[domenic]

I am with @lsmith that this is not really up to the implementation. In particular, the fact that it's impossible to provide a consistent ordering in the general case, where promises are not immediately fulfilled, seems to nix any idea of specifying an order for the specific case of already-settled promises.

[novemberborn]

@Twisol:

I've implemented it in my own branch of when.js, and it's actually quite simple. Feel free to peruse if you want to compare and contrast the implementations.

Yea, as soon as I wrote my earlier commented I wanted to try out a trampoline. No optimizations or solid tests but seems to work.

@domenic:

I am with @lsmith that this is not really up to the implementation. In particular, the fact that it's impossible to provide a consistent ordering in the general case, where promises are not immediately fulfilled, seems to nix any idea of specifying an order for the specific case of already-settled promises.

If we don't specify an order, then surely it is up to the implementation?

[domenic]

@novemberborn right, indeed, misspoke :).

[Twisol]

I know I said I'd sit out - I wanted to see how this progressed without reiterating arguments I've already made to @briancavalier - but I thought of something new. Sorry!

The whole point of promises, from my perspective, is to allow you to write code that appears synchronous over future values. That suggests an obvious symmetry between synchronous and asynchronous code. Consider:

p.then(f).then(g);
p.then(h);

Would the synchronous analogue not be this?

g(f(p));
h(p);

That's phenomenally awesome, in my opinion. It's a very simple and straightforward translation, and it suggests that then is simply function application within a future thread of execution. You don't need to do any complicated mental gymnastics, because your experience with synchronous processes immediately applies to promise-based processes as well.

But how does evaluation order fit in? Unless something very fishy is going on, synchronous code follows the fgh order. Yet, it's that very property that's under debate here. The fhg order breaks this fundamental symmetry between asynchronous and synchronous code, and introduces a subtle new barrier to learning that must be overcome, and a new mental context that must be juggled. Besides, I'm not even sure if there is a synchronous analogue under this model. Whatever it is, it has to allow for other arbitrary functions to be run between f and g.

[domenic]

@Twisol how do you respond to the fact that if f returns a pending promise, it will be literally impossible for fgh order to take place?

I think the synchronous analog of such a situation does not exist; rather, the asynchronous analog of

g(f(p));
h(p);

is

p.then(function (pResult) {
  f(pResult).then(function (fResult) {
    g(fResult).then(function () {
      h(pResult);
    });
  });
});

[Twisol]

@Twisol how do you respond to the fact that if f returns a pending promise, it will be literally impossible for fgh order to take place?

Two points:

1. That's down to the fact that resolve, as specified, is both a bind and a join (in Haskell terms). Speaking from a pure point of view, if f returns a promise, that promise is what should be provided to g, not its resolved value. However, that kind of thing is simply irritating in Javascript, so we move on to...
2. If f returns a promise, that's part of its public API. It should be known to consumers of its results that there will be a delay before any handlers are executed. Compare to the fhg alternative, where regardless of the result of f, arbitrary functions may insert themselves in-between. There is no way to explicitly call it out, because it's pervasive and non-obvious.

[domenic]

The entire point of then's behavior on return is that it doesn't matter whether you return a promise or a non-promise. That should be an invisible refactoring that does not change the semantics of the code executed. Saying that it's part of the public API whether the handler returns a promise or a non-promise value is just not true. Maybe in typed Haskell land, but not in JavaScript.

If you want order guarantees between g and h, write your code like in my example above. Otherwise, you should have no expectations.

[Twisol]

The entire point of then's behavior on return is that it doesn't matter whether you return a promise or a non-promise. That should be an invisible refactoring that does not change the semantics of the code executed.

As I said: anything else is freaking annoying in Javascript. I raise it for theoretical grounding, not suggested semantics. 😄

[Twisol]

Saying that it's part of the public API whether the handler returns a promise or a non-promise value is just not true. Maybe in typed Haskell land, but not in JavaScript.

But it necessarily must be. Even with the status quo, this code will execute differently based on if f returns a promise:

p.then(f).then(g);
p.then(h).then(i);

Returns a promise: fhig
Returns a regular value: fhgi

[domenic]

Yes. That's my point. Order is not guaranteed, unless you explicitly do ordering with then.

[domenic]

Implementations don't necessarily have to choose fhig for the "returns a promise case"; they could choose anything that satisfies f < g, h < i, and f < h. An implementation could easily choose fhgi, e.g. if it buffers fulfillments for 100 ms.

[Twisol]

No, of course you're right about that. I just think that, in the same way that a random walk leaves something to be desired, an approach symmetric with synchronous code is easier to analyze.

I'll return to the background for now. 😄

[domenic]

All I'm saying is you have your sense of symmetry wrong. See my example upthread. The only way to guarantee the same order of synchronous code is to actually explicitly lay out that order by putting your calls inside then callbacks.

[domenic]

In particular,

p.then(f).then(g);
p.then(h);

has no synchronous analog, since in synchronous code, two operations (in this case f and h) cannot be taking place concurrently. (Note that even if f is initiated before h, they still take place concurrently, and either one could finish before the other. This last part is the crux of the asymmetry.)

[Twisol]

I've love to discuss this with you one-on-one, because I'm not sure what you mean. I'm currently in the #cujojs channel on Freenode, but I can go elsewhere too. If you're cool with that, send me a private message or something.

[domenic]

Maybe later; gotta head home and dinner and stuff now. Hopefully someone else can clarify, although I think my original example was clear as well.

[briancavalier]

I think we're all in agreement here that Promises/A+ simply can't make a guarantee for any and all possible f's, g's, and h's (and developers will use any and all possible!). Let's just help developers embrace the g/h nondeterminism, and force them to guarantee order by using then "correctly", i.e. if g before h is a requirement, the developer must guarantee it:

p.then(f).then(g).then(h)

Closing, but as always, if there's a reason to reopen, feel free.

[jkroso]

I think its perfectly doable. The idea of writing async code which parallels sync is generally interesting too.