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 に参加できない方はこっちに応募してみてください！

『Ruby でつくる Ruby』の購入方法

書籍『Ruby でつくる Ruby』が発売されて 2 月ほど経ちました（当時の告知）。いろいろなところでわりと好意的な感想が聞こえてくるので、うれしい限りです。
本書はラムダノートにとっての最初の出版ということで、発売当初は直販サイトでしか入手できませんでした。しかし最近は、販路開拓が進んだようで購入手段が増えてきました。まだ買ってない人のために、簡単にご紹介。

ラムダノート直販サイト

ref: https://www.lambdanote.com/products/ruby-ruby
直販サイトです。よく知らないサイトで物を買うのは不安かもしれませんが、実体は Shopify という有名なオンラインストア用サービスなので、そんなに怖くないです。
購入方法にこだわりが無いなら、ここで買うことをオススメします。なぜなら、出版社と著者への利益が最大なので。

Amazon.co.jp

RubyでつくるRuby ゼロから学びなおすプログラミング言語入門

posted with amazlet at 17.05.19

遠藤侑介
ラムダノート
売り上げランキング: 63,507

Amazon.co.jpで詳細を見る

言わずと知れたアマゾンです。最近詐欺で有名になったマーケットプレイスですが、ラムダノート直営なので心配ありません。中古販売などではなく、ちゃんと新品が届きます。
誰かレビュー書いてください。

ジュンク堂書店池袋本店

5/13お知らせ：本日より技術書出版ラムダノートさんの書籍をお取り扱い始めました！店頭で販売しているのはジュンク堂書店池袋本店だけ！！皆様のご来店をお待ちしております。 pic.twitter.com/o5Og22Lejc

— ジュンク堂書店池袋本店/PC書 (@junkudo_ike_pc) 2017年5月13日

東京・池袋にあるジュンク堂書店です。6 階に、ふつうに現物が置いてあります。サンプルもあるので中も見えます。
今のところ、現物をその場で買って帰れる唯一の手段です。「ネット通販はイヤでござる」という人はぜひこちらで。

honto

ref: https://honto.jp/netstore/pd-book_28490380.html
honto カードの honto です。自分は honto で買ったことはないのですが、とっても大手なのでまあ大丈夫でしょう。
店舗在庫状況を見ると、「在庫あり」になっているのはジュンク堂書店池袋本店だけ。ここに載ってる他のお店でも取り寄せられるのでしょうか？誰か挑戦して報告くれたらうれしいです。

ラムダノート出張販売

ラムダノートが行商するイベントに行って買う。
近いうちに行商するという予定は聞いていないので、期待しない方がいいです。「ラムダノート社長の鹿野さんに会いたい！」という動機でもない限り、おすすめしません。

おまけ

『プロフェッショナル SSL/TLS』のほうも同じ手段で買えるはず。アマゾンのアフィリエイトリンクを置いておきます。

プロフェッショナルSSL/TLS

posted with amazlet at 17.05.19

Ivan Ristić 齋藤孝道
ラムダノート
売り上げランキング: 133,698

Amazon.co.jpで詳細を見る

"Purely Functional Data Structures" の邦訳『純粋関数型データ構造』が発売されます

純粋関数型データ構造

posted with amazlet at 17.03.16

Chris Okasaki
KADOKAWA (2017-04-28)
売り上げランキング: 266

Amazon.co.jpで詳細を見る

伝説の名著、"Purely Functional Data Structures"（通常 PFDS）を翻訳しました。4 月末にアスキードワンゴから発売されます。

『20分でわかる Purely Functional Data Structures』などを通じて日本に PFDS を布教した @kinaba との共訳です。ちなみに編集さんはアスキードワンゴ編集長の鈴木嘉平さん。

関数型プログラマ向けの紹介

「リストの結合が O(n) で遅いな」とか「まともなキューはどうやって作るの」とかいった問題に一度は直面したことがありますよね。純粋関数型プログラミングではどうしても無理、と思って諦めている人もいるのではないでしょうか。

