async/awaitと合成可能性

κeenです。async/awaitって実装の都合と利便性の良い所取ってるよなーと常々思ってるのを言語化してインターネットに放流します。 何度か似たようなことを言ってるのですがスライドであることが多くてあまり情報量を詰め込めなかったのでブログにまとめます。

非同期処理と継続

非同期処理は時間のかかる処理を待ち合わせずに別の処理をし、時間のかかる処理が終わってから元の処理を継続する仕組みです。

let url = "http://example.com"
let html = fetch url (* この結果を待たずに別の計算をする *)
(* fetch urlが終わったあとでここに戻ってきて後続の処理をする *)
print html

「継続」や「後続」などのキーワードが出てきているとおり、継続の影がチラチラ見えます。 継続とはいってもスレッドのようなタスク単位で分割したいのでフルの継続ではなくて限定継続ですね。

現実的には限定継続が使える言語はそう多くないのでユーザにCPS変換させて、コールバックという名前で継続を取ることが多いようです。

let url = "http://example.com";
fetch_url_cb(url, (html) => {
    console.log(html);
});

これで一応非同期実行は実現できるのですが、2つ問題があります。 1つは書きづらい点。コールバック地獄なんかの名前がついているのでも有名ですね。 本来は限定継続を使っていれば発生しない問題ですが、ユーザにCPS変換させるとまあ、そうなりますよね。 もう一つは過剰な要求をしている点。殆どの言語では関数(クロージャ)は何度も呼べます。 しかしコールバックは一度しか呼ばれないので何度も呼べる関数を要求するのは過剰です。 もうちょっと具体的に言うとローカル変数のアロケートはタスク単位でスタックになるのに、クロージャはヒープに置かれるので無駄になります。

なのでワンショットで使える限定継続があれば問題は解決します。

コルーチン

そういうワンショットで使える限定継続はコルーチンという名前で知られています。 フルネームでいうとstackful asymmetric coroutineと言われるらしいです。

実際、非同期処理とコルーチンを組み合わせた例はいくつかあって、crystalのfiberだとかgoのgoroutineだとかJavaのProject Loomだとかがあります。

しかしこれらは言語設計の段階から準備しないとつらいものがあります。 Project Loomのように尋常ならざる努力をするなら別として、殆どの言語には後付けでコルーチンを入れるのはつらいでしょう。 ランタイムをかなりいじり、関数の呼び出しモデルを変えるなどしないと実装できないはずです。 30億のデバイスで動くJavaで既存の関数の互換性を損なわず、しかもパフォーマンス的にもペナルティのない実装をしようとしているJavaは本当にすごい。

コルーチンの実装のどこがつらいかというとユーザレベルスレッドとも言われるように、スレッド相当の機能を実装しないといけない点です。 OSのスレッドの上にべったり実装していた関数呼び出し(コールスタックの実装)なんかがユーザレベルスレッドに移ってしまいます。 単純なインタプリタならそれもそこまで難しくないのですが大抵の実用言語はC拡張も持っているのでCの関数呼び出しまで制御下に置かないといけなくなります。 やるとしたら一大プロジェクトになるでしょう。

一応Cレベルではコルーチンライブラリはありますが、実装はアセンブラになっているはずです(読んだこと無い)。可搬性を気にする人は注意しましょう。 もちろん、これで切り取れるスタックはCのスタックなのでインタプリタ言語での実装には使えません。あとネイティブ言語でもGC付き言語だとroot setがどうなるかは知りません。

スタックレスコルーチン

関数呼び出しをサポートしない、1関数内で閉じたコルーチンだと簡単に実装できます。これはコールスタックが必要ないからか、stackless coroutineと呼ばれるようです。 言語によってはジェネレータと呼ばれるものがこれに相当するものもあります。 stackless coroutineはかなり簡単な仕組みで実装できます。 ステートマシンにすればそれで済みます。

ランタイムに手を入れず、1関数内のプログラム変換だけで実装できるので後付けで言語に入れるにはもってこいです。 さらに特別な仕組みが必要ないということはパフォーマンス的にも優れます。最速なプログラムは何もしないプログラムですからね。 ただし関数呼び出しを飛び越えられないので恐ろしく不便です。ライブラリでコルーチン処理をする関数すら提供できません。

合成可能性

言語次第ですが、スタックレスコルーチン(ジェネレータ)を合成可能にしているものもあります。というか合成可能なものをジェネレータということが多いかな? 1つ1つのジェネレータは1関数内でしか制御できませんが、それらを合成可能にすることで関数を超えて組み合わせることができます。 例えばPythonのジェネレータは yield from で合成できます。

# ジェネレータ関数を定義する。
# yield単体はそれが使われている関数内しか制御できない
def upto(n):
    for i in range(1, 10):
        yield i

def downto(n):
    for i in range(n,0,-1):
        yield i

# ジェネレータ関数を組み合わせて使う
def triangle(n):
    yield from upto(n)
    yield from downto(n)

JavaScriptでも yield* というキーワードでジェネレータを合成できるみたいですね。

1つ1つの機能は小さくても組み合わせられることで利便性が広がります。

Future

話が少し脇道に逸れて(戻って?)、非同期の話です。 言語によっては同じものをPromiseと呼ぶこともありますし、PromiseとFutureは別のものとして扱っている言語もあります。

非同期処理の「いつか完了する」という概念を値にしたものです。 値なので第一級市民として扱えて、メソッドを定義できたり関数の引数に渡せたりします。 コールバック関数の設定をメソッド呼び出しにできます。

let url = "http://example.com";
fetch_url_ft(url) // ここの返り値がFutueとする
  // Futureのthenメソッドが呼べて、それでコールバックを指定できる
  .then((html) => {
    console.log(html);
});

こちらも値なので合成ができます。

しかしコールバックよりは便利とはいえ、後続の処理を関数で渡すのでコールバックと同様の扱いづらさは残ります。

async/await

Futureをジェネレータと同様に構文でラップしたものです。 Futureが内部モデルで、async/awaitが表層構文という関係です。

let url = "http://example.com";
let html = await fetch_async(url);
console.log(html);

さらなる一般化

Futureとジェネレータで同様の実装ができるということは、もっと一般化できるということです。 例えばScalaのfor式はそのようになっています。

// ジェネレータの使い方
for (i <- 1 to 3) println(i)
// Futureの使い方
val purchase = for {
  usd <- usdQuote
  chf <- chfQuote
  if isProfitable(usd, chf)
} yield connection.buy(amount, chf)

このほうが便利ですよね。 しかしこれには(脱糖と型システムの関係次第ですが)型システムに高カインド多相が必要になり、それなりの言語設計が要求されます。 高カインド多相は実用されている言語ではScalaくらいにしか実装されていないようです1

まとめ

非同期処理を簡潔に書けるようにするには(限定)継続やコルーチンなどの機能が欲しくなりますが、これらは実装/実行コストが重いです。 一方でFuture+async/awaitだと比較的楽に入れられる上にそこまで利便性を損ないません。

ここでよくある勘違いを指摘しておきます。

  • async/awaitはCPS変換で実装されている → CPS変換でも実装できるけどもっと軽い方法があるよ
  • async/awaitよりもFutureの方が好き → 直交する概念じゃないよ。Futureのためにasync/awaitがあるんだよ。
  • 何故モナドを入れないのか → モナドを入れるには高カインド多相とかそれなりの機能が必要なんやで

たまーにこういう言説を見てもやもやしてたのでムシャムシャしてこの記事を書いた。


  1. Scalaのfor式は高カインド多相に依存してないのでややこしいですが… [return]
Written by κeen
Later article
Effective Idris: Lazy