As Sloth As Possible

可能な限りナマケモノでありたい

タグ:言語処理系

なんでなのかと聞かれても「なんか暇だったから…」としか。

いや元々はこう周期的に来る「なんか仕事と全然関係ないコード書きたい」期だっただけなんだけど、Goとかで遊んでる最中にひょんなことからRustを見付けてしまってへー面白そうとか手を出してみることになり、「慣れない言語を使うときはとりあえずWhitespaceの処理系を作ってみるとなんか慣れたような気分になる」という癖でですね。なんか出来ちゃった。

記事書いてる時点の最新のnightly(v0.12.0-pre)ではコンパイル通るのを確認済み(というか多分0.12.0でしかビルドできない。流石いつβが出るとも分からないα言語、0.10.0と0.11.0と0.12.0で互換性無いし、ドキュメント見に行ったら標準ライブラリを含むほとんどのAPIがexperimentalだった)。rust-albinoの方をcloneしたら最新のrustcと対応するcargoをrustupかなんかで入れて、

cargo build
するとビルドできる。homebrewでも入れられるけどバイナリだと0.11.0、ソースからのビルドだとかなり時間かかるので大人しくnightlyのバイナリ使うがよろし。

Albinoがコマンドラインツールで、こいつがWhitespaceを実行したり逆アセンブルしたりしてくれる。最初は普通にインタプリタ作ってたんだけど、例のごとくWhitespace読めないし書けないからアセンブリ言語でもでっちあげよう、あとその昔書いたDTとかも動かしたいよねー、とかやってたらいつの間にかVMとパーサが分離して副産物として何故かライブラリになっちゃったのがWhitebase

厳密に言うと本体はWhitebaceの方でAlbinoはただのインターフェースだったりするけど細かいことは気にしない。先に名前が決まったのはWhitebaseの方で、Whitespaceの命令セットを持ったVMとパーサのライブラリなので「白地」というのが由来であって決して某19歳に見えない艦長率いる連邦の戦艦ではない。合わせてツールの方はWhitedevilにしようかなーとか一瞬考えたけどコマンド名としては長すぎるしrx78とかエイリアスするはめになるのでアルビノにした。VMとパーサが分離した結果どういうわけかBrainf*ck派生の言語をWhitespaceの命令セットに変換できるようになったので、「本来白くないものまで白くなっている」からアルビノなんです。

得られたもの。Rustがなかなか触っていて楽しいということが分かった。いまどきっぽいサブコマンド型のコマンドどうやって作ってるのかなーってのが分かった。WhitespaceもしくはBrainf*ckのトークンの内部表現を返すイテレータさえ実装できれば簡単にオレオレ言語が作れるライブラリが出来たので、今後さっと言語を作ってドヤリングしたいときは一瞬で出来るようになった。Brainf*ckの任意のプログラムからWhitespaceのコードが生成できるようになった。

失なったもの。時間。結構な無駄な時間。

ゴールデンウィークを利用して久々にろくでもないものができたので晒しておく。

「ごっこじゃないよ、兄ちゃん!」「才能の無駄遣いじゃなくて、無駄そのものだよ、お兄ちゃん。」

前のと何が違うの?

そもそもの発端についてはプログラミング言語「DT」という記事を、実際の言語仕様についてはREADMEでも読んでもらうとして、何で再実装したのかという話。

3年前に作ったのは「Whitespaceのトークンを置換した処理系をインタプリタとしてRubyで実装」したものなんだけど、何を思ったかコンパイルしてみたいと思い立ってしまい、んでそれ自体はLLVMが良く分かんなかったとか、llvmruby自体がプロジェクトとして大分アレな感じになってしまっていたとか、そういう事情で挫折してたんだけど、時は流れ、なんか見返してみたら普通にLLVMアセンブリ読み書きできるようになってたし、ruby-llvmがちゃんと動くようになってるみたいだし、ということで再実装してみることにした。

