パイプライン演算子の歴史

(You can read this article in English.)

Ruby の開発版にパイプライン演算子(pipeline operator)が試験的に導入されましたが、いろいろあってプチ炎上になっています(チケット)。

せっかくの機会なので、パイプライン演算子の歴史を調べてみました。付け焼き刃の調査なので、間違ってたら教えてください。

パイプライン演算子とは

こんな感じのものです。

x |> f |> g |> h  # h(g(f(x))) と同じ意味

h(g(f(x))) という関数適用の式は、関数が呼ばれる順序(fgh)と、プログラムの字面上の順序(hgf)が逆でわかりにくいとされます。この問題は、特に、関数が大きくなったときに顕著になります。

wonderful_process_h(
  marvelous_process_g(
    fantastic_process_f(
      astonishing_argument_x
    )
  )
)

語順問題に加え、インデント地獄まで発生しています。人類はとにかく深いインデントをきらいます。

|> を使うと、インデントを深めず、実行順の通りに書くことができます。

astonishing_argument_x
|> fantastic_process_f
|> marvelous_process_g
|> wonderful_process_h

言語ごとに実現方法がだいぶ異なるのですが、ユーザ視点ではだいたいこういうものです。

Isabelle/ML のパイプライン演算子

The Early History of F# によると、パイプライン演算子を最初に導入したのは定理証明支援系の Isabelle/ML だそうです。1994 年の議論が発掘されています。

目的は上に述べた通り、関数名を処理順に並べていきたいというものでした。AAA というものを作り、それに BBB を足し、それに CCC を足し、DDD を足し、という処理を ML で素直に書くと

add DDD (add CCC (add BBB (make AAA)))

みたいな感じになります。これを、

make AAA
|> add BBB
|> add CCC
|> add DDD

と書くために導入されたことがわかります。

ちなみに、導入当初は also という名前だったようです。ML では infix という機能を使って文字だけの関数を中置演算子にできます*1。上の例で言うと実は add を中置演算子にする手もあるのですが(make AAA add BBB add CCC add DDD と書ける)、たくさんある add 系関数をすべて中置演算子にするのは抵抗がある、ということで、also を導入することになったようです。

さらに余談ですが、also から |> に至るまでにいろいろな名前が検討されていておもしろいです(ツイート)。

Isabelle/ML のコミットログを貼っておきます。

F# のパイプライン演算子

F# は Microsoft が開発した .NET Framework 向けの言語の 1 つです。OCaml がベースになっています。

F# がパイプライン演算子を取り入れたことで、パイプライン演算子は広く一般に認知されました。F# の主設計者である Don Syme も、著書の "Expert F#" でパイプライン演算子を「おそらく最も重要な演算子」と言っています。

The Early History of F# によると F# がパイプライン演算子を導入したのは 2003 年らしいです。F# で |> が重宝されるのには、「語順が気持ちいい」という以外に、「型推論で都合がよかった」という特有の事情があるようです。F# の型推論はふつうの HM 型推論ではないらしく*2、プログラムの字面上で先に書かれた式から型を決定していくらしいです。その結果、型注釈が余分に必要になることがあります。

let data = ["one"; "three"]
data |> List.map (fun s -> s.Length)

は、datastring list とあらかじめ分かるので型注釈はいりませんが、|> なしで書くと

List.map (fun (s: string) -> s.Length) data

というように、data が後に出てきてしまうので、無名関数の引数に s: string という型注釈が必要になってしまっています。*3

余談ですが、F# で広まったパイプライン演算子は、2013 年に OCaml に逆輸入されました。F# は OCaml ベースですが、パイプライン演算子については F# が先とのこと。

ML 系におけるパイプライン演算子のポイント

歴史からちょっと外れて、要点を整理しておきます。

ML 系言語における |> は、言語組み込みの演算子ではなく、単なる関数として実現されています。関数型プログラミングフリークが好きそうな非常にクールなハックです。このハックが成立する背景には、次のポイントがあると言えます。

  1. ユーザが中置演算子を定義できること
  2. カリー化が組み込みであること
  3. 「プライマリ」な引数を最後に受け取るという慣習があること

1 はまあ面白機能という感じですが、2 と 3 が特に重要だと思います。

「プライマリ」とは、たとえばリスト処理関数ならリスト、配列処理関数なら配列のように、その関数の「主対象」と言えるような引数のことです。F# ではそういう引数を最後に受け取る仕様が徹底されています("Expert F# より引用↓)。たとえば List.map だと、まず変換関数(クロージャ)を受け取り、それからリストを受け取って、その各要素を変換した新しいリストを返します。

List.map   : ('a -> 'b) -> 'a list -> 'b list
Array.map  : ('a -> 'b) -> 'a[] -> 'b[]
Option.map : ('a -> 'b) -> 'a option -> 'b option
Seq.map    : ('a -> 'b) -> #seq<'a> -> seq<'b>

これらのポイントによって、|> は単に次の定義だけで実現できてしまいます。クール。*4

let (|>) x f = f x

パイプライン演算子とメソッドチェーン

述べた通り、F# の |> は、処理順に関数をつなげて並べるために使われます(x |> f |> g |> h)。

ところで、オブジェクト指向プログラミングによるメソッドチェーンも、処理順に関数をつなげて並べます(x.f().g().h())。

これが偶然の一致なのか、F# がこれをねらって |> を導入したのかはわかりません。しかし、.NET Framework の別言語である C#オブジェクト指向であることもあってか、パイプライン演算子とメソッドチェーンを関連付けて考える人は結構いるようです。

Elixir のパイプライン演算子

歴史にもどります。

Elixir がパイプライン演算子を導入しました。Elixir の作者の José Valim によると F# が由来のようです。見た目は F# と同じように書けます。

x |> f |> g |> h

見た目こそ F# たちと同じですが、実は言語仕様面から見たらかなり別物です。Elixir において |> は、単なる演算子というより、言語組み込みの構文です*5

x |> f(args..) # f(x, args...) と同じ意味

|> の左側の評価結果を、右側の関数呼び出しの先頭の引数にします(最後ではなく先頭)。

ふつうの二項演算子であれば、左右の式は独立した式になります。足し算を例にすると、expr1 + expr2 の 2 つの expr はどちらも単体で成立する式ですよね。F# の expr1 |> expr2 でも、expr2 は単体で成立する関数です。引数を複数取る関数のときは、カリー化を活用して部分適用しておきます。パイプラインで渡したい「プライマリ」の引数は最後なので、これがピタッとハマります。

一方 Elixir の |> の右側は、単体の関数呼び出し式として見ると引数が足らないので、独立していません。よって、Elixir の |>演算子というより構文と言うべきでしょう。

なぜこうなっているかというと、Elixir は先に述べた 3 つのポイントを 1 つも満たしていないためです。中置演算子を自由に増やすことはできず*6、デフォルトのカリー化はなく、主要な引数を最後に受け取る関数群の一貫設計もありません*7。なので、F# のパイプライン演算子の見た目だけを真似たもので、個人的な感覚では完全な別物、という印象です。

とはいえ、実用プログラミング言語の設計においては見た目こそが重要なことであり、言語マニアから見て別物とかは、ユーザ視点ではどうでもいいことです。(皮肉ではなく本当に)

Ruby のパイプライン演算子

最後に、つい先日 Ruby に試験的に導入されたパイプライン演算子の話です。

x |> f |> g |> h # x.f().g().h() と同じ意味
x |> f(args...) # x.f(args...) と同じ意味

|> の左側の式の評価結果をレシーバとして、右の名前のメソッドを呼び出します。

Ruby も Elixir と同じく、前述のポイントを満たしていません。よって、単なる演算子ではなく構文として導入する必要がありました。

Elixir の |> は、左側の式を右側の関数呼び出しの第一引数としました。一方 Ruby|> は、右側のメソッド呼び出しのレシーバとしています。これは、Ruby のメソッドにおける「プライマリ」な引数がレシーバであることを考えると、ある意味で自然な設計です。

しかしこれでは . と大差がありません。何がうれしいかというと、複数行に渡るメソッドチェーンを明示的に書いたり、括弧を省略できたりするというのが挙げられます。

(1..)
.take(10)
.each {|x| p x }

1..
|> take 10
|> each {|x| p x }

下のほうが簡潔でよい、という人がいることを否定することは出来ません。(自分もすごい良いと思ってるのかというと、まあそこまでではないんですが)

一方で問題点もあります。

  • Elixir に慣れた人たちにはわかりにくい
  • 従来のメソッドチェーンとできることが変わらないので意義が乏しい

前者については、自分が知る限りレシーバという概念がある言語にはじめてパイプライン演算子を導入する事例なんですよね*8Ruby は Elixir じゃないし Elixir はオブジェクト指向じゃないんで、「Elixir と違う!」とだけ言ってもしょうがない。また、Ruby では関数的なメソッド(File.joinMath.logなど)はそれほど出てこないので、Elixir に合わせる需要が少ない可能性も考えられます。

後者については、何か有用な使い方が見つかるかも知れないし、見つからなければ matz が消すと思うんで、リリースの 12 月までもうちょっとゆっくり考えてみてもよいのではないかと、個人的には思っています。

しかしこのあたりの問題点の指摘をうけて、現在名称や記号の変更が検討されています。Ruby の「パイプライン演算子」は幻想で終わってしまうのか、生暖かく見守っていきましょう。

まとめ

パイプラインの歴史を駆け足で追ってみました。ほとんど一晩でざっと調べただけなので、なんか間違ってたら教えてください!

追記(2019-06-16) ○○言語の pipeline に言及がない!っていう悲しみの声を聞きます。ここでは Ruby のパイプライン演算子の先祖(と自分が思っているもの)だけを書きました。他の言語にもありますが、まともに調べてないので詳しい言及はせず、知ってる範囲で列挙だけしておきます。

  • Elm と Julia には |> がある。
  • Scala には pipe が最近入った。
  • R には %>% を提供するライブラリ(tidyverse)がある。
  • Racket や Clojure の threading macro も同じような概念。
  • JavaScript では部分適用とあわせて現在検討中。

なお、興味深いことに shell スクリプトのパイプラインは、あまり関係ないかも知れません。というのも、Isabelle/ML の議論では "pipeline" という名前は一回も出てきていません。| という記号も、シェルを意識したという雰囲気は感じられませんでした。F# では "pipe" という名前がついていますが、名前をつけるときにシェルを意識していたかどうかはわかりません。

追記(2019-06-17)

@cedretaber さんの記事がとても参考になります。ざっと書くと

  • Clojure の threading macro
  • BuckleScript/Reason のパイプファースト演算子(Elixir のように先頭に挿入する構文、記号はそれぞれ |.-> らしい)
  • D言語の UFCS(func(a, b, c) という関数呼び出しを、a.func(b, c) と書ける機能)

という感じです。あと Elixir の |> は言語組み込みではなくマクロだそうです(この本文にも注釈を足しておきました)。詳しくはあちらの記事をご参照ください。

qiita.com

*1:できない ML もあるかも。

*2:追記(2019-06-17):話はもうちょっと複雑で、基本は HM 型推論だけど、.NET のライブラリで推論が効かないケースがあるとコメントで教えてもらいました。

*3:この例は The Early History of F# からの引用です。

*4:実行時オーバーヘッドにならないよう、処理系がなにか特別な最適化をしている、という話はどこかで見かけました。

*5:追記(2019/06/17):言語組み込みではなくマクロで実現されているそうです。

*6:あらかじめ用意されたいくつかの中置演算子を自由に再定義することは可能なようです。

*7:逆に、主要な引数を最初に受け取る一貫設計になっているのだと思います。

*8:メジャーな前例があったら教えて!

新雑誌「n月刊ラムダノート」の『「コルーチン」とは何だったのか?』の草稿を公開します

『Ruby でつくる Ruby』などでお世話になっているラムダノートが、新しい雑誌「n月刊ラムダノート」を創刊しました。

www.lambdanote.com

コンピュータ関係の技術情報の記事だけが載るそうです。創刊号は、『TCPの再送制御機構』、『「コルーチン」とは何だったのか?』、『MLOpsの歩き方』、の 3 本です。

  • TCP の再送制御機構』は、パケットを送ってから返事が来るまでの RTT (Round-Trip Time) を計測する方法や、RTT を使った再送のアルゴリズムや、RTT を使わない再送のアルゴリズムなど、TCP の再送に関する仕様・実装の歴史から最新提案までを、日本語話者の中では間違いなく世界一詳しい第一人者である西田佳史さん(@nsd)が広く深く紹介しています。
  • 『「コルーチン」とは何だったのか?』は、ぼくが書きました。伝統的なコルーチンの説明から、JavaScript 界隈から始まった言葉の転用までを駆け足で紹介しています。
  • 『MLOps の歩き方』は、MLOps とは DevOps の ML 版 *1 ということで、機械学習を実際のサービス運用で使っていく上で発生する課題や解決を、この分野のプロの practitioner であり『仕事ではじめる機械学習』の著者の一人でもある有賀康顕さん(@chezou)が最新状況を網羅的に解説しています。

とんでもなくマニアックな雑誌ですね。

