μSchemeR の Ruby による実装を読む(その1 - 簡単な演算)

言語処理系のお勉強をしようと思って調べてみたところ、上の文書を見つけました。RubyScheme の一種を実装しようというものです。これから、自分なりのお勉強記録を残しておこうと思います。なお、自分はこの文書を購入しましたが、上のリンクから購入できるだけでなく、無料ダウンロードを行うことができます。どちらでも中身は変わりません。SchemeLisp 方言のひとつであり、μSchemeRRuby によるその簡易実装です。クロージャを実装しているところが特徴ではないでしょうか。以下、Scheme については特に解説しません。


まず、「1 + 2」の計算をするのに、

[:+, 1, 2]

という「式」を書く言語を考えます。「(1 + 2) * 4」だったら

[:*, [:+, 1, 2], 4]

となります。これを「評価」するメソッドを、Ruby でこう書いてみます。

def _eval(exp)
  if not list?(exp)
    if immediate_val?(exp)
      exp
    else
      lookup_primitive_fun(exp)
    end
  else
    fun = _eval(car(exp))
    args = eval_list(cdr(exp))
    apply(fun, args)
  end
end

式 exp を評価する _eval() で、式がリストでなければ即値かどうかを調べます。即値なら自身を返し、でなければ組み込み関数として lookup_primitive_fun() で処理します。式がリストならば、「関数」として apply() で処理します。リストの先頭が「関数名」、のこりが「引数」ということになります。_eval() の実行に必要なメソッドは以下です。

def list?(exp)
  exp.is_a?(Array)
end

def lookup_primitive_fun(exp)
  $primitive_fun_env[exp]
end

$primitive_fun_env = {
  :+ => [:prim, lambda{|x, y| x + y}],
  :- => [:prim, lambda{|x, y| x - y}],
  :* => [:prim, lambda{|x, y| x * y}],
  :/ => [:prim, lambda{|x, y| x / y}],
}

def immediate_val?(exp)
  num?(exp)
end

def num?(exp)
  exp.is_a?(Numeric)
end

car(), cdr() は Lisp ではおなじみですね。それぞれリストの先頭要素、それ以降のリストを与えるメソッドです。

def car(list)
  list.first
end

def cdr(list)
  list.drop(1)
end

引数の評価は以下です。リストの各要素が評価されて、評価されたところのリストが返ります。

def eval_list(exp)
  exp.map{|e| _eval(e)}
end

関数の適用です。

def apply(fun, args)
  apply_primitive_fun(fun, args)
end

def apply_primitive_fun(fun, args)
  fun_val = fun[1]
  fun_val.call(*args)
end

fun の内容が [:prim, lambda{|x, y| x + y}]、args の内容が [1, 2] だとすれば、lambda{|x, y| x + y}.call(1, 2) が実行されることになります。


以上でとりあえず動きます。

puts _eval([:*, [:+, 1, 2], 4])   #=>12

「(1 + 2) * 4」が「12」と実行されました。

いろいろやってみましょう。

puts _eval([:/, [:*, [:-, 7, 2], 4], 5])    #=>4

 
ここではリストは端的に「関数」です。テキストでは「λ式」と呼んでいます。


obelisk.hatenablog.com