この本の技法を使えば、「結合が O(1) のリスト」や「挿入・削除が O(1) のキュー」など、嘘みたいな計算量を達成できてしまいます。もちろん、破壊的更新を使わずに。ああ、15 年前の自分に教えてあげたい*1。

結合が O(1) のリストがほしいだけであれば、既存実装の Data.Sequence あたりを使っとけば良いです。しかし、こういう出来合いのソリューションでは困るケースもあります。たとえば Data.Sequence は償却計算量なので、リアルタイム性が重要だと困るとか。

この本は単なる「結合が O(1) の列の実装方法」ではなく、「効率的な純粋関数型データ構造を実装するための汎用技法」を教えてくれます。効率的な列やキューの実装は、その技法の適用デモとして説明されます。なので、特定のケースで必要なデータ構造もいざとなれば自作できるようになります。

ということで、関数型プログラマを目指すならこの本の内容は確実に抑えておくべきでしょう。プロの方はすでに抑えてると思いますが、ハンドブックとしてお手元に是非。

Rubyist 向けの紹介

言うなれば、「すべてのオブジェクトが freeze した世界で、どこまで効率的なデータ構造を作れるか」を追究した本です。

破壊的更新が使えないのでデータ構造を実装するのが難しくなることが多いですが、逆に簡単になることもあります。たとえば、文字列の結合。普通は、メモリコピーが発生するので遅いですよね。しかしすべての文字列が freeze されていれば、コピーの必要はありません。2 つの文字列を並べた配列として表現すればいいです（こういう実装を Rope と言います）。こういう感じの考え方をひたすら深めていったような本です。

本書自体は Standard ML とかいう馴染みの薄そうな言語で説明されていて、Rubyist に全力でおすすめできる本ではないのですが、ふつうの Ruby から一歩踏み出したい方は ML 系の教科書と合わせて読んでみていただけると嬉しいです。

（『Ruby でつくる Ruby』を読んで「木って、すごく面白いな！」と思ったような人は素質あるかも）

裏話

『Ruby でつくる Ruby』とほぼ同時公表となったこの本ですが、どちらもラムダノートの鹿野桂一郎さんが絡んでたりします。

鹿野さんには TAPL の終わりごろから PFDS の翻訳企画を持ちかけていました。鹿野さんがラムダノートの社長と化したタイミングで再度持ちかけたら、アスキードワンゴの鈴木嘉平さんが企画しているとわかったので、繋いでくれて今回の告知に至る。*2

一方、ラムダノートでやる企画なくなったなーと思っていたら、鹿野さんから「ちょっと変わった Ruby 入門ってどうだろう」と持ちかけられ、『Ruby でつくる Ruby』につながっていきました（非公式あとがき参照）。

ということで

『Ruby でつくる Ruby』と合わせて、みなさん是非読んでみてください！

*1:原著はそれより前（1998 年）に出版されているわけですが。

*2:さらっと言いましたが PFDS の翻訳も容易ではありませんでした。遅延評価の force とか suspension とか意外に定訳がない単語が多かったり、アホな誤訳をちょくちょくかましていたり。共訳の @kinaba 殿やレビュアーの方々に救われて出版にこぎつけました。感謝の限り。

書籍『Ruby でつくる Ruby』が発売されます

ref: https://www.lambdanote.com/collections/frontpage/products/ruby-ruby

おかげさまで、ASCII.jp で連載していた『Ruby で学ぶ Ruby』が紙の本になる運びとなりました。わーい。『Ruby でつくる Ruby ― ゼロから学びなおすプログラミング言語入門』と微妙にタイトルが変わったので注意。

一番大切なことを先に言っておくと、書店に並ぶ予定はありません。ラムダノート株式会社という出版社の直販サイトで購入できます。アスキーじゃないの？と聞かないでください。追記：今はいろいろ購入方法が増えました。『Ruby でつくる Ruby』の購入方法をご参照ください。

ラムダノートは『型システム入門』のときにもお世話になった編集の鹿野さんが立ち上げた新しい出版社です。鹿野さんと高尾さんの編集コンビは、技術書については知る限り最強なので、何か書きたいネタがある人はラムダノートに持ち込むといいですよ。

どんな本？

