Quine Tweet: 自分自身へのリンクを持つ再帰的ツイート

This tweet is recursive. https://t.co/bZISaPd3Ts

— Quine Tweet (@quine_tweet) 2016年9月19日

「このツイートはありません」となっていますが、URL をクリックすれば自分自身に飛べます。

以下、このツイートが生まれるまでの経緯を長々と書きます。

問題設定

そのツイート自身の URL を埋め込んだツイートを作ります。ツイートの URL はツイートをした後でないと決まらないし、ツイート文面を後から更新する手段はない（と思う）ので、単純ですが意外に難しい問題です。

調査

ご存知のように、現在のツイートの URL は次のような形式です。

https://twitter.com/<username>/status/<id>

username はそのままなので、id を事前に予測できれば解決です。*1

調べてみるとこの id は、snowflake という分散ナンバリングシステムで決められているようでした。いくつかの解説記事によると、id は以下のような 64 ビット整数であるようです。

+--------------------+--------------------+-------------------+
| timestamp (42 bit) | worker-id (10 bit) | sequence (12 bit) |
+--------------------+--------------------+-------------------+

それぞれの意味は以下の通り。細かいことは snowflake のソースコード*2を見て確かめました。

• sequence: 同じミリ秒枠内での衝突を回避するためのシーケンス番号（ミリ秒ごとに 0 リセット）
• worker-id: この id を発行したサーバ固有の番号 *3
• timestamp: System.currentTimeMillis() - 1288834974657L の値。（2010-11-04 10:42:54 頃からの経過ミリ秒）

上位ビットが timestamp なので、この番号はおおよそ時間順に増えていきます。

アプローチ

それぞれの値を予測して id を作り、ツイートを投げてみて、外れたらツイ消し。Quine ツイートに成功するまで、延々とこれを続けます。各ツイート試行は独立と仮定すれば、典型的なベルヌーイ試行ですね。

観察と見積

TL に流れているツイートをいくつか集めて、それぞれの値の傾向を観察して、成功までにかかりそうな時間を見積もりました。

• sequence はミリ秒ごとにリセットされるので、0 と予想するのが鉄板です。実際、TL に流れているツイートの sequence をいくつか拾ってみると 0 が多めでした。1 日にツイッターに流れる全ツイート数は数億で、1 日は 8640 万ミリ秒なので、時間帯の偏りを考えればこんなものでしょう。
• worker-id は原理的には 2^10 = 1024 通りの値を取りえます。いくつかのツイートを観察しても特に傾向はつかめませんでした。
• timestamp は、なんとなく ±500 ミリ秒くらいの精度で当てられるんじゃないかなーと考えました。

これらの観察から、値が一致する確率（ヒット率と呼ぶことにします）をそれぞれ 50 % 、0.1 % 、0.1 % と仮定しました。それぞれの値が一致する確率は独立と仮定して、Quine ツイートが生まれる確率は 50 % × 0.1 % × 0.1 % = 0.00005 % 、期待値で言うと 200 万回のツイートで 1 回成功する計算になります。

ツイッター API のレートリミットを調べると、1 時間に 100 ツイート程度が許されるそうです。少し余裕を見て、40 秒に 1 回ツイートすることにしました。200 万回のツイートをするには 3 年弱かかる計算になります。

値	事前見積
sequence ヒット率	50 %
worker-id ヒット率	0.1 %
timestamp ヒット率	0.1 %
必要なツイート数期待値	2M 個
所要時間の見込み	3 年

心が折れそうになりましたが、3 年がかりの Quine というのもロマンがあっていいだろう*4、と前向きに考え、とりあえずやってみることにしました。

簡易版での試行

専用の Twitter アカウントを作成し、次のような適当な予測で挑戦しました。

• sequence は 0 固定。
• worker-id は「前回の失敗ツイートの worker-id をそのまま送る」という戦略。ナンバリングサーバが常時 1024 台起動してはなさそうですし、ロードバランサの振り分け先にも偏りあるんじゃないかと期待。
• timestamp は単純に、前回の失敗ツイートから 40,000（40 秒）を足して作ります。ただし、ローカルの時計と前回の失敗ツイートの timestamp のズレを見て、ツイート発射タイミングは調整します。

これで半日走らせてみましたが、まあ、当たりませんでした。

失敗データの分析

試行によって 1000 ツイート分くらいの失敗データが溜まったので、それぞれの値のヒット率を評価してみました。

