おまけ: Scheme on YARV

これで今日のYARV勉強会はおしまいです。

って、これではやけに短くなってしまったので、おまけとして、るびま で触れられていた

本当は、今回何か簡単な言語のコンパイラを作ろうと思っていたのですが、間に合いませんでした。誰か Scheme あたりで挑戦してみませんか。かなり簡単だと思いますよ。

これをやってみようと思います。

yasm.rb

記事で紹介されているyasmモジュールがRubyのtrunkに見つからなかったので、旧YARVのレポジトリ

• http://www.atdot.net/svn/yarv/trunk/lib/yasm.rb

から拾ってきて適当に修正して使っています。変えたのは、YARVの仮想マシンオブジェクトを表すクラス名と

- module YARVCore
+ class VM

- YARVCore::
+ VM::

メソッド名としてSymbolを渡すと怒られるみたいだったのでStringにしたところと

      def initialize type, name, filename, args, vars, lopt, parent
        @type = type
-       @name = name
+       @name = name.to_s
        @filename = filename

関数形式のメソッド呼び出しを表すフラグが1<<2から1<<3になっているようなのでその反映

      def call id, argc, block = nil
-       @body << [:send, id, argc, block, 0x04, nil]
+       @body << [:send, id, argc, block, 0x08, nil]
      end

の３カ所です。

目標

SchemeというかLispっぽいコードを文字列で渡したら、それを評価して結果を返すメソッドを作るのを目標とします。もちろん中ではインタープリター形式ではなくて、YARVのマシン語にコンパイルして実行しますよ。

p scheme("(+ (* 2 3) 4)")   # ==> 10

こういう風に動けばいいな、と。
さて、ちゃんとしたものを作るのは大変そうなので、ちゃんとしてないものを作りましょう。えい。

require 'yasm'

def scheme(text)
  # とっても手抜きなS式パーザ
  # "(+ (* 2 3) 4)"  ==>  [:+, [:*, 2, 3], 4]
  s = eval text.gsub( /(\()|(\))|(\d+)|([^()\s]+)/ ) {
    case
      when $1 then "["
      when $2 then $'[/\S/] ? "]," : "]"
      when $3 then "#$3,"
      else         ":#$4,"
    end
  }

  # コンパイル
  iseq = YASM.toplevel {
    scm_compile s
    leave
  }

  # 実行
  iseq.eval
end

まずSchemeのプログラムをとても適当に構文解析（？）して、再帰的な配列とSymbolの形に変換します。それを、scm_compileメソッドに渡してYARVのマシン語にコンパイル。で、実行。scm_compile関数はこれから書きます。

scm_compile : 四則演算

面倒なのでYASM::SimpleDataBuilderのメソッドにしちゃいました。とりあえず数字と四則演算だけの場合を考えよう。

class YASM::SimpleDataBuilder
  def scm_compile(s)
    case s
      when Array
        op,*arg = s
        case op
          when :+
            scm_compile arg[0]
            arg[1..-1].each{|a| scm_compile a; send :+,1}
          when :-
            scm_compile arg[0]
            arg[1..-1].each{|a| scm_compile a; send :-,1}
          when :*
            scm_compile arg[0]
            arg[1..-1].each{|a| scm_compile a; send :*,1}
          when :/
            scm_compile arg[0]
            arg[1..-1].each{|a| scm_compile a; send :/,1}
        end
      else
        putobject s
    end
  end
end

sが配列の場合は、たとえば (+ 1 2 3 4) みたいなS式なので、

putobject 1
putobject 2
send :+, 1
putobject 3
send :+, 1
putobject 4
send :+, 1

という命令列にコンパイルしたいのです、というコードになっています。sが配列でない場合は、ただの数値と仮定してしまって、そのままputobjectしています。ええと、これだけで

p scheme("(+ (* 2 3) 4)")   # ==> 10

これは動くようになってしまいました。簡単だ！

scm_compile : 関数定義

次は、関数を定義できるようにしてみます。こんな構文で

(define (norm x y)
   (+ (* x x) (* y y)))

