連鎖性言語を作る

Ruby

スタック指向言語、とか、連鎖性言語、などと呼ばれる言語がある。有名どころではForthやPostScriptあたりで、かなり古くから存在していて、最近ではFactorといった関数オブジェクトを扱える実用的なものまである。
基本的なコードの例としては、

1 2 + print

て感じで、文字を空白で区切って記述する。1と2をスタックに積んで、+を呼び出すと+はスタックから2個取り出して加算結果を積んで、スタックの中身は3になり、それを表示する、と。パッと見、逆ポーランド記法的な書き方になっているが、実際そうで、

1 2 + 3 4 + * print

これで21が表示される。1と2を足して3と4を足して掛ける、と日本語表現と相性が良いので日本語プログラミング言語のMindとかなでしこも見た目は日本語だが実体は連鎖性言語である。
さて、最近「なんか言語作ってみたいなあー」などとぼんやり思っていたのだが、難しいことはできそうにないので簡単に作れそうな連鎖性言語を作ってみよう。

字句解析

何が簡単かって、字句解析、構文解析がほとんど必要無いというあたり。空白で区切って順番に処理すればよい。作るのが簡単なぶん読み書きが辛くなるのはそういうもんだろう。

token = []
DATA.readlines.each do |t|
  token.concat t.split(" ")
end
p token
__END__
1 2 +
3 4 +
*
print

実行結果は["1", "2", "+", "3", "4", "+", "*", "print"]となる。

構文解析

全部文字列ではあとあと面倒なので、処理しやすいようにそれぞれ変換する。Forth系言語では数字や文字列はリテラル、それ以外はワードとして扱う。ワードは基本的には関数だが、特殊な処理をするためのものもある。
今回は数字と文字列(""でくくられたもの)と、ワードを区別して配列に格納することにする。リテラルはそのままRubyのオブジェクトへ変換、ワードはシンボルに変換して持っておこう。

class Parser
  def parse(token)
    ast = []
    token.each do |t|
      if t =~ /^\d+$/
        ast << t.to_i
      elsif t =~ /^".*"$/
        ast << t[1..-2]
      else
        ast << t.to_sym
      end
    end
    ast
  end
end

token = []
DATA.readlines.each do |t|
  token.concat t.split
end
p Parser.new.parse(token)
__END__
1 2 +
3 4 +
*
print

実行結果は[1, 2, :+, 3, 4, :+, :*, :print]。

VMを作る

VMと言っても難しいものではなくて、渡されたASTを前から順番に処理(リテラルはスタックに積む、ワードは実行)するだけ。ベタで書いてしまおう。

class Parser
  def parse(token)
    ast = []
    token.each do |t|
      if t =~ /^\d+$/
        ast << t.to_i
      elsif t =~ /^".*"$/
        ast << t[1..-2]
      else
        ast << t.to_sym
      end
    end
    ast
  end
end

token = []
DATA.readlines.each do |t|
  token.concat t.split
end
ast = Parser.new.parse(token)

class VM
  def run(ast)
    stack = []
    ast.each do |d|
      if Symbol === d
        case d
        when :+
          stack << (stack.pop + stack.pop)
        when :*
          stack << (stack.pop * stack.pop)
        when :print
          puts stack.pop
        end
      else
        stack << d
      end
    end
  end
end

VM.new.run(ast)

__END__
1 2 +
3 4 +
*
print

これで実行結果は21。できた。簡単すぎてこれだけでは面白く無い(手抜きすぎなだけだが)。
Forthでもワードを自分で定義できるし、Factorにはクオーテーションという関数オブジェクトもあるので、今後はそのへんを追加してみよう。条件分岐も繰り返しもできないのでそのへんも欲しい。