Hatena::ブログ(Diary)

まめめも このページをアンテナに追加 RSSフィード

2016-11-17

[] 二分探索サンプルコード集(コピペ用)

二分探索は、感覚的なわかりやすさに反してバグが入りやすいことで有名なアルゴリズムです。20 の教科書のうち 15 でバグっていたという報告もあるそうです。

実際、自分も書くたびにバグに苦しんできました。変な値を返すだけでなく、out of bounds アクセスや無限ループもよく起きます。一旦動いたと思っても、後になってバグ発症することも多く、たちが悪いです。

そこで、きちんとテストした二分探索のサンプルコードを自分のコピペ用に作ってみました。

動作仕様 (境界探索版)

ソートした配列 a に対して、「値が c 以上になる範囲のうちの一番左のインデックス」を返す関数 bsearch_min を書きます。

a = [0, 1, 1, 1, 2, 2, 2, 3]
p bsearch_min(a, 2) #=> 4

値が c 以上になる値がない場合は a.size を返します。空配列の場合は 0 を返します。

p bsearch_min(a, 4)  #=> 8 (a.size と同じ)
p bsearch_min([], 0) #=> 0 (a.size と同じ)

よって、bsearch_min の返り値は 0 以上 a.size 以下です。

なお、「値が c 未満になる範囲のうちの一番右のインデックス」が欲しくなることもありますが、この場合は bsearch_min の返り値から 1 を引けば OK です(その場合の返り値は必然的に -1 以上 a.size 未満になります)。どちらかというと、「左端」と「右端」のどちらが欲しいのかを混乱しないことが重要です。

区間を使う bsearch_min

def bsearch_min(a, c)
  l, r = 0, a.size - 1
  while l <= r
    m = l + (r - l) / 2
    if a[m] < c
      l = m + 1
    else
      r = m - 1
    end
  end
  l
end
  • l と r の扱いが対称的で美しい。
  • 終了時、l - 1 == r となっている。よって、「左端」ではなく「右端」が欲しくなったときは全く同じコードで r を使えばよい。
  • 除算の丸めに対してロバスト。つまり m = l + (r - l + 1) / 2 としても正常に動作する。
  • l = m + 1 と r = m - 1 から、イテレーションのたびに範囲が狭くなることが見た目に明らか。二分探索は無限ループバグを入れやすいので重要。
  • m が求めるインデックスだった場合にも r = m - 1 を実行して大丈夫なのか不安になる。つまり、求めているインデックスを i としたとき、i が (l..r) の範囲外になることがある。たとえば bsearch_min([1, 2, 3], 2) を実行すると、求めるインデックスは 1 なのに、(l..r) は (0..2) → (0..0) になるので、1 は範囲外になる。その後で l が r を追い越して (l..r) = (1..0) になり、l を返すので、バグではない。

半開区間を使う bsearch_min

def bsearch_min(a, c)
  l, r = 0, a.size # 変更点 (1)
  while l < r # 変更点 (2)
    m = l + (r - l) / 2
    if a[m] < c
      l = m + 1
    else
      r = m # 変更点 (3)
    end
  end
  l
end
  • 違いは、(1) r = a.size - 1 から r = a.size になった、(2) ループ条件が l <= r から l < r になった、(3) r = m - 1 から r = m になった、の 3 点。
  • l と r の扱いが対称的でない。半開区間だから当然だけど。
  • 終了時に l == r になっている。混乱しないという意味では利点? ただし、「右端」が欲しくなったら l - 1 を計算する必要がある。
  • 除算の丸めは floor でないといけない。(半開区間なので、すでに r に 1 足されてるようなもの)
  • r = m なので、無限ループバグが怖くなる。ループ中は l < r なので、除算が floor なら必ず m < r になる、よって範囲は確実に狭まる。というように考えれば大丈夫だとわかるんだけど、二分探索は脳力を使うところが多いので疲れる。
  • 求めているインデックスは必ず (l..r) の範囲にある。ただし、半開区間を閉区間として解釈すれば、という話なので余計にややこしい気もする。

動作仕様 (有無判定版)

ソートした配列 a に対して、「値 c を含むかどうか、含む場合はそのインデックス」を返す関数 bsearch_any を書きます。

a = [0, 1, 1, 1, 2, 2, 2, 3]
p bsearch_any(a,  2) #=> 4 or 5 or 6
p bsearch_any(a, -1) #=> nil
p bsearch_any(a,  4) #=> nil

該当する値が複数ある場合は、どれかのインデックスを返します。

区間を使う bsearch_any

def bsearch_any(a, c)
  l, r = 0, a.size - 1
  while l <= r
    m = l + (r - l) / 2
    return m if a[m] == c # c と等しい要素を見つけたら return
    if a[m] < c
      l = m + 1
    else
      r = m - 1
    end
  end
  nil # 見つからなかった
end

境界探索版との違いは、return 文を入れたことと、最後に nil を返すところだけです。

半開区間を使う bsearch_any

def bsearch_min(a, c)
  l, r = 0, a.size
  while l < r
    m = l + (r - l) / 2
    return m if a[m] == c # c と等しい要素を見つけたら return
    if a[m] < c
      l = m + 1
    else
      r = m
    end
  end
  nil # 見つからなかった
end

こちらも同様。

講評

「閉区間より半開区間を使う方がプログラムが綺麗になることが多い」という経験則を持ってる人は多いと思いますが、こと二分探索に関しては閉区間に分があるように思いました。

