(cache) CSNAGOYA RWH & RHG 読書会

no title については英語の読み方についての話が主だったので略。

RHG 読書会は id:miura1729 さんをお招きしての yarv2llvm の話。自分の気になったところだけメモ。

資料: http://cloud.github.com/downloads/miura1729/yarv2llvm/yarv2llvm-slide.pdf

yarv2llvm では変数の型を推論し、メソッド呼び出しをインランイン化して高速化をはかる。例えば、次のようなプログラムが与えられた場合（実際の説明はフィボナッチ数だったか説明の簡単のために階乗計算にしておく）、

def fact(n)
   if n == 1 then
      n
   else
      n * fact(n - 1)
   end
end

fact(10)

fact の定義を見ると、 fact の型は fact :: (α#== :: Fixnum -> Boolean, α#- :: Fixnum -> α, α#* :: α -> α) => α -> α と推論できそうに見える（ここで、 (α#β :: γ -> δ) => は α クラスのインスタンスメソッド β が γ クラスのインスタンスを取り、結果として δ クラスのインスタンスを返すという型制約を表すことにしておく）。これだとほとんど嬉しくないように見えるが、 yarv2llvm ではさらに呼び出し側の fact(10) も見て、そこにいくらかのヒューリスティックとグラフ簡約を用いたユニフィケーションを使って fact :: Fixnum -> Fixnum と推論するそうだ（詳しくは略）。型推論は Types and Programming Languages にあるアルゴリズムを使うと綺麗にできないかという意見が出ていた。

型推論によって、 n の型が Fixnum と推論できたので、 LLVM のコード上では ==, *, - をメソッド探索を行なわずに直接整数値の演算にすることができる。

ところで、これだと Fixnum が溢れた場合にどうなるのか気になったが、今のところのアイデアではまず、 fact を

整数値の演算
桁溢れしていたら Bignum へ変換

のように定義しておき、 Bignum を計算する必要があるとわかったときに fact を再コンパイルし、 Bignum 演算の呼び出しを行なうようにすることを考えていらっしゃるそうだ。動的再コンパイルについては Strongtalk が参考にならないか、と思って質問をしてみたが、門外漢の質問なのでうまくまとめられず。ところで、 Gauche:Bignum演算経由 The Distribution of Integer Magnitudes in Polynomial Arithmetic では、プログラム中で使われる整数値の約 95% が 30bit 整数に収まったそうだ。スクリプト言語的な用途ではこの割り合いはさらに高くなるであろうから、 Bignum 対応のコードの生成を遅延するのは理にかなっているように感じた。

さて、 Ruby と言えば eval である。 R6RS Scheme では eval の能力はかなり制限されているのであまり問題がないが、 Ruby の eval はほぼ無制限の能力がある。 Ruby の eval の使用例としてよくあるのは eval("1.0") のような文字列からオブジェクトへの変換^[要出典]と動的なメソッドの定義である。前者については Lisper の立場としては、 read と eval が分離されていれば、リテラルオブジェクトについては (read-from-string "1.0") のようにでき eval を呼ぶ必要がなくなるように思う。再利用性としてもそちらの方が高くなるのではないか。正規表現で構文チェックをしてから String#to_f などを呼ぶというのもありではあろう。後者については一旦インタプリタに動作を戻してごにょごにょするのはどうかというお考えだそうだが、そのあたりのオーバーヘッドはどうだろう、という意見も出ていた。

型推論というとプログラムの正当性検証のイメージが強かったので新鮮だった。

検証目的だと、 Haskell の型クラスみたいに特定のメソッド群を受け入れるオブジェクトの集合をクラスにしたりするのかな。 JSSST SIG-PPL あたりに論文があると思う。

型推論を使って Ruby のメソッド補完を実現しようとするプロジェクト: rsense - Ruby Code Assistant Tools - Google Project Hosting

Cuckoo Hashing - Radium Software, Cuckoo hashing - Wikipedia, the free encyclopedia。テーブルを作るときにプログラムが停止する保証がまったくないような気がしたけれど、駄目だったら適当なところで打ち切ってハッシュ関数を取り替えるのか。完全ハッシュ関数を作るよりは計算量が少ないのかしら。

通常の Rubyソースコード完全解説読書会は「第11章状態付きスキャナ」から。これも気になったところだけメモ。

メソッド名の途中に ? を含めようとするとどうなるか。

irb(main):001:0> def foo?bar; 1; end
=> nil

エラーは出ない。しかし呼び出そうとすると、

irb(main):002:0> self.foo?bar
NameError: undefined local variable or method `bar' for main:Object
        from (irb):2
        from :0
irb(main):003:0> self.send('foo?bar')
NoMethodError: undefined method `foo?bar' for main:Object
        from (irb):3:in `send'
        from (irb):3
        from :0

はて、と思って調べてみると、 ? はメソッド名の末尾にしか現れることができないので、上のコードは def foo?(bar); 1; end と解釈されているのだった。

irb(main):004:0> foo?(0)
=> 1

ところで、次のコードはどのように解釈されるのか。

def foo?
   true
end

foo = false

foo?1:2

これは、まず最左最長一致の原則に従い foo? が tFID になる。 1 は literal → arg のようになる。次に :2 を読もうとしたとき、 lex_state = EXPR_END になっているので、 p.298 にあるとおり、 : がスキャナからそのまま返ってくる。したがって次のようなエラーになる。

irb(main):007:0> foo?1:2
SyntaxError: compile error
(irb):7: syntax error, unexpected ':', expecting $end
foo?1:2
      ^
        from (irb):7
        from :0