値	事前見積	簡易版
sequence ヒット率	50 %	80 %
worker-id ヒット率	0.1 %	7.0 %
timestamp ヒット率	0.1 %	0.05 %
必要なツイート数期待値	2M 個	35k 個
所要時間の見込み	3 年	17 日

worker-id は予想よりもかなり当てやすいことがわかりました。
timestamp は、1000 ツイート程度では 1 回もヒットしませんでした。事前見積から言っても、1000 ツイートで timestamp がヒットする期待値は 1 なので、ヒットなし自体は想定範囲です。しかし、誤差分布を見てみると ±1500 ミリ秒くらいで広がっていて、予想よりも厳しそうです。誤差分布をカーネル密度推定してヒット率を見積もったところ、0.05 % でした。ネットワーク越しだとこんなものか。

しかし worker-id のヒット率がだいぶ楽観視できるようになったので、所要時間の期待値を計算しなおすと、約 17 日になりました。3 年に比べたら全然行けます。ロマンはなくなりましたが。

改良版での挑戦

17 日なら待ってもいいんですが、せっかくなので予測方式を改良しました。

• sequence は変わらず 0 固定。
• worker-id は、「直近 5 つの失敗ツイートの worker-id を多数決して選ぶ」としました。*5
• timestamp のタイミング補正に PID 制御を導入しました。

これでヒット率を見てみました。（2 日ほど走らせた時点）

値	事前見積	簡易版	改良版
sequence ヒット率	50 %	80 %	75 %
worker-id ヒット率	0.1 %	7.0 %	9.8 %
timestamp ヒット率	0.1 %	0.05 %	0.08 %
必要なツイート数期待値	2M 個	35k 個	15k 個
所要時間の見込み	3 年	17 日	8 日

sequence が若干悪化しましたが、簡易版でデータ採取したときは Twitter が混雑していない時間帯だったのかも。（そういうときは sequence の衝突が生じにくい）

とにかく、これで所要時間の期待値は約 8 日に。そこでちょうど帰省するタイミングになったので、モニタリングの仕組みだけ作ってそのまま放置しました。

結果

簡易版の実験を 9 月 13 日にやって、改良版を 9 月 14 日の 0 時ごろから改良版の実行を開始しました。9 月 20 日の朝 5 時ごろ、14377 ツイート目にして、ついに Quine に成功しました。苦節 6 日と 5 時間。だいたい予想通りですね。
正直、いろいろ不安でした。せっかく成功したのにスクリプトのバグでツイ消ししてしまわないか*6とか、Twitter 側で完全に recursive なツイートはエラー扱いにするような処理が入っていないかとか。「開始から 5 日経ってるから、そろそろ当たってもおかしくない……」みたいな典型的なギャンブラーの誤謬に陥ったり。実際にうまくいくとホッとしました。この不安、3 年間は耐えられなかった気がする。

関連研究

やり始めた後で気づいたんですが、ネタ自体は既出でした。ショック。

Self referential tweet http://twitter.com/SelfRefer/status/3128391843

— Diomidis Spinellis (@SelfRefer) 2009年8月4日

これは 2009 年のツイートです。当時の Twitter では、id がただの連番で、一定間隔でツイートを投げれば番号がおよそ 200 増える（作者による解説の図を見ると、あんまりブレてない）ので、今よりだいぶ難易度が低かったようです。ミリ秒当てしなくていいのは大きい。

現在のナンバリングシステムになってからのものとしては、次のツイートがありました。

I love recursion, as seen here: http://t.co/M8jOdH8

— Markus Persson (@notch) 2011年8月15日

ただしこれはチートという噂です。TinyURL を作りかけの状態でツイートし、そのツイートの URL で TinyURL を完成させる、という手順でできるそうです。

まあ今より簡単だろうがチートだろうが既出ネタは既出ネタなんですが、楽しかったのでよいことにします。

今後の課題

