miura1729の日記

進みましたが、バグがいっぱいです

18:43 |

ytlのアセンブラはRubyにアロケートしたメモリにバイナリを生成してJITで実行できるようになりました。でも、いろいろ試していたらバグがいっぱい出てきて直さないといけないです。特に、間接アドレッシングの当りは全然だめです。こんな感じでプログラムが動きます。いずれにしてもあまりオーバヘッドなくコードが生成できるのでいろいろおもしろそうなことができそうです。

Hello World

def hello
  asm = Assembler.new(cs = CodeSpace.new)
  
  # registor definition
  eax = OpEAX.instance
  esp = OpESP.instance
  hello = OpImmidiate32.new("Hello World".address)
  asm.mov(eax, hello)
  asm.push(eax)
  rbp = address_of("rb_p")
  asm.call(rbp)
  asm.add(esp, OpImmidiate8.new(4))
  asm.ret
  asm.flush
  cs.call(cs.base_address)
end
hello

Fib

def fib(n)
  cs0 = CodeSpace.new
  cs1 = CodeSpace.new
  cs2 = CodeSpace.new
  
  # registor definition
  eax = OpEAX.instance
  ebx = OpEBX.instance
  esp = OpESP.instance

  asm = Assembler.new(cs0)
  ent = cs1.base_address

  asm.mov(eax, OpImmidiate32.new(n))
  asm.call(ent)
  asm.add(eax, eax)
  asm.add(eax, OpImmidiate8.new(1))
  asm.ret
  asm.flush
  
  asm = Assembler.new(cs1)
  asm.cmp(eax, OpImmidiate32.new(2))
  asm.jl(cs2.base_address)
  asm.sub(eax, OpImmidiate32.new(1))
  asm.push(eax)
  asm.call(ent)
  asm.pop(ebx)
  asm.sub(ebx, OpImmidiate32.new(1))
  asm.push(eax)
  asm.mov(eax, ebx)
  asm.call(ent)
  asm.pop(ebx)
  asm.add(eax, ebx)
  asm.ret
  asm.flush
  
  asm = Assembler.new(cs2)
  asm.mov(eax, OpImmidiate32.new(1))
  asm.ret
  asm.flush

  cs0.call(cs0.base_address)
end

(1..39).each do |i|
  p fib(i)
end

現実逃避しています

21:45 |

　いまは、非常に忙しいです。忙しいので、こんなことをしていてはいけないのですが、プログラムを作っています。これが楽しい。で、なにを作っているかというと、Rubyでアセンブラを作っているのです。

http://github.com/miura1729/ytljit

初めにアセンブラを書いておいて、これで次期yarv2llvm(ytl)のVMを書こうという魂胆です。つまり、llvmはもう使わないということです。

アセンブラはこんな感じで使えます。

require 'lib/ytljit/ytljit.rb'

include YTLJit

asm = Assembler.new

# registor definition
eax = OpEAX.instance
ecx = OpEAX.instance

asm.mov(eax, OpImmidiate32.new(0))
loop = asm.current_address
asm.add(eax, OpImmidiate8.new(1))
asm.jo(loop)
asm.ret

File.open("foo.bin", "w") {|fp|
  asm.flush(fp)
}

これで、こんなコードが出てきます。

$ objcopy -I binary -O elf32-i386 -B i386 foo.bin foo.o; objdump -D foo.o

foo.o:     file format elf32-i386


Disassembly of section .data:

00000000 <_binary_foo_bin_start>:
   0:   b8 00 00 00 00          mov    $0x0,%eax
   5:   83 c0 01                add    $0x1,%eax
   8:   70 fb                   jo     5 <_binary_foo_bin_start+0x5>
   a:   c3                      ret

アセンブラ作成にあたって、fujita-yさんのYpsilonとhigeponさんのMosh JITのコードを参考にさせてもらいました。ありがとうございます。

追記

こんなこともできます

arynew = address_of("rb_ary_new")
asm.call(arynew)

yarv2llvmの作り直しの検討　MethodBehaviorクラス