さて、ラムダノートと相談して、『「コルーチン」とは何だったのか?』の草稿を公開することにしました。上記の通りこの雑誌は多方向にマニアックで、けっしてこの記事が「n月刊ラムダノート」の方向性を代表するようなものではないのですが、なんとなく雰囲気を感じて頂ければ幸いです。

執筆と草稿公開の経緯

さっさと草稿を見たい人はこの節をスキップ。

執筆のきっかけは、最初は↓の不用意なツイートです。

「独裁者を辞めた途端」云々は、"Ruby is dead" みたいな軽口だったんですが、あまり上品じゃなかったですね。反省してます。

このツイートにはいくつかご意見や情報をいただきましたが、Python が(ぼくの知っていた)コルーチンとは違うものをコルーチンと呼んでいるのは確かなようでした。現状をまとめてみようと思い、最初はブログ記事として書き始めました。

しかし初期の草稿を @bonotake さんに見てもらい、そこからさらに掘り下げて調べていくうちに、自分の勘違い *2 や複雑な経緯がわかってきて、うまくまとめられず放置してました。

そんなとき、ラムダノートの鹿野さん(@golden_lucky)から雑誌を創刊すると聞いて、この記事の出口が決まりました。もう少し正確に言うと、昨年末頃に鹿野さんから「雑誌創刊するから記事ないですか」と言われたときには、コルーチンの記事を完全に忘れていて、「考えとく」で終わりました。今年になって、鹿野さんやうちの奥さん(@hirekoke)とコルーチンや継続について雑談していて、日本語での体系的な解説が欲しいという話になり、「そういえばこんなブログ記事を書きかけてた」と言って見せたら、「えっこれ雑誌に載せられるのでは」ってなりました。雑談は大切。

草稿を公開することにした理由ですが、

  • もともとブログ用に書いていたものなので、できれば一般公開して広く知ってもらいたかった(遠藤の気持ち)
  • 草稿を公開することで「n月刊ラムダノート」の雰囲気を知ってもらったり、ラムダノートでの執筆プロセスが身近であることを知ってもらったりしたい(ラムダノートの気持ち)

ということで、著者と出版社の希望がかさなったためです。ここで公開するこの草稿はわりとファイナルに近いもの(ラムダノートに内容・構成レベルの改善提案をいただいて直した後のもの)です。それでもまだまだ適当な状態ですね……。「★なんかそれっぽい書き出し」とか。図もまったくありません。参考文献は、Slack で適当にリンク貼りつけて伝えました。そのあたりがいい感じになっているのは、だいたいラムダノートによる「編集」です。ということでみなさんも、ちょっと気合を入れたブログ記事を書いたら、公開する前にラムダノートに提案をしてみるといい感じになるかもしれません *3 。ちょうど記事募集をはじめたらしいので、見てみるとよいのではないでしょうか。

ということでここから草稿です↓

「コルーチン」という用語が指すもの(仮題)

★なんかそれっぽい書き出し

「コルーチン」という言葉が指すものが、プログラミング言語の文化圏によってだいぶ変わってしまっているようです。

調べた限りで分かった状況をまとめてみたいと思います。間違ってるところがあったら、ご指摘ください。

1. 伝統的なコルーチン

まず、伝統的なコルーチンである「対称コルーチン」と「非対称コルーチン」を説明します。

1.1. 対称コルーチン

対称コルーチンは、互いに制御を渡し合う手続きのようなものです。疑似コードで示します。

coroutine A() {
  print("A-start");
  B.transfer();
  print("A-end");
}

coroutine B() {
  print("B-start");
  A.transfer();
  print("B-end");
}

A.transfer(); //=> "A-start", "B-start", "A-end"

X.transfer() で、コルーチン X に処理を渡します。このように、対称コルーチンでは飛び先を常に明示します。非常に原始的・明示的で分かりやすい反面、実用上はなかなか扱いにくく、実際にはほとんど使われていません。

対称コルーチンは、コルーチンの発案者(の一人)とされる Conway の 1963 年の論文に登場する、元祖のコルーチンです。メインルーチン・サブルーチンのような親子関係ではなく、対等に協調し合うルーチンとして考案されました。COBOL コンパイラを実装する上で、lexer と parser を別モジュールとして実装するためのテクニックだったようです。 transfer で中断したコルーチンを再開するのは、完全にプログラマの責任になります。再開し忘れると、コードが実行されないことになります。上の例でも print("B-end") が実行されていません。再開しそこねて、後処理(ファイルのクローズとか)が抜けると、痛い目にあいます。対称コルーチンの提案は構造化プログラミング(1969 年)より前なので、現代的なプログラミングと相性がよくないのはしかたないですが、現代で使われていないのはこういう不便さのためだと思われます。

対称コルーチンが実装されている例。

1.2. 非対称コルーチン

対称コルーチンの間に親子関係を持たせることで使いやすくしたものです。次の疑似コードを見てください。

coroutine A {
  print("foo");
  yield "bar";
  print("baz");
}

// 呼び出し側
x = A.resume(); //=> "foo"
print(x);       //=> "bar"
A.resume();     //=> "baz"

A.resume() でコルーチン X を起動し、yield でコルーチンを「中断」し、呼び出し側に制御を一旦もどします。すると、A.resume() の呼び出しがリターンして、yield の引数であった "bar" が変数 x に代入されます。その後、print(x) を実行してから、再度 X.resume() すると、コルーチンの中断箇所から実行を再開します。すると、yield "bar" が終了し、最後の print("baz") が実行されます。コルーチン A は、resume のたびに、yield までを細切れに実行できる関数のように振る舞います。

重要なことなのでもう一度言っておきます。非対称コルーチンで「中断」と言ったら、「呼び出し側に制御を一旦もどす(そのあとで再度 resume されたら中断箇所から再開する)」という意味です。後の説明でも出てくるので覚えておいてください。

元祖のコルーチンと区別を明示するために、元祖の方を対称コルーチン(symmetric coroutine)、こっちを非対称コルーチン(asymmetric coroutine)と言います(参照: http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf)。しかし、前述の通り、元祖のコルーチンはほとんど使われていないので、単にコルーチンと言ったらだいたい非対称コルーチンを指します(少なくとも後述する JavaScript の「イディオム」が登場するまでは)。他に、非対称コルーチンは semi-coroutine や fiber という名前で呼ばれることもあります。

対称コルーチンとの違いは、resume で別のコルーチンを呼び出した場合、必ず制御が戻ってくることです(呼び出されたコルーチンが yield または終了すると戻ってくる)。これにより、必ず実行してほしい後処理が抜ける心配が大きく減ります。ただし、yield で中断したコルーチンが再度 resume されてくるかどうかはプログラマ次第なので、yield の後に必ず実行してほしい後処理を書くのはちょっと注意が必要です。(余談ですが、この問題は本質的に解決不可能で、Ruby で未解決の最古のバグチケット #595 にもなっています)

次は、非対称コルーチンを実装した言語・ライブラリの例です。

  • Simula
  • Lua の SemiCoroutine
  • Ruby の Fiber#resume / Fiber.yield や、Enumerator
  • Python の generator (PEP 342)
  • JavaScript の function* / yield
  • C#イテレータ (yield で IEnumerator を得る。Unity の文化圏ではコルーチンとも呼ぶ)
  • Boost.Coroutine の asymmetric_coroutine
  • ScalaJava での実験的な実装

あとで出てくるのでもう一度いっておきますが、「JavaScript の function*/yield」=「Python の generator」は、非対称コルーチンです。

1.3. コルーチンの利用例

伝統的なコルーチンの代表的なユースケースは、無限長の列を表現することです。非対称コルーチンで説明します。

coroutine natural_numbers() {
  i = 1;
  while(true) {
    yield i;
    i += 1;
  }
}

このコルーチンは、最初に resume すると 1 を yield し、次に resume すると 2 を yield し、というのを無限に繰り返します。このように、resume するごとに次の要素を yield で返す非対称コルーチンは、無限列を表現しています。

このような無限列の表現を、ジェネレータといいます。非対称コルーチンが一部の言語で generator やイテレータと呼ばれているのは、このユースケースに特化しているためです*4

Ruby は Enumerator と Fiber の両方を提供しています。前者はジェネレータとして使いやすい API 、後者は対称・非対称コルーチンとして使いやすい API になっているという違いがありますが、Enumerator は内部的に Fiber で実装されていて、本質的に同等です。なお、Fiber という名前はマイクロソフト .NET の Fiber に由来します(Fiber は「繊維」という意味です。スレッド(糸)よりもメモリ使用量が少なく大量に作れる軽量スレッドという意味で名付けられたようですが、実体としてはコルーチンの再発明です。))。

他にも非対称コルーチンは、ゲームやシミュレーションのオブジェクト(resume するごとにフレームやシミュレーション単位 1 つ分だけ動作をすすめる)を表現するためなどにも使われます。

2. JavaScript における事情

ここから、JavaScript コミュニティでコルーチンと呼ばれるものの話が始まります。これまでの話とはだいぶ違うので、気持ちを切り替えて読んでください。

2.1. JavaScript の言語的特徴

ご存じのとおり、JavaScript は、ブラウザの上で動く言語です。マウスクリックのようなユーザ操作のイベントが起きたときに呼ばれる関数(コールバック)を書くのが元々の想定ユースケースでした。一方で、JavaScript はシングルスレッドの言語です*5。そのため、コールバックの中で時間のかかる処理(sleep や IO 待ちなど)を行うと、その間は他のイベントが処理できなくなってしまいます。

これを解決するために、JavaScript の世界では、「すべての関数は一瞬でリターンする」という API 設計が徹底されています。たとえば n ミリ秒間待ってから何かを行いたい場合、JavaScript 以外の言語では sleep(n) のような「呼び出しから n ミリ秒後にリターンする関数」を使いますが、JavaScript では setTimeout(function() { ... }, n) のように「呼び出しから n ミリ秒後にコールバックする関数を登録する関数」を使います。

// 普通の言語の 1 秒待ち
sleep(1000);
print("foo");

// JavaScript の 1 秒待ち
setTimeout(function() {
  print("foo");
}, 1000);

この言語設計は非常に合理的ですが、結果的に JavaScript のプログラムはコールバックであふれることになりました。コールバックの中にコールバックを書く、ということも日常的に行われます。

// 普通の言語で 1 秒ごとに foo 、bar 、baz という
sleep(1000);
print("foo");
sleep(1000);
print("bar");
sleep(1000);
print("baz");

// JavaScript で 1 秒ごとに foo 、bar 、baz という
setTimeout(function() {
  print("foo");
  setTimeout(function() {
    print("bar");
    setTimeout(function() {
      print("baz");
    }, 1000);
  }, 1000);
}, 1000);

このように、インデントがどんどん深まって行きます。この現象でコードが読み書きしづらくなることは、コールバック地獄と呼ばれています。

2.2. コルーチンを使ったイディオム

実は、このインデントの現象は、非対称コルーチンできれいに解決できます。疑似コードで説明します。

coroutine A {
  yield setTimeout(function() { A.resume(); }, 1000);
  print("foo");

  yield setTimeout(function() { A.resume(); }, 1000);
  print("bar");

  yield setTimeout(function() { A.resume(); }, 1000);
  print("baz");
}

A.resume();

A.resume() を呼ぶと、コルーチン A は setTimeout によってコールバックを設定し、yield で一旦呼び出し側に処理を戻します。それから 1 秒後にコールバックが呼ばれ、そのコールバックは A.resume() を行います。これにより、yield したところから再開して print("foo") が実行されます。そしてまた setTimeout をして yield します。これを繰り返すことで、1 秒ごとに何かやる処理を表現できます。

JavaScript でも、非対称コルーチンである function*/yield を用いて、次のようなコードを書くのが流行しました。

const co = require('co')
co(function* () {
  yield new Promise(function(f) { setTimeout(f, 1000); });
  print("foo");

  yield new Promise(function(f) { setTimeout(f, 1000); });
  print("bar");

  yield new Promise(function(f) { setTimeout(f, 1000); });
  print("baz");
})

co とか new Promise(...) とか登場人物が増えてややこしいのですが、簡単に説明すると

  • new Promise(...) は、コールバック関数の登録を受け付ける "Promise" オブジェクトを返します。
  • co は、渡された非対称コルーチンを resume し、yield で中断したら "Promise" オブジェクトにコールバックを登録し、コールバックが起きたら再度 resume する、を繰り返す補助関数です。

これらによって本質的には上のコルーチンのコードと同等になっています*6

さて、JavaScript コミュニティでは、このイディオムを漠然と「コルーチン」と呼ぶようです。その理由を推測すると、

  • function/yield は実際に非対称コルーチンであるから(ただし、JavaScript では通常 function/yield のことをジェネレータと呼びます)
  • 「ブロック処理があったら関数実行が中断する」という説明がなんとなく「中断できる関数」という非対称コルーチンの説明に似ているから

というのが何となく絡み合って、慣習になったのだと思われます。実際、このあたりを混乱したような説明をしばしば見かけます。しかし、ここで言っている「中断」は、非対称コルーチンで言っていた「中断」とはもはや意味が違うことに注意してください。このイディオムの説明で言う「中断」は、「ブロック処理を待つこと」であって、「呼び出し側に処理を一旦返すこと」ではなくなっています。この言葉の使い方は、同期的なブロック処理 API を避けている JavaScript の事情に特化したものになっています。