もともと作りたかったのは「自分自身を埋め込んだツイート」だったのですが、残念ながら「このツイートはありません」となってしまいました。ツイート作成時点（自分自身がまだ作成されていない）でリンク先をフェッチして記録するようなので、当たり前ですね。普通の Twitter card のリンクなら 1 週間程度で再クロールしてくれるらしいですが、ツイートのリンクは Twitter card とは別の仕組みで埋め込まれているっぽいので、クロールし直してくれない予感がします*7。残念。何か手はあるかなあ。
予測的な改良の余地は 2 つ。まず、ツイート発射スクリプトが Ruby なので、発射タイミング自体がミリ秒単位では制御できていません。リアルタイム OS でもっときちんと制御して発射すれば、クライアント側のブレが減って timestamp のヒット率が上がる可能性があります（が、ネットワークと Twitter サーバのブレは消せないので、大きく改善することはないと思っている）。それから worker-id は、プロダクションレベルのサービスやロードバランサの知識を持っている人が考えれば、もっと賢い予測方法を思いつくのかも知れません。
他に作りたいのは、相互再帰的なツイートのペアです。といっても同じような難易度で作れるはず（所要時間は倍になる）。今後も Quine Tweet の採掘を続けるためには、自宅 PC ではつらいので VPS などを借りたいところです。が、このためにお金は払いたくないなあ。。。*8

まとめ

Quine を作るには、データサイエンスや制御理論のちょっとした知識が役に立つこともあります*9。Quine 自体は何の役にもたちませんが、いろんな知識・技術を実践的に試すきっかけに最適なので、ぜひあなたも。

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

posted with amazlet at 15.09.01

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

Amazon.co.jpで詳細を見る

*1:余談ですが、username の部分は別の文字列に変えてもツイートは開けるようです（正しい username に転送される）。username を変えてもデッドリンクにならないようにこうなっていると思われますが、他人のツイートを URL 上では偽装できるとも言えますね……。

*2:GitHub のリポジトリからは消えていますが、README にある通り、リリースは残っています。

*3:snowflake のソースコード内では、datacenter-id と worker-id という名前で、それぞれ 5 ビットずつのようです。

*4:3 年ならおそらく生きているうちには終わるだろうし、投稿スクリプトもほとんど sleep なので電気代はかからないし。

*5:同数の場合は適当。5 というパラメータは、1000 の失敗ツイートのデータでシミュレーションして一番ヒット率が高くなった値。

*6:実際、成功時の処理に typo があって例外になってました。ツイ消しには至らなかったものの、これだから Ruby は……（逆恨み）

*7:存在しなかったツイート URL が後から現れる可能性を考慮する必要は（普通は）ないので。

*8:他にも Twitter bot 作りたいネタはあるんですが、VPS をケチっているので話が進まない。

*9:大したことしてないのに偉そう。

『Rubyで学ぶRuby』連載開始

「Ruby で Ruby を作りながら Ruby を学ぼう！」というトンデモ連載企画、『Ruby で学ぶ Ruby』を ascii.jp で始めました。

ref: http://ascii.jp/elem/000/001/228/1228239/

何を言ってるかわからないかもしれないので補足すると、「Ruby（言語）で Ruby（のインタプリタ）を作りながら Ruby（でのプログラミング）を学ぼう！」ということです。Ruby でのプログラミングを学ぶなら、Ruby インタプリタ以上の題材はありません（断言）。Ruby というプログラミング言語の本質を、外側（ユーザ視点）と内側（処理系実装者視点）の両面で見ていきます。

対象読者は「Rubyを学びたいプログラミング初心者」です。Ruby 言語について最低限のことを伝えるところから始めるので、すでに Ruby を知っている人はダルく感じるかもしれません。しかし Ruby インタプリタを作るためには、普段当たり前に使っている言語機能でもきちんと整理して理解しておくことが重要です。初心者向け説明ではありますが、説明する言語機能を慎重に選択し、要所を意識しながら書いているので、読んでもらえるとうれしいです。それでも「俺様に初心者向け説明は要らん」という人は、インタプリタ制作に入る予定の第 4 回くらいから読んでください。

連載の当面のゴールは「ブートストラップ」です。ブートストラップとは、言語 X を使って言語 X の処理系を書くことです。つまりこの連載では最終的に、自分で書いた Ruby インタプリタを使って自分で書いた Ruby インタプリタを実行することを目指します。何言ってるかわからないかもしれませんが、大丈夫です。連載を読んでいくうちにわかるはずです。そこに行くまでに打ち切りになってしまうと悲しいので、応援よろしくお願いします。

ちなみに絵は『あなたの知らない超絶技巧プログラミングの世界』の挿絵も書いてもらった hirekoke さんです。それから編集さんは、TAPL 翻訳の際に担当編集さんだった鹿野桂一郎さんです。絵も文もイメージを伝えるだけで完成品が仕上がってくる布陣です。