09:06 |

yarv2llvmを作成していて、メソッド呼出毎にさまざまにコンパイルの仕方を変える必要があることがわかりました。

例えば、eachは多くの場合インライン化する必要があるし、String#packは第1引数のテンプレートを見て型推論を行う必要があるし、newはエスケープ解析の結果でどこにアロケートするか変えないといけないわけです。

現状のyarv2llvmはこの辺をアドホックにテーブルを作って対応していたのですが、メソッドごとの振る舞いをちゃんとクラスにまとめたほうがいいなと気付きました。

• 振る舞いの異なるメソッドごとに用意する
• MethodBehaviorクラスは次のような動作をおこなうメソッドを用意する
  • 初期トラバース
  • 型推論
  • コード生成
• MethodBehaviorDefaultクラスを用意し、普通のメソッドはそれを利用する。また、他のクラスは、MethodBehaviorDefaultを継承するようにする

追記

　いっそのこと、これらのオブジェクトをノードにするASTを作ったほうがいいと気付いた。MethodBehaviorという名前はSendNodeHogehogeとかとい名前になる。他にも変数参照などのノードも作る。ASTを作成後、型推論のトラバースを型が収束するまで繰り返し、コード生成をトラバースする。

動的に型づけされた言語の実現方法の資料

16:32 |

私の知る範囲の動的に型づけされた言語の実現方法の資料をまとめてみました。英語は苦手なんで日本語中心です。

こういうのがあるよとか、こんなところにリンクしないでくれとかありましたら教えてください。

思い出したら追加します。

変更履歴

2009/12/13

初版

美しい日本のMLコンパイラを追加

動的言語を動的に型づけされた言語に変更

TAO/KCLを追加

2009/12/25

マルチパラダイム言語TAO追加

Garbage Collection

http://wiki.livedoor.jp/author_nari/

Gauche

http://practical-scheme.net/wiliki/wiliki.cgi?Gauche

http://practical-scheme.net/chaton/gauche/

http://www.nicovideo.jp/watch/sm7543249 (shibuya.lispでのshiroさんの講演)

ypsilon

http://d.hatena.ne.jp/fujita-y/

http://www.nicovideo.jp/watch/sm5049451 (shibuya.lispでのy-fujitaさんの講演)

Ruby

http://www.loveruby.net/ja//rhg/ (Ruby Hacking Guide)

YARV

http://www.atdot.net/yarv/yarvarch.ja.html

http://www.atdot.net/~ko1/w3ml/w3ml.cgi/yarv-dev/ (yarv-devメーリングリストのログ)

ML

http://min-caml.sourceforge.net/index3.html

TAO

http://ci.nii.ac.jp/search?q=tao%2Felis&range=0&count=20&sortorder=1

http://www.nue.org/nue/tao/bitao/index.html (bitに連載されていたのマルチパラダイム言語TAO)

KCL

http://ci.nii.ac.jp/naid/110002673528

短歌作成プログラム

21:38 |

ひょんなことから短歌作成プログラムを作ることになりました。

もっと優先順位の高いやらなければいけいないことが多いので、忘れないようにメモをします。

基本的な考え方

1. 基本的な考え方は５・７・５・７・７になるように単語をランダムに並べる
2. 単に並べるだけではまともなものが出来ないので、ある単語を選んだらその次に続く単語の推移確率をテーブル化する。この推移確率は実際に短歌を生成して、その評価によって調整される
3. 推移確率は単語レベルのものと品詞レベルのもの、さらに単語->品詞、品詞->単語の４種類を用意する。例えば、形容詞 -> 名詞, 名詞 -> "は", "白い" -> "雪"などの推移確率を表現できるようにする。

単語テーブルのデータ構造 TODO

単語、文字数、品詞

文字数と品詞から検索できなければならない

推移確率テーブルのデータ構造 TODO

４つの推移テーブルとそれぞれのテーブルの重み付け？

推移テーブルの調整アルゴリズム TODO

多分、作りながらじゃないと決定不可能