二分探索というと、境界探索より有無判定を指すことが多いようです。が、個人的には二分探索を使いたい場合には境界探索をしたいことが多い気がする。特に、「複数ある場合はどれでもいい」というケースは出会った記憶がない(重複がないとわかってる場合に使う?)。あと、境界探索版を有無判定版にするのはミスしにくいんだけど、逆は脳力を要する(a[m] == c の場合に l と r のどちらを変えるべきか、最終的な返り値は l と r のどちらか)ので、やはり境界探索版をベースだと思っておいたほうが良いと思う。

なお、Ruby なら組み込みの Array#bsearch や Range#bsearch を使うべきです。この記事はあくまで、何かやむを得ない事情で自力実装が必要になったとき用の備忘録です。

以下、テストに使ったコード。隣同士の差が 0 から 2 になる配列を長さ 0 から 8 まで網羅的に試しています。

def bsearch_min_closed(a, c)
  l, r = 0, a.size - 1
  while l <= r
    m = l + (r - l) / 2
    if a[m] < c
      l = m + 1
    else
      r = m - 1
    end
  end
  l
end

def bsearch_min_half_open(a, c)
  l, r = 0, a.size
  while l < r
    m = l + (r - l) / 2
    if a[m] < c
      l = m + 1
    else
      r = m
    end
  end
  l
end

def bsearch_any_closed(a, c)
  l, r = 0, a.size - 1
  while l <= r
    m = l + (r - l) / 2
    return m if a[m] == c
    if a[m] < c
      l = m + 1
    else
      r = m - 1
    end
  end
  nil
end

def bsearch_any_half_open(a, c)
  l, r = 0, a.size
  while l < r
    m = l + (r - l) / 2
    return m if a[m] == c
    if a[m] < c
      l = m + 1
    else
      r = m
    end
  end
  nil
end

0.upto(8) do |nn|
  [0, 1, 2].repeated_permutation(nn) do |diff|
    next if diff.last != 0
    a = []
    n = 0
    diff.each do |d|
      a << n
      n += d
    end
    p a
    -2.upto((a.max || 0) + 2) do |c|
      answer = a.find_index {|v| v >= c } || a.size
      raise if bsearch_min_closed(a, c) != answer
      raise if bsearch_min_half_open(a, c) != answer
      if a.include?(c)
        raise if a[bsearch_any_closed(a, c)] != c
        raise if a[bsearch_any_half_open(a, c)] != c
      else
        raise if bsearch_any_closed(a, c) != nil
        raise if bsearch_any_half_open(a, c) != nil
      end
    end
  end
end

2016-09-20

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

「このツイートはありません」となっていますが、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 年間は耐えられなかった気がする。

関連研究

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

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

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

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

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

今後の課題

もともと作りたかったのは「自分自身を埋め込んだツイート」だったのですが、残念ながら「このツイートはありません」となってしまいました。ツイート作成時点(自分自身がまだ作成されていない)でリンク先をフェッチして記録するようなので、当たり前ですね。普通の Twitter card のリンクなら 1 週間程度で再クロールしてくれるらしいですが、ツイートのリンクは Twitter card とは別の仕組みで埋め込まれているっぽいので、クロールし直してくれない予感がします*7。残念。何か手はあるかなあ。

予測的な改良の余地は 2 つ。まず、ツイート発射スクリプトRuby なので、発射タイミング自体がミリ秒単位では制御できていません。リアルタイム OS でもっときちんと制御して発射すれば、クライアント側のブレが減って timestamp のヒット率が上がる可能性があります(が、ネットワークTwitter サーバのブレは消せないので、大きく改善することはないと思っている)。それから worker-id は、プロダクションレベルのサービスやロードバランサの知識を持っている人が考えれば、もっと賢い予測方法を思いつくのかも知れません。

他に作りたいのは、相互再帰的なツイートのペアです。といっても同じような難易度で作れるはず(所要時間は倍になる)。今後も Quine Tweet の採掘を続けるためには、自宅 PC ではつらいので VPS などを借りたいところです。が、このためにお金は払いたくないなあ。。。*8

まとめ

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

あなたの知らない超絶技巧プログラミングの世界
遠藤 侑介
技術評論社
売り上げランキング: 3,000

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

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

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

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

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

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

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

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

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

2016-09-14

[] 『Rubyで学ぶRuby』連載開始

RubyRuby を作りながら 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 翻訳の際に担当編集さんだった鹿野桂一郎さんです。絵も文もイメージを伝えるだけで完成品が仕上がってくる布陣です。

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

2016-09-01

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

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

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

概要

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

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

構成

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

  • 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 しか知らないのではないかと思います。「型宣言がない方が書きやすい」は個人的には大筋同意です(記号処理なんかでは型を意識したほうがわかりやすい場合もあります)が、「型宣言がない方が読みやすい」はちょっと疑問です(特に本書が想定していそうな大規模アプリでは)。コンパイラの型チェックで見つかるような型エラーは、動的型付けでも実際に起きることなどほぼない、と言われていますが、自分にはそんなこととても言えないです。「この節を読んでおけば、静的型付け寄りの友人に議論を持ちかけられたときに論争を避けられる」のように言われていますが、この節のようなことを言えば間違いなく喧嘩・疎遠になるでしょう。(異教徒の友人と手を切らせる作戦?)

2016-08-22

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

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

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

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

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

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

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

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

プログラミングElixir
プログラミングElixir
posted with amazlet at 16.08.22
Dave Thomas
オーム社
売り上げランキング: 1,168

川崎 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]) = <<total>> + sum(tail) とか。アキュムレータの説明をしたかったようですが。まあ、「この本で関数型プログラミングを勉強しよう」と思う人はいないと思うので大丈夫かと思います)

Elixir について

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

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

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

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

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

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

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

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

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

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

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