更新は隔週の予定です。よろしくお願いします。

『オブジェクト指向設計実践ガイド』を読んで

オブジェクト指向設計実践ガイド ~Rubyでわかる 進化しつづける柔軟なアプリケーションの育て方

posted with amazlet at 16.09.01

Sandi Metz
技術評論社
売り上げランキング: 20,383

Amazon.co.jpで詳細を見る

自著を書いたご縁で、技術評論社さまから贈本いただきました。ありがとうございます。

本書は明日 9/2 (金) に発売らしいですが、発売前に読み終わったので書評など書きます。（書評アフィリエイトブログみたい）

概要

一言で言えば、「仕様変更に強い Ruby プログラムを設計する方法」というテーマの本です。

2 つのクラスにまたがる関心事を実装するとき、どっちのクラスにどんなメソッドを持たせるべきか、ということは誰でも悩んだことがあると思います。正解があるわけではないので、自分で基準を選んで決定するしかないわけですが、この本は「将来、仕様変更が起きたときにコード変更量がなるべく小さくなるようにする」という基準、というか、そういう特性を持つようなプログラムにするための指針を教えてくれます。自分ははっきり言って、書いたコードを継続的に維持した経験がほとんどないので、こういう知見を実践的に得る機会がありませんでした。そういう意味で、非常に興味深い本でした。

構成

本書は大まかに 3 部構成になっています。（本書で部の構成が明示されているわけではなく、個人的な印象です）

• まず 1 〜 5 章は、クラスの「インターフェイス」を意識することについて書かれています。インターフェイスとは要するに、どういうメソッド群があるか、その引数はどういうメソッドを実装していることを前提にしているか、ということです。1 つのクラスが複数のインターフェイスを実装していることもあります。Java だと interface を明示的に書かされるので強制的に意識させられますが、Ruby だとあまり意識していなかったかもしれません。しかしプログラムの設計の良し悪しは、クラス定義の良し悪しというより、クラスが実装しているインターフェイス設計の良し悪しで決まります。なのでまずインターフェイスを意識することが説かれているのだと思います。その上で、自転車を題材にインターフェイス設計の例を挙げ、それがどのような変更に弱いか、どうすればよいインターフェイスになるか、を段階的に説明しています。

• 6 〜 8 章に入って、継承・mixin・コンポジションといった、オブジェクト指向の言語機能を利用した設計方法が説明されます。この章は Ruby の初心者が読むといいと思います。入門書を読んで継承や mixin の振る舞いを理解したものの、実際のところどんな風に使うといいのかわからない、という人に、ベストプラクティスを示してくれます。個人的に目新しい内容はありませんでしたが、自分の場合は試行錯誤や他人のソースコード読解で徐々に習得していった知識なので、先にこういうのを読んでおけば楽だったと思います。あ、「継承関係をあまり深くするな」*1というのは良いことを言ったと思います。

• 最後の 9 章は、仕様変更に強いテストの書き方です。仕様変更を実装すると、既存のテストが失敗するようになります（純粋な仕様追加でない限り、それ自体は自然です）が、むやみやたらにテストが失敗すると対応が辛いのも事実です。そうならないようなテストの書き方を、本書で説明してきた設計・実装技法それぞれについて説明してありました。

仕様変更に強い設計という話題を中心に据えつつ、具体的な Ruby のコーディングテクニックや Ruby に限定されない原理・原則にも触れながら、展開されていました。

注意点

一応、要注意だなと思ったことも挙げておきます。

• プログラム設計について体系的・網羅的に書かれているものではないので、ハンドブック的な内容を期待したらダメです。タイトルの通り、あくまでガイドブック、読み物だと思います。
• 上流設計の話にありがちですが、説明がやや抽象的なところがあります。ある程度大規模 Ruby アプリで設計ミスを経験した人であれば「あるあるネタ」として簡単に理解できるんだと思いますが、自分はそういう経験がないので、イメージしづらいところもありました。*2
• 原著は 2012 年の本なので、多少古い記述もあります。たとえば、キーワード引数を自力実装する話は、キーワード引数が組み込まれた現代では完全に不要です。ただし、そういうところにはきちんと訳注がついているので、間違って覚えてしまう心配はないです。

以下は、個人的に同意しづらかったところ。