そんで作り直す過程で「Whitespaceの置換ってのもなんだか面白くないな」と思ってVMのアーキテクチャと言語仕様を見直すことにした(ぱっと見だと全然分かんないけど、旧DTと新DTの間に互換性は無い)。そのせいで実際にはチューリング完全じゃなくなってると思うし、そもそもちゃんと出来てるのかどうか怪しいものだけど、とりあえず「Hi!」って出力するのとフィボナッチ数を出すのは動いたので良しとする。

当初の目標だった「DTコードをネイティブのバイナリにまでコンパイルして高速に実行」ってのも実現して、DTインタプリタで250msくらいかかるfib.dtをコンパイルすると4msくらいで結果が出るようになった。似たようなRubyのコードだと大体100msくらいだったので素敵に速い。まぁ、コンパイル自体はLLVMとコンパイラに任せているので大して威張れるあれでもないのだけども。そして高速に動いたからなんだという話なのだけども。

ぶっちゃけDTよりLLVMアセンブリの方が遥かに記述力高いし書きやすい。当たり前のように構造体とか関数ポインタとか使えるのな。Cの関数呼べるし。最初Cで書いてたVMを途中でLLVMアセンブリ直接書くようにしたけど、大して変わらない。DTで書くくらいならLLVMアセンブリ書いた方がいいです。LLVMの無駄遣いタグを付けていただきたい。

DTの存在意義については疑問を差し挟む余地もなく皆無だと言っていいけど、その過程でレジスタマシンについて色々調べて、はー、こんぴゅーたーってこうやってうごいてるのかー、と勉強になったのでそれはそれで良かった。よくこんなの考えられるよなぁ。CPUとかコンパイラとか作ってる人達、本当に俺と同じ種類の生き物なのだろうか。凄い。

ここ数日、LLVMについて少し勉強している。そもそもなんでLLVMを触り始めたかというと、Twitter上で「今コンパイル欲求に駆られている」と(割と何も考えずに)つぶやいたところ、

  1. 「じゃあDTコンパイルしようぜ」
  2. srd!
  3. でもあれコンパイラとは名ばかりでぶっちゃけ文字列をRubyコードにtranslateしてるだけだったりするね
  4. 「DTパーサを改良してLLVMにブリッジして、クロスプラットフォーム環境で高速に動作するDT処理系にするといいよ」
  5. 何その無駄に敷居高いお仕事!誰得!でもなんか面白そう!

というやりとりがあって、じゃあ本当に誰が得するのかわからないけど面白そうだからLLVMをバックエンドで使ってesotericがサポートしてるコードからバイナリを生成するコンパイラ作ろうぜ、という流れになったから。実にLLVMの無駄遣いですね。この記事ブクマするときは「LLVMの無駄遣い」ってタグを付けるといいですよ。

LLVMって何さ?

まずそもそも、iPod touchのJail Breakに手を出そうとしたときにちょこっと調べたりした(iPhoneSDK発表以前、JBしたiPod touch/iPhone向けにアプリを開発する際にはLLVMを使ってiPhone OS向けにコンパイルする必要があった。最近は追ってないので今どうなってるかは知らない)程度だったので、実のところLLVMが何をするものなのかちゃんと分かってなくて、どうすんべーとまず調べ直すところから始める。

LLVMとはLow Level Virtual Machineの略で、Lightweight Languageとは特に関係がないようだ(お約束)。知ってたよ。うん。知ってたってば。調べた結果、コンパイラ基盤と呼ばれるものでコンパイラを作るのに使うライブラリ・ツール群であること、VMの名の通り一度LLVMで処理できる中間言語にした後、それをLLVMのツールで実行したりネイティブのバイナリに変換したりして使うということ、コンパイル時や実行時に様々な最適化を施してくれて、より実行効率の良いプログラムを作れるようにしてくれるらしいこと、なんかが分かった。他にも色々あるけど、それはきっと詳しい人がどっかでまとめてくれてるから割愛。うん。分かんなかったわけじゃないよ。違うってば。

