uehaj's blog

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

どう書く.org課題「BFコンパイラー」

どう書く.org課題「BFコンパイラー」は、その名をはばかるBrainf*ckという言語処理系(Wikipedia)のGroovyでの実装です。この課題のポイントはインタプリタではなく、コンパイラということで、まずターゲット言語(この場合Groovy)での実行可能表現を考えないといけません。アイデアとしては、「インスタンスごとのメタクラス」を使って、文字そのものを実行可能なインストラクションにしよう。すると、コンパイル後のBFのインストラクション列は、必然的に文字列になって、あれれ元と同じだ。インタプリタじゃないかこれは。いや、一周して戻ってきているというか、作った側としては明らかに違うのだが・・。

以下はコンパイラそのものではなく、Groovyで書いたBFコンパイラが生成したターゲットコードとしてのGroovyコードね。最後の一行以外はランタイムってことになります。

String.metaClass.define {
  jump { ip, direc, target, curr ->
         if (code[ip] == curr) {
           ip = jump(ip+direc, direc, target, curr)
         }
         if (code[ip] == target) {
           return ip+direc
         }
         jump(ip+direc, direc, target, curr)
  }
  run {
    code = delegate
    for (int ip=0; ip>=0 && ip<code.size(); ip=code[ip].intern().exec(ip))
      ;
    System.out.flush()
  }
}
  
'>'.metaClass.exec={ ptr++; it+1 }
'<'.metaClass.exec={ ptr--; it+1 }
'+'.metaClass.exec={ data[ptr]++; it+1 }
'-'.metaClass.exec={ data[ptr]--; it+1 }
'.'.metaClass.exec={ System.out.write(data[ptr]); it+1 }
','.metaClass.exec={ System.in.read(data, ptr, 1); it+1 }
'['.metaClass.exec={ (data[ptr]==0 ? jump(it+1, +1, ']', delegate) : it+1) }
']'.metaClass.exec={ (data[ptr]!=0 ? jump(it-1, -1, '[', delegate) : it)+1 }

data = new byte[30000]
ptr = 0

'>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[<++++>-]<+.[-]++++++++++.'
  .run()

GCCとかLLVMのバックエンドとかで、BFを生成するコードジェネレータとかリンカとか無いのかなー。