Future/Promise はいつモナドになったのか

Programming Scala

「非同期計算をモナドで合成し、依存関係に従ってパイプライン化する」というアイデアはいつ誰が提案したのか、というのを調べてみたけどよく分からなかった記録。網羅的な調べ方はしてないので、何か知ってる人がいたら教えてください。

明示的 vs. 暗黙的

id:xuwei さんに教えて頂いた Wikipedia の記事によると「まだ完了していない計算結果へのプロキシオブジェクト」というコンセプトが Future や Promise と名付けられたのは 1976〜1977 年頃らしい。

1976 年に出た Daniel P. Friedman と David Wise の論文や Peter Hibbard の論文で言及されていた Promise（あるいは Eventual）は明示的 (explicit) に使うものだった。つまり、Java の（Completable じゃない方の）Future のように、promise から値を取り出すのに get のようなメソッドを呼ぶ必要があるということ。

一方で、アクターモデルの研究者である Henry Baker と Carl Hewitt による論文（1977 年）が言及している Future は、そのまま普通の参照のように使える暗黙的 (implicit) のものとされていた。

Promise Pipelining

次に、Promise 同士をつなぎあわせてパイプライン化しましょうというアイデアの登場は、Promise の発明から約 10 年後、1988 年の Barbara Liskov と Liuba Shrira の論文を待つことになる。また、同様のアイデアは、一部のアレゲな紳士諸君に著名な Xanadu プロジェクトの一環として Mark S. Miller*1 や Dean Tribble らからも 1989 年に提出されている。

ただ、これらの Promise Pipelining に関する論文の主眼は、同一マシン上に配置した Promise 間のネットワーク通信を削減したりして性能を向上させることなので、「非同期計算の合成」という点に限れば、もっと以前からアイデアはあったのかもしれない。

また、当時、これらの論文のまともな形の実装が世に出ることは無かったらしい。Wikipedia では、Promise Pipelining を実装した処理系として、後に Miller らが 1997 年に発表した E 言語 や、同様に Tribble らが 1996 年に発表した Joule 言語が挙げられている。

ちなみに、E 言語での記法はこんな感じ（x <- a() は「x にメッセージ a() を送る」と読ます）:

t3 := (x <- a()) <- c(y <- b())

これを展開するとこうなる:

t1 := x <- a();
t2 := y <- b();
t3 := t1 <- c(t2);

どことなく Reactive Programming っぽい…？

JavaScript の Deferred

「Deferred に A => Deferred[B] を受け取って Deferred[B] を返すメソッド then() を持たせましょう」みたいなのは JavaScript ではかなり以前からあり、CommonJS では、先行例として MochiKit や Dojo's Deferred を挙げている。少なくとも 2006 年頃にはあった模様。Twisted の Deferred は「明示的」なスタイルなのでちょっと違うかな。

最近は、Promises/A+ 仕様として標準化されて Thenable と呼ばれている。

Future/Promise モナド

結論から言うと、少なくとも Scala の実装においては、「Future/Promise はモナドである」というようなことを書いてる論文等があったり、それを参照して実装したりした、というわけではなさそう。

まず、Akka において公開レポジトリで辿れる最古の Future 実装を見ると完全に「明示的」なスタイルで、map も flatMap も見当たらない。

sealed trait Future[T] {
  def await : Future[T]
  def awaitBlocking : Future[T]
  def isCompleted: Boolean
  def isExpired: Boolean
  def timeoutInNanos: Long
  def result: Option[T]
  def exception: Option[Throwable]
}

その後 map が追加されたりしたけど、ちゃんとモナドであることを意識した実装になったのはこの辺（2011 年 2 月）。下記のディスカッションによると、提案者の当初のモチベーションとしては、Akka に Scalaz の（ような？）型クラスを導入したいということだったらしい。

ちなみに、Twitter-Util の Future は、2010 年 8 月の公開当初からモナディックになってる。Marius さんは、Twitter の非同期処理系の API について Concurrent ML を参照しているとか言ってたので、あるいはそっち方面からアイデアを得たのかなぁ…？

追記: Scalaz の昔のコードを調べたらもっと古い実装があった（2009 年 5 月）。Scala 界隈だとこれが最古？ どちらにせよ、リファクタリングの一環で自然に入ってきた的なノリを感じる。

まとめ

Haskell 方面の歴史を知ってれば一発なのかもしれないけど、Haskell の Future/Promise モナドに相当する型クラスってどれなんですかね…。Continuation モナド？

追記

この Par モナドに成功／失敗の文脈を組み合わせると近いのかな。

追記2

*1:Wikipedia によると、今は Google のひとで、ECMAScript の仕様策定をやってる TC39 のメンバーでもあるらしい。