RE: The Paradox of Partial Parametricity

Following Tab's comments on the a Promise monad, I prototyped a Future library based on DOM Future using TypeScript. Since TS has no concept of a union type, I'm using TS overloads to approximate the Ref<T> union type example. It has roughly the following API:

```ts
class FutureResolver<T> {
  accept(value: T): void;
  resolve(value: Future<T>): void;
  resolve(value: T): void;
  reject(value: any): void;
}

class Future<T> {
  constructor(init: (resolver: FutureResolver<T>) => void);

  // unconditional lift
  static accept<TResult>(value: TResult): Future<TResult>;

  // autolift
  static resolve<TResult>(value: TResult): Future<TResult>;
  static resolve<TResult>(value: Future<TResult>): Future<TResult>;

  static reject<TResult>(value: any): Future<TResult>;

  // assimilation of thenables, similar to `Q()`. Assimilation stops at the first `Future`
  static from<TResult>(value: any): Future<TResult>;

  // autolifting then.
  // for `p.map` like operation, `resolve` should return `Future.accept(u)`
  // for `p.flatMap` like operation, `resolve` can return u or `Future.resolve(u)`, but no error is thrown
  then<TResult>(resolve: (value: T) => Future<TResult>, reject: (value: any) => Future<TResult>): Future<TResult>;
  then<TResult>(resolve: (value: T) => TResult, reject: (value: any) => Future<TResult>): Future<TResult>;
  then<TResult>(resolve: (value: T) => Future<TResult>, reject: (value: any) => TResult): Future<TResult>;
  then<TResult>(resolve: (value: T) => TResult, reject: (value: any) => TResult): Future<TResult>;

  catch<TResult>(reject: (value: any) => Future<TResult>): Future<TResult>;
  catch<TResult>(reject: (value: any) => TResult): Future<TResult>;

  done(resolve: (value: T) => void, reject: (value: any) => void);
}
```

In the AsyncTable example you would write:

```ts
class AsyncTable<T, U> {
  private m = new Map<T, U>();

  set(keyP: Future<T>, val: U): void {
    keyP.done(key => { this.m.set(key, val); });
  }

  get(keyP: Future<T>): Future<U> {
    return keyP.then(key => Future.accept(this.m.get(key))); // accept causes an unconditional lift.
  }
}
```

In Mark's second example, using the union type, you might instead have:

```ts
class AsyncTable<T, U> {
  private m = new Map<T, Future<U>>();

  set(keyP: Future<T>, val: Future<U>): void;
  set(keyP: Future<T>, val: U): void;
  set(keyP: Future<T>, val: any): void {
    keyP.done(key => { this.m.set(key, Future.resolve(val)); }); // autolift `Ref<U>`-like union to `Future<U>`
  }

  get(keyP: Future<T>): Future<U> {
    return keyP.then(key => this.m.get(key)); // no need for unconditional lift, `then` will merge the already auto-lifted `Future<U>`
 }
}
```

And Mark's third example might be:

```ts
class AsyncTable<T, U> {
  private m = new Map<T, Future<U>>();

  // gah! TS needs union types...
  set(keyP: Future<T>, val: Future<U>): void;
  set(keyP: T, val: Future<U>): void;
  set(keyP: Future<T>, val: U): void;
  set(keyP: T, val: U): void;
  set(keyP: any, val: any): void {
    Future.resolve(keyP).done(key => { this.m.set(key, Future.resolve(val)); });  // autolift key and val
  }

  get(keyP: Future<T>): Future<U>;
  get(keyP: T): Future<U>;
  get(keyP: any): Future<U> {
    return Future.resolve(keyP).then(key => this.m.get(key)); // autolift key, val is already a `Future<U>`
  }
}
```

Ron

From: es-discuss-bounces@mozilla.org [mailto:es-discuss-bounces@mozilla.org] On Behalf Of Claude Pache
Sent: Friday, May 10, 2013 11:25 AM
To: Mark S.Miller
Cc: public-script-coord@w3.org; es-discuss
Subject: Re: The Paradox of Partial Parametricity


Le 10 mai 2013 à 14:55, Mark S. Miller <erights@google.com<mailto:erights@google.com>> a écrit :


[+es-discuss]

I didn't realize that I composed this in reply to a message only on public-script-coord. Further discussion should occur only on es-discuss. Sorry for the confusion.

On Fri, May 10, 2013 at 5:52 AM, Mark S. Miller <erights@google.com<mailto:erights@google.com>> wrote:

I think the key exchange in these threads was

On Fri, May 3, 2013 at 4:17 PM, Jonas Sicking <jonas@sicking.cc<mailto:jonas@sicking.cc>> wrote:
[...]
I.e. permitting nested promises creates a more complex model and with
that you always get more confusion and more questions.

 On Sat, May 4, 2013 at 1:48 AM, Claus Reinke <claus.reinke@talk21.com<mailto:claus.reinke@talk21.com>> wrote:
[...]
>From the perspective of a-promise-is-just-like-other-wrapper-classes,
auto-flattening promises creates a more complex model


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 clarity I define the following APIs so I can define the three architectural choices in terms of the subset of these APIs they contain. Obviously, I do not intend to start a bikeshed yet on the particular names chosen for these operations. Let's stay focused on semantics, not terminology.

An upper case type variable, e.g. T, is fully parametric. It may be a promise or non-promise.
A lower case type variable, e.g. t, is constrained to be a non-promise. If you wish to think in conventional type terms, consider Any the top type immediately split into Promise and non-promise. Thus type parameter t is implicitly constrained to be a subtype of non-promise.




Ref<T> is the union type of T and Promise<T>.

Q.fulfill(T) -> Promise<T> // the unconditional lift operator

Q(Ref<t>) -> Promise<t> // the autolift operator

p.map: Promise<T> -> (T -> U) -> Promise<U>

p.flatMap: Promise<T> -> (T -> Promise<U>) -> Promise<U>
// If the onSuccess function returns a non-promise, this would throw an Error,
// so this type description remains accurate for the cases which succeed.

p.then: Promise<T> -> (T -> Ref<u>) -> Promise<u>
// Ignoring the onFailure callback



* 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.



Hello,

With this explanation, from my perspective (as someone who has never used promises, but rejoices in advance to use them), the Q-like model of promise seems far superior to me:

* lifting (for non-promises) + no-op (for promises) is advantageously replaced by one method, autolifting (working with both);
* `flatMap` (for promises) + `map` (for non-promises) is advantageously replaced by one method, `then` (working with both);

It follows that:
* it is impossible to have a promise for a promise, reducing the probability of bugs;
* it makes it easier to write generic algorithms that work for both non-promises and promises;
* in many situations, there is no need to ask oneself if one should provide a promise or a non-promise, reducing the burden of thinking to programmers and therefore the probability of bugs.

Not wanting to ask oneself «Should I provide a promise or a value?» is not sloppiness, but it is because promises are just uninteresting wrappers. I never ask myself: «Should I provide a string or a String object to the `substring` method?», because it doesn't matter, and the String object is just an uninteresting wrapper. And to push the comparison further: it is dubious, and hopefully impossible, to wrap a String object in another String object, just like it is dubious to have a promise for a promise.





<snip>

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.

Indeed, the advantages I have mentioned vanished if we add unconditional lifting to autolifting + `then`, because its bare use forces the programmer to think what type of object he should provide (a promise or a non-promise) in some situations. If you allow me to do a somewhat shaky comparison, the usefulness of ASI is greatly reduced by the few situations where ASI does not work; therefore most style guides recommend to not use ASI at all.


-Claude




--
    Cheers,
    --MarkM