Promise の all と race だけで書ける待ち合わせ、書けない待ち合わせ

ECMAScript 2015 で導入された [Promise](http://www.ecma-international.org/ecma-262/6.0/#sec-promise-objects) の関数 `all` と `race` だけで表現できる非同期処理の待ち合わせについての考察です。

考察の対象とした待ち合わせの条件は、「過半数の `Promise` が解決されるまで待つ」をはじめとした特殊なものです。**結論からいうと、`all` と `race` だけを組み合わせて、多数決による待ち合わせを表現可能です。**ただし、与えられた Promise の解決順序に依存する待ち合わせは、`all` と `race` だけで~~は書けません（ただし証明はできてないです~~ **追記2020/11/08** 書けるようです（否定的に証明されました）。


# 制約条件

`Promise#then` を使えば、なんでもできてしまいます。
そのため、この後の議論では `Promise#then` は封印します。 :pray: 


# 待ち合わせの書き方

まず、待ち合わせの表現方法を導入します。

非同期に解決される Promise `A`, `B`, `C` があり、それぞれ `a`, `b`, `c` という値で解決されるとします。
さらに、これらの Promise に A → B → C のように解決される順序の組み合わせがあると考えます。
この解決順序に対応する待ち合わせの完了タイミングを表として書けば、待ち合わせの特性をうまく表現できます:

| 解決順序（Promiseが3つの場合） | 待ち合わせが完了すべきタイミング  |
|:-:|:-:|
| A → B → C | （例：A → B → 完了） |
| A → C → B |  |
| B → A → C |  |
| B → C → A |  |
| C → A → B |  |
| C → B → A |  |

なお、注意点が一つあります。

**「A → B → 完了」と書かれている場合、ここに列挙されていない C の Promise が解決される/されないに関わらず、結果の Promise は完了する必要があります。**つまり、C が永遠に解決されない Promise であったとしても、A の後に B が解決されれば、結果の Promise も解決されるべきです。

では、具体的な例として `Promise.all` と `Promise.race` の表を見てみましょう。


# 単純な例
## すべてが解決されるまで待つ（`Promise.all`）

すべて解決されるまで待つ待ち合わせは、`Promise.all([A, B, C])` ですね。
これは次のような表になります:

| 解決順序 | 待ち合わせが完了すべきタイミング |
|:-:|:-:|
| A → B → C | A → B → C → 完了 |
| A → C → B | A → C → B → 完了 |
| B → A → C | B → A → C → 完了 |
| B → C → A | B → C → A → 完了 |
| C → A → B | C → A → B → 完了 |
| C → B → A | C → B → A → 完了 |



## どれか一つが解決されるまで待つ（`Promise.race`）

どれか一つが解決されるまで待つ待ち合わせは、`Promise.race([A, B, C])` です。
これは次のような表になります:

| 解決順序 | 待ち合わせが完了すべきタイミング |
|:-:|:-:|
| A → B → C | A → 完了 |
| A → C → B | A → 完了 |
| B → A → C | B → 完了 |
| B → C → A | B → 完了 |
| C → A → B | C → 完了 |
| C → B → A | C → 完了 |

このように、渡された Promise のうち、すべて/どれか一つが解決されるまで待機する待ち合わせは `Promise.all` と `Promise.race` で簡潔に書けます。


# ちょっと複雑な例

では、もう少し複雑な例を見てみましょう。


## 3つのうち2つが解決されるまで待つ

渡された3つの Promise のうち、2つが解決したら解決する待ち合わせを考えます。
この待ち合わせは、次のような表になります：

| 解決順序 | 待ち合わせが完了すべきタイミング |
|:-:|:-:|
| A → B → C | A → B → 完了 |
| A → C → B | A → C → 完了 |
| B → A → C | B → A → 完了 |
| B → C → A | B → C → 完了 |
| C → A → B | C → A → 完了 |
| C → B → A | C → B → 完了 |

さて、これを実現するには、どのようにすればいいでしょうか。
実は、次のように `Promise.all` と `Promise.race` を組み合わせることで実現できます：

```js
Promise.race([
  Promise.all([A, B]),
  Promise.all([B, C]),
  Promise.all([C, A]),
]);
```

実際に、[JSFiddle](https://jsfiddle.net/0teeq8m8/2) で動作を試せます。


## n 個の Promise のうち、m 個が解決されるまで待つ

前の例を一般化してみましょう。
与えられた n 個の Promise のうち、m 個が解決されるまで待機する待ち合わせを考えます：

| 解決順序 | 待ち合わせが完了すべきタイミング |
|:-:|:-:|
| X1 → X2 → ... → Xn-1 → Xn | X1 → X2 → ... → Xm → 完了 |
| X1 → X2 → ... → Xn → Xn-1 | X1 → X2 → ... → Xm → 完了 |
| ... | ... |
| Xn → Xn-1 → ... → X2 → X1 | Xn → Xn-1 → ... → Xn-m → 完了 |

この処理は次のように書けます：

```js
Promise.race([
  Promise.all([X1, X2, X3, ..., Xm]),
  Promise.all([X1, X3, X4, ..., Xm+1]),
  ...,
  Promise.all([Xn-m, Xn-m-1, ..., Xn]),
]);
```

さらに、どの n と m （ただし n >= m）を選んでも対応できるようにするなら、次のように書けます：

```js
const combinationsOfPromises = combinationsOf([X1, X2, ..., Xn], m)
  .map((xs) => Promise.all(xs));

// 与えられた配列の要素から、m 個選ぶ組み合わせをすべて返す関数。
function combinationsOf(xs, m) { /*（省略）*/ }

Promise.race(combinationsOfPromises);
```


## 過半数が解決されるまで待つ

また、これまでの例を利用すれば、Promise の多数決のようなこともできます：

```js
const promises = [X1, X2, ..., Xn];
const combinationsOfPromises = combinationsOf(promises, Math.ceil(promises.length / 2))
  .map((xs) => Promise.all(xs));

// 与えられた配列の要素を、m 個選ぶ組み合わせをすべて返す関数。
function combinationsOf(xs, m) { /*（省略）*/ }

Promise.race(combinationsOfPromises);
```

さて、これまで見てきた通り、`all` と `race` を組み合わせることで、任意の個数の Promise の過半数の待ち合わせを実現できることがわかりました。ここからは、誰得のおまけです。


# `all` と `race` で表現できない例
## 解決される順序によって待ち合わせる個数を変える

これまでは、解決される順序によらず、待ち合わせる Promise の個数が一定でした。
さて、この数が一定ではないケースでも表現可能でしょうか。

例えば、次のように解決される順序によって、待ち合わせる個数を変えることを考えます：

| 解決順序 | 待ち合わせが完了すべきタイミング |
|:-:|:-:|
| A → B → C | A → 完了 |
| A → C → B | A → 完了 |
| B → A → C | B → A → 完了 |
| B → C → A | B → C → 完了 |
| C → A → B | C → A → B → 完了 |
| C → B → A | C → B → A → 完了 |

~~この待ち合わせの形式は `all` と `race` だけでは書けません。~~
~~執筆時点では証明を思いつきませんでしたが、`all`と`race`だけでは、Promise の解決順序による条件分岐を実現できないことが核心にあると思われます。~~

---

**訂正はじめ（2020/11/08）**

all と race だけでは書けないという仮説に反例を発見したためこの記述は間違いです。ECMAScript 2015 を読む限り、Promise の job の積まれ方は積んだ順であり呼ばれる順もこの順であるそうなので素直に解釈すると以下のコードは条件分岐を実現できます（Chrome の v86 で実装の動作も確認できています）：

```javascript
Promise.race([
  Promise.all([X1, X2]),
  Promise.all([X1, X1]),
])
```

| 解決順序 | 待ち合わせが完了すべきタイミング |
|:-:|:-:|
| A → B | A → 完了 |
| B → A | B → A → 完了 |

なお、古い仕様の [Promise/A+](https://promisesaplus.com/) では A → B のケースで非決定的な結果になり、A → 完了のケースと A → B → 完了のどちらでも仕様を満たすことになりそうです（[Promise/A+ を参考にした形式証明](https://github.com/Kuniwak/isabelle-promise-combinators/blob/0c7b7e25773254c0d45c1755c5f0fc10173a3655/PromiseCombinators.thy#L383-L427)）。

**訂正終わり（2020/11/08）**

---


さて、このような複雑なケースにも対応できるようにするにはどうしたらよいでしょうか。
今回は、`all` と `race` に並ぶ第三の関数として `select` を導入します:

```js
// select 関数は、2つ1組の Promise 配列を受け取り、以下の条件で戻り値を決める。
// もし、A1 が B1 より先に解決したら、A2 を返す。
// もし、B1 が A1 より先に解決したら、B2 を返す。
select([
  [A1, A2],
  [B1, B2],
]);

// さらに長い配列でも同様に振る舞うとする。
select([
  [A1, A2],
  [B1, B2],
  [C1, C2],
  ...
]);
```

この `select` 関数を使うと、先ほどの表の Promise は次のようにして作成できます:

```js
select([
  [
    A,
    Promise.all([A]),
  ],
  [
    B,
    Promise.race([
      Promise.all([B, A]),
      Promise.all([B, C]),
    ]),
  ],
  [
    C,
    select([
      [A, Promise.all([C, A, B])],
      [B, Promise.all([C, B, A])],
    ]),
  ],
]);
```

この `select` 関数の実装は意外に面倒で、次のようになります:

```js
function select(xs) {
  return new Promise((resolve, reject) => {
    let pending = true;

    xs.forEach(([x, y]) => {
      x.then(() => {
        if (pending) {
          pending = false;
          resolve(y);
        }
      }, (e: any) => {
        if (pending) {
          pending = false;
          reject(e);
        }
      });
    });
  });
}
```

実は、この `select` を応用すると、次のように `all` や `race` と同じタイミングで解決する関数を実装できます:

```js
function all2(xs) {
  return select([
    [xs[0], xs[1]],
    [xs[1], xs[0]],
  ]);
}

function race2(xs) {
  return select([
    [xs[0], xs[0]],
    [xs[1], xs[1]],
  ]);
}
```

このように、`select` も豊かな表現力を持っていることがわかります。

もし、複雑な待ち合わせを実現するならば、`select` を導入してみてもいいかもしれません（ただし、Parser Combinator の応用のような別のパターンのほうが見通しが良さそうな予感があります）。


# まとめ

`all` と `race` の組み合わせは、多数決を表現できるほど豊かな表現力を持っています。
私は、この素晴らしい2つの関数の設計者をとても尊敬しています。