• 将来の変更に対する予防的なコーディングテクニックには、抵抗感あるものもあります。たとえば、インスタンス変数はすべて attr_reader 経由で読めとか。*3
• 5.3 節で静的型付けと動的型付けが言及されていますが、完全に動的型付け信者の放言になっているので、真に受けないほうが吉です。*4

まあ、書籍には多かれ少なかれポジショントークが含まれるものなので、読み手側が用法・用量を見つけて参考にするべきでしょう。

まとめ

Ruby プログラムの設計を考える上で、とても参考になる本でした。「設計についてはこの一冊ですべてわかる」というような本ではないですが（そんな本は存在しないと思います）、大規模 Ruby プログラムのメンテナンスをやっているけれどソフトウェア上流設計みたいな言葉を聞いたことがないという人は、ぜひ読むといいと思います。

*1:継承パスの途中で変更があったときに動かなくなりがち、という本書の主張もその通りだと思いますが、なにより個人的には理解するのが辛いです。Java みたいに衒学ぶって分類しまくるのは悪。

*2:自分のこの書評もずいぶん抽象的なので、上流設計の説明というのは本質的に難しいのかもしれません。

*3:そうすることで、仕様変更があった時に attr_reader :foo を def foo; @foo * 2; end などと置き換えるだけで済む場合がある、と言っているのですが、こんなハックは混乱の元なので書くべきでないです。Java の getter/setter 教がそのまま来ているようで、getter 自体にはメリットもあるようですが、この説明はあんまり。

*4:ほとんどの静的型付け言語ではすべての変数や型引数に型注釈が必要、静的型付けでも予期せぬ nil の出現（ぬるぽ）は防げない、というような記述から、おそらく著者の方は静的型付け言語を Java しか知らないのではないかと思います。「型宣言がない方が書きやすい」は個人的には大筋同意です（記号処理なんかでは型を意識したほうがわかりやすい場合もあります）が、「型宣言がない方が読みやすい」はちょっと疑問です（特に本書が想定していそうな大規模アプリでは）。コンパイラの型チェックで見つかるような型エラーは、動的型付けでも実際に起きることなどほぼない、と言われていますが、自分にはそんなこととても言えないです。「この節を読んでおけば、静的型付け寄りの友人に議論を持ちかけられたときに論争を避けられる」のように言われていますが、この節のようなことを言えば間違いなく喧嘩・疎遠になるでしょう。（異教徒の友人と手を切らせる作戦？）

『プログラミング Elixir』を読んで

プログラミングElixir

posted with amazlet at 16.08.22

Dave Thomas
オーム社
売り上げランキング: 1,168

Amazon.co.jpで詳細を見る

川崎 Ruby 会議 01 の会場で、訳者の笹田さん・鳥井さんから一冊献本いただきました！ありがとうございます！さっそく読み終えたので、紹介を書いてみます。

書評

Elixir に興味がある人がこの本を読むべきなのは、言うまでもないと思います。そういう人は、Elixir に詳しそうな人による書評（このへんとかこのへんとか）を見るといいと思います。

正直、自分はさほど Elixir に興味ないのですが、この本はとてもおもしろく読むことができました。なぜかというと、Ruby っぽいオレオレ言語を作りたい野望を漠然と持ってる人間には、非常に刺激的な内容だったからです。Elixir 自身が「Erlang VM の上で Ruby っぽい言語を作ったらどうなるか」というのを体現していて、「あーわかるわかる、Ruby ここ良くないよね」とか「うわー Erlang VM のつらみを継承してるなー」とか思いながら読んでたら、一日で読み終えてました。

Elixir 自身だけでなく、本書の構成や説明がどことなく「Ruby ファンの、Ruby ファンによる、Ruby ファンのための」という感じだったのも面白かったです。Erlang/Elixir というと、とにかく並列性の話を期待しますが、本書の第 I 部（2〜13 章）では並列性の話は全く出てきません。150 ページ以上かけて、Elixir 言語自体をじっくり説明します。しかし、退屈にならないように構成と説明が工夫されています。まずはパターンマッチ（2 章）と不変性（3 章）という Ruby にはない性質から始めて、それから言語全体を概観する（4 章）。それから関数の話をし、リストとからめて再帰まで説明する（5〜7 章）。その勢いで他のコレクションや文字列などデータ構造の話を流し（8〜11 章）、ここでいまさら制御フロー（12 章）。斬新な流れでした。ここで終わると、この後いざ何か書こうとしたときに砂漠の真ん中に放り出されたような気分になりそうですが、最後の 13 章で、GitHub の issues をフェッチして整形出力するちょっとしたアプリを題材に Elixir での開発フローのデモがあり、フォローも万全でした。

