Rubyでレイトレーシングした - yhara.jp
上の画像はここの ray5.rb を実行したもの。なおこれは ppm 画像ファイルのデータを出力するコードであり、
$ ruby ray5.rb > rayimg.ppm
みたいに実行するとよい。ppm 形式については
http://ruby.kyoto-wu.ac.jp/~konami/Campus/IntroductionToGraphics.pdf
でお勉強しようかな。なお、上の画像は正確には ppm から png に変換してある。
まずは if文を実装しましょう。書き方はこんな感じ。
[:if, [:>, 3, 2], 1, 0]
まずは従来のメソッドを書き直します。（あとで :letrec も実装するので、それも書き加えています。）
def special_form?(exp) lambda?(exp) or let?(exp) or letrec?(exp) or if?(exp) end def eval_special_form(exp, env) if lambda?(exp) eval_lambda(exp, env) elsif let?(exp) eval_let(exp, env) elsif letrec?(exp) eval_letrec(exp, env) elsif if?(exp) eval_if(exp, env) end end
if文の実装です。「scheme の if文」の実装に「Ruby の if文」を使うわけですね。
def eval_if(exp, env) cond, true_clause, false_clause = if_to_cond_true_false(exp) if _eval(cond, env) _eval(true_clause, env) else _eval(false_clause, env) end end def if_to_cond_true_false(exp) [exp[1], exp[2], exp[3]] end def if?(exp) exp[0] == :if 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}], :>= => [:prim, lambda{|x, y| x >= y}], :< => [:prim, lambda{|x, y| x < y}], :<= => [:prim, lambda{|x, y| x <= y}], :== => [:prim, lambda{|x, y| x == y}], } $boolean_env = {:true => true, :false => false} $global_env = [$primitive_fun_env, $boolean_env]
以上で if文の実装は終了です。実行してみましょう。
puts _eval([:if, [:>, 3, 2], 1, 0], $global_env) #=>1 puts _eval([:if, [:<, 3, 2], 1, 0], $global_env) #=>0
OK ですね！
さて、if文を実装したので、:lambda で再帰が書けるでしょうか？ やってみましょう。
exp = [:let, [[:factorial, [:lambda, [:n], [:if, [:<, :n, 1], 1, [:*, :n, [:factorial, [:-, :n, 1]]]]]]], [:factorial, 4]] puts _eval(exp, $global_env) #=>`lookup_var': couldn't find value to variables:'factorial' (RuntimeError)
エラーになります。これは if文で偽となるときに :factorial を評価しますが、:let 文ではこの :factorial を環境に含むことができないために起きるエラーです。
解決策としては、:let文の代わりに使う :letrec文で、環境にパラメータの領域を確保しておき（中身は :dummy でよい）、（eval_list() で評価する際に）必要になった場合に参照して、set_extend_env!() で中身を書き換えるようにします。（ここのところはややこしいので、元の文書の説明を参考にして下さい。実行例。）:letrec の実装はこんな具合です。
def eval_letrec(exp, env) parameters, args, body = letrec_to_parameters_args_body(exp) ext_env = [parameters.map {|para| [para, :dummy]}.to_h] + env set_extend_env!(parameters, eval_list(args, ext_env), ext_env) new_exp = [[:lambda, parameters, body]] + args _eval(new_exp, ext_env) end def set_extend_env!(parameters, args_val, ext_env) parameters.zip(args_val).each do |parameter, arg_val| ext_env[0][parameter] = arg_val end end def letrec_to_parameters_args_body(exp) let_to_parameters_args_body(exp) end def letrec?(exp) exp[0] == :letrec end
これで確かめてみます。
exp = [:letrec, [[:factorial, [:lambda, [:n], [:if, [:<, :n, 1], 1, [:*, :n, [:factorial, [:-, :n, 1]]]]]]], [:factorial, 4]] puts _eval(exp, $global_env) #=>24
きちんと 4 の階乗が再帰で計算されました！
さて、以上でじつは純粋関数型言語の実装が完成しました。これには副作用をもつ「代入」というものがありません。:lambda, :let, :if, :letrec を実装することにより、クロージャをもった再帰プログラミングが可能です。
それ以外の機能は、おまけで付け加えていくことにしましょう。
ここまでの全コードです。
def _eval(exp, env) if not list?(exp) if immediate_val?(exp) exp else lookup_var(exp, env) end else if special_form?(exp) eval_special_form(exp, env) else fun = _eval(car(exp), env) args = eval_list(cdr(exp), env) apply(fun, args) end end end def list?(exp) exp.is_a?(Array) 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}], :> => [:prim, lambda{|x, y| x > y}], :>= => [: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 def car(list) list.first end def cdr(list) list.drop(1) end def eval_list(exp, env) exp.map{|e| _eval(e, env)} end def apply_primitive_fun(fun, args) fun_val = fun[1] fun_val.call(*args) end def lambda?(exp) exp[0] == :lambda end def apply(fun, args) if fun[0] == :func lambda_apply(fun, args) else apply_primitive_fun(fun, args) end end def special_form?(exp) lambda?(exp) or let?(exp) or if?(exp) or letrec?(exp) end def lambda_apply(obj, args) vals = obj[1].zip(args).to_h _eval(obj[2], [vals] + obj[3]) end def eval_lambda(exp, env) parameter, body = exp[1], exp[2] [:func, parameter, body, env] end def eval_special_form(exp, env) if lambda?(exp) eval_lambda(exp, env) elsif let?(exp) eval_let(exp, env) elsif if?(exp) eval_if(exp, env) elsif letrec?(exp) eval_letrec(exp, env) end end def lookup_var(exp, env) alist = env.find{|alist| alist.key?(exp)} if alist == nil raise "couldn't find value to variables:'#{exp}'" end alist[exp] end def eval_let(exp, env) parameters, args, body = let_to_parameters_args_body(exp) new_exp = [[:lambda, parameters, body]] + args _eval(new_exp, env) end def let_to_parameters_args_body(exp) [exp[1].map {|e| e[0]}, exp[1].map {|e| e[1]}, exp[2]] end def let?(exp) exp[0] == :let end def eval_if(exp, env) cond, true_clause, false_clause = if_to_cond_true_false(exp) if _eval(cond, env) _eval(true_clause, env) else _eval(false_clause, env) end end def if_to_cond_true_false(exp) [exp[1], exp[2], exp[3]] end def if?(exp) exp[0] == :if end def eval_letrec(exp, env) parameters, args, body = letrec_to_parameters_args_body(exp) ext_env = [parameters.map {|para| [para, :dummy]}.to_h] + env set_extend_env!(parameters, eval_list(args, ext_env), ext_env) new_exp = [[:lambda, parameters, body]] + args _eval(new_exp, ext_env) end def set_extend_env!(parameters, args_val, ext_env) parameters.zip(args_val).each do |parameter, arg_val| ext_env[0][parameter] = arg_val end end def letrec_to_parameters_args_body(exp) let_to_parameters_args_body(exp) end def letrec?(exp) exp[0] == :letrec end $boolean_env = {:true => true, :false => false} $global_env = [$primitive_fun_env, $boolean_env]
以前に Ruby の GUI で、ここの Ruby/Tk でやろうとしていることを Green Shoesでやろうとしてみた。
obelisk.hatenablog.com
でもそれは元記事の意図とはちがっていて、「ボタンを押した時に、多重入れ子構造で内側に配置したウィジェットから外側に定義したメソッドを呼びたい」のであるとコメントを頂いた。それができると、いろいろ捗るということなわけですね。
暇なので、Ruby/GTK+ でもう一度考えてみた。基本的な考え方としては、ボタンを押したときに呼ばれるブロックを、外へ持ち出せばよい。そのとき、ブロックを呼び出したいインスタンス・メソッドに紐づける。
gtk_sample2b.rb
require 'gtk2' class GUI < Gtk::Window Meth = [:wanwan, :nya] def initialize super("GUI") set_width_request(200) box = Gtk::VBox.new add(box) @button1 = Gtk::Button.new("イヌ") @button2 = Gtk::Button.new("ネコ") label1 = Gtk::Label.new("吾輩はイヌである") label2 = Gtk::Label.new("吾輩はネコである") [@button1, label1, @button2, label2].each do |widget| box.pack_start(widget, true, true, 5) end @meth = {} signal_connect("destroy") {Gtk.main_quit} end Meth.each do |name| define_method(name) {|&bk| @meth[name] = bk} end def mainloop [@button1, @button2].zip(Meth).each do |bt| bt[0].signal_connect("clicked", &@meth[bt[1]]) end show_all Gtk.main end end g = GUI.new g.wanwan do puts "わんわん" md = Gtk::MessageDialog.new(g, Gtk::Dialog::MODAL, Gtk::MessageDialog::INFO, Gtk::MessageDialog::BUTTONS_OK, "わんわん") md.signal_connect("response") {md.destroy} md.run end g.nya {puts "にゃー"} g.mainloop
こんなのでどうでしょうか。
わんわん にゃー わんわん わんわん にゃー
「イヌ」ボタンの方はこんなメッセージダイアログが出ます。
Gtk2 を使っているのは、既に枯れた技術だから。いまなら Gtk3 の方がよいのかも知れません。なお、以上は Linux でやっていますが、Gtk2 なら Windows でもふつうに動きます。Gtk3 はどうか知らない。
Ruby/GTK+ は面倒という人もいるようだが、上を見てもらえばそれほど面倒でないとわかると思う。
Ruby/GTK+ の日本語サイトもまだ更新されていて頼もしいです。
Ruby-GNOME2 Project Website - Ruby-GNOME2 Project Website
※追記（8/4）
ブロック内でメソッドを定義するバージョンも考えてみました。
Ruby/GTK+ でちょっと考えた · GitHub
:lambda にクロージャを実装する前に、let文を実装します。
[:let, [[:x, 3], [:y, 2]], [:+, :x, :y]]
は
[[:lambda, [:x, :y], [:+, :x, :y]], 3, 2]
と同等です。
実装。単純です。:lambda に変換しているだけです。
def eval_let(exp, env) parameters, args, body = let_to_parameters_args_body(exp) new_exp = [[:lambda, parameters, body]] + args _eval(new_exp, env) end def let_to_parameters_args_body(exp) [exp[1].map {|e| e[0]}, exp[1].map {|e| e[1]}, exp[2]] end def let?(exp) exp[0] == :let end
既存のメソッドも多少変更して let文に対応します。
def special_form?(exp) lambda?(exp) or let?(exp) end def eval_special_form(exp, env) if lambda?(exp) eval_lambda(exp, env) elsif let?(exp) eval_let(exp, env) end end
実際に使ってみます。
puts ([:let, [[:x, 3], [:y, 2]], [:+, :x, :y]], [$primitive_fun_env]) #=>5
OK です。
さて、クロージャというなら、以下の文が動かなくてはなりません。
[:let, [[:x, 2]], [:let, [[:fun, [:lambda, [], :x]]], [:let, [[:x, 1]], [:fun]]]]
そしてさらに、これが 2 を返さなければいけません。:let は:lambda を作るので lambda_apply() で「環境」を作ります。ただし、このままでは NoMethodError が出ます。:lambda の「パラメータ」が空リストになっているからです。
lookup_var() を以下のごとく変更します。こうすると :lambda の「パラメータ」がなくても :let で作った「環境」を参照することができます。
def lookup_var(exp, env) alist = env.find{|alist| alist.key?(exp)} raise "couldn't find value to variables:'#{exp}'" unless alist alist[exp] end
実際に確かめてみます。
exp = [:let, [[:x, 2]], [:let, [[:fun, [:lambda, [], :x]]], [:let, [[:x, 1]], [:fun]]]] puts _eval(exp, [$primitive_fun_env]) #=>2
確かに 2 が返ります。
さらなる例。
exp = [:let, [[:x, 3]], [:let, [[:fun, [:lambda, [:y], [:+, :x, :y]]]], [:+, [:fun, 1], [:fun, 2]]]] puts _eval(exp, [$primitive_fun_env]) #=>9
すばらしい！ 確かに「環境」が保持されています。これこそがクロージャです。
簡単な演算ができるようになったので、次に無名関数を実装してみます。
具体的には、
[[:lambda, [:x, :y], [:+, :x, :y]], 3, 2]
というような関数を評価することを考えます。これは Ruby でなら
lambda do |x, y| x + y end.call(3, 2)
みたいなものですね。
ここで一旦もとのテクストを離れます。元のテクストはここで let 文とクロージャを一気に実装しますが、まだそこまでやりません。
まず、_eval() をこう変えます。とりあえず引数 env に環境が入っていると思って下さい。
def _eval(exp, env) if not list?(exp) if immediate_val?(exp) exp else lookup_var(exp, env) end else if special_form?(exp) eval_special_form(exp, env) else fun = _eval(car(exp), env) args = eval_list(cdr(exp), env) apply(fun, args) end end end
:lambda 式を処理するメソッドです。
def special_form?(exp) lambda?(exp) end def lambda?(exp) exp[0] == :lambda end def eval_special_form(exp, env) parameter, body = exp[1], exp[2] [:func, parameter, body, env] end
eval_special_form() メソッドでいわば「関数オブジェクト」を作っています（[:func, parameter, body, env]）。「関数オブジェクト」には「環境 env」が組み込まれています。
この「関数オブジェクト」に「引数」を apply() します。
def apply(fun, args) if fun[0] == :func lambda_apply(fun, args) else apply_primitive_fun(fun, args) end end def lambda_apply(obj, args) vals = obj[1].zip(args).to_h obj[3].merge!(vals) _eval(obj[2], obj[3]) end def lookup_var(exp, env) env[exp] end
lambda_apply() で :lambda のパラメータを登録し、関数の本体を評価します。lookup_var() は引数に値を入れます。
これでほぼ終了です。eval_list() も引数を保持するようにしましょう。
def eval_list(exp, env) exp.map{|e| _eval(e, env)} end
実行してみます。ただし、最初の環境として $primitive_fun_env （組み込み関数）を与えて実行します。
puts _eval([[:lambda, [:x, :y], [:+, :x, :y]], 3, 2], $primitive_fun_env) #=>5 exp = [[:lambda, [:x], [:+, [[:lambda, [:y], :y], 2], :x]], 1] puts _eval(exp, $primitive_fun_env) #=>3
一見よいようです。
しかしよく似ていますが引数を同じにした
exp = [[:lambda, [:x], [:+, [[:lambda, [:x], :x], 2], :x]], 1] puts _eval(exp, $primitive_fun_env) #=>4
というのはうれしくありません。:lambda はスコープをもってほしいので、これは 3 になるべきです。
多少改変します。変数がスコープをもつようにしてみます。
def lambda_apply(obj, args) vals = obj[1].zip(args).to_h _eval(obj[2], [vals] + obj[3]) end def lookup_var(exp, env) env[0][exp] || env[-1][exp] end
試してみると、
exp = [[:lambda, [:x], [:+, [[:lambda, [:y], [[:lambda, [:x], :x], :y]], 2], :x]], 1] puts _eval(exp, [$primitive_fun_env]) #=>3
このように複雑な式でもちゃんと動きます（$primitive_fun_env が配列に入ったことに注意）。OK ですね！
ちなみにこれは :y をさらに :x にしても同じ結果を与えます。
しかし、これではまだ :lambda はクロージャではありません。
まず、「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
ここではリストは端的に「関数」です。テキストでは「λ式」と呼んでいます。
何となくやってみました。
$ pry [1] pry(main)> 5.times {|i| puts i} 0 1 2 3 4 => 5 [2] pry(main)> (1..5).each {|i| puts i} 1 2 3 4 5 => 1..5 [3] pry(main)> 1.upto(5) {|i| puts i} 1 2 3 4 5 => 1 [4] pry(main)> for i in 1..5 [4] pry(main)* puts i [4] pry(main)* end 1 2 3 4 5 => 1..5 [5] pry(main)> i = 1 => 1 [6] pry(main)> while i <= 5 [6] pry(main)* puts i [6] pry(main)* i += 1 [6] pry(main)* end 1 2 3 4 5 => nil [7] pry(main)> def count(i) [7] pry(main)* return if i > 5 [7] pry(main)* puts i [7] pry(main)* count(i + 1) [7] pry(main)* end => :count [8] pry(main)> count(1) 1 2 3 4 5 => nil [9] pry(main)> co = Enumerator.new do |y| [9] pry(main)* i = 1 [9] pry(main)* while i <= 5 [9] pry(main)* y << i [9] pry(main)* i += 1 [9] pry(main)* end [9] pry(main)* end => #<Enumerator: ...> [10] pry(main)> loop {puts co.next} 1 2 3 4 5 => nil [11] pry(main)> co = Enumerator.new do |y| [11] pry(main)* i = 1 [11] pry(main)* loop do [11] pry(main)* y << i [11] pry(main)* i += 1 [11] pry(main)* end [11] pry(main)* end => #<Enumerator: ...> [12] pry(main)> puts co.take(5) 1 2 3 4 5 => nil [13] pry(main)> puts 1.step.take(5) 1 2 3 4 5 => nil
ふーんという感じでしょうか。
