連鎖性言語を作る8 - mirichiの日記

オレ言語の実装として、Rubyの配列にオブジェクトを詰めたものをASTとして扱っているのは特徴的だ。実際コード自身がオブジェクトを並べたような見た目をしているのでこれはこれで直感的とも言える。ところでVMはそのASTを解釈して実行しているわけなので、これは名前はVMだが素朴なインタプリタじゃないのか、という思いがある。今回はここを名実ともにVMにしてみよう。
ASTをもっとASTっぽくNodeなんちゃら的なクラスのインスタンスを詰めた配列にしてもいいのだが、それは単純に無駄っぽいので、ここはそのままにしておく。ASTをなんらかの命令列に変換して、VMでの実行直前にコンパイル、VMはコンパイル後の命令列を実行する。と言うとちょっとカッコイイのだが。

コンパイラ

とりあえず命令列の表現方法を考える。つってもやることはオブジェクトをスタックに入れるかワードを呼び出すかの2択なので、命令は2個となる。たかだか2個の命令を表現するならそれこそtrue/falseでもいいんじゃないかと思うわけだが、今後を考えてStructを使って命令とデータを持たせるようにしよう。

class Instruction < Struct.new(:insn, :data)
end

これを配列に並べたものが命令列となる。命令は:pushと:callとして、スタックに入れる、ワードを呼び出すを表現する。データはそれぞれ扱うデータで、:pushの時はスタックに格納するオブジェクト、:callの時は呼び出すワードのシンボル、となる。
コンパイラはこのようにしてみた。ASTを表す配列を受け取って、コンパイルした後、配列のインスタンス変数@bytecodeにコンパイル結果を格納する。別にバイトコードでもないので名前は変だがRubyでほんとにバイトコードを扱うのも無駄なので。雰囲気だけ。

module CodeGenerator
  def self.generate(ast)
    ast.instance_variable_set(:@bytecode, ast.map{|d|
      case d
      when Symbol
        Instruction.new(:call, d)
      when OreSymbol
        Instruction.new(:push, d.sym)
      else
        Instruction.new(:push, d)
      end
    })
  end
end

バイトコード インタプリタ

このバイトコードを実行するVMを実装すればバイトコードインタプリタを名乗ることができるようになるわけだ。バイトコードではないけど。

  def run(ast)
    unless ast.instance_variable_defined?(:@bytecode)
      CodeGenerator.generate(ast)
    end

    ast.instance_variable_get(:@bytecode).each do |d|
      case d.insn
      when :call
        @words[d.data].call
      when :push
        @stack << d.data
      else
        raise
      end
      break if @break_flg
    end
  end

ASTの配列に@bytecodeが無い場合はCodeGenerator.generateを呼び出して命令列を生成する。あったら呼ばない。caseの中身でクラスの判別をしなくてよくなったのでちょっとだけすっきりした。
このようなプログラムの問題点は、実行時に生成したQuotationで1度呼び出した後に中身を変更してもう1度呼び出した場合に、コンパイル済み命令列を削除しないと前の状態の命令列が残ってしまうところで、実行中に中身を書き換えたらクリアするような処理が本来は必要である。Rubyの実装で言うならメソッドキャッシュはメソッド再定義時にクリアしないといけない、みたいな話だ。動的言語には常に付きまとう厄介な問題だが、とりあえず面倒なのでスルーしといた。実際のところ、Ruby側に渡してそっちで中身を書き換えるなどもできるわけなので、オレ言語におけるこの問題は非常に厄介で、そもそもどんな言語でも言語を作るならそういうのを一つ一つ丁寧に解決していく作業が必須になる。大変なんだなあーとシンプルすぎる言語を作りながら思う次第である。