μSchemeR の Ruby による実装を読む（その4 - 再帰、純粋関数型言語の完成）

まずは 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)    #=>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 を実装することにより、クロージャをもった再帰プログラミングが可能です。

それ以外の機能は、おまけで付け加えていくことにしましょう。

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]