一言で言えば、Ruby で Ruby インタプリタをつくる本です。Ruby インタプリタとは、Ruby プログラムを動かすためのプログラムのことです。この開発を通して、Ruby という言語を外側と内側の両面から学んでいけます。

環境のセットアップから説明していくので、Ruby について何も知らなくても、いっそプログラミングをしたことがない人でも読めるように書いたつもりです。そこからはじめて、たった 144 ページで、Ruby インタプリタを「自作」していきます。もちろん完全な Ruby インタプリタではなく、いろいろ端折った簡略版の Ruby（MinRuby と呼んでいます）のインタプリタですが、いちおう「ブートストラップ」ができます。つまり、自分で書いたインタプリタで、自分で書いたそのインタプリタ自身を動かせるということです。ここまでできれば胸を張って「インタプリタを自作した」と言えるレベル。本の内容については、連載開始時の記事や連載終了時の記事もご参照ください。

あと、記念すべきラムダノートの初出版本 2 冊のうちの 1 冊ということで、なんか採算度外視の豪華な本になっています。なんと言っても、本文が全ページフルカラーです。絵本なのかな。hirekoke さんのかわいい（そしてエキセントリックな）挿絵が全部載っています。（なお、もう 1 冊の初出版は、"Bulletproof SSL and TLS" の翻訳本「プロフェッショナル SSL/TLS」です）

連載時からの改善点

ところで、自分にとって初の連載記事であった『Ruby で学ぶ Ruby』は、連載の恐怖を知る機会にもなりました。それは、「締め切り」、ではなくて、「公開しちゃった部分を変えられない」ということです。もちろん Web 連載なので typo なんかは直せるんですが、「これ、あのときに合わせて説明しておけばよかったな」とか「この用語、ちゃんと説明しないまま使ってしまっているなあ」などというレベルのミスは最新版で中途半端に補足するしかなくて、文章がツギハギだらけになっていく。今回、鹿野さんと高尾さんの全面バックアップの下、その手のツギハギを一掃しました。おかげで、かなり読みやすくなったと思います。

付録として自力構文解析も載せたいと思っていたのですが、こっちは残念ながら紙面の都合で載せられませんでした。ざっと見積もって、144 ページが 200 ページ超になりそうだった。一応、興味のある人向けに、further reading というか調べると良さそうなキーワードを足しておきました。この本が売れれば続編を書く機会が得られるのではないかと思うので、なにとぞ、なにとぞ！

注意点

• 書店に並ぶ予定はありません（再掲）。ラムダノートの直販サイトから購入してください。追記：今は『Ruby でつくる Ruby』の購入方法をご参照ください。
• 直販サイトがイヤな人は、ラムダノートが行商をするタイミングを狙いましょう。とりあえず、4/9（日）に秋葉原で行われる技術書典 2 のラムダノートのブースでは販売される見込みです。
• 電子書籍はありません（予定もありません）。理由は大人の事情によるらしい（ぼくもよくわかってない）。ちょっともどかしいのですが、この本が売れれば電子書籍になる可能性もあるみたいです。

どうぶつしょうぎ名人

どうぶつしょうぎ AI を作りました。絶対に勝てません。無力感を味わってください。

ref: http://mame.github.io/dobutsu-shogi-master

どうぶつしょうぎとは

3 マス x 4 マスの単純化された将棋です。ライオン（王相当）、ぞう（1 マスしか進めない角行）、キリン（1 マスしか進めない飛車）、ひよこ（歩相当、にわとりに成ったら金相当）の 4 種類の駒を動かして、相手のライオンを取るか、トライ（ライオンを一番奥の行まで運ぶ、ただし直後に取られる場合はだめ）に成功すれば勝ちです。詳しくは Wikipedia の記事を見てください。
どうぶつしょうぎは後手必勝であることが知られています（研究報告）。つまり、後手が正しくプレイする限り、先手は絶対に勝てません。どうぶつしょうぎ名人は常に正しくプレイするので、先手のあなたは絶対に勝てません。

なんで作ったのか