そうして Elixir という言語を一通り理解した上で、第 II 部はついに並列性の話です。が、ここはさらっと流されている感じでした。プロセスやノードの低レベル API の話（14〜15 章）と、高レベル API というか OTP という並列実行管理システムの話（16〜18 章）などでした。この辺は明らかに、これだけで本が数冊書けるレベルのものなんだろうなーというところはよく分かりました（そして自分が興味ないところなので、ここを飛ばすのは「いいぞもっとやれ」という感じ）。最後の第 III 部は、マクロやモジュールに駆け足で触れて終わり。

ということで、第 I 部が個人的には一番エキサイティングでした。Elixir に興味がなくても Ruby とオレオレ言語設計に興味がある人（誰？）は是非読むといいと思います。

（なお、関数型プログラミングに関する記述については、ちょっと怪しい雰囲気がありました。sum の再帰的構造が sum([head|tail]) = <> + sum(tail) とか。アキュムレータの説明をしたかったようですが。まあ、「この本で関数型プログラミングを勉強しよう」と思う人はいないと思うので大丈夫かと思います）

Elixir について

さて、以下は書籍ではなく Elixir 自体への感想となります。

上述の通り、良くも悪くも「Erlang VM の上で Ruby っぽい言語を作ったらどうなるか」という感じの言語でした。Erlang といえば「VM は最強だけど言語は残念」ということで有名なので、かなり使い易くなっていると言えるのではないでしょうか。（使い込んだわけではないので印象ですが）

さらに、Ruby の弱点を克服しているところも好印象でした。Ruby 最大の不足である（と自分が思っている）パターンマッチは、Erlang 由来でばっちり用意されています。ブロックがキーワード引数の構文糖であることはすばらしいアイデアだと思いましたし、構文木をいじれるマクロは良し悪しですが、これらを組み合わせることで if 文相当が自力で定義できるのは非常にポイント高いです（Ruby がメソッド呼び出し 1 個あたりブロック 1 個しか書けないのは、if 文的なのを自分で定義できないのでしばしば苦痛です）。地味ですが、独自拡張可能な %-記法（Elixir では ~-記法）も「わかってるなー」という感じでした。

ただまあ、enjoy programming 勢としては、Elixir を普段使いにしたいとは思いませんでした。並列性ごときのために、あらゆる値が不変（配列やハッシュがない）のは、無理です*1。文字列・バイナリ周りのややこしげな仕様は、Erlang VM を利用する宿命かなんかですかね。それから、関数型プログラミングのは多分不変性と相性がいいからかと思うのですが、それにしても「メッセージを順次処理する」という単純なループを表現するのに末尾再帰を使うのは、やや滑稽に感じました。*2

それから、並列性がウリというわりには、それに特化した言語機能はないですよね。プロセス起動の spawn_link などには専用の記法があってもよさそうな。また、並列プログラミングのヤバさ（デバッグやテストがしにくい）を軽減してくれるような言語機能もなさげなので、ちょっと期待外れ感もありました。Erlang 的にはこのへんは言語機能ではなく、OTP という超重厚システムが頑張ってくれるというスタンスなんでしょうが、どうせ新たに言語を作るなら、OTP で培われたノウハウを言語機能として取り込めばよかったのになー、と思いました。OTP をほとんど理解してない人間の印象ですが。

ということで、Erlang VM の利点も欠点も継承してるなーという感じの言語でした。表層言語は Erlang から大分幸せになってるようですが（そしてそれはかなり重要ですが）、やっぱりこれは本質的に Erlang なんだと思います。

出来合いの VM の上で言語を作ると、どうしてもこういう妥協の産物になるんですよね。かといってスクラッチから書くと完成しないんですが。という感じで、オレオレ言語を作りたい野望を刺激される本でした。ああ。

*1:その犠牲を払ってでも並列性を必要としている人がいるのはわかってますし、そういう人にはいいんだと思います。でも自分にはつらい。

*2:普通は OTP の handle_call とかを実装するだけで、実際にはループを実装することがほとんどない言語なのかもしれません。

川崎 Ruby 会議 01 で基調講演しました

8/20 (土) に、川崎教育文化会館で川崎 Ruby 会議 01 が行われました。恐れながら、基調講演なるものをさせて頂きました。