normという名前の関数を定義します。ここまでの勉強会で読んだ内容を思い返してみると、YARVで新しく関数（メソッド）を定義するには、命令列オブジェクトを作成してから、それを引数にdefinemethod命令を実行すればいいのでした。そんな風にコンパイルします。

          when :define
            mname, *mparam = arg[0]
            putnil
            definemethod mname, YASM.method(mname, mparam) {
              scm_compile arg[1]
              leave
            }
            putnil

一個目のputnilは、トップレベルオブジェクトのメソッドとして定義する指定です。二個目のputnilは、とりあえずdefineの式の値はnilとするということにして、nilをスタックに置いているものです。
あと、式の中で引数を参照できるようにしないといけません。S式がシンボルだった場合は、その名前のローカル変数を参照するということにします。

    case s
      when Array
        ...
      when Symbol
        getlocal s
      else
        ...
    end

これで関数定義ができました。Rubyからも簡単に呼び出せます。

scheme <<EOS
  (define (norm x y)
     (+ (* x x) (* y y)))
EOS

p norm(3,4)  # ==> 25

scm_compile : 関数呼び出し

って、まだ、Schemeの中から関数を呼び出せるようになってませんでした。さて。

          when :+
            ...
          when :-
            ...
          when :*
            ...
          when :/
            ...
          when :define
            ...
          else
            putnil
            arg.each{|a| scm_compile a}
            call op, arg.size

配列の先頭要素が特別な値でなかったら、全部その名前の関数呼び出しと見なすことにします。今回はselfはnilで、引数を全部スタックにおいて、yasmのシンタックスシュガーであるcall疑似命令で関数を呼び出します。

p scheme("(/ (norm 5 12) 13)")  # ==> 13

できました。

def cube(x)
  x * x * x
end

p scheme("(cube 11)")   # ==> 1331

Rubyの関数をSchemeから呼び出したりもできました。

scm_compile: 条件分岐

(if 条件 then部 else部)

条件分岐がないとプログラミング言語っぽくないですよね。というわけでif文やってみました。Rubyのif文をコンパイルするのと何もかわりません。

          when :if
            scm_compile arg[0]
            branchunless :else_part
            scm_compile arg[1]
            jump :end
          _ :else_part
            scm_compile arg[2]
          _ :end

これだけです。これだけだと四則演算しかないので条件判定とかができませんので、比較演算も足しておきます。

          when :==
            scm_compile arg[0]; scm_compile arg[1]; send :==, 1
          when :<
            scm_compile arg[0]; scm_compile arg[1]; send :<, 1
          when :>
            scm_compile arg[0]; scm_compile arg[1]; send :>, 1
          when :<=
            scm_compile arg[0]; scm_compile arg[1]; send :<=, 1
          when :>=
            scm_compile arg[0]; scm_compile arg[1]; send :>=, 1

こんな感じで。これで、

scheme <<EOS
  (define (fib x)
     (if (<= x 1)
         1
         (+ (fib (- x 2)) (fib (- x 1)))))
EOS

p scheme("(fib 10)")    # ==> 89

フィボナッチできました。

scheme <<EOS
  (define (facs x)
     (if (== x 0) 1 (* x (facr (- x 1)))))
EOS
def facr(x)
  if x == 0 then 1 else x * facs(x-1) end
end

p facs(10), facr(10)   # 3628800 \n 3628800

RubyとSchemeで相互再帰する階乗計算！

scm_compile: 速度比較

あまりにもサクサクできてしまったので、ほんとにちゃんとコンパイルされているか心配になってきました。Rubyで書いたものと比較ベンチマークしてみましょう。

def fibr(x)
  if x <= 1
    1
  else
    fibr(x-2) + fibr(x-1)
  end
end

require 'benchmark'
3.times {
  print "Scheme:", Benchmark.measure { fib(36)  }
  print "Ruby:  ", Benchmark.measure { fibr(36) }
}

とりゃ。

Scheme:  8.942000   0.000000   8.942000 (  8.973000)
Ruby:    8.853000   0.000000   8.853000 (  8.863000)
Scheme:  8.863000   0.000000   8.863000 (  8.863000)
Ruby:    8.873000   0.000000   8.873000 (  8.872000)
Scheme:  8.852000   0.000000   8.852000 (  8.853000)
Ruby:    8.863000   0.000000   8.863000 (  8.863000)

Rubyネイティブのものとほぼ同じパフォーマンスが出ていることがわかります。