将棋の AI が何かと話題になる近今ですが、ぼくはトッププロに勝てるかどうかにはあんまり興味がありません。自分より強いことは確実だし。
そんなことより、先手必勝なのか後手必勝なのかという事実の方が面白いですよね。どうぶつしょうぎはすでに完全解析されていたので、それを体感してみたいと思ったので作りました。やってみると、素人の直感では不利そうな感じの手が一番生き延びる手だったりして、意外に楽しかったです。
（あと、いらすとやの人工知能イラストを使ってみたかったというのも）

実装の概要

AI とは名ばかりで、後手盤面ごとに指すべき手を事前計算してあります。「なーんだ」という感じですが、単純やると 2 億個の盤面を覚えないといけない。単純に作ると、手の選択のたびにサーバに問い合わせることになりますが、それはなんとなく嫌だった（ネットワークがなくても動く方がかっこよく感じる）ので、ちょっと工夫してあります。

指すべき手の事前計算

まず、前述の研究報告の解析を再現しました。初期盤面から到達可能な盤面を全列挙します。それから、末端局面から逆にたどって（後退解析）、各盤面の深さ（そこから終局までにかかる最短手数）を求めました。
8 年前の研究報告では盤面列挙に 19 分、後退解析に 5.5 時間かかったそうですが、ちょっとした工夫*1で、ノート PC でもそれぞれ 5 分、15 分弱でできました。盤面数などが論文と一致したので、バグってはないと思います。*2

最短勝利手順データベースの生成

初期盤面から到達可能な全盤面の深さが決まりました。この時点では、後手必勝の盤面だけで約 2 億個あります*3が、これを全部データベースに入れる必要はありません。というのも、後手（AI）は常に最善手（最短で終局に向かう手）を選ぶので、理論上到達可能でも実際には到達しなくなる盤面が出てくるからです。
ということで、「先手は任意の手を選ぶ、後手は最善手を選ぶ」というルールで初期盤面から辿りなおして、覚えるべき盤面を絞り込んでいきます。*4
このとき、最善手が複数ある（どっちを選んでも終局までの手数が同じ）場合があります。どれを選んでもいいのですが、覚える盤面数に影響があります。覚える盤面数を最小化する最善手を選ぶのは、単純な 0-1 整数計画問題に直せます*5。これは NP 困難ですが、人類の英知を結集したソルバ（CPLEX 殿とか Gurobi 殿とか）を使えば、わりとよい近似解が得られます。
CPLEX 自体は有償なので、CPLEX をオンラインで無償で使わせてくれる NEOS サーバを使います。投稿用の LP ファイルを生成しました。が、NEOS サーバは問題サイズが 16 MB までという制限があったので、LP ファイルゴルフをしました*6。ギリギリ 16 MB を下回ることができたので投稿してみると、CPLEX はすぐにメモリ不足で止まるので使えない子だったのですが、SCIP というソルバがそこそこの近似解を出してくれました。
これを元にデータベースを作ったら、およそ 10 万盤面程度を覚えればいいことになりました。2 億件が 10 万件に。

データベースの圧縮

10 万件ならバイナリで 1 MB 程度なのでブラウザでも扱えます。ただ、あんまりかっこよくない気がしたので、完全ハッシュ関数を実装しました（有名な論文）。これでバイナリで 200 KB 程度。
このくらいならメモリに載せてもいいけど、通信量的はもうちょっと頑張りたい（あとできれば ajax 使いたくない）と思ったので、Range coder で圧縮しつつテキスト形式にしました*7。これで、テキストで 170 KB 程度になりました。あとはこの文字列を JavaScript に埋め込んで、実行時に解凍するだけ。

実装に使った言語

主に事前計算と Web クライアントの開発なので、どちらも Ruby には向いていません。せっかくの機会なので、使ったことがない言語を使ってみるようにしました。

Rust

事前計算は明らかに実行速度が重要だったので、Rust で書くことにしました。が、型システムが煩わしくてしょうがないので、一旦 C で書いて動作確認してから Rust に移植しました。そして、当然ながら C より遅いという*8。うーん、不毛。
LP ファイルゴルフの方も Rust でやりたかったのですが、どうも Rust でグラフ構造を扱うのは鬼門なようで*9、後半はあきらめて Ruby で書きました。
Rust 、どうなんでしょうね。(1) 実行速度重要、(2) メモリ管理重要、(3) 高度なアルゴリズムは非重要*10、なユースケースには向いているのかな。でも、OCaml に比べるとたくさんの人がすでに使っているようなので、みんな賢いなあすごいなあ、という印象。

