indyでBrainfuckを実装してみよう!
唐突ですが、indy*1を使用して、Brainfuck言語処理系を実装してみます。Brainfuckはいわゆる一つの奇妙なプログラミング言語ですが、処理系の実装が容易であることを重視して設計されたチューリング完全な言語であり、試しに実装してみるのには良いでしょう。
とはいえ、残念ながらBrainfuckは動的言語ではないので、あんまりindyが役にたちません。
そこで、一捻りとして、"++--"といった命令列を文字列として保持し、Bootstrapメソッドの実行時に「メソッド呼び出しの列を表現するMH」として生成してみます。"+"がp()、"-"がm()というメソッド呼び出しに対応するとすると、"++--"というオプション引数を受けとったならば、「p(), p(), m(), m(),」という一連の呼び出しを結合したMHをMethodHandles.filterReturnValueで作成し、CallSiteにして返すようなBootstrapメソッドを実装します。これによってクラスファイルのサイズが減少することを期待します。
以下がBrainfuckコンパイラのコード(compile.groovy)です。
// ネストしたループにおけるラベル名を管理するためのデータとコード。 def list = [].withDefault{0} def nestLevel = 0 def level = { it << list[0..nestLevel-1].join('_') }.asWritable() def increaseLevel = { list[nestLevel++]++; level(it) }.asWritable() def decreaseLevel = { level(it); nestLevel-- }.asWritable() // Brainfuck命令をJVMバイトコードにコンバートする def genCode = { new File(args[0]).text.replaceAll(/[^\+\-\<\>\.\,\[\]]/, '').eachMatch(/[^\[\]]+|[\[\]]/) { g0 -> if (g0 == '[') { it << """ _GOTO tmp$increaseLevel lab$level: """ } else if (g0 == ']') { it << """ tmp$level: getstatic '.data','[B' getstatic '.dp','I' baload ifne lab$decreaseLevel """ } else { it << """ invokedynamic 'dummy', '()V', [H_INVOKESTATIC, 'Brainfuck', 'bootstrap', [CallSite, Lookup, String, MethodType, String]], '$g0' """ } } }.asWritable() println """\ @GrabResolver(name="maven-repo", root="https://raw.github.com/uehaj/maven-repo/gh-pages/snapshot") @Grab("groovyx.ast.bytecode:groovy-bytecode-ast:0.2.0-separate-asm") import groovyx.ast.bytecode.Bytecode import java.lang.invoke.* import java.lang.invoke.MethodHandles.Lookup import static groovyjarjarasm.asm.Opcodes.H_INVOKESTATIC class Brainfuck { // Bootstrapメソッド public static CallSite bootstrap(Lookup lookup, String methodName, MethodType type, String instructions) { MethodHandle result = null instructions.tr('<>.','lgo').each { insn -> MethodHandle mh = lookup.findStatic(Brainfuck, insn, MethodType.methodType(void.class)) result = (result == null) ? mh : MethodHandles.filterReturnValue(result, mh) } new ConstantCallSite(result) } // Brainfuck実行のためのデータ構造 static int dp // データポインタ static byte[] data = new byte[30000] // メモリ // Brainfuck命令群 static void '+'(){data[dp]++} static void '-'(){data[dp]--} static void l(){dp--} // メソッド名が'<'だとクラスファイルとして違法なメソッド名になるので妥協 static void g(){dp++} // '>' static void o(){print((char)data[dp])} // '.' static void ','(){System.in.read(data, dp, 1)} @Bytecode static void main(String[] args) throws Exception { // Brainfuckからコンバートされたコード $genCode return } }"""
Bytecode DSLを使っています。
このコードは、Brainfuck言語のソースファイルを引数として起動すると、Bytecode DSLを用いたアセンブラコードを含むGroovyコードを標準出力に出力します。
以下は実行例です。
% cat hello.bf >+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[<++++>-]<+.[-]++++++++++. % groovy compile.groovy hello.bf > a.groovy % groovy -Dgroovy.target.bytecode=1.7 a.groovy Hello World!
上でa.groovyにはこんなコードが生成されています(抜粋)。全体はこちら。
class Brainfuck { // Bootstrapメソッド public static CallSite bootstrap(Lookup lookup, String methodName, MethodType type, String instructions) { MethodHandle result = null instructions.tr('<>.','lgo').each { insn -> MethodHandle mh = lookup.findStatic(Brainfuck, insn, MethodType.methodType(void.class)) result = (result == null) ? mh : MethodHandles.filterReturnValue(result, mh) } new ConstantCallSite(result) } // Brainfuck実行のためのデータ構造 static int dp // データポインタ static byte[] data = new byte[30000] // メモリ // Brainfuck命令群 static void '+'(){data[dp]++} static void '-'(){data[dp]--} static void l(){dp--} // < static void g(){dp++} // > static void o(){print((char)data[dp])} // . static void ','(){System.in.read(data, dp, 1)} @Bytecode static void main(String[] args) throws Exception { // Brainfuckからコンバートされたコード invokedynamic 'dummy', '()V', [H_INVOKESTATIC, 'Brainfuck', 'bootstrap', [CallSite, Lookup, String, MethodType, String]], '>+++++++++' _GOTO tmp1 lab1: invokedynamic 'dummy', '()V', [H_INVOKESTATIC, 'Brainfuck', 'bootstrap', [CallSite, Lookup, String, MethodType, String]], '<++++++++>-' tmp1: getstatic '.data','[B' getstatic '.dp','I' baload ifne lab1 invokedynamic 'dummy', '()V', [H_INVOKESTATIC, 'Brainfuck', 'bootstrap', [CallSite, Lookup, String, MethodType, String]], '<.>+++++++' _GOTO tmp2 lab2: invokedynamic 'dummy', '()V', [H_INVOKESTATIC, 'Brainfuck', 'bootstrap', [CallSite, Lookup, String, MethodType, String]], '<++++>-' :
実行にはJava 7が必要です。indyなので。
詳しくはこちらかこちら。
では!!
