Re: The Paradox of Partial Parametricity

[Forgot to pick up es-discuss in this message. >_<]

On Fri, May 10, 2013 at 11:42 AM, Tab Atkins Jr. <jackalmage@gmail.com> wrote:
> 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 20:01:47 UTC