(これ以下削除で良さそう)上のイディオムの中で、具体的に何をコルーチンと呼んでいるかは、人によって異なるようです。少なくとも以下が観測できました。

★promise が未定義語になってしまった

2.3. async function の登場

JavaScript の人たちは、コルーチンを使ったイディオムでは満足せず、async/await という専用の文法を導入するに至りました。C# の async/await を参考に取り込んだと思われます。

async function asyncABC() {
  await sleep(1000);
  print("foo");

  await sleep(1000);
  print("bar");

  await sleep(1000);
  print("baz");
}

これはしばしば、前述の「イディオム」への構文糖として説明されます*7

  • async function foo() { ... }function foo() { co(function* () { ... }) } 相当*8
  • await baryield bar 相当

ざっと調べた限り、JavaScript の言語仕様においては、async function で定義された関数は "async function" と呼ぶようで、これのことをコルーチンとは呼んでいないと思います。前述のイディオムとの区別が曖昧になりますしね。

async function と伝統的コルーチンは、全くの別物であることに注意してください。async function は function*/yield の構文糖ではありますが、非対称コルーチンの特徴を失っています。というのも、co が暗黙的に埋め込まれるので、「呼び出し側に処理を一旦戻す」ということができなくなっているのです。await で非対称コルーチンの yield を呼んでも、co がそれを拾って勝手に resume してしまうので、非対称コルーチンでいう「中断」にはなりません。

また、他にも異なる点があります。伝統的なコルーチンでは、コルーチンが transfer/resume/yield したとき、次にどのコルーチンが再開するかはプログラマは完全に把握できるものでした。よって、「次にどのコルーチンが再開するかをプログラマが制御する・制御できる」という性質もコルーチンの特徴のひとつと考えられていました。しかし JavaScript では、イベント処理のために async function を使うことが多かったので、await してからいつどれが再開するかはプログラマにも把握できず、場合によっては複数の async function が再開可能な状態になる、という状況が生まれました。どの async function が再開するかは、言語やライブラリが用意したスケジューラが勝手に決める(プログラマが管理しない・できない)ということになります。

重要なのでもう一度いいますが、async function と伝統的コルーチンは、全くの別物です。

3. 「コルーチン」の新たな意味の誕生

JavaScript の async function は非同期処理の記述として大ヒットし、他言語にも取り入れられるようになりました。

3.1. Python のコルーチン

Python は 3.5 から async/await を導入しました。このとき、JavaScript が async function と呼んでいるものを、Python は「コルーチン」と名付けました。

Python に async/await を提案した PEP 492 によると、「generator から native coroutine を切り出す」と書かれています。これだけ読むと「generator = 非対称コルーチン」を意識していると思えますが(実際、PEP 342 の方は generator = (asymmetric) coroutine を明確に意識しています)、読み進めると、この提案は完全に JavaScript のイディオムを念頭においているようです。PEP 492 には、JavaScript の他に HHVM 、DartScala などを参考にしたと書かれていますが、ざっと調べた限りこれらは誰も async function を「コルーチン」と呼んでいません。JavaScript コミュニティでなんとなく呼ばれている「コルーチン」を、なんとなく持ってきたのだと思います。

ここにきて、async function を指して「コルーチン」と呼ぶ用法が確立したようです。

少し補足すると、Python の async は暗黙的に co 相当の機能を埋め込むわけではなくもう少しややこしいもののようです。async function と future と組み合わせれば、対称コルーチンをエンコードすることも出来るようです。ただ、これをもって「async で定義された関数は対称コルーチンである」とは(普通は)言わないと思います。

3.2. Kotlin のコルーチン

Kotlin では、非対称コルーチン(ジェネレータ)と async function をすべてまとめて「コルーチン」と呼ぶようです。

sequence { ... } と書けば非対称コルーチンが、async { ... } と書けば async function が得られるようです。

Kotlin は規格策定のときにいろいろサーベイをした様子が伺え、伝統的なコルーチンから JS や Python の状況までを踏まえて、このようにしたのではないかと思います。

4. まとめ

コルーチンという言葉はプログラミング言語文化圏によって、いろいろなものを指します。とくにこの 10 年で、その意味はとても拡散してしまったようです。

繰り返しですが、調べながら書いたもので、特に JS には詳しくありません。なんか事実誤認があったらご指摘ください。

謝辞

この文書をまとめるにあたって、調査やレビューを @bonotake さんや笹田耕一さんにご協力いただきました。ありがとうございました。

付録A. Promise と JavaScript

Promise は、並行処理を記述する言語機能です。JavaScript 以外の言語の Promise は、こんな感じに動きます。

// 1 秒かかる計算を Promise にする
x = new Promise(function() { sleep(1000); return 42; });

// Promise の生成は一瞬で終わる(1 秒待たされない)

// get を呼ぶと、sleep(1) が終わるのを待って、計算結果の 42 が得られる
print(x.get()); //=> 42

しかし JavaScript では、sleep(1) は書けないですし、それを同期的に待ち受ける get() 関数も書けません。そこで、例によってコールバックを使います*9

x = new Promise(function(f) { setTimeout(function() { f(42); }, 1000); });

x.then(function(r) { print(r) }); //=> (1 秒後に)42

Promise オブジェクトに対して then メソッドで関数を渡すと、Promise の計算が終わったあとでコールバックしてくれます。

2 つの Promise を連続で待ちたい場合、単純に考えると入れ子にする必要があります。

x = new Promise(function(f) { setTimeout(function() { f(42); }, 1000); });

x.then(function(r) {
  print(r); //=> (1 秒後に)42

  y = new Promise(function(f) { setTimeout(function() { f(43); }, 1000); });

  y.then(function(r) {
    print(r); //=> (さらに 1 秒後に)43
  });
});

これではインデント問題は解決されません。しかし JavaScriptthen は少し工夫されていて、コールバックを含めた全体の Promise を返します。つまり、次のように書けます。

x = new Promise(function(f) { setTimeout(function() { f(42); }, 1000); });

x.then(function(r) {
  print(r); //=> (1 秒後に)42

  y = new Promise(function(f) { setTimeout(function() { f(43); }, 1000); });

  return y;
}).then(function(r) {
  print(r); //=> (さらに 1 秒後に)43
});

これにより、インデント問題は解決されました。しかし、then を大量に書く必要があり、あまり簡潔とは言えません。そのため、本文のコルーチンを使ったイディオムに進化していったようです。

付録B. 継続とコルーチンの関係

たまにコルーチンと混同される言語機能に、「継続」という非常に強力な言語機能があります。継続とは何かを説明するととても長いのですが、関係だけを一言で言えば、継続はコルーチンの上位互換です。継続を使うと、コルーチンを表現できます。つまり、継続を使えば、resume や yield を普通の関数として定義できてしまいます。

しかし、継続=コルーチンではありません。継続にできてコルーチンにできない典型的な例だけを挙げておきます。

for i in 0..2 do
  for j in 0..2 do
    for k in 0..2 do
      puts "(%d, %d, %d)" % [i, j, k]
    end
  end
end

というコードは、(0, 0, 0) から (2, 2, 2) まで辞書順に出力するコードです。これは、要素の数だけインデントが深まるというインデント地獄になっています。

コルーチンでは、このインデント地獄を解決することはできません。しかし継続を使うと、

try do
  i = amb(0..2)
  j = amb(0..2)
  k = amb(0..2)
  puts "(%d, %d, %d)" % [i, j, k]
end

というコードで同じ動作をする関数 amb が書けます。

ポイントは、amb(0..2) という 1 回の関数呼び出しが 3 回リターンする(それぞれ 0 、1 、2 を返す)というところです。これはコルーチンにはできず、継続にはできるところです。詳細は、Scheme/継続の種類と利用例 - Wikibooks や他の参考書を見てください。

*1:Meta Language ではなく Machine Learning のほう。

*2:コルーチンはプログラミング言語理論の中で生まれたと思い込んでましたが、出自はもっと実践的なものだったとか。くわしくは記事の方で。

*3:さすがに「★なんかそれっぽい書き出し」とかはひどいので、なるべくちゃんと書きましょう(自省)。

*4:歴史的には、ジェネレータは 1970 年代に CLU や Icon という言語の中で登場していますが、当時の論文にはコルーチンの語が出てこないので、おそらく独立して再発明されたものと思われます。

*5:シングルスレッドの理由としては、性能の低い計算機でも動かせること、バグの元であるマルチスレッドプログラミングをユーザに課さないこと、元々の想定ユースケースではシングルスレッドで問題なかったこと、などが考えられます。なお、WebWorker のような拡張を使うとマルチスレッドができますが、これは置いておきます。

*6:"Promise" については、付録 A で簡単に説明します。

*7:もちろん、実際の実装が構文糖になっているわけではないと思います。

*8:簡単のため、引数は無視しています。

*9:コールバックによる Promise は Python の Twisted ライブラリの deferred から持ってきたようです。

ruby 0.62 のソースコードを復活させた

RubyKaigi の後夜祭で、akr さんが「327 種類の Ruby をビルドする方法 〜0.49 から 2.6.0-preview2 まで〜」という発表をされていました。

その中で、ruby-0.62.tar.gz と ruby-0.63.tar.gz のファイルは「gzip 形式じゃないといわれて展開できない」ということで、ビルド対象から外されていました。

いろいろやって、めでたくこの 2 ファイルを復活させることに成功しました。そのプロセスを書きます。

なお、壊れていたファイルも記念として次の URL に残されています(拡張子が .broken になってます)。

どのように壊れているのかを突き止める

とりあえず当該ファイルをダウンロードし、file してみました。

$ file ruby-0.62.tar.gz ruby-0.63.tar.gz 
ruby-0.62.tar.gz: data
ruby-0.63.tar.gz: data

にべもありません。しょうがないので、バイナリを観察しました。

$ od -c ruby-0.62.tar.gz
0000000   " 253   G 342 302   ;   "       ;   " 243   Y   ' 324 270 354
0000020 210 200 003 262   * 373 016 276   \ 304 325 346 276   e 177 212
0000040 327 214   u 021 030 231   X   F   G 342   ] 231 265 343 216   x
0000060 253 016   ` 222   Y 251 235 255 273   "   *   " 253   b  \v   -
0000100   [   C   N 217 016 257  \f   $ 366 177 361   r   Z 360 256 310
0000120 210 016 310 250   "   (   < 221 207   .   I   ?   &   H 267 004
0000140 021 262   H   N 310 210 016 310 253 211 306   p 035 211 226   d
0000160   Y   * 324 273   "   *   " 253   D 332 257 373 336 353 326 313
0000200   F   P 266 006   v   6 266 235       }   ~ 207   w 337   o   }
0000220 366 257 212 305   ;   O   v   t 032 033 333   v 275   w 024 336
0000240 226 034 330 326 322 373   "   * 240 226   d   Y   * 324 273   "
0000260   *   " 253   B 336 343 214   y 232 032   i 027 332   2   W 336
0000300 206 206   Z 332   [   Z 333 232 266   {   \  \r   0 346   ( 354
0000320   m   {   N   u 274 255 002  \f 217 364   \   1 005   X 273 016
0000340   {   "   * 240 226   d   Y   * 324 273   "   *   " 253   o 312
0000360 374 256 373 346 371 334   j 177 230   8 026   T   = 023  \a 356
0000400 322 177 347   C   W   ~ 347 201 203 221 330 330 332 334 374 350
0000420 375   ; 332 032 233 234 250   ? 246 366 346 273   "   * 240 226
0000440   d   Y   * 324 273   "   *   " 253   V 366 226 207   [   j   ?
0000460 365 251 267   s 354   q 251 320   S   ?   | 377 327 177 357 367
0000500 263 224   ; 353       l   a 247   C   {   * 036 210 220 203   ]
0000520 322 035   Q   U 354 210 200 354 212 275 317 262   " 252 004 273
0000540   "   *   " 253   Q   g   ; 032 025 031   a 367 004   T 005   \
0000560 315 016 307   K   s 261 221 275 222 263 324   y 236   <   q   w
0000600   b 234 201 354 210 200 354 212 266 242   M 245   r 356 275 226
0000620 030 236 326 257   h 357 262   " 252 004 273   "   *   " 253   |
0000640  \r 351   J   "   c   ( 254   5 316 356 227 366 302 357 343   8
0000660   O   ;   c   - 250 211   m   ] 355   < 326 247 225 305 264 362
0000700   M 023 374   c   Q   1 263 205 230 362 352 357   ;   "   * 240
0000720 357 262   " 252 004 273   "   *   " 253   ~   7 200 347 271 002
0000740 366 216   {   D 313   A   L 304 237 030   ~   L 271 337   0 363
0000760 251 274 377  \t 220 222   O   x  \r 304 346   z 266 223 227 240
0001000 265 314 226 254   _   c 262   " 003 262   *   _ 262   " 252 004
0001020 273   "   *   " 253   q 363 351 177 341   2 376 026 337   8 302
0001040   3 323   e   >   C   o 244   R 263 374   &   D 263 330   i 307
0001060   `   D 024   B   !   c 374 223   _ 243 305 303   c 354 210 200

ダブルクォートとアスタリスクが多いな、という印象ですが、さっぱりわかりません。ただ、NUL 文字で埋まっているとかでもないので、完全に無意味なデータとも思えません。