TypeScript

クライアント側の実装には TypeScript を使ってみました。JavaScript のスーパーセットということで、いろいろ妥協の産物という感じです。型システムも適当なので、「通ったら安心」というたぐいのものではないです*11。それでも、JavaScript を直接使うよりはだいぶ幸せでした。
ただ、型チェックに数秒程度もかかるのはつらい。vim が保存時に毎回固まる。UI のための JavaScript はちょっとした変更を繰り返すものなので、忍耐力が必要です。コードサイズに応じて遅くなっていく（いまは 1000 行弱）ので、大規模なものを書くのは厳しいかも。
なお、npm を中心としたエコシステムは立派だなあと思いました（小並感）。流行ってるようだったので webpack を使ってみましたが、一年後にはどうなっているのでしょうか。

まとめ

どうぶつしょうぎが後手必勝であることを実感できるデモでした。将棋 AI が人間に勝つかどうかとかいう世俗的なことより、オセロが後手必勝なのかどうかのような理論上のことにみんな興味を持つといいなと思います。

今後の課題としては、人間が後手を取ったときでも指してくれるようにしたいなと思っています。覚えないといけない範囲が一気に広がるので、サーバ問い合わせが必要なんですよね。サーバ持ってないのですぐにはできない。

*1:後退解析では、深さ n の盤面から深さ n+1 の盤面を特定していきます。具体的には、単純に深さ n の盤面から直前の盤面を逆計算するアプローチと、深さ未決定の盤面のうちで深さ n の盤面に進めるものを絞り込むアプローチがあります。深さ n の盤面数と、深さ未決定の盤面数を比べて、早そうなアプローチを選択することで、大幅に高速化できました。

*2:実はバグで再現するのに結構手間取ったんですが、こういうのって初めて研究する人はどうやって解析の正しさに確信を持つんだろう。

*3:左右反転して同一になる盤面は含んでいません。

*4:あと、深さ 3 以下の盤面は覚えないことにしました。JavaScript でも実行時に一瞬で探索できる深さなので。

*5:ある盤面 x を覚えるかどうかを変数 x で表すことにします（x は 0 または 1）。後手盤面 w から先手盤面 b1, b2, ..., bn に遷移可能なとき、b1+b2+...+bn >= w という制約を与えます（w を覚えるなら b1 から bn のどれかを覚えなくてはならない）。また、先手盤面 b から後手盤面 w1, w2, ..., wn に遷移可能なとき、w1+w2+...+wn >= n*b という制約を与えます（b を覚えるなら w1 から wn のすべてを覚えなくてはならない）。これらの制約の下で、すべての後手盤面 w の合計（Σw）を目的関数とし、これを最小化する変数割当を求めます。

*6:やったのは、(0) 簡単な実験で明らかに望みがなさそうな枝をアドホックに刈る、(1) 覚えることが確定している盤面に関する制約を除去する、(2) 目的関数に寄与しない制約を除去する、(3) 一本道になっている手順をマージする、(4) 変数名をゴルフ的に圧縮する。簡単なグラフ処理と文字列処理です。

*7:表示可能文字 95 文字からダブルクォートとバックスラッシュを除いた 93 進数で出力した。

*8:主に重いのは HashSet の読み書きでした。「デフォルトが SipHash だから遅い」と言うのはよく見かけるのですが、FnvHash にしても遅かった。HashSet の実装自体も遅いんじゃないだろうか。キーを u64 限定として、khash.h を参考に再実装したら C の 2 倍くらいになりました。その後もこまごま調整したら 1.5 倍くらいにはなったようです。

*9:unsafe でない双方向リンクリストが話題になるくらい。

*10:といっても今どきグラフも気軽に扱えないのでは、OS やブラウザのようなシステムプログラミングにも厳しいのではないか。そのへんはとても賢い人が書いたライブラリを使う、というのでどうにかなる？