Ruby で高速なプログラムを書く from mametter

内容は、東京 Ruby 会議 05 で話した Optcarrot の完全版でした。基調講演というと「その会合や分野の基本方針を示す講演」ですが、Ruby 会議関係の基調講演で（Matz の発表以外で）そういう感じの発表を見たことがなかったので、単に好きなことを話しました。

東京 Ruby 会議 05 の方では細かい実装技法の話しかしなかったので、我ながら偉そうだなーと思いながらも「最適化についての心構え」なるものを語ってみました。こんな感じ。

1. 目標値を決めろ：最適化とはコードを汚すことなので、どこまで汚すかを事前に決めるべき。
2. ボトルネックをいじれ：ボトルネック以外をいじるな。（ボトルネックを特定しないのは論外）
3. アルゴリズム最適化を考えよ：メソッド展開とか汚い最適化は割に合わない。
4. 効果を検証せよ：実行平均時間の単純比較ではなく統計的検定とか使うといい。有意差がなかったら変更を捨てろ。

2 と 3 はよく聞く話ですが、1 と 4 は一応自分のオリジナルです（同じこと言ってる人はいそうですが）。あと具体的なプロファイリングの方法とかを簡単に紹介しました。

川崎 Ruby 会議 01 の発表は、正直思っていたのの数倍以上に面白かったです*1。「Ruby の話をしたら負け」というカラーで、普通の RubyKaigi に飽き気味の人にはよかったと思います*2。運営チームの皆さん、ありがとうございました。次があったらまた参加します。

*1:面白さゼロという意味ではない。

*2:普通に Ruby の話が聞きたい人には微妙かもしれませんが、まあ川崎なら近隣の地域 Ruby 会議に行くのも難しくないので。逆に、他の地域 Ruby 会議にマンネリ感を覚えている人は特に来るといいのではないでしょうか。

[C][IOCCC] The 24th IOCCC: Best One-liner

f(y,x){int m,z;for(m=z=1;m*m<=y?z=y%m?z:m:x+1?z<2?x?f(x,0):putchar(64):f(z,x),putchar(x?10:32),y-=z:(f(z,y/z),0);)m++;}main(y){f(y-1,-1);}

実行します。

$ gcc -o prog prog.c

$ ./prog @
@ 

$ ./prog @ @
@ @ 

$ ./prog @ @ @
@ @ @ 

$ ./prog @ @ @ @
@ @ 
@ @ 

$ ./prog @ @ @ @ @
@ @ @ @ @ 

$ ./prog @ @ @ @ @ @
@ @ @ 
@ @ @ 

$ ./prog @ @ @ @ @ @ @
@ @ @ @ @ @ @ 

$ ./prog @ @ @ @ @ @ @ @
@ @  @ @  
@ @  @ @  

$ ./prog @ @ @ @ @ @ @ @ @
@ @ @ 
@ @ @ 
@ @ @ 

$ ./prog @ @ @ @ @ @ @ @ @ @
@ @ @ @ @ 
@ @ @ @ @

以上。

戦略と狙い

Animated Factorization Diagrams をイメージして作ってみました。

正直、これが通ったのは予想外でした。ワンライナーで大切なのは「こんな複雑そうなものがたったこれだけで！」というインパクトだと思うのですが、因数分解なんかはいかにも短く書けそうなネタなので、インパクト弱いなーと思ってました。しかも因数分解だけで 140 文字ぎりぎりになってしまうというゴルフ力のなさにがっかりした。でも解析したくなる程度の複雑さなのが逆によかったのかもしれない。

まとめ

ということで、IOCCC に入賞した endoh の 4 プログラム紹介でした。今回は本当にレベル高かったので、ぜひ他のプログラムも見てみてください。

