まずは 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
if文を使うための演算子と、論理値のリテラルを追加します。
$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)
puts _eval([:if, [:<, 3, 2], 1, 0], $global_env)
OK ですね！
さて、if文を実装したので、:lambda で再帰が書けるでしょうか？ やってみましょう。
exp = [:let,
[[:factorial,
[:lambda, [:n], [:if, [:<, :n, 1], 1, [:*, :n, [:factorial, [:-, :n, 1]]]]]]],
[:factorial, 4]]
puts _eval(exp, $global_env)
エラーになります。これは 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)
きちんと 4 の階乗が再帰で計算されました！
さて、以上でじつは純粋関数型言語の実装が完成しました。これには副作用をもつ「代入」というものがありません。:lambda, :let, :if, :letrec を実装することにより、クロージャをもった再帰プログラミングが可能です。
それ以外の機能は、おまけで付け加えていくことにしましょう。
obelisk.hatenablog.com
ここまでの全コードです。
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]