*11:この点 Rust は、型システムを通れば安心、かと思いきや、型システムを通すために参照を避けて配列＋インデックス番号にするインセンティブが働くので、index out of bounds 遭遇率が高まるという。「それはそうするお前が悪い」という声が聞こえてきそうですが、グラフ構造の実装では「アリーナ」とかいってまさに同様の手法（ノードを集めたでっかい配列を用意して、参照のかわりにインデックス番号を使う）を提案している人が結構いるようですよ。ポインタがない N88-BASIC みたいな世界。

『Ruby で学ぶ Ruby』非公式あとがき

ref: http://ascii.jp/elem/000/001/230/1230449/

「Ruby で Ruby を作りながら Ruby を学ぼう！」という ascii.jp の連載、おかげさまでほぼ予定通りに無事に終わりました。執筆の経緯を書いておきます。

昨年の 6 月ごろ、「抽象によるソフトウェア設計」や「型システム入門」のときにおせわになった編集者の鹿野さんに声をかけて頂きました。「ふつうの Ruby 入門はもうたくさんあるので、ちょっと変わった Ruby 入門を書けないか」という話でした。

それを聞いた瞬間、「Ruby インタプリタの開発を通して Ruby を学ぶ」という構想が湧きました。Ruby は主に Web やテキスト処理を対象としているので、言語処理系や記号処理を題材にした入門は目新しそうだし、なによりそういうのに興味を持つ Ruby ユーザがもっと増えてほしい。

「○○言語で○○言語のインタプリタを作る入門」は、Lisp や ML ではわりと普通のことです*1。「インタプリタの実装」というと何やら難しそうですが、言語のサブセットの切り出しさえうまくやればそんなに難しくないのです。

とはいえ、さすがにプログラミング言語をまったく知らない人向けの題材としては重すぎるかな？という不安はあったので*2、まずは自分でインタプリタを書いてみました。言語のサブセットの取り方を試行錯誤しながらでしたが、数時間くらい、ソースコードにしてたった 100 行強でブートストラップできたので、大丈夫な気がしてきました。個人的に盛り上がってきたので、そこから 1 週間で全 8 回（当時）の原稿をすべて書き上げました（なおこの時点では連載は決まっていない）。

それから無事に 1 か月後くらいに連載が決まり、9 月中旬に連載開始となりました。連載は隔週で、すでに書き上げた原稿を鹿野さんが膨らませ、@hirekoke さんが挿絵を入れて出す、自分はそれを見守る、という体制。のはずでしたが、説明方法や説明順序を調整したのでそんなに楽ではありませんでした。ちょっと説明方法や構文木を変えただけのつもりでも、後から整合性を取るのが苦しくなるとか。関数の回を前後編に分けることになったので当初より全 9 回になりましたが、それでも基本的には予定通りに進むことができました。

少し心残りなのは、字句構文解析を完全に省いてしまったところです。言語処理系の教科書と言うと、まずは字句構文解析の小難しくて面白くない説明（※個人の感想です）がダラダラ続くんですよね。そこより先に言語処理系のおもしろさがあるのに、多くの人が脱落してしまうのはもったいないと思っていました。ただ、字句構文解析がないとオレオレ言語の開発はできないし、ブートストラップも完全とは言い難い。まあ、この連載は言語処理系開発の入門ではなく、あくまで Ruby 入門の題材として言語処理系を扱うということで、妥協しました。いちおう MinRuby の再帰下降解析のパーサ（これだけで 100 行強）は書いたので、そのうちどこかで書きたい。

ということで、『Ruby で学ぶ Ruby』を楽しんで頂けたなら幸いです。公開が停止するわけではないのでまだ読んでないなら今からでもぜひ。

あと、「これで Ruby はだいたいわかった！」という気になったら、拙著もどうぞあわせて読んでください。Ruby プログラムのサンプルがいっぱい載っています。

あなたの知らない超絶技巧プログラミングの世界

posted with amazlet at 15.09.01

遠藤 侑介
技術評論社
売り上げランキング: 3,000

Amazon.co.jpで詳細を見る

