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

現在のオレ言語の実装にはひとつ問題点がある。それは、数字のリテラルをRubyのオブジェクトに変換して保持し、計算はRubyのメソッドを呼んでいるところだ。それにより挙動がRubyの仕様に引きずられる。これは文字列についても同様であり、Rubyの文字列には+メソッドが存在しているので、例えば、

"a" "b" "c" + + print

とすると結果はcbaになる。スタックトップのオブジェクトの+メソッドを、トップから2番目のオブジェクトを引数にして呼び出しているから、だ。数字の足し算では順番は問題にならないから気づかないが。
これをどうするかを考えてみたのだが、とりあえずレシーバと引数を入れ替えて、あとはRubyにお願いしますでいいのかな、みたいな。+ワードは足し算をする機能ではなくて、スタックの2番目をレシーバにしてトップを引数に+メソッドを呼ぶ機能なのだ、と。独立した言語をRubyで作っているのではなくて、Rubyの上にかぶせる言語を作っているのだ、と。まあ、都合の良い解釈。
そうすると今度はRubyのメソッドと名前がぶつかるワードをどうしていくかというのが問題になるわけだが、それは後で。あんまり難しいことは考えていない。
では今回はワード定義を作る。つもり。

VMを修正する

VMでワードがハードコーディングされているので、後から追加できるようにこれをハッシュ化する。ついでにこの手の言語に必須の基本的なスタック操作ワードを追加して、unit-testも作っておこう。

class VM
  def initialize
    @stack = []
    @words = {
      :+ => ->{a=@stack.pop;b=@stack.pop;@stack << (b + a)},
      :* => ->{a=@stack.pop;b=@stack.pop;@stack << (b * a)},
      :call => ->{self.run(@stack.pop)},
      :print => ->{puts @stack.pop},
      :drop => ->{@stack.pop},
      :dup => ->{@stack << @stack[-1]},
      :over => ->{@stack << @stack[-2]},
      :swap => ->{@stack[-2], @stack[-1] = @stack[-1], @stack[-2]},
      :"unit-test" => ->{self.run(@stack.pop);r=@stack.shift;raise "#{@stack} is not #{r}" unless r == @stack;@stack=[]},
    }
  end

  def run(ast)
    ast.each do |d|
      if Symbol === d
        @words[d].call
      else
        @stack << d
      end
    end
  end
end

dropはスタックトップを捨てる、dupはスタックトップをコピーして積む、overはトップから2個目をコピーして積む、swapはトップと2番目の交換、である。さっそくdupがRubyとぶつかっているが、これはRubyのdupを呼ぶのではなく、単純に参照のコピーをトップに入れる。
unit-testはQuotationを2つ用意してから呼ぶ。トップのQuotationを実行した結果、スタックの状態が2番目のQuotationの中身と同じにならなければ例外が出る。この機能はFactorにあるのだが、Factorの場合はトップから2番目のQuotatinoはQuotationではなく配列になる。オレ言語には配列が無いのでQuotationで作った。なお、手抜きなのでunit-testはスタックが空の状態から実行することが前提になっていて、実行するとスタックが空になる。
今回の機能をテストする場合はこんな感じ。

[ "a" 3 ] [ "a" 1 2 + ] unit-test
[ "a" 2 ] [ "a" 1 2 * ] unit-test
[ "a" "abc" ] [ "a" "a" "b" "c" + + ] unit-test
[ "a" 2 ] [ "a" [ 1 [ 1 + ] ] call call ] unit-test
[ "a" 1 ] [ "a" 1 2 drop ] unit-test
[ "a" 1 1 ] [ "a" 1 dup ] unit-test
[ "a" 1 2 1 ] [ "a" 1 2 over ] unit-test
[ "a" 2 1 ] [ "a" 1 2 swap ] unit-test

頭に"a"を置いて余分にスタックが食われていないこともついでに確認している。

ワード定義

Forth系言語のワード定義は伝統的にコロン定義と呼ばれる方法で記述する。

: plus1 ( x -- y ) 1 + ;

()はスタックエフェクトと呼ばれるコメントである。何を入力して何を出力するのかを表現する。Factorの場合はスタックの状態のチェックやコンパイルのヒントに使われたりするらしい。ともあれ、コロンで始まり、ワード名、スタックエフェクト、ワードの中身、セミコロンと続く。Forthではコロンを発見すると実行解釈モードからコンパイルモードに切り替わり、後ろの中身を取り込んで、セミコロンを発見すると実行解釈モードに戻る、みたいな動作をするらしい。なんかめんどい。
もっとシンプルにできねーかな、と考えて、以下のような形式で表現することにした。

"plus1" [ 1 + ] define-word

ワード名の文字列、中身のQuotationをスタックに積んでdefine-wordを呼ぶと定義される。名前が文字列なのはそのままワード名を書くと実行しようとしてしまうからである。
このdefine-wordを作るのは簡単で、VMクラスの@wordsハッシュの設定に一行加えてやればいい。

      :"define-word" => ->{quot=@stack.pop;name=@stack.pop.to_sym;@words[name]=->{self.run(quot)}},

このようなコードが実行できるようになる。

"plus1" [ 1 + ] define-word
[ 2 ] [ 1 plus1 ] unit-test

コロン定義

とはいえForthチックな見た目をした言語であるからして、Forthチックにコロン定義をしたいところである。これを作るのはさほど難しくなく、既にdefine-wordを作ってあるので、Parserレベルでコロン定義文をdefine-word形式に変換するようなシンタックスシュガーを追加してやれば事足りる。

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 == "("
        begin
          @i += 1
        end while @token[@i] != ")"
        @i += 1
        t = @token[@i]
      end

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

ついでにスタックエフェクトも書けるように()によるコメントを追加しておいた。きわめて手抜き実装ではあるが。
ともあれこれでコロン定義が書けるようになった。

: plus1 ( x -- y ) 1 + ;
[ 2 ] [ 1 plus1 ] unit-test

うん、それっぽくなってきた。

あと

他にやってみたいのはloop系の構文だが、Forthでは低レベルな内部命令に分割したりするっぽく、Factorでは再帰呼び出しで繰り返しを実行する(たぶんGOTOに変換される？)っぽい。内部命令はめんどいし再帰は今の作りだといずれスタックオーバーフローするしで、とりあえずRubyで実装しちゃうぐらいしかまともな案が無い。ifも同様。
それ以外に、もっとたくさんのワードを定義してやらないとそもそも使い物にならず、さすがに大変なのでRubyの機能を呼び出せるようなインターフェイスが欲しい。欲を言えばRuby側から自然な形で呼べるようなインターフェイスもあると良い。最終的にはコンパイルして効率良いRubyのコードを出力するみたいなことができればRubyで書く代わりに使うこともできるだろう。メリットがあるかどうかはわからないが。