そこでまず、Ruby の歴史を文献調査しました。高橋会長の Ruby 年表によると、Ruby 0.62 は itojun 氏提供のクローズドなメーリングリストで配布されていたらしい。メール配布でデータが壊れる原因と言えば、BASE64uuencode などのバイナリ・テキスト変換が頭をよぎります。

そうこうしていると、shinh さんから重要なヒントが。

xxd -c 59 の結果はこちら。

00000000: 22ab 47e2 c23b 2220 3b22 a359 27d4 b8ec 8880 03b2 2afb 0ebe 5cc4 d5e6 be65 7f8a d78c 7511 1899 5846 47e2 5d99 b5e3 8e78 ab0e 6092 59a9 9dad bb22 2a  ".G..;" ;".Y'.......*...\....e....u...XFG.]....x..`.Y...."*
0000003b: 22ab 620b 2d5b 434e 8f0e af0c 24f6 7ff1 725a f0ae c888 0ec8 a822 283c 9187 2e49 3f26 48b7 0411 b248 4ec8 880e c8ab 89c6 701d 8996 6459 2ad4 bb22 2a  ".b.-[CN....$...rZ......."(<...I?&H....HN.......p...dY*.."*
00000076: 22ab 44da affb deeb d6cb 4650 b606 7636 b69d 207d 7e87 77df 6f7d f6af 8ac5 3b4f 7674 1a1b db76 bd77 14de 961c d8d6 d2fb 222a a096 6459 2ad4 bb22 2a  ".D.......FP..v6.. }~.w.o}....;Ovt...v.w........"*..dY*.."*
000000b1: 22ab 42de e38c 799a 1a69 17da 3257 de86 865a da5b 5adb 9ab6 7b5c 0d30 e628 ec6d 7b4e 75bc ad02 0c8f f45c 3105 58bb 0e7b 222a a096 6459 2ad4 bb22 2a  ".B...y..i..2W...Z.[Z...{\.0.(.m{Nu......\1.X..{"*..dY*.."*
000000ec: 22ab 6fca fcae fbe6 f9dc 6a7f 9838 1654 3d13 07ee d27f e743 577e e781 8391 d8d8 dadc fce8 fd3b da1a 9b9c a83f a6f6 e6bb 222a a096 6459 2ad4 bb22 2a  ".o.......j..8.T=......CW~...........;.....?...."*..dY*.."*
00000127: 22ab 56f6 9687 5b6a 3ff5 a9b7 73ec 71a9 d053 3f7c ffd7 7fef f7b3 943b eb20 6c61 a743 7b2a 1e88 9083 5dd2 1d51 55ec 8880 ec8a bdcf b222 aa04 bb22 2a  ".V...[j?...s.q..S?|.......;. la.C{*....]..QU........"..."*
00000162: 22ab 5167 3b1a 1519 61f7 0454 055c cd0e c74b 73b1 91bd 92b3 d479 9e3c 7177 629c 81ec 8880 ec8a b6a2 4da5 72ee bd96 189e d6af 68ef b222 aa04 bb22 2a  ".Qg;...a..T.\...Ks......y.<qwb.........M.r.......h.."..."*
0000019d: 22ab 7c0d e94a 2263 28ac 35ce ee97 f6c2 efe3 384f 3b63 2da8 896d 5ded 3cd6 a795 c5b4 f24d 13fc 6351 31b3 8598 f2ea ef3b 222a a0ef b222 aa04 bb22 2a  ".|..J"c(.5.......8O;c-..m].<......M..cQ1......;"*..."..."*
000001d8: 22ab 7e37 80e7 b902 f68e 7b44 cb41 4cc4 9f18 7e4c b9df 30f3 a9bc ff09 9092 4f78 0dc4 e67a b693 97a0 b5cc 96ac 5f63 b222 03b2 2a5f b222 aa04 bb22 2a  ".~7......{D.AL...~L..0.......Ox...z........_c."..*_."..."*
00000213: 22ab 71f3 e97f e132 fe16 df38 c233 d365 3e43 6fa4 52b3 fc26 44b3 d869 c760 4414 4221 63fc 935f a3c5 c363 ec88 80ec 8a82 459f e1b7 b222 aa04 bb22 2a  ".q....2...8.3.e>Co.R..&D..i.`D.B!c.._...c......E...."..."*
0000024e: 22ab 57ab 16ef 0d31 4af4 d8df 1879 9388 4e7c 4b4b c885 3ec8 880e c8aa 4d66 6a6a 3bce 49d8 0c63 ea73 1e58 bf1e bfc9 c402 e501 10af b222 aa04 bb22 2a  ".W....1J....y..N|KK..>.....Mfjj;.I..c.s.X..........."..."*
00000289: 22ab 52b8 5cb9 aaf8 54dc fae6 6bde c888 0ec8 a812 bc1a f0fa 4812 f8ec 66f2 6716 044f 0aaa be3d 9b80 e89d 2e98 bf7b 9097 b2b2 456f b222 aa04 bb22 2a  ".R.\...T...k...........H...f.g..O...=.......{....Eo."..."*
000002c4: 22ab 5a5d b673 b8a6 fe49 683e eda5 b599 ad51 57b9 1967 31ca c4f5 de0a bf8b 7810 fb22 203b 22a9 8f2c 65f8 6be3 6c12 ba01 fc6c 0dfb b222 aa04 bb22 2a  ".Z].s...Ih>.....QW..g1.......x.." ;"..,e.k.l....l..."..."*
000002ff: 22ab 52c2 06d5 af81 6c09 ad05 1c93 2c8b fcfb 2220 3b22 ab9f dba8 33ec 8880 ec8a b08a e0a5 8533 669e 3ec8 880e c8ab 2fc5 0bc8 cd04 4636 9fb2 2203 b2  ".R.....l.....,..." ;"....3..........3f.>...../.....F6.."..
0000033a: 22ab 4bbc cbfe 0b2c 2740 2467 44ae 0599 82d2 ef0c 3c73 7525 e085 a127 e738 7acc e7cb 4f08 0548 719e e125 5e27 bf4f 1fbb 222a a004 4636 9fb2 2203 b2  ".K....,'@$gD.......<su%...'.8z...O..Hq..%^'.O.."*..F6.."..
00000375: 22ab 7572 6d1a f013 c5a3 1a06 ec88 80ec 8ab1 a98e ec68 62c8 3db3 9c56 cabb cf68 1963 5888 b79a e142 7c1a a8b7 6c40 1926 425d 47ec 8880 aa02 2203 b2  ".urm................hb.=..V...h.cX....B|...l@.&B]G....."..
000003b0: 22ab 693b 9d46 c8dd 3950 ac8e 2b27 75bb 8353 fc8f 2b11 376c 28d1 e919 429f 5133 10ad 990c a835 8708 3e28 eda8 7959 e5fb 222a a0ec 8880 aa02 2203 b2  ".i;.F..9P..+'u..S..+.7l(...B.Q3.....5..>(..yY.."*......"..
000003eb: 22ab 6b4c 1cd7 d1dd f3f7 bbf4 c83f 2f69 e961 93da 5af4 3dc6 742e 8c6d cf8f ab5e fb22 203b 22a4 2fd4 7bce a1f7 7aec 8880 ec8a 9eb3 3b5c e170 fb22 2a  ".kL.........?/i.a..Z.=.t..m...^." ;"./.{...z.......;\.p."*
00000426: 22ab 45bd cec8 880e c8aa 127a 77b2 2203 b22a 65d7 ed72 4678 7a28 06ac 8482 9a80 8378 eec8 880e c8aa 0301 cbca 1d33 b222 03b2 2abf 9cbc 8974 56d0 45  ".E........zw."..*e..rFxz(.......x...........3."..*....tV.E

各行が必ず 22ab で始まります(shinh さんの言うとおり、この傾向は最初の約 59000 バイトまでで、その後は規則性がなくなります)。

ここで、各行の 3 文字目がだいたいアルファベットに揃っていることに気づきました。これは、3 文字目の上位 2 ビットが固定されている兆候です。つまり、やはり BASE64 ではないか?と思い、59 バイトずつ BASE64 エンコードしてみると

$ ruby -e 'File.binread("ruby-0.62.tar.gz").scan(/.{59}/m) {|s| puts [s].pack("m0") }'
IqtH4sI7IiA7IqNZJ9S47IiAA7Iq+w6+XMTV5r5lf4rXjHURGJlYRkfiXZm14454qw5gklmpna27Iio=
IqtiCy1bQ06PDq8MJPZ/8XJa8K7IiA7IqCIoPJGHLkk/Jki3BBGySE7IiA7Iq4nGcB2JlmRZKtS7Iio=
IqtE2q/73uvWy0ZQtgZ2NradIH1+h3ffb332r4rFO092dBob23a9dxTelhzY1tL7IiqglmRZKtS7Iio=
IqtC3uOMeZoaaRfaMlfehoZa2lta25q2e1wNMOYo7G17TnW8rQIMj/RcMQVYuw57IiqglmRZKtS7Iio=
Iqtvyvyu++b53Gp/mDgWVD0TB+7Sf+dDV37ngYOR2Nja3Pzo/TvaGpucqD+m9ua7IiqglmRZKtS7Iio=
IqtW9paHW2o/9am3c+xxqdBTP3z/13/v97OUO+sgbGGnQ3sqHoiQg13SHVFV7IiA7Iq9z7IiqgS7Iio=
IqtRZzsaFRlh9wRUBVzNDsdLc7GRvZKz1HmePHF3YpyB7IiA7Iq2ok2lcu69lhie1q9o77IiqgS7Iio=
Iqt8DelKImMorDXO7pf2wu/jOE87Yy2oiW1d7TzWp5XFtPJNE/xjUTGzhZjy6u87Iiqg77IiqgS7Iio=
Iqt+N4DnuQL2jntEy0FMxJ8Yfky53zDzqbz/CZCST3gNxOZ6tpOXoLXMlqxfY7IiA7IqX7IiqgS7Iio=
Iqtx8+l/4TL+Ft84wjPTZT5Db6RSs/wmRLPYacdgRBRCIWP8k1+jxcNj7IiA7IqCRZ/ht7IiqgS7Iio=
IqtXqxbvDTFK9NjfGHmTiE58S0vIhT7IiA7Iqk1mamo7zknYDGPqcx5Yvx6/ycQC5QEQr7IiqgS7Iio=
IqtSuFy5qvhU3Prma97IiA7IqBK8GvD6SBL47GbyZxYETwqqvj2bgOidLpi/e5CXsrJFb7IiqgS7Iio=
IqtaXbZzuKb+SWg+7aW1ma1RV7kZZzHKxPXeCr+LeBD7IiA7IqmPLGX4a+NsEroB/GwN+7IiqgS7Iio=

いくつか気づくことがあります。

  • 綺麗に先頭が Iqt で揃っている。よくわからないけれど冗長なデータ。
  • 最後の方の 10 文字くらいは、なんだか前の行と同じことが多い。つまり、59 バイト全部に情報が詰まっているわけではなさそう。*1
  • 先頭の Iqt を含め、Iq が頻出している。これがダブルクォート頻出の正体ですね。

さて、冒頭の Iqt が何なのかはともかく、あきらかに冗長なデータなので、展開に必要な情報ではありません。よって、これを取り除いて BASE64 をデコードしてみようと思うのは自然なことです。

$ ruby -e 'print [File.binread("ruby-0.62.tar.gz")[0, 59]].pack("m0")[3, 60].unpack("m").first' | xxd
00000000: 1f8b 08ec 8880 ec8a 8d64 9f52 e3b2 2200  .........d.R..".
00000010: 0ec8 abec 3af9 7313 579a f995 fe2b 5e31  ....:.s.W....+^1
00000020: d444 6265 6119 1f89 7666 d78e 39         .Dbea...vf..9

"1f 8b 08" がでてきました。これは gzip のファイルヘッダです。冒頭 3 文字が偶然一致するとは思えないので、やはりこれは tar.gz のようです。しかし、このままでは gzip 展開できません。

$ ruby -e 'puts [File.binread("ruby-0.62.tar.gz")[0, 59]].pack("m0")[3, 60].unpack("m").first' | gzip -cd
gzip: stdin is encrypted -- not supported

正常に展開できる ruby-0.60.tar.gz や ruby-0.64.tar.gz を見ると、ヘッダは "1f 8b 08 00 (タイムスタンプ 4 バイト) 00 03" となるのが正しそうです。しかし、上のように、"1f 8b 08 ec" となっているのでダメなようです。

もう少しヒントを得るために、タイムスタンプを探すことにしました。ruby-0.60.tar.gz のタイムスタンプは 0x2ee6c66d (1994-12-08 17:40:13 +0900) 、ruby-0.64.tar.gz のタイムスタンプは 0x2f1267f7 (1995-01-10 19:56:55 +0900) なので、この間の数値と思われます。0x2e か 0x2f のビットパターン、つまり 00101110 か 00101111 を探します。

$ ruby -e 'print [File.binread("ruby-0.62.tar.gz")[0, 59]].pack("m0")[3, 60].unpack("m").first' | xxd -b
00000000: 00011111 10001011 00001000 11101100 10001000 10000000  ......
00000006: 11101100 10001010 10001101 01100100 10011111 01010010  ...d.R
0000000c: 11100011 10110010 00100010 00000000 00001110 11001000  .."...
00000012: 10101011 11101100 00111010 11111001 01110011 00010011  ..:.s.
00000018: 01010111 10011010 11111001 10010101 11111110 00101011  W....+
0000001e: 01011110 00110001 11010100 01000100 01100010 01100101  ^1.Dbe
00000024: 01100001 00011001 00011111 10001001 01110110 01100110  a...vf
0000002a: 11010111 10001110 00111001                             ..9

発見。

$ ruby -e 'print [File.binread("ruby-0.62.tar.gz")[0, 59]].pack("m0")[3, 60].unpack("m").first' | xxd -b
00000000: 00011111 10001011 00001000 11101100 10001000 10000000  ......
00000006: 11101100 10001010 10001101 01100100 10011111 01010010  ...d.R
                                                           ^~~~
0000000c: 11100011 10110010 00100010 00000000 00001110 11001000  .."...
          ~~~~

ここからリトルエンディアンでタイムスタンプの 4 バイトを取り出すと、

$ ruby -e 'print [File.binread("ruby-0.62.tar.gz")[0, 59]].pack("m0")[3, 60].unpack("m").first' | xxd -b
00000000: 00011111 10001011 00001000 11101100 10001000 10000000  ......
00000006: 11101100 10001010 10001101 01100100 10011111 01010010  ...d.R
                                ^~~~ ~~~~^~~~ ~~~~^~~~ ~~~~^~~~
0000000c: 11100011 10110010 00100010 00000000 00001110 11001000  .."...
          ~~~~

0x2ef549d6 (1994-12-19 17:52:38 +0900) になります。夕方なのがそれっぽい *2

ということで、"1f 8b 08 00 (タイムスタンプ 4 バイト) 00 03" のうち、最初の 3 バイトとタイムスタンプの位置は特定できました。が、間の 00 はどこへ行ったのか。

BASE64 なり uuencode なり、6 ビットごとに区切ったデータにノイズが混ざったのではないか、という確信を得つつあったので、6 ビットごとに区切って観察します。

$ ruby -e 'print File.binread("ruby-0.62.tar.gz").unpack1("B*").scan(/.{6}/)[0, 20].join(" ")'
001000 101010 101101 000111 111000 101100 001000 111011 001000 100010 000000 111011 001000 101010 001101 011001 001001 111101 010010 111000
                     ^~~~~~ ~~^~~~ ~~~~^~ ~~~~~~                      ^~~~~~                        ^~~~ ~~~~^~ ~~~~~~ ^~~~~~ ~~^~~~ ~~~~
		     1f       8b       08                             ??????                        timestamp (4 bytes)

いま探しているのは 00 なので、?????? の部分が目につきます。これに着目すると、000000 が "111011 001000 100010" と "111011 001000 101010" で挟まれているんじゃないか?と感じました。他の行も探してみると、どうも "111011 001000 100010" や "111011 001000 101010" は頻出で、その間は 000000 であることに気づきます。まるで、000000 をエスケープするためのモード切替のよう。

と感じた瞬間にピンと来ました。モード切替といえば、ISO-2022-JPエスケープシーケンスだ!

ISO-2022-JP(いわゆる JIS 文字コード)は、"ESC ( B" という 3 文字で ASCII モードに、"ESC ( J" という 3 文字で日本語モードに切り替わる文字エンコーディングです。これが "111011 001000 100010" や "111011 001000 101010" に対応しているんじゃないか。

BASE64 で 000000 は "A" の文字で、"A" だけエスケープされる理由は謎だったので、uuencode を疑います。uuencode はよく知らなかったので、Wikipedia を調べます。

デコードにおいては、変数 c にエンコードされた文字のASCIIコードが入っているとすると (c XOR 0x20) AND 0x3f でデコードできる(範囲外の文字が入っている可能性は考慮していない)。

uuencode - Wikipedia

早速 "ESC ( B" をこれでデコードしてみます。

$ ruby -e '"\e(B".bytes {|c| p "%06b" % ((c ^ 0x20) & 0x3f) }'
"111011"
"001000"
"100010"

$ ruby -e '"\e(J".bytes {|c| p "%06b" % ((c ^ 0x20) & 0x3f) }'
"111011"
"001000"
"101010"

ビンゴ! みごと、問題の断片がでてきました。

古い uuencode で 000000 は、空白文字になります。よって、何らかのアクシデントで、uuencode されたデータの中の空白文字は ASCII モードに、空白文字以外は日本語モードになるように、エスケープシーケンスが混ざってしまったのでしょう(最初の 59000 バイトだけそうなったのは、この時点では原因不明でしたが、あとでわかります)。

こうして見直すと、各行冒頭の "001000 101010" も、エスケープシーケンスの 2 文字目と 3 文字目なんじゃないかと気づきます。1 文字目はどこに行ったのか。

行の先頭はその行に含まれるオクテット数を示す。通常は45オクテットなので「M」であり、45オクテットに満たない行は別の文字となる。

uuencode - Wikipedia

とあります。「M」ではなく ESC 文字がオクテット数として解釈されたのでは?と思い至り、調べます。すると ESC 文字は 0b111011 、つまり 59 です。これが、shinh さんの指摘した 59 バイト周期の理由。本当は 45 オクテットしかないのに、59 オクテットあるとみなして無理やりデコードされたのでした(ちなみに各行 3 つめの 101101 は、uuencode で「M」で、Wikipedia に書いてある本来のオクテット数です)。

59 バイトの終盤部分が妙に繰り返していたのも、45 オクテット分の情報しかないのに 59 オクテットとしてデコードしたため、バッファの終わりのほうがちゃんと初期化されなかったからでしょう。すべてが腑に落ちていきます。

ということで、

という確信を得ました。これを実証するには、エスケープシーケンスっぽい 3 文字を取り除いて uudecode してみればいいのです。

めでたく(冒頭のみですが)gzip 展開できて、tar っぽいデータがでてきました。やった!

gzip の回復を試みる

壊れ方がわかったので、元のメールが得られれば容易に回復できることは明らかでした。が、クローズドなメーリングリストだったので、アーカイブなどはありません。しょうがないので壊れたデータからの回復を試みます。

基本的には、エスケープシーケンスを取り除くだけです。本来 45 バイトなのに、59 バイトあるものとして無理やり uudecode されているため、多少エスケープシーケンスが混ざっていても、情報は欠損しません。それでも、不幸にも大量のエスケープシーケンスが混ざってしまった行については、情報の欠損が発生します。調べてみると、200 バイトほど欠損しているとわかりました。

今回は、ruby-0.60.tar.gz や ruby-0.64.tar.gz が正常に展開できるので、欠損部分もだいたい想像できます。DEFLATE をデコードしていき、欠損部分については前後バージョンから平文を推定し、それを DEFLATE エンコードすることで、欠損データを補完していくスクリプトを書きました。簡単に言ってますが一晩はかかってます。

この方法でデータ部分は回復していけたのですが、残念ながら、途中でハフマンテーブルが 100 ビットほど欠損していることがわかりました。これは致命傷で、自分にはブルートフォースしか思いつきませんでしたが、2^100 のブルートフォースは現代の計算機ではちょっと無理です。

ということで、諦めモードに。

すると

ということで、石塚さんに問合せました。すると、ほんの数時間で「元メイルをお送りします」という返事が! 20 年以上前のメールをパッと引っ張り出せる石塚さんすごい!

あとはごく普通に uudecode したら、無事に解凍できる ruby-0.62.tar.gz と ruby-0.63.tar.gz を得ることができました。復元の苦労はなんだったのか。

ちなみに、ruby-0.62.tar.gz は uuencode で 1000 行ずつ、5 通のメールに分割されて送信されていました。1 通めだけ冒頭に日本語が書かれていて、残りの 4 通は uuencode のデータだけでした。そのせいで、冒頭 59000 バイト程度だけ ISO-2022-JPエスケープシーケンスが混ざっていたのでした。

まとめ

ruby-0.62.tar.gz と ruby-0.63.tar.gz を回復するまでの道のりでした。しいて教訓っぽいものを得るとしたら、目の前の資料を化学分析するだけではなく、発掘のようなフィールドワークも大切にしよう、みたいな。なんにせよ、考古学は楽しい。

なお、回復されたデータはすでに公式に配布されています。

https://cache.ruby-lang.org/pub/ruby/1.0/

また、akr さんの all-ruby にも含めてもらったようです。

*1:C 言語に慣れてる人は、「未初期化メモリを参照したような挙動だな」という直感が働きます。

*2:ruby-0.63.tar.gz のほうは昼過ぎでしたが気にしない。

emruby: emscripten でブラウザで動く MRI

(この記事は Ruby 25th anniversary のための寄稿です)

Ruby をブラウザで動かすというと Opal ですが、他の選択肢として、C で書かれた Ruby 処理系を emscripten で JS に変換するという選択肢もあります。
しかし調べてみたところ、mruby を WebAssembly に変換した記録は見つかりましたが、MRI でやった例が見つけられなかったので、やってみました。

手順

https://github.com/mame/emruby/ に書いてあるとおりです。

ビルドコマンドは次の通り。

$ emconfigure ./configure CFLAGS="-m32 -s EMULATE_FUNCTION_POINTER_CASTS=1"
$ emmake make V=1 miniruby.js EXEEXT=.js

emconfigure は emscriptenコンパイラとして使う前提で configure を動かすためのラッパ。しかしあまり出来はよくなくて、64 bit 環境で動かすと SIZEOF_LONG が 8 と推定されてしまった(JS 上で sizeof(long) は 4 になるので食い違う)ので、手動で "-m32" を与えています。そのため -m32 でコンパイルできる環境が必要で、ubuntu なら apt-get install libc6-dev-i386 などする必要があります。
また、MRI は関数ポインタについてあまり行儀がよくない(3 引数の関数に 4 つの引数を渡すとかがそこらじゅうにある)ので、"-s EMULATE_FUNCTION_POINTER_CASTS=1" を与える必要があります(参考:emscripten の Function Pointer Issues)。
emmake は make のラッパ。単に miniruby.js を生成するだけです。

所感など

  • 動作するまでに細かい問題がいくつかありましたが、Ruby 側を少しだけいじって対応しました(変更 1変更 2変更 3)。Ruby が公式に emscripten に対応するのは難しそうな印象ですが、本体に無害なパッチならこっそり取り込めると思うので、プルリクお願いします。
  • Kernel#emscripten_run_script を生やしています。(パッチ)
  • miniruby ではなく ruby が動かしたい。(プルリクウェルカム)
  • ファイルシステムを調べて irb くらい動くようにしたい。(プルリクウェルカム)
  • Run ボタンが一回しか押せない。プロセス再実行する方法が見つけられなかった。
  • miniruby.js が 29 MB もある。WebAssembly だと 5 MB くらいになるようですが、Chrome で素直に動かなかったのでよく見ていません。
  • WebAssembly で Ruby が Web フロントエンド市場に(今度こそ)進出できるといいなあ。Opal は JS に合わせて Ruby の仕様を歪めてるのがあんまり好きじゃなくて、emscripten/WebAssembly なら幸せになるかと思ったけど、まだよくわかりません。

SA-IS 法のメモ

suffix array を線形時間で構築する SA-IS 法についてのメモです。

SA-IS 法の解説はわりと世の中にいっぱいありますが、実際のプログラムにする方法がよくわからなったり、どうしてそれでうまく行くのか書かれてなくて気持ち悪かったりするものが多くて、自分の望む感じのものがありませんでした。アルゴリズムは当然プログラムで見たいし、厳密な証明は要らないけど直観的な理由は知りたい。

ということで、自分なりの理解を書いてみました。

suffix array とは

文字列の suffix とは、文字列の途中から最後までの部分文字列のことです。題材の文字列を "mmiissiissiippii" とすると、次の 17 個の部分文字列です。

 0 mmiissiissiippii$
 1 miissiissiippii$
 2 iissiissiippii$
 3 issiissiippii$
 4 ssiissiippii$
 5 siissiippii$
 6 iissiippii$
 7 issiippii$
 8 ssiippii$
 9 siippii$
10 iippii$
11 ippii$
12 ppii$
13 pii$
14 ii$
15 i$
16 $

最後の $ は番兵です。

これを普通に辞書順にソートします。文字には普通に全順序があり、番兵は他のどの文字よりも小さいとします。

16 $
15 i$
14 ii$
10 iippii$
 6 iissiippii$
 2 iissiissiippii$
11 ippii$
 7 issiippii$
 3 issiissiippii$
 1 miissiissiippii$
 0 mmiissiissiippii$
13 pii$
12 ppii$
 9 siippii$
 5 siissiippii$
 8 ssiippii$
 4 ssiissiippii$

このときのインデックスの列、[16, 15, 14, 10, 6, 2, 11, 7, 3, 1, 0, 13, 12, 9, 5, 8, 4] を suffix array といいます。今回説明しませんが、suffix array は検索や圧縮などでいろいろと役立つ数列です。

suffix array を求めるプログラムを Ruby でナイーブに書くと、これだけです。

s = "mmiissiissiippii".bytes + [0]

p (0...s.size).sort_by {|i| s[i..-1] }
#=> [16, 15, 14, 10, 6, 2, 11, 7, 3, 1, 0, 13, 12, 9, 5, 8, 4]

このプログラムは、ソートに O(n log n) 、しかも各比較に O(n) もかかるので、全体で O(n^2 log n) もかかります。SA-IS はこれを O(n) でやってしまいます。すごい。

SA-IS 法の超概要

流れとしては、次のような感じのアルゴリズムです。

  1. 適当な「種」を元に、induced sort というのをやる → 間違った suffix array が得られる
  2. 間違った suffix array を使って、正しい「種」を得る
  3. 正しい「種」を元に、induced sort をもう一度やる → 正しい suffix array が得られる

「種」が何かはあとで説明するとして、最初の目標は induced sort というものを理解することです。しかし induced sort を理解するには、「L 型と S 型」「LMS」「ビン」という概念をまず理解する必要があります。順に説明します。

L 型と S 型

文字列 s のインデックス i から始まる suffix を s[i..] と書くことにします。s[0..] = "mmiissiissiippii$" です。

各インデックスを、次のルールで L 型と S 型に分けます。

  • 最後(番兵)のインデックスは S 型
  • s[i..] > s[i+1..] だったらインデックス i は L 型(i は i+1 より Larger)
  • s[i..] < s[i+1..] だったらインデックス i は S 型(i は i+1 より Smaller)

「インデックス i が L 型」と言ったり、「s[i..] が L 型」と言ったりします。なお、すべての suffix は長さが異なるので、s[i..] == s[i+1..] になることはありません。

例題の文字列を分類すると次の通り。

mmiissiissiippii$
LLSSLLSSLLSSLLLLS

これを計算するには、文字列を逆順に走査して決めていけばいいです。基本的に s[i] と s[i+1] の文字を比べて決めていきます。

# 題材の文字列
s = "mmiissiissiippii".bytes + [0]
k = 256 # 文字種の数

# L 型か S 型か
t = [nil] * s.size

# 最後は S
t[-1] = :S

(s.size - 2).downto(0) do |i|
  # s[i] < s[i+1] なら明らかに s[i..] < s[i+1..] => i は S 型
  # s[i] > s[i+1] なら明らかに s[i..] > s[i+1..] => i は L 型
  # s[i] == s[i+1] の場合、s[i..] <=> s[i+1..] の比較結果は
  # s[i+1..] <=> s[i+2..] に準ずる (つまり t[i + 1] と同じ)
  case
  when s[i] < s[i + 1] then t[i] = :S
  when s[i] > s[i + 1] then t[i] = :L
  else                      t[i] = t[i + 1]
  end
end

LMS と LMS 部分文字列

インデックス i - 1 が L 型、i が S 型になっているとき、i を LMS(Left-most S, 最も左の S)と言います。

例題で言えば、2 番目、6 番目、10 番目、16 番目が LMS 。印をつけた位置。

          1111111
01234567890123456
mmiissiissiippii$
LLSSLLSSLLSSLLLLS
  ^   ^   ^     ^ <= LMS のインデックス

ついでに、LMS から次の LMS までの部分文字列を LMS 部分文字列と言います。これはだいぶ後で出てきます。

mmiissiissiippii$
LLSSLLSSLLSSLLLLS
  ^   ^   ^     ^
  iissi           <= LMS 部分文字列
      iissi       <= LMS 部分文字列
          iippii$ <= LMS 部分文字列
                $ <= LMS 部分文字列

ビン

まず、文字列 s と同じ長さの配列 sa を用意します。ここに suffix array の数列を入れるのが目標です。

# 作業領域
sa = [nil] * s.size

冒頭の suffix array を見ると、i で始まる suffix は 1 番目から 8 番目、m で始まる suffix は 9 番目から 10 番目、というように、suffix の先頭の文字ごとに範囲が決まっています。この範囲を、文字の「ビン」といいます。たとえば、「文字 i のビン」は 1 番目から 8 番目です。

このビンは、文字列 s の中の各文字の出現回数を数えればわかります。

# s に出現する文字種ごとのカウント
bin = [0] * (k + 1)
s.each {|ch| bin[ch + 1] += 1 }

# 文字種を累積することで bin のインデックスを決める
sum = 0
bin = bin.map {|v| sum += v }

これによって、文字 ch で始まる suffix は、sa の bin[ch] 番目から bin[ch+1] - 1 番目のどこかに入れればよい、ということになります。

それから、L 型の suffix と S 型の suffix が同じビンに入る場合(つまり先頭の文字が同じ場合)、必ず L 型の方を前に入れることになります。理由は→*1

ということで、配列 sa を次のように表現することにします。

 0 $ S : --
 1 i L : --
 2 i L : --
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S : --
 7 i S : --
 8 i S : --
 9 m L : --
10 m L : --
11 p L : --
12 p L : --
13 s L : --
14 s L : --
15 s L : --
16 s L : --

左端の数字は sa 内のインデックス、その右の文字はビン、さらにその右の文字は L 型か S 型かを表してます。たとえば、i で始まる S 型の suffix は 3 番目から 8 番目のどこかに入ります。induced sort では、このルールを満たすように suffix のインデックスを入れていきます。

induced sort

いよいよ最初の目標であった induced sort の説明に入ります。induced sort は 3 つの段階からなります。

  1. LMS のインデックスをビンの終わりから詰めていく
  2. L 型のインデックスをビンの頭から詰めていく
  3. S 型のインデックスを(LMS を含めて再度)ビンの終わりから詰めていく

とりあえずアルゴリズムを説明して、それからそれがだいたい何をやっているか説明します。

induced sort: ステップ 1

ステップ 1 は、LMS のインデックスを詰めていきます。LMS の 2 、6 、10 、16 を、それぞれ i 、i 、i 、$ のビンに終わりから入れます。

 0 $ S : 16 $
 1 i L : --
 2 i L : --
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S :  2 iissiissiippii$
 7 i S :  6 iissiippii$
 8 i S : 10 iippii$
 9 m L : --
10 m L : --
11 p L : --
12 p L : --
13 p L : --
14 p L : --
15 s L : --
16 s L : --

右端に、インデックスから始まる suffix を参考に書いています。

ステップ 1 を Ruby で書くとこんな感じ。

# インデックス i が LMS かどうか
def lms?(t, i)
  i > 0 && t[i - 1] == :L && t[i] == :S
end

# LMS のインデックスだけ取り出したリスト(「種」)
lmss = (0...s.size).select {|i| lms?(t, i) }

# ステップ 1: LMS のインデックスをビンの終わりの方から入れる

count = [0] * k # ビンごとにすでに挿入した数をカウントする

# 挿入する順序は適当
lmss.reverse_each do |i|
  ch = s[i]
  # ch を入れるビンの終わり (bin[ch + 1] - 1) から詰めていれる
  sa[bin[ch + 1] - 1 - count[ch]] = i
  count[ch] += 1
end

実はこのとき、LMS をどういう順序で挿入するかが、超概要で言っていた「種」です。正しい順で LMS を挿入すれば、induced sort によって正しい suffix array が計算できてしまいます。しかし、この時点で正しい順序はわからないので、適当に 2 、6 、10 と並べました。正しくは上から 10 、6 、2 の順にならないといけないので、不正解です。最終的な結果も間違ったものになります。しかし不思議なことに、その間違った結果から、正しい「種」を抽出できるのです。詳しくは後で。

induced sort: ステップ 2

ステップ 2 は、sa を正順に走査して L 型の suffix を埋めていきます。

まず、sa に入っている最初のインデックスは 16 です。その 1 つ前のインデックス 15 は L 型なので、ステップ 2 で扱う対象です。s[15] は i なので i のビンに入れます。このとき、ビンの頭に詰めます。

 0 $ S : 16 $    <===== 今見ているところ
 1 i L : 15 i$   <===== 挿入位置
 2 i L : --
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S :  2 iissiissiippii$
 7 i S :  6 iissiippii$
 8 i S : 10 iippii$
 9 m L : --
10 m L : --
11 p L : --
12 p L : --
13 p L : --
14 p L : --
15 s L : --
16 s L : --

このとき、「挿入位置」は必ず「今見ているところ」より後に来ます。理由→*2

次は、入れたばかりの 15 です。14 も L 型なので入れます。これを繰り返していくと、最終的に次のようになります。

 0 $ S : 16 $
 1 i L : 15 i$
 2 i L : 14 ii$
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S :  2 iissiissiippii$
 7 i S :  6 iissiippii$
 8 i S : 10 iippii$
 9 m L :  1 miissiissiippii$
10 m L :  0 mmiissiissiippii$
11 p L : 13 pii$
12 p L : 12 ppii$
13 s L :  5 siissiippii$
14 s L :  9 siippii$
15 s L :  4 ssiissiippii$
16 s L :  8 ssiippii$

ステップ 2 を Ruby で書くとこんな感じ。

# ステップ 2: sa を昇順に走査していく

count = [0] * k # ビンごとにすでに挿入した数をカウントする

sa.each do |i|
  next if i == nil
  next if i == 0
  next if t[i - 1] == :S

  # sa に入っているインデックス i について、i - 1 が L 型であるとき、
  # 文字 s[i - 1] に対応するビンに i - 1 を頭から詰めていれる
  ch = s[i - 1]
  sa[bin[ch] + count[ch]] = i - 1
  count[ch] += 1
end

induced sort: ステップ 3

ステップ 3 は、sa を逆順に捜査して S 型の suffix を埋めていきます。LMS も S 型の一種なので埋めなおします。

まず、sa の最後に入っているインデックスは 8 です。その 1 つ前のインデックス 7 は S 型なので埋めます。s[7] は i なので i のビンに入れます。このとき、ビンの終わりから詰めていれます。

 0 $ S : 16 $
 1 i L : 15 i$
 2 i L : 14 ii$
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S :  2 iissiissiippii$
 7 i S :  6 iissiippii$
 8 i S :  7 issiippii$   <===== 挿入位置
 9 m L :  1 miissiissiippii$
10 m L :  0 mmiissiissiippii$
11 p L : 13 pii$
12 p L : 12 ppii$
13 s L :  5 siissiippii$
14 s L :  9 siippii$
15 s L :  4 ssiissiippii$
16 s L :  8 ssiippii$    <===== 今見ているところ

ステップ 2 と同じように、「挿入位置」は必ず「今見ているところ」より前に来ます。理由も同様です。

なお、もともと入っていた 10 を書きつぶしていることに注意。最初から入っていた LMS は("$" を除いて)いったん全部書きつぶされ、その後で再挿入されます。理由は次の節で。

これを繰り返すと、最終的に次のようになります。

 0 $ S : 16 $
 1 i L : 15 i$
 2 i L : 14 ii$
 3 i S : 10 iippii$
 4 i S :  2 iissiissiippii$
 5 i S :  6 iissiippii$
 6 i S : 11 ippii$
 7 i S :  3 issiissiippii$
 8 i S :  7 issiippii$
 9 m L :  1 miissiissiippii$
10 m L :  0 mmiissiissiippii$
11 p L : 13 pii$
12 p L : 12 ppii$
13 s L :  5 siissiippii$
14 s L :  9 siippii$
15 s L :  4 ssiissiippii$
16 s L :  8 ssiippii$

確かに LMS の 2 と 6 と 10 が(元と異なる位置に)挿入されています。

こうして得られた sa は、ほぼソートされているように見えますが、一部間違っています。例えば、s[4..] = "ssiissiippii$" が 15 番目、s[8..] = "ssiippii$" が 16 番目に来ていますが、この順序は逆ですね。これは後で直します。

Ruby はこちら。

# ステップ 3: sa を逆順に走査していく

count = [0] * k # ビンごとにすでに挿入した数をカウントする

sa.reverse_each do |i|
  next if i == nil
  next if i == 0
  next if t[i - 1] == :L

  # sa に入っているインデックス i について、i - 1 が S 型であるとき、
  # 文字 s[i - 1] に対応するビンに i - 1 を終わりから詰めていれる
  ch = s[i - 1]
  sa[bin[ch + 1] - 1 - count[ch]] = i - 1 # 上書きすることもある
  count[ch] += 1
end

induced sort の結果の考察

induced sort をしたとき、その結果はどんな性質を満たしているでしょうか。

ステップ 1 はビンソートなので、少なくとも各 suffix の最初の文字についてはちゃんとソートできています。しかし、各 suffix の 2 文字目以降はソートされていないかもしれません。次の図はステップ 1 の結果で、ソートされていないかもしれないところを ... で省略して表示しています。

 0 $ S : 16 $
 1 i L : --
 2 i L : --
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S :  2 i...
 7 i S :  6 i...
 8 i S : 10 i...
 9 m L : --
10 m L : --
11 p L : --
12 p L : --
13 s L : --
14 s L : --
15 s L : --
16 s L : --

ステップ 2 では、すでに入っている suffix より 1 つ長い suffix を入れていきます。このとき、先頭 n 文字についてソートされていた suffix を 1 つ伸ばした suffix は、先頭 n + 1 文字がソートされていることが保証されます。理由→*3

これを繰り返すと、ステップ 2 完了時点で次のようになります。

 0 $ S : 16 $
 1 i L : 15 i$
 2 i L : 14 ii$
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S :  2 i...
 7 i S :  6 i...
 8 i S : 10 i...
 9 m L :  1 mi...
10 m L :  0 mmi...
11 p L : 13 pii$
12 p L : 12 ppii$
13 s L :  5 si...
14 s L :  9 si...
15 s L :  4 ssi...
16 s L :  8 ssi...

ステップ 3 はステップ 2 と全く同様です。

 0 $ S : 16 $
 1 i L : 15 i$
 2 i L : 14 ii$
 3 i S : 10 iippii$
 4 i S :  2 iissi...
 5 i S :  6 iissi...
 6 i S : 11 ippii$
 7 i S :  3 issi...
 8 i S :  7 issi...
 9 m L :  1 mi...
10 m L :  0 mmi...
11 p L : 13 pii$
12 p L : 12 ppii$
13 s L :  5 si...
14 s L :  9 si...
15 s L :  4 ssi...
16 s L :  8 ssi...

ということで、... になっていない部分についてはソートされていることが保証されます。これが induced sort によって言えること。

さて、もしもステップ 1 の段階で、LMS が正しい順序(「種」)で挿入されていたとします。ステップ 2 とステップ 3 の「先頭 n 文字についてソートされている suffix を元に、1 つ長い suffix を先頭 n + 1 文字についてソートされた状態で挿入する」という性質から、正しい「種」から始めて最終的に得られる sa は、すべての suffix の全体についてソートされていることになります。それはすなわち、正しい suffix array です。

ということで、どうにか正しい「種」を得るというのが残る課題です。実はこれは、上記の「間違った induced sort の結果」を使って取り出すことができるのですが、その前に正しい「種」とは何かを考察します。

正しい「種」

正しい「種」を取り出すナイーブな実装としては、LMS の suffix を列挙して、辞書順にソートすればいいです。

LMS の suffix を列挙したもの。

 2: iissiissiippii$
 6: iissiippii$
10: iippii$
16: $

↓ソート

16: $
10: iippii$
 6: iissiippii$
 2: iissiissiippii$

この [16, 10, 6, 2] が求める「種」です。induced sort のステップ 1 で、この「種」を逆順に走査して、各ビンの最後から詰めていくと次のようになります。

 0 $ S : 16 $
 1 i L : --
 2 i L : --
 3 i S : --
 4 i S : --
 5 i S : --
 6 i S : 10 iippii$
 7 i S :  6 iissiippii$
 8 i S :  2 iissiissiippii$
 9 m L : --
10 m L : --
11 p L : --
12 p L : --
13 p L : --
14 p L : --
15 s L : --
16 s L : --

この状態でステップ 2 と 3 を実行すれば、めでたく正しい suffix array が得られます。

ただ、ナイーブな実装では O(n) が達成できません。そこで、このソートに SA-IS 法を再帰的に使うというのが、SA-IS 法の肝です。

SA-IS 法の再帰

LMS の suffix の列を SA-IS 法でソートするために、suffix の文字単位を「粗く」するのがポイントです。

"mmiissiissiippii$" を LMS 部分文字列(LMS を導入したときについでに説明してました)で分割すると、["iissi", "iissi", "iippii$", "$"] になります *4 。ここで、"iissi" や "iippii$" を 1 つの「文字」とみなし、この列を「文字列」と考えます。そして、この「文字列」のすべての suffix を並べてみます。

0: ["iissi", "iissi", "iippii$", "$"] ( 2: iissiissiippii$)
1: ["iissi", "iippii$", "$"]          ( 6: iissiippii$)
2: ["iippii$", "$"]                   (10: iippii$)
3: ["$"]                              (16: $)

最後の "(2: iissiissiippii$)" や "(16: $)" は、各 suffix が元の文字列のどの suffix に対応するかを表しています。

各「文字」の順序関係("$" < "iippii$" < "iissi")に注意しつつ、この「文字列」の suffix の列をソートします。

3: ["$"]                              (16: $)
2: ["iippii$", "$"]                   (10: iippii$)
1: ["iissi", "iippii$", "$"]          ( 6: iissiippii$)
0: ["iissi", "iissi", "iippii$", "$"] ( 2: iissiissiippii$)

注目すべきは、元文字列のインデックスの列。めでたく、[16, 10, 6, 2] という正しい「種」が得られています。

ところで、今おこなったソートは、"iissi" などを「文字」とみなした「文字列」の suffix array を作ったのと同じです。よって SA-IS 法が再帰的に適用できます。再帰すると全体で O(n) にならなくなりそうですが、「文字列」の長さは元の文字列の長さに比べて半分未満になってるので、O(n + n/2 + n/4 + ...) = O(2n) = O(n) ということで、線形時間が保たれます。すごい。

ちなみに、このアルゴリズム構成技法を再帰減速(recursive slowdown)といいます。余談ですが、これを遅延評価でやった暗黙的再帰減速(implicit recursive slowdown)という技法もあります。こういうのが面白いなと思った人は、次の本がとても面白いかもしれません。

純粋関数型データ構造
Chris Okasaki
KADOKAWA (2017-04-28)
売り上げランキング: 82,013

「文字」に番号を振る

さて、"iissi" や "iippii$" を 1 つの「文字」として扱うと言いましたが、実際にこういう部分文字列を切り出すと、比較に O(n) かかってしまうのでダメです。そこで、次のように番号を振ることを考えます。

"$"       => 0
"iippii$" => 1
"iissi"   => 2

この番号付けは、"$" < "iippii$" < "iissi" という順序関係を維持しています。そして、番号同士なら比較が O(1) でできます。よって、番号で置き換えてから SA-IS 法を再帰すれば OK です。

ただ、この番号を振る方法は自明ではありません。下手をしたら番号を振るために O(n^2) とかかかってしまいます。

この番号付けのために、1 回目の induced sort の(間違った)結果が使えます。再掲。

 0 $ S : 16 $
 1 i L : 15 i$
 2 i L : 14 ii$
 3 i S : 10 iippii$
 4 i S :  2 iissi...
 5 i S :  6 iissi...
 6 i S : 11 ippii$
 7 i S :  3 issi...
 8 i S :  7 issi...
 9 m L :  1 mi...
10 m L :  0 mmi...
11 p L : 13 pii$
12 p L : 12 ppii$
13 s L :  5 si...
14 s L :  9 si...
15 s L :  4 ssi...
16 s L :  8 ssi...

ここから、LMS の suffix だけを取り出してみます。

 0 $ S : 16 $
 3 i S : 10 iippii$
 4 i S :  2 iissi...
 5 i S :  6 iissi...

... を除くと、LMS 部分文字列ばかり出てきました。これは偶然ではありません。理由→*5

よって、この情報を活用することで、さっきのような番号付けを実現できます。隣り合う LMS 部分文字列を比べて、異なる場合は別の番号を、同じ場合は同じ番号を順に振っていけば OK です。具体的には次のような感じ。

  • "$" に番号 0 を振っておく
  • "$" と "iippii$" は異なるので、"iippii$" に番号 1 を振る
  • "iippii$" と "iissi" は異なるので、"iissi" に番号 2 を振る
  • "iissi" と "iissi" は同じなので、新しい番号は振らない

これで所望の番号付けができました。ちなみに、このときは LMS 部分文字列を直接比較しますが、文字の比較回数の合計が O(n) なので、問題ありません。

実装

実際にほしいのは、単なる番号付けではなく、["iissi", "iissi", "iippii$", "$"] の各 LMS 部分文字列を番号で置き換えたもの、つまり [2, 2, 1, 0] です。これを一気に求めます。

# induced sort の結果から LMS の suffix だけ取り出す
sa = sa.select {|i| lms?(t, i) }

# LMS のインデックス i に対して番号 nums[i] を振る
nums = []

# sa[0] の LMS は $ と決まっているので、番号 0 を振っておく
nums[sa[0]] = num = 0

# 隣り合う LMS を比べる
sa.each_cons(2) do |i, j|
  diff, d = false, 0

  # 隣り合う LMS 部分文字列の比較
  s.size.times do |d|
    if s[i + d] != s[j + d] || lms?(t, i + d) != lms?(t, j + d)
      # LMS 部分文字列の範囲で異なる文字があった
      diff = true
      break
    elsif d > 0 && (lms?(t, i + d) || lms?(t, j + d))
      # LMS 部分文字列の終端に至った
      break
    end
  end

  # 隣り合う LMS 部分文字列が異なる場合は、番号を増やす
  num += 1 if diff
  
  # LMS のインデックス j に番号 num を振る
  nums[j] = num
end

# nums の中に出現する番号のみを並べると、LMS 部分文字列を番号に置き換えた列が得られる
nums = nums.compact

sa.each_cons(2) の中で sa.size.times を使っているので、一瞬 O(n^2) の二重ループのようにも見えますが、よく考えるとループの実行回数は最大でも元の文字列全体を 1 回走査するのと同じなので、O(n) に収まります。

さて、これで得られた nums に SA-IS 法を再帰適用します。ただ、もし隣り合う LMS 部分文字列が全部異なるものだった場合、つまり番号の重複がない場合は、いちいち再帰するまでもなく、ビンソート(各ビンのサイズは 1)の考え方で suffix array を直接求めることができます。

if num + 1 < nums.size
  # 番号の重複があるので再帰
  sa = sa_is(nums, num + 1)
else
  # 番号の重複がない場合、suffix array を容易に求められる
  sa = []
  nums.each_with_index {|ch, i| sa[ch] = i }
end

そして、これで得られる sa は上記で言う [3, 2, 1, 0] に相当する数列なので、これを LMS インデックスの列 [16, 10, 6, 2] に変換します。

lmss = (0...s.size).select {|i| lms?(t, i) }
seed = sa.map {|i| lmss[i] }

そして、この「種」を元に induced sort を再度行えば、ついに完了です。長かった。

まとめ

suffix array を O(n) で作るアルゴリズム SA-IS 法を説明しました。

世にある解説が自分にはいまいちわかりにくいものしか見つからなかったので書いてみましたが、やっぱりこれも他の人にとってはわかりにくいものになっているのかもしれません。コメントをくれたら改良を考えます。

おまけ:プログラム全体

# インデックス i が LMS かどうか
def lms?(t, i)
  i > 0 && t[i - 1] == :L && t[i] == :S
end

def induced_sort(s, k, t, lmss)
  # 作業領域
  sa = [nil] * s.size

  # s に出現する文字種ごとのカウント
  bin = [0] * (k + 1)
  s.each {|ch| bin[ch + 1] += 1 }

  # 文字種を累積することで bin のインデックスを決める
  sum = 0
  bin = bin.map {|v| sum += v }
  
  # ステップ 1: LMS のインデックスをビンの終わりの方から入れる

  count = [0] * k # ビンごとにすでに挿入した数をカウントする

  lmss.reverse_each do |i|
    ch = s[i]
    # ch を入れるビンの終わり (bin[ch + 1] - 1) から詰めていれる
    sa[bin[ch + 1] - 1 - count[ch]] = i
    count[ch] += 1
  end

  # ステップ 2: sa を昇順に走査していく

  count = [0] * k # ビンごとにすでに挿入した数をカウントする

  sa.each do |i|
    next if i == nil
    next if i == 0
    next if t[i - 1] == :S

    # sa に入っているインデックス i について、i - 1 が L 型であるとき、
    # 文字 s[i - 1] に対応するビンに i - 1 を頭から詰めていれる
    ch = s[i - 1]
    sa[bin[ch] + count[ch]] = i - 1
    count[ch] += 1
  end

  # ステップ 3: sa を逆順に走査していく

  count = [0] * k # ビンごとにすでに挿入した数をカウントする

  sa.reverse_each do |i|
    next if i == nil
    next if i == 0
    next if t[i - 1] == :L

    # sa に入っているインデックス i について、i - 1 が S 型であるとき、
    # 文字 s[i - 1] に対応するビンに i - 1 を終わりから詰めていれる
    ch = s[i - 1]
    sa[bin[ch + 1] - 1 - count[ch]] = i - 1 # 上書きすることもある
    count[ch] += 1
  end

  sa
end

def sa_is(s, k)
  # L 型か S 型かのテーブル
  t = [nil] * s.size

  # 最後は S
  t[-1] = :S

  (s.size - 2).downto(0) do |i|
    # s[i] < s[i+1] なら明らかに s[i..] < s[i+1..] => i は S 型
    # s[i] > s[i+1] なら明らかに s[i..] > s[i+1..] => i は L 型
    # s[i] == s[i+1] の場合、s[i..] <=> s[i+1..] の比較結果は
    # s[i+1..] <=> s[i+2..] に準ずる (つまり t[i + 1] と同じ)
    case
    when s[i] < s[i + 1] then t[i] = :S
    when s[i] > s[i + 1] then t[i] = :L
    else                      t[i] = t[i + 1]
    end
  end

  # LMS のインデックスだけを集めた配列
  lmss = (0...s.size).select {|i| lms?(t, i) }

  # 適当な「種」:seed = lmss.shuffle でもよい
  seed = lmss

  # 1 回目の induced sort
  sa = induced_sort(s, k, t, seed)

  # induced sort の結果から LMS の suffix だけ取り出す
  sa = sa.select {|i| lms?(t, i) }

  # LMS のインデックス i に対して番号 nums[i] を振る
  nums = []

  # sa[0] の LMS は $ と決まっているので、番号 0 を振っておく
  nums[sa[0]] = num = 0

  # 隣り合う LMS を比べる
  sa.each_cons(2) do |i, j|
    diff, d = false, 0

    # 隣り合う LMS 部分文字列の比較
    s.size.times do |d|
      if s[i + d] != s[j + d] || lms?(t, i + d) != lms?(t, j + d)
        # LMS 部分文字列の範囲で異なる文字があった
        diff = true
        break
      elsif d > 0 && (lms?(t, i + d) || lms?(t, j + d))
        # LMS 部分文字列の終端に至った
        break
      end
    end

    # 隣り合う LMS 部分文字列が異なる場合は、番号を増やす
    num += 1 if diff
  
    # LMS のインデックス j に番号 num を振る
    nums[j] = num
  end

  # nums の中に出現する番号のみを並べると、LMS 部分文字列を番号に置き換えた列が得られる
  nums = nums.compact

  if num + 1 < nums.size
    # 番号の重複があるので再帰
    sa = sa_is(nums, num + 1)
  else
    # 番号の重複がない場合、suffix array を容易に求められる
    sa = []
    nums.each_with_index {|ch, i| sa[ch] = i }
  end

  # 正しい「種」
  seed = sa.map {|i| lmss[i] }

  # 2 回目の induced sort
  sa = induced_sort(s, k, t, seed)

  sa
end

# 題材の文字列
s = "mmiissiissiippii".bytes + [0]
k = 256 # 文字種の数
p sa_is(s, k)

なお、このプログラムは Ruby らしく大変富豪的に書かれています(配列作りまくり)。元論文の C プログラムは、ビンの位置以外の配列をすべて SA という 1 つの配列の再利用で解決していてかっこいいです。

出典

  • Ge Nong, Sen Zhang, and Wai Hong Chan. Two Efficient Algorithms for Linear Time Suffix Array Construction

追記(2018-02-10):コメントでの指摘を受けてバグ修正。「隣り合う LMS 部分文字列の比較」のループ終了条件が間違ってました。

*1:L 型は、1 文字目が 2 文字目より Larger です(例:"ba...")。S 型は、1 文字目が 2 文字目より Smaller です(例:"bc...")。明らかに "ba..." < "bc..." なので、確かに L 型は S 型より前に来てます。1 文字目と 2 文字目が同じになっている文字列の場合もまあ同じように証明できます。

*2:インデックス i に対して i-1 が L 型のときだけ挿入する。L 型の定義から s[i-1..] > s[i..] 。つまり s[i-1..] の挿入位置は s[i..] より後になる。

*3:インデックス 10 の suffix "i..." は先頭 1 文字についてソートされています。今回は、インデックス 10 を元に、インデックス 9 の suffix "si..." が sa[15] の位置に挿入されました。これに注目してみます。もしも "si..." を s[15] に入れることが間違いだとしたら、sa[15] は文字 s のビン内なので、"si..." より大きいか、または小さい文字列が入るべきだったことになります。もし仮に、s[15] の位置には "si..." より大きい文字列(たとえば "sz...")が入るべきだったとすると、s[13] から s[14] はすでに埋まっていることから、"si..." はいったいどこに行けばいいのかわからない、ということになるので矛盾。s[15] の位置に "si..." より小さい文字列(たとえば "sa...")が入るべきだったとすると、a の文字のビンの中に "a..." のような文字列があったはずです。そしてステップ 2 では上から順番に処理しているので、その文字列が先に処理され、sa[15] にはすでに "sa..." が入っていたはずです。しかし実際には sa[15] にそういう文字列が入っていなかったので、矛盾。ということで、インデックス 5 の suffix "si..." が入るのが正しいということになります。

*4:先頭の "mm" は LMS 部分文字列ではないので捨てます。また、LMS 部分文字列の切れ目で 1 文字重複してます。

*5:特定の suffix に注目して induced sort の動きを見てみます。ステップ 1 で sa[8] (sa の 8 番目) に入れられたインデックス 10 に注目してみましょう。ステップ 2 では、インデックス 10 を元に、L 型インデックス 9 が s[14] に入れられました。そのインデックス 9 を元に、L 型インデックス 8 が s[16] に入れられました。次のインデックス 7 は S 型なので、ステップ 2 はここで終わりです。ステップ 3 では、インデックス 8 を元に、S 型インデックス 7 が s[8] に入れられました。インデックス 7 を元に、S 型インデックス 6 が s[5] に入れられました。次のインデックス 5 は L 型なので、ステップ 3 はここで終わり。要するに、LMS から始めてその前の L 型を順次追加し、さらにその前の S 型を順次追加する、スタートの LMS からみて 1 つ前の LMS にたどり着いた時点で終了、という動きになっています。LMS から 1 つ前の LMS までの範囲(すなわち LMS 部分文字列)についてソートされる、ということになります。

『テスト駆動開発』を読んで

テスト駆動開発
テスト駆動開発
posted with amazlet at 17.10.12
Kent Beck
オーム社
売り上げランキング: 563

オーム社さまから電子書籍を贈本いただきました。ありがとうございます。

本書はテスト駆動開発(TDD)の原典で、たいへん有名な本です。が、自分は食わず嫌いで読んだことがありませんでした。

というか、TDD 自体もちゃんと理解したことがありませんでした。なんだろう、なんか怖かった。

そんな自分が今回この本をいまさら読んでみたら、なるほどこれは確かにいい本でした。なんというか、語りたくなる感じ。ということでご紹介。

紹介

テストとプログラムを交互に書いていく開発方法 TDD を、例題を用いて実演していく本です。

TDD というと「プログラムより先にテストを書く」というところだけ強調されますが、正直それではよくわからないのでした *1 。本書によると、

  1. テストを 1 つ書き足す
  2. それをパスする仮実装を追加する
  3. 仮実装をまともな実装にする

を細かく繰り返す、というものだそうです。仮実装は本当にテキトーで、テストの期待値をそのままプログラムに埋め込んだりします。「仮実装をまともな実装にする」は、本書では「テストとプログラムの間で重複を省く」と表現されています。というのも、プログラムに期待値を埋め込むことで、その期待値がテストとプログラムの間で重複するので。この重複をいい感じに省くことで、徐々にまともな実装になっていく。

テスト駆動開発」という名前ですが、テストを書くための方法ではなく、あくまで設計開発の方法ということがよくわかりました。テストはあくまで実装のガイド。テストはそえるだけ。

構成としては、第 1 部は通貨の足し算や掛け算を扱うプログラムを Java で、第 2 部はテスティングフレームワークPython で、それぞれ TDD の実演で開発してみせます。上記の繰り返しそのときどきの思考が、なんというか非常に生々しく書かれていて、ライブ感に溢れています(訳者あとがきで「まるで Kent Beck とペア・プログラミングしているかのような体験をしました」と書かれていて、まさにそんな感じ)。第 3 部は TDD にまつわる色々な話題を集めていて、まえがきによると「リファレンスとして使うのがよいだろう」だそうですが、自分の印象としてはエッセイ集みたいな感じです。ただ、第 3 部はまだ流し読みしかしていないので、あとでちゃんと読む。

本書自体も(読んだことのなかった自分には)面白い内容でしたが、この翻訳には訳者の t_wada さんによる「訳者解説:テスト駆動開発の現在」という付録がついてます。TDD の原著が出てから現在までの歴史と現状が非常にコンパクトにまとまっていて、さらに現代で TDD とどう向き合っていくべきかが書かれています。ここの良さを説明するのは困難ですが、とりあえず、自分が TDD を強迫観念みたいに感じていた理由と、別に怖くない(人もいる)というのがよくわかりました。

所感

まあ、自分が TDD を実践したくなったかと言うと、そうでもないです。TDD の真のポイントは TODO 管理だと思うんですよね。仮実装が一部仮のまま次のテストに進むことがあったり、テストとプログラムの間で頻繁にコンテキストスイッチしたりするので、TODO を忘れずにこなせる人でないと厳しそう。普段の生活でも TODO 管理が辛いのに。

とはいえ、テストをパスする状態を維持するというのは強く共感しました(というか、こういう本などが布教した考え方なんだろう)。Quine を書くときも、まずはでかくて不格好でもとにかく動く Quine にし、そのあとは動く状態を維持しつつ形や長さを改良する修正を少しずつやっていきますよね。うん。あと、こういう頻繁にテストを実行するやり方では、コンパイルに数秒もかかるような言語処理系では無理だよねー。

それから、TDD が別に万能ではないことがちゃんと書かれているのが好印象でした。設計のひらめき自体は TDD では得られない(83 ページ)とか、アサーションで使う述語自体が間違ってたら TDD は無力になる(27 ページ)とか。あと、通貨換算の責務は Expression ではなく Bank に持たせたい(83 ページ)と言いつつ、その後はせっせと Expression#reduce を実装してたり、最適化を実装しようとしたものの抽象度が壊れるから諦めて(128 ページ)、「パフォーマンスの懸念もあるが、実際の使われ方を見てから最適化を考えるので十分だと思う」(135 ページ)とか強がるあたり、ニヤニヤしながら読めた。そんな気取らない作風でした。

まとめ

TDD の考え方がよくわかる本でした。自分と同じように「なんか TDD とか聞くけどよくわかってない」という人は読んでみるといいです。t_wada さんによる付録で、原著以降の BDD などの歴史や現状、TDD の用法・用量までよくわかるおまけつき。TDD くらいすでに知ってるよ、という人も、この付録は読む価値があると思います。

*1:中にはちゃんと説明してくれている人もいたんだろうけど、自分の方がちゃんと聞く気がなかった。

RubyKaigi 2017 の予稿:An introduction and future of Ruby coverage library

RubyKaigi 2017 の 2 日目に "An introduction and future of Ruby coverage library" というタイトルで発表します。事前資料の公開が推奨されていたので、簡単ですがどんな内容かを書いておきます。

要約

カバレッジ(テストカバレッジ、コードカバレッジ)は、ソースコードのどの程度の割合がテストによって実行されたかを表す指標で、「テストの良さ」に関するヒントを与えてくれるものです。Rubyでは、品質を保証する手段がいまのところテストしかないので、カバレッジをうまく使うことは重要です。

本発表では、我々が経験や見聞を通じて得たカバレッジとの付き合い方を紹介します。簡単に言うと、カバレッジは「コードに対する網羅率」に過ぎず、「仕様や設計に対する網羅率」ではないことを理解した上で、前者だけでなく後者も上げるためのヒントとしてカバレッジを活用することです。(なお、カバレッジの定義から丁寧に説明するので、前提知識は必要ありません。)

また、Rubyカバレッジ測定の現状として、SimpleCov や coverage.so などを紹介した上で、2.5 に向けての coverage.so の拡張計画を説明します。具体的には、関数カバレッジと分岐カバレッジの測定を可能にする予定で、そのために現在検討中の coverage.so の仕様を紹介します。他言語のカバレッジ管理ツールとの連携のために必要な情報を提供するように設計していて、実際に LCOV や Cobertura で可視化できることをデモする予定です。

解説

Ruby3x3 で導入される(とされている)型システムに注目が集まっていますが、プログラムの堅牢性を高める手段は、なにも型だけではありません。コードレビューだって立派な品質保証手段ですし、普通の型よりも強力に検証する手段もあります。しかし、現時点で一番普及している手段は明らかに、テストです。そこでテストの度合いのヒントとなるカバレッジは重要なはずですが、テストに比べると普及度が低いように感じています。
カバレッジが十分に活用されていない理由はいろいろ考えられますが、「カバレッジの(うまい)活用方法があまり知られていない」「Rubyカバレッジ測定ライブラリが貧弱」という 2 つの問題を緩和するために、今回発表してみることにしました。

2008 年にコミッタになって最初にやった仕事が、Ruby 本体のテストカバレッジ向上でした。主にそのころに得た知見と反省などを元に、漠然と考えていた「カバレッジのうまい活用方法」を明文化してみたので、共有したいと思います。

そのころに作った Ruby カバレッジ測定ライブラリ coverage.so は、便利なラッパ SimpleCov が登場したおかげでそこそこ使われているようです。しかし、当時 coverage.so の仕様を適当に決めてしまったために、行カバレッジ以外をサポートしづらく、放置していました(すみません)。今回一念発起し、関数カバレッジと分岐カバレッジをサポートする方向で仕様の検討と実装の試作をし、昨日コミットしました。まだ細かいところが詰めきれていないのですが、2.5 のリリースまでには決めたいと思っています。

なお、超絶技巧みたいな話は今回はありません。ない予定です。ないんじゃないかな。期待しないでください。

宣伝

拙著『Ruby でつくる Ruby』が、ジュンク堂書店の RubyKaigi 出張店で販売される予定です。サイン会もあるみたいなので、ぜひお買上げを!なお、RubyKaigi 出張店は RubyKaigi 1 日め(9/18(月・祝))だけなので要注意です。サイン会も 1 日めですが、本さえあればいつでもサインするので適当に捕まえてください。

さらに、ラムダノートがRubyKaigi 2017 便乗、サイン入り書籍プレゼント企画!(connpass)をしています。RubyKaigi に参加できない方はこっちに応募してみてください!