読者です 読者をやめる 読者になる 読者になる

uehaj's blog

Grな日々 - GroovyとかGrailsとかElmとかRustとかHaskellとかFregeとかJavaとか -

indyでBrainfuckを実装してみよう!

groovy indy invokedynamic java7 Bytecode DSL

f:id:uehaj:20130823134705p:plain

唐突ですが、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なので。
詳しくはこちらこちら

では!!

*1:Java VM上での動的言語の実行を効率化することを目的とした一連の機能拡張(JSR 292: Supporting Dynamically Typed Languages on the Java Platform)が導入されました。この機能拡張で追加された新規バイトコード命令「invokedynamic」にちなみ、この機能を愛称としてindyと呼びます。

広告を非表示にする