[C][IOCCC] The 24th IOCCC: Back to the Future Award

  #include   /*recall-the\    /-good--old-\    /IOCCC-days!\    */<unistd.h>
   typedef  unsigned/*int*/  short U;U(main)  [32768],n,r[8];  __attribute__((
  # define  R(x)       A(r[  7-(n       >>x&  7)],       (n>>  x>>3       )%8)
  #define   C(x)       (U*)  ((/*             |IO|             -dpd
  */char*)  main       +(x)  )/*|             |CC|             ll*/
  # define  A(v,       i)(i  ?i<2             ?C(v             ):i\
  -4?v+=2,  C(i-       6?v-  2:v+       *C(v  -2))       :C(v  -=2)       :&v)
  /*lian*/  constructor))U(  x)(){for(;;*r+=  2,*r+=!n?_exit(  write(2,"Illeg"
  "al ins"   "truction ;-"    "(\n",24)),0:     n>>8==001?(      signed char




                 )n*2   :548==n>>    6&&usleep     /**/(10
                 )+n%  64==   4?0*  write  (r[7   /**/],C(
                 *C(*  r)),   *C(*  r+2)   )+4:  /**/ n>>9
                 ==63   &&--r[7-n/   64%8]?n%+  /**/  64*-
                 2:0,         n>>6  ==47   ?*R( 0):n>>12==1?
                 *R(0  )=*R   (+6)  :n>>  12==+       14?*
                 R(0)   -=*R(2*3)    :0)n=*C(*        r);}

普通に実行してもエラーが出るだけです。

$ gcc -o prog prog.c
$ ./prog
Illegal instruction ;-(

さて、これはなんでしょうか。

ネタバレ紹介

このプログラムを理解するには、第一回 IOCCC の優勝作品を知っている必要があります。これです。

short main[] = {
        277, 04735, -4129, 25, 0, 477, 1019, 0xbef, 0, 12800,
        -113, 21119, 0x52d7, -1006, -7151, 0, 0x4bc, 020004,
        14880, 10541, 2056, 04010, 4548, 3044, -6716, 0x9,
        4407, 6, 5568, 1, -30460, 0, 0x9, 5570, 512, -30419,
        0x7e82, 0760, 6, 0, 4, 02400, 15, 0, 4, 1280, 4, 0,
        4, 0, 0, 0, 0x8, 0, 4, 0, ',', 0, 12, 0, 4, 0, '#',
        0, 020, 0, 4, 0, 30, 0, 026, 0, 0x6176, 120, 25712,
        'p', 072163, 'r', 29303, 29801, 'e'
};

http://ioccc.org/1984/mullender/mullender.c

有名なので知っている人も多いかと思います。main が配列になっている素敵なプログラムです。つまり、機械語を直接、数字の配列として定義しています。C 言語の関数ってのは、実装上は機械語の先頭アドレスに対応するシンボルに過ぎないので、こういうことも可能なのです。

ぜひ動かしてみたいと思いますが、この機械語は PDP-11 とかいう 1980 年ごろのマシンで動くので、残念ながら現代では動かせません。*1

そこで冒頭に示したプログラムが使えます。PDP-11 の「なんちゃって」エミュレータです *2 。以下のように実行してください。

$ wget http://ioccc.org/2015/endoh3/prog.c
$ wget http://ioccc.org/1984/mullender/mullender.c
$ clang -o mullender prog.c mullender.c
$ ./mullender

伝説の mullender.c が動きます。やったね。

このプログラムは GCC 拡張の __attribute__( (constructor) ) を使って、main より先に実行をフックします。その中で main 配列の要素を読み出し、PDP-11 のエミュレーションを行う、という仕組みです。

なお、PDP-11 の全命令はサポートしていません。というか、mullender.c が使っている 6 種類の命令しかサポートしてません。なので「なんちゃって」エミュレータ。

戦略と狙い

IOCCC の Rule 1 、「あなたの作品は完全なプログラムでなければならない」に挑戦するというテーマで作りました。過去作品の mullender.c にべったり依存しているので、これは完全なプログラムと言えるのかどうか。しかも mullender.c が使っている命令しかサポートしていないので、他のものはとても動かせない。どやー。

と思って作ったのですが、よく見たら SOB という命令があったのでした。これは 1 引いて非ゼロだったら（後ろ方向限定で）ジャンプするという命令なんですが、実はこの一種類の命令だけでチューリング完全になるというたいへん強力な命令です。なので、やってみたらBrainfuck がエンコードできてしまいました。まあそれはそれでむしろ面白いので、円周率計算とコッホ曲線のプログラムを PDP-11 のマシン語で書いて、おまけとしてつけました。

当初のテーマが達成できたかどうかは微妙ですが、いろんな意味で IOCCC ならではのプログラムになったと思います。過去に類のないプログラムなんで一抹の不安はありましたが、今大会 2 位のポジションにつけたようなのでまずまず。

*1:PDP エミュレータを使えば動かせるんだろうけど、よくわからないのでやったことはありません。

*2:コード中に ll-dpd とか書いてあります。逆さまに読めば pdp-11 。