*1:むしろ自分の中で Lは「Lisp で Lisp インタプリタを作る入門」のための専用言語くらいの位置づけです

*2:あと、いつのまにか鹿野さんが ASCII.jp に企画提案していたので。

ELVM を使った multiquine

言語間を自由に行き交うことができる Quine の集合のことを multiquine と言います。例えば mq.rb と mq.py が multiquine であるとは、

• ruby mq.rb rb と実行すると mq.rb が出てくる（普通の Quine）
• python mq.py py と実行すると mq.py が出てくる（普通の Quine）
• ruby mq.rb py と実行すると mq.py が出てきて、逆に python mq.py rb と実行すると mq.rb が出てくる（相互に出力する）

という感じです。5 言語で普通に書かれた multiquine の図がわかりやすいでしょう。ぼくの本でもちょっと言及されています。

あなたの知らない超絶技巧プログラミングの世界

posted with amazlet at 15.09.01

遠藤 侑介
技術評論社
売り上げランキング: 3,000

Amazon.co.jpで詳細を見る

なお、拙作の Quine リレー（ウロボロス Quine とも）とは別のものです。Quine リレーは言語の進む方向が固定の輪ですが、multiquine は自由に行き来できるという自由度があります。

multiquine の難しさ

実のところ、「普通」の言語に限定すれば、multiquine はそんなに難しくありません（Quine リレーよりは難しいですが）。特に、「C 風の文字列リテラルがある言語」に限れば、極端に簡単になります（25 言語の例）。

しかし、この言語の中に Brainfuck や Lazy K が入ったとしたら、極端に難しくなります。Quine 自体が難しいわけではありません。Brainfuck で他 N-1 言語のコード生成器を書かなきゃならない、というところが辛いです。言語を増やしていくごとに、O(N^2) で実装タスクが増えていきます。

multiquine を効率的に実装する方法

これを解決する構想は昔からありました。こんなのです。

1. 中間言語を設計する
2. 中間言語で、Quine を書く
3. 中間言語で、中間言語から各言語へのコード生成器を書く
4. 各言語で、中間言語の処理系を書く

これらを組み合わせれば multiquine が作れます。2 で Quine (in 中間言語) を生成し、それを 3 で好きな言語に吐き出します。これらはすべて 4 の上で動かします。吐き出す先を実行時に変えれば、multiquine になります。

この方法の良い所は、言語を追加したいと思ったときに必要なのが

• 中間言語でその言語向けのコード生成器を書き、
• さらにその言語で中間言語の処理系を書く

だけとなることです。つまり、言語同士が独立になるので、N 言語 multiquine の実装量が O(N) になります。

ただ、中間言語の設計が辛くて実現してませんでした。中間言語を簡素にするとコード生成器の実装が辛くなり、中間言語を複雑にすると処理系の実装が辛くなるというバランスが取りきれなかった。

ELVM の登場

などとグダグダ言っていたら、shinh さんが ELVM とかいうものを爆誕させてくれました。わーい。上の 1 から 4 のタスクのうち 2 以外が黙っていたらできてしまった格好です。

ためしてみた

ということで、2 の部分だけ作って multiquine を作ってみました。

https://gist.github.com/mame/53fb5cf7b448b3249270ea771ef89655

詳しくはコメントを見てもらいたいですが、次のような感じで動きました。

$ ruby mq-gen.rb
$ gcc -o mq mq.c

$ echo c | ./mq > mq2.c
$ diff -s mq.c mq2.c
Files mq.c and mq2.c are identical

$ echo rb | ./mq > mq.rb
$ echo rb | ruby mq.rb > mq2.rb
$ diff -s mq.rb mq2.rb
Files mq.rb and mq2.rb are identical

$ echo c | ruby mq.rb > mq2.c
$ diff -s mq.c mq2.c
Files mq.c and mq2.c are identical

一応 bf も動くはずなのですが、とんでもなく遅いので動作は未確認。うーん、できたはできた（と思う）んだけど、現実的には Brainfuck と Lazy K の multiquine は無理そうだし（ていうかよく見たら ELVM が Lazy K をサポートしてなかった）、すっきりしないので未完。