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

連鎖性言語というのは英語でConcatenative Languageと言って、要するに連結、繋げて書く言語のことである。ま、左から右に繋がっているので。対比される言葉は適用型言語(Applicative Language)。CとかRuby、関数型言語など、だいたいほとんどの言語は適用型なんだそうだ。関数を呼ぶのにfunc(x)という書き方をするから関数呼び出しをネストすると右から左に読むことになる。
連鎖性言語のハシリであるForthという言語はかなり古くて、小さくシンプルでアセンブラで処理系を書いて組み込みで使うなどと言った使い方がされていたりする。一般のプログラマにはあまり縁が無いが、地味に色々なところに使われているらしいし、その影響力もデカい。どれぐらいデカいかと言うと、JavaのVMはスタックマシンだが、あれはForthを参考にして作ったものなんだそうだ。

さて、前回作ったのはForthと似たような感じの基本部分だけだったが、今回はちょっと趣向を変えて、FactorのQuotationみたいなものを作ってみよう。
そういえば書き忘れたが使っている言語はRuby。ってこのブログだから当たり前だよね〜、タグにRubyってあるからわかるよね〜。

Quotation

Factorは関数オブジェクトを扱えるForthみたいな言語で、Factorの関数オブジェクトをQuotationと呼ぶ。クオーテーション。これがあるせいでFactorは低レベルなForthっぽい見た目のくせに高級な関数型言語のような色々なことができるようになっている。
Quotationはこのような書き方をする。

[ 1 1 + ] call print

これで2が表示される。[と]はそれぞれ空白で区切って1文字として、これで囲まれた範囲はひとつの関数オブジェクトとしてスタックに積まれる。callというワードでスタックトップにある関数オブジェクトを実行する。Rubyで言うところのProcのようなもんだ。
興味深いのはスタックが共有されるところで、例えば

1 [ 1 + ] call print

としても2が表示されるし、

1 1 [ + ] call print

としても同じだ。下から上に見ていくと+関数に引数を部分適用していっているようにも見える。理屈で言えばまさにそれで、連鎖性言語というのはワードを並べたものが関数合成それそのものであり、関数型の考え方と親和性が高い。
実際のところFactorは連鎖性言語の顔をした関数型言語なんじゃないかと思っていて、サンプルとか見るとQuotationがビシバシ使われているし、その関連の組み込みワードもすごく多い。
ということでこれが面白そうだったのだな。

構文解析

字句解析については何も変わらないので省略。[と]も空白で区切って書くからひとつのトークンになるだけだ。

class Parser
  def parse(token)
    @i = 0
    @token = token
    self.parse_quotation
  end

  def parse_quotation
    ast = []
    while @i < @token.size
      t = @token[@i]
      if t =~ /^\d+$/
        ast << t.to_i
      elsif t =~ /^".*"$/
        ast << t[1..-2]
      elsif t == "["
        @i += 1
        ast << self.parse_quotation
      elsif t == "]"
        break
      else
        ast << t.to_sym
      end
      @i += 1
    end
    ast
  end
end

メソッドを2つにわけた。parse_quotationはQuotationを処理するメソッドという扱いである。プログラム全体をひとつのQuotationと考えたわけだな。parse_quotationの中で[と]を固定で見ていて、その中の処理はparse_quotationを再帰呼び出しして変換する。AST全体がRubyの配列に入るのと同様に、QuotationはRubyの配列で表現していて、ASTの中にArrayオブジェクトという形で格納される。トークン配列全体と処理中の位置は共有する必要があるのでインスタンス変数にした。
この実装からすると将来的にこの言語に配列を実装しようとしたら、それはきっとQuotationと同じものになるだろうし、プログラムで配列を生成してcallワードで実行するみたいなことができるようになるかもしれない。コードとデータが一体になってて楽しい。
ちなみにこの実装だとプログラムの途中にいきなり]が来ると終了してしまう。手抜き言語だからいいか。

VM

class VM
  def initialize
    @stack = []
  end

  def run(ast)
    ast.each do |d|
      if Symbol === d
        case d
        when :+
          @stack << (@stack.pop + @stack.pop)
        when :*
          @stack << (@stack.pop * @stack.pop)
        when :call
          self.run(@stack.pop)
        when :print
          puts @stack.pop
        end
      else
        @stack << d
      end
    end
  end
end

こちらもメソッドを分けた。というよりスタックをインスタンス変数化して、callワードで再帰呼び出しするようにした。callワードの動作はスタックトップのQuotationを取り出してから実行、である。
これで上のほうに書いた2を表示するコードがちゃんと動くようになるし、

[ [ 1 1 + ] ] call call print

なんて入れ子になったQuotationも動く。とは言え正直これだけでは何もできないので次はワードを定義できるようにしてみよう。ワード定義ができると一気に面白くなる。かもしれない。