μSchemeR の Ruby による実装を読む(その1 - 簡単な演算)
言語処理系のお勉強をしようと思って調べてみたところ、上の文書を見つけました。Ruby で Scheme の一種を実装しようというものです。これから、自分なりのお勉強記録を残しておこうと思います。なお、自分はこの文書を購入しましたが、上のリンクから購入できるだけでなく、無料ダウンロードを行うことができます。どちらでも中身は変わりません。Scheme は Lisp 方言のひとつであり、μSchemeR は Ruby によるその簡易実装です。クロージャを実装しているところが特徴ではないでしょうか。以下、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
ここではリストは端的に「関数」です。テキストでは「λ式」と呼んでいます。