Re: The Paradox of Partial Parametricity

On Fri, May 10, 2013 at 5:52 AM, Mark S. Miller <erights@google.com> wrote:
> Together with each of their explanations about what they meant. They are
> both right. Lifting and auto-lifting do not mix. Q Promises give us
> autolifting with no lifting. Monadic promises would give us lifting but no
> autolifting. Having both in one system creates a mess which will lead
> programmers into the particular pattern of bugs Jonas warns about in his
> message.

(For the benefit of those confused, "auto-lifting" is what has been
termed elsewhere "conditional lifting". It's what Future.resolve()
does: if passed a promise, it returns a new promise chained from it
(as if you'd called p.then() with no arguments); if passed anything
else, it returns a new promise that immediately accepts with that
value.)

I have no idea why you're trying to claim that "monadic promises"
gives no auto-lifting.  Perhaps you've gotten yourself confused over
the proposals, and have reverted to a particularly strict view of what
"monadic promises" means?

The proposal called "monadic promises" implies nothing more than that,
if the value returned by a .then() callback is a promise, one level of
unwrapping will occur.  If you purposely return a nested promise, we
won't strip out *all* the levels, only the outermost.

There's nothing about this that is incompatible with a conditional
lift operator, a la Future.resolve().  Nor is there any reason to
believe that the presence of Future.resolve() would lead to bugs.
This confuses me - adding Future.resolve() makes nested futures no
more likely (it can't create them), and *not* adding it makes some
code patterns (where you want to accept either a value or a promise
for the value, and work consistently in both situations) more
difficult to code for.

> * A Monadic promise system would have Q.fulfill, p.map, and p.flatMap.
>
> * A Q-like promise system would have Q, and p.then
>
> * The dominant non-Q-like proposal being debated in these threads has
> Q.fulfill, Q, and p.then.
>
> This note explains why I believe the last is much worse than either of the
> other two choices. As Jonas points out, generic code, to be useful in this
> mixed system, has to be careful and reliable about how much it wraps or
> unwraps the payloads it handles generically. Had programmers been armed with
> .map and .flatMap, they could succeed reliably. Arming them only with .then
> will lead to the astray. As an example, let's start with a variant of Sam's
> async table abstraction. The parts in angle brackets or appearing as type
> declarations only documents what we imagine the programmer may be thinking,
> to be erased to get the real code they wrote. In this abstraction, only
> promises for keys are provided. The get operation immediately returns a
> promise for the value that will have been set. (An interesting variant is a
> table that works even when the get arrives first. But we can ignore this
> wrinkle here.)
>
>
>     class AsyncTable<T,U> {
>         constructor() {
>             this.m = Map<T,U>(); // encapsulation doesn't matter for this
> example
>         }
>         set(keyP :Promise<T>, val :U) {
>             keyP.then(key => { this.m.set(key, val) });
>         }
>         get(keyP :Promise<T>) :Promise<U> {
>             return keyP.then(key => this.m.get(key));
>         }
>     }
>
> When U is a non-promise, the code above works as intended. The .then in the
> .get method was written to act as .map. When tested with U's that are not
> promises, it works fine. But when U is actually Promise<V>, the .get method
> above returns Promise<V> rather than Promise<U>. As far as the author is
> concerned, the .then is functioning as a broken .map in this case, with the
> signature
>
> p.then: Promise<T> -> (T -> U) -> Promise<V>  // WTF?

Yes, if you're writing generic code that may return either a plain
value or a promise, you have to wrap your return value in another
promise.  The .then() magic (acting like either map() or flatMap(),
depending on the return value's type) is more convenient for normal
usage, but less convenient for people writing more generic code.

The "unabashed monadic" version is more predictable for generic code,
but less convenient for normal code (you have to be sure of whether
your return value is a plain value or a promise, while .then() lets
you ignore that for the most part).

The Q version (auto-flattening all the time, no nested promises) is
predictable both ways, but at the cost of erasing an entire class of
use-cases where you want to be able to interact with a promise
reliably without regard to what's inside of it.  (In other words, it
becomes less predictable in regards to *time*, as what you thought
would just be a retrieval delay might turn into a larger delay while
the "inner" promise waits to be fulfilled.)

> In a system with autolifting, you can't get full parametricity of promises
> simply by adding an unconditional lift. You have to remove, or at least
> strongly discourage, autolifting. Or you have to take pains to carefully
> work around it.
>
> The main failure mode of standards bodies is to resolve a conflict by adding
> the union of the advocated features. Here, this works even worse than it
> usually does. The coherence of lifting depends on the absence of
> autolifting, and vice versa. We need to make a choice.

Nope, the correct way to write the code in the proposed version (with
.then() and both types of lifting) is:

     class AsyncTable<T,U> {
         constructor() {
             this.m = Map<T,U>();
         }
         set(keyP :Promise<T>, val :U) {
             keyP.then(key => { this.m.set(key, val) });
         }
         get(keyP :Promise<T>) :Promise<U> {
             return keyP.then(key => Q.fulfill(this.m.get(key)));
         }
     }

Or, using Future terminology and erasing the types:

     class AsyncTable {
         constructor() {
             this.m = Map();
         }
         set(keyP, val) {
             keyP.then(key => { this.m.set(key, val) });
         }
         get(keyP) {
             return keyP.then(key => Future.accept(this.m.get(key)));
         }
     }

(Alternately, we could wrap the value in a promise in the set()
function, and then just return it in the get() function.  It doesn't
matter *where* the wrapping happens, just that it happens somewhere,
if you want to be generic.)

And we can do even better!  Let's make the two functions accept
promises *or* plain values as keys:

     class AsyncTable {
         constructor() {
             this.m = Map();
         }
         set(key, val) {
             Future.resolve(key).then(key => { this.m.set(key, val) });
         }
         get(key) {
             return Future.resolve(key).then(key =>
Future.accept(this.m.get(key)));
         }
     }

Easy and convenient!

~TJ

Received on Friday, 10 May 2013 18:49:30 UTC