あと、llvm-gccとかclangとかを使えばC/C++/Objective-CのコードをLLVMに対応させてコンパイルできるようだ。それはそれで面白いけど今回は「自作の言語をコンパイルするのにLLVMを使う」のが目的なので、どっちかというとそれ相当のものを作ることになるのでとりあえずその辺は後で見ることにする。DTコンパイラをllvm-gccと並べてよいものかとかそこにツッコミを入れるのは無しの方向で。石を投げたりしないで下さい。

Rubyから使う

大雑把に何なのかはわかったけど、さてどう使おう。C++では使えるようだしサンプルもC++のコードが並んでるんだけど、C++書いたことないしなぁ、ってかRubyで書いてたのをC++を勉強しつつ書き直すとか面倒くさいなぁ、むしろObjC書きたいなぁObjC、とか段々脱線しはじめたときに、RubyからLLVMを使うgemがあるのを見つけた。

これこれ、これが欲しかったのよと早速gem installしてみたところ、コンパイルは通ってちゃんとインストールできるんだけど、サンプルコードを動かしてみたところdylibのload errorが出る。MacOSX10.5のRuby1.8.7(LLVM、RubyともにMacPortsからインストール)でしか試してないけど、どうも上手く行かない様子。調べてみようと思ってgithubからソース落としてきて、ローカルでgemをビルドするところからやってみたら、そっちはちゃんと動くようになった。あれかなぁ、リンクするライブラリとか違うとこ見ちゃうのかな。まあいいや、とりあえず深追いするのはもう少し後にしよう。

大雑把にllvmrubyの使い方を説明すると、大体以下の通り。

  1. LLVM::Moduleのオブジェクトを作る
  2. LLVM::Module#external_functionで外部のライブラリの関数を使えるようにする
    • CやC++のライブラリから取ってこれるようなので、Rubyの組み込み関数とかも呼べる
  3. LLVM::Module#get_or_insert_functionで関数を定義する
    • 上のメソッドがLLVM::Functionのオブジェクトを返すので、それのcreate_blockメソッドでブロック(関数の中身)を用意する
    • ブロックのBuilderを取得して、それに対してごにょごにょして中身を作る
    • b = method.create_block.builderですね
  4. LLVM::Module#write_bitcodeでコンパイルしてファイルに書き出すか、LLVM::ExecutionEngineのrun系メソッドでそのまま実行する

ちなみにこれはLLVMのバイトコードを生成する手順だけど、他にRuby1.9のVMの命令セット互換の中間表現を実行するruby_vm.rbが添付されてたり、Rubyのコードをllvmrubyを使ってJITコンパイルするものだと思われる(ちゃんと見てないので間違ってたらツッコミ歓迎)yarv2llvmってgemがあったりする。ただまぁ、「DTをRuby上で高速に実行したい」のではなくて「DTからスタンドアローンのネイティブプログラムを生成したい」ので、こっちは今回は使わない。Cでの拡張をしないアプローチでRubyのプログラムを高速化したくなったらこの辺のを使うのかな、多分。ruby_vm.rbの方は後でVMを実装するときに参考になりそうだからそのときにまた読もう。

ぐぬぬ

ここまでは何とか辿りついた。実はここまでで結構試行錯誤してるけど、まぁ何とかここまではよしとする。で、だ。ここで問題なのは、前回のバージョンアップで中間表現をRuby2Rubyで扱えるASTにしてしまったこと。何が問題かって、これのコンパイラを作るってのはつまりRubyのコンパイラを作るってことになるわけですよね。うん。…できるかっ!

そもそも言語処理系の基礎知識も何もない状態でネタで始めた言語作り、いきなりRubyのASTを処理できるコンパイラを作るとか正直敷居が高すぎるので、もう一度中間表現の見直しをすることにした。もっとシンプルなASTにしておけばコンパイラの方でも扱いやすいし、前回ぶっ殺したEsotericVMの方ももう少し楽に作れるかもしれない。

