μSchemeR の Ruby による実装を読む（その2 - 無名関数）

簡単な演算ができるようになったので、次に無名関数を実装してみます。

具体的には、

[[: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 はクロージャではありません。

obelisk.hatenablog.com
obelisk.hatenablog.com