そこで今少しずつ仕様の見直しをしつつコンパイラを書きつつ進めてるのだけど、Low Level Virtual Machineと言うだけあってライブラリ側では大分コアなところしか用意はしてくれないわけですよね。てことで諸々のデータ型とか最低限必要な組み込みの関数とか自分で用意してやらなきゃいけないわけで、その辺考えてたら大分混乱してきた。

どう考えてもDTにオブジェクトシステムとかGCとかは要らないので適当に端折ろうとは思うのだけど、esotericはパーサ部分で大方の言語固有の要素を解決しちゃってコンパイラやVMの方は汎用的な言語処理系の基盤にしたいわけで、そうすると一応はちゃんと考えて設計しないといけないよなぁ。いかにミユビナマケモノとはいえそろそろノリでなんとかできる範囲を超えてきた感じ。助けてくだしあ。とりあえずお薦めの書籍とか誰か教えてくれると嬉しいなぁ。情報系の学生が読むようなの。

こないだ作ったesotericがあろうことか0.0.2にバージョンアップしました。主な変更点は以下の通り。

  • 各言語をコンパイルしてできる中間コードが、前のバージョンでは似非アセンブラ的な何かだったものを、ParseTreeなんかで作るようなRubyの抽象構文木(AST)的な何かに変わった。VMでの実行前に生成されたコードを最適化するとかできるようになるとか、他のRubyライブラリにEsoteric Languageパーサが埋め込めるようになるとか、無駄に夢が広がる感じで。
  • もちろん似非VMでは動かなくなったので、作り直さなきゃいけないんだけど、ちょっと時間かかりそうなので似非VM殺した。そのかわり、ASTはRuby2RubyとかでRubyコードに変換できるように作ってあるので、とりあえずRuby2Rubyを使うようにして誤魔化すことにした。
  • 副産物としてDTやWhitespaceのコードを実行可能なRubyスクリプトに変換するコンパイラもどきのツールが出来た。Cへのトランスレータもあるみたいだし、そういうの使えば本当にコンパイルしてバイナリも作れたりしますね。DTでコマンドとか作れるようになるね。まったくやりたくないけどね。
  • Brainf*ckのパーサを追加
  • てってってーのパーサを追加。一応一通りの仕様は満たしてると思うけど、「「\xAB」「\uABCD」「\d00000」:エスケープシーケンスとして、それ全体で1文字と扱われる。(予定)」ってのはまだ実装してない。あと「ててー」と「てっー」が微妙な動きをするのを解決してないけど、まぁそのうちなんとかする。

とまぁ、そんな感じ。次はまず、VMの再実装と、あとSpec書く。それ終わったらRubyで作る奇妙なプログラミング言語 ~Esoteric Language~に載ってたStarryやBolicでも実装しようかな。あとはとかやってみようかしら。

大分楽しくなってきたところだけどアイマスSP買ってきてしまったので、一回休み。そしたら来月ぐらいから仕事が忙しくなるに違いないのでまた一回休み。一段落ついたら多分飽きてるだろうからまた(ry。まぁまったりもったりやりますかねぇ。

最近「Rubyで作る奇妙なプログラミング言語 ~Esoteric Language~」を読んで、ついカッとなって言語処理系を作ってみた。それも、チューリング完全な、本物の(ry まぁ、Whitespaceのトークンを置き換えただけだけど。

一応、上記の本に習って、ソースコードをWhitespaceの命令セットを持つ中間言語にコンパイルしてVMで実行する形にしてみた。あとはパースする部分を適当に置き換えたコンパイラを作ればそれっぽいのが簡単に作れる。んで、いくつかネタ言語を作ってみたんだけど、その中でも一番しょーもないのがDT。DTでは次のようなソースを実行することができます。("Hi!\n"を出力する)

「○○くんて、もしかして童貞?」
「どどど童貞ちゃうわっ!どど童貞ちゃうわっ!どどど…童貞ちゃうわっ!」
「えー。その慌てっぷりが余計怪しなぁw」
「…どどどどど童貞ちゃうわっ!童貞ちゃうわっ!ど童貞ちゃうわっ!どど童貞ちゃうわっ!…童貞ちゃうわっ!」
「はいはい、わ、わかったってば。そんなにムキになんないでよ。」
「…どどどどど童貞ちゃうわっ!どどどど童貞ちゃうわっ!…童貞ちゃうわっ!」
「だから、わかったってば。もう言わないから。」
「…どどどどど童貞ちゃうわっ!ど童貞ちゃうわっ!ど…童貞ちゃうわっ!」
「いやその、なんか、ほんとごめんね。そんなに気にしてると思わなかったから、あの…」
「どど…」
「(ほんとキモいなぁ…)」
「…」

バレンタインだと言うのに一体何をしてるんですかね、僕は。ちなみに「ど」「童貞ちゃうわっ!」「…」以外の文字は全て無視するので、それらの順番と数さえあってればどんなコメントを挟んでも問題ない。コメント記法とかも特にない。ちなみに上記のコードから有効な部分を抜き出すとこんな感じ。一応読みやすくするために改行は入れてある。

どどど童貞ちゃうわっ!どど童貞ちゃうわっ!どどど…
童貞ちゃうわっ!…どど
どどど童貞ちゃうわっ!童貞ちゃうわっ!ど童貞ちゃうわっ!どど童貞ちゃうわっ!…
童貞ちゃうわっ!…どど
どどど童貞ちゃうわっ!どどどど童貞ちゃうわっ!…
童貞ちゃうわっ!…どど
どどど童貞ちゃうわっ!ど童貞ちゃうわっ!ど…
童貞ちゃうわっ!…どど
………

あと他に「アイドルが機嫌良さげに踊るののワ型言語HRK」とか、「9つの世界を巡る変身ヒーロー型言語Decade」とか作ったけど、どれも今のところただのWhitespaceなのでどんなソースになるかは想像つきますね。てことで割愛。もちろんどれも入出力や四則演算やジャンプ命令を備えてますので、フィボナッチ数列を無限に出力するとか余裕だし、その気になればきっとWebアプリぐらい書けますね。やりたかないけど。ていうかどれも書くことを全く考慮してないので、俺もうざくなって似非中間言語書いてそれを置換してソースコードにするっていう本末転倒なことしないと書けない。まぁそんなもん。

そろそろWhitespaceにも飽きたので、次は何しよう。Ruby分は十分補充できたので、Objective-CでVM書くとか、Parrotの上で処理系作るとかしようかな、とか。関数型言語もまだやってないので、それを実装するのもいいし、処理系をHaskelで書いてみるとかもしたい。しょーもない見た目の「まともな」言語仕様を考えるとかもしたいなー。やってみると結構面白い。ハマる。十分脳味噌ほぐれたらちゃんとした言語処理系のソースでも読んでみよう。

と、そんな現実逃避をして過した休日。うーん、充実した土日だった。え?何?何でDTなんか作ったのって?もしかしてfaultierって童…いいいいいやいやいや。どどどどど童貞ちゃうわっ!

注意

上の言語はほんとしょーもないですが、Rubyで作る奇妙なプログラミング言語 ~Esoteric Language~の方はちゃんと面白い本なので誤解のなきよう。変な言語も色々紹介されてるし、Rubyでサクっと言語処理系つくるやりかたも書いてあるので、オススメです。

Rubyで作る奇妙なプログラミング言語 ~Esoteric Language~Rubyで作る奇妙なプログラミング言語 ~Esoteric Language~
著者:原 悠
販売元:毎日コミュニケーションズ
発売日:2008-12-20
おすすめ度:4.0
クチコミを見る

追記

これ書いた後にクチコミを見たら弾さんがてってってーとかやってて、その記事のさらに元記事が結構なブクマ数だったりして、今頃それに気付いてなんか負けた気分。ぬぅ…。いいもん、ちゃんとののワさん言語完成させるから。もうなんかiPhoneで動くようにしちゃうから。配布できないけど(インタプリタは規約でAppStoreに登録できなかったはず)。

↑このページのトップヘ