Rubyで学ぶRuby 第8回

関数を実装する（後編）

こんにちは。 機能限定版のRubyインタプリタ（MinRubyインタプリタ）を作りながらRubyとプログラミングを学ぶ連載、今回は前回に引き続き「関数」の実装です。

前回は、関数のうち、MinRubyインタプリタに最初から機能として用意しておく「組み込み関数」を実装しました。 最初に関数名のための環境を作り、そこにpなどの基本的な関数の定義を組み込んで、それをMinRubyプログラムから呼び出せるようにしました。

現状のMinRubyインタプリタは次のようになっています。

require "minruby"
def evaluate(tree, genv, lenv)
  case tree[0]
  when "lit"
    tree[1]
  when "+"
    evaluate(tree[1], genv, lenv) + evaluate(tree[2], genv, lenv)
  when "-"
    evaluate(tree[1], genv, lenv) - evaluate(tree[2], genv, lenv)
  when "*"
    evaluate(tree[1], genv, lenv) * evaluate(tree[2], genv, lenv)
  when "/"
    evaluate(tree[1], genv, lenv) / evaluate(tree[2], genv, lenv)
  when "stmts"
    i = 1
    last = nil
    while tree[i]
      last = evaluate(tree[i], genv, lenv)
      i = i + 1
    end
    last
  when "var_assign"
    lenv[tree[1]] = evaluate(tree[2], genv, lenv)
  when "var_ref"
    lenv[tree[1]]
  when "if"
    if evaluate(tree[1], genv, lenv)
      evaluate(tree[2], genv, lenv)
    else
      evaluate(tree[3], genv, lenv)
    end
  when "while"
    while evaluate(tree[1], genv, lenv)
      evaluate(tree[2], genv, lenv)
    end
  when "func_call"
    args = []
    i = 0
    while tree[i + 2]
      args[i] = evaluate(tree[i + 2], genv, lenv)
      i = i + 1
    end
    mhd = genv[tree[1]]
    if mhd[0] == "builtin"
      minruby_call(mhd[1], args)
    else
      # 埋める（次回）
    end
  end
end
# ① プログラムの文字列を読み込む
str = minruby_load()
# ② プログラムの文字列を抽象構文木に変換する
tree = minruby_parse(str)
# ③ 抽象構文木を実行（計算）する
genv = { "p" => ["builtin", "p"] }
lenv = {}
evaluate(tree, genv, lenv)

今回は、まずMinRubyプログラムの中で関数を定義できるようにし、 それから上記の「# 埋める（次回）」となっている部分を埋めることで、その関数を同じプログラムで実行できるようにします。 インタプリタを開発する人だけでなく、インタプリタを使う側の人が関数を定義できるようにしようというわけです。

インタプリタを使う側の人が定義する関数のことを、「ユーザ定義関数」といいます。 難しそうに聞こえるかもしれませんが、ようするに、これまでdef文を使って定義してきた関数が「ユーザ定義関数」です。 したがって今回の課題は、MinRubyインタプリタにdef文を実装することだといえます。

def文を使った関数の定義をサポートするためには、 def文の抽象構文木に対応する処理をevaluateに追加しなければなりません。 具体的には、関数名の環境genvに新しく関数を登録する必要があります。

それから、そのようにして定義された関数をプログラムの中で使えるようにする必要があります。 これには、環境genvから、関数の定義を呼び出してこなければなりません。

関数名の環境genvから関数の定義を呼び出す部分は、組み込み関数のときと同じでいいように思えるかもしれません。 しかし、実は「引数」の扱いに、組み込み関数のときにはなかった注意が必要です。 その注意を理解するために、まずは「引数」の区別について話をしておきましょう。

仮引数と実引数

プログラミング言語で関数の引数について考えるときには、仮引数と実引数という区別をします。

仮引数というのは、関数定義に出てくる引数のことです。 つまり、def add(x, y)のxやyです。

一方、実引数というのは、関数呼び出し側で引数の場所に書くものを指します。 つまり、add(10, 30 + 2)の10や30 + 2のことです （この例のように、実引数は値のこともあれば、評価前の式のこともあります）。

このように区別はしますが、引数というものが2種類あるわけではありません。 「呼び出される側」の呼び方が仮引数、「呼び出す側」の呼び方が実引数というだけの違いです。

ただし、いまのようにインタプリタを実装しているときは、 仮引数と実引数を区別しておかないとユーザ定義関数の実装で混乱してしまいます。 「呼び出される側」と「呼び出す側」のどちらの立場で引数について考えているのかを区別するために、 それぞれ言葉だけ覚えておいてください。

関数定義を実装する

それでは実装に入りましょう。 まずは関数定義、つまりdef文を実装していきます。

いつものように、まずは抽象構文木を見てみます （抽象構文木とその確認方法は第4回の記事を参照してください）。 例として下記のような関数定義を考えましょう。

def add(x, y)
  x + y
end

このdef文の抽象構文木は次のようになっています。

["func_def",
  "add",
  ["x", "y"],
  ["+", ["var_ref", "x"], ["var_ref", "y"]]]

絵にするとこうです。

これを見る限り、抽象構文木そのものはそれほど複雑ではありませんね。 ["func_def", 関数名, 仮引数名の配列, 関数本体]という構造になっていることが見て取れると思います。

問題は、この抽象構文木をevaluateでどのように扱うかです。 MinRubyインタプリタの利用者がdef文でやりたいことは新しい関数の定義なので、 この抽象構文木の「関数名」に対応するエントリを環境genvに追加する必要があります。

def evaluate(tree, genv, lenv)
  case tree[0]
  when "func_def"
    genv[tree[1]] = ["user_defined", tree[2], tree[3]]
  ...(略)...
  end
end

抽象構文木treeは、先ほど確認したように["func_def", 関数名, 仮引数名の配列, 関数本体]です。 したがって、ここでハッシュgenvに追加しているのは次のような対応です。

関数名 => ["user_defined", 仮引数名の配列, 関数本体]

あとでMinRubyプログラムの中でこの関数名が使われたときに、組み込み関数ではなくユーザ定義関数として扱いたいので、 組み込み関数の関数定義を表す"builtin"と区別するためのラベルとして"user_defined"という文字列を使うことにしました。

関数定義そのものは、このラベル"user_defined"に続けて「仮引数名の配列」と「関数本体」を並べるだけでおしまいです。 新しい関数を定義しても、その場で関数の中身が実行されるわけではありませんよね。 関数定義というのは、あくまでも「関数の定義」であり、「この関数はこういうことをするものとして覚えておけ」とインタプリタに命令するだけです。 そのため、このように素直に関数定義を覚えておくだけで十分なのです。

ユーザ定義関数の呼び出し

次は、ユーザ定義関数を関数名の環境から呼び出して実行する部分を実装します。 現状のMinRubyインタプリタはこんなふうになっているはずです。

def evaluate(tree, genv, lenv)
  case tree[0]
  when "func_def"
    genv[tree[1]] = ["user_defined", tree[2], tree[3]]
  when "func_call"
    args = []
    i = 0
    while tree[i + 2]
      args[i] = evaluate(tree[i + 2], genv, lenv)
      i = i + 1
    end
    mhd = genv[tree[1]]
    if mhd[0] == "builtin"
      minruby_call(mhd[1], args)
    else
      # 埋める（ユーザ定義関数の呼び出しの実装）
    end
  ...(略)...
  end
end

MinRubyプログラムの中で関数が呼び出されていて、しかもそれがユーザ定義関数だったら、 mhdには["user_defined", 仮引数名の配列, 関数本体]という配列が入っています （そういう配列がgenvに登録されるように、前節で"func_def"の場合の処理を実装したのでしたね）。

いまやりたいのは、この配列の最後の要素である「関数本体」を評価することです。 ここで、「関数本体」のようすを思い出しておきましょう。 関数定義が次のような内容だったら、

def add(x, y)
  x + y
end

抽象構文木は次のようになっています。

["func_def",
  "add",
  ["x", "y"],
  ["+", ["var_ref", "x"], ["var_ref", "y"]]]

この木の最後の葉が「関数本体」でした。

["+", ["var_ref", "x"], ["var_ref", "y"]]

いまは、このような関数本体を、MinRubyプログラムで関数が呼び出されるときに指定されていた引数、 つまり実引数を使って評価したいわけです。

実引数は、前回組み込み関数を実装したときに、whileを使って配列argsに集めるようにしてあります。 実引数は、関数本体のどこで使えばいいでしょうか？ いうまでもありませんね。 関数を定義したときに使った引数、つまり仮引数が出てくる箇所で、対応する実引数が使われるようにする必要があります。

言い換えると、いまやるべきことは「仮引数のそれぞれに、対応する実引数を覚えさせた状態で、関数本体を評価する」です。 何かを覚えさせるということは、変数の出番です。 現在、仮引数名の配列はmhd[1]に、実引数の配列はargsに入っているので、 それぞれの対応を順番に変数の環境lenvへと入れていきます。

  params = mhd[1]
  i = 0
  while params[i]
    lenv[params[i]] = args[i]
    i = i + 1
  end

この状態で関数本体を評価すれば、仮引数の箇所で実引数が使われます。 関数本体はmhd[2]に入っているので、次のようにすればいいでしょう。

  evaluate(mhd[2], genv, lenv)

これでようやく、ユーザ定義関数のできあがりです。まとめて書くと以下のようになります。

def evaluate(tree, genv, lenv)
  case tree[0]
  when "func_call"
    args = []
    i = 0
    while tree[2][i]
      args[i] = evaluate(tree[2][i], genv, lenv)
      i = i + 1
    end
    mhd = genv[tree[1]]
    if mhd[0] == "builtin"
      minruby_call(mhd[1], args)
    else
      params = mhd[1]
      i = 0
      while params[i]
        lenv[params[i]] = args[i]
        i = i + 1
      end
      evaluate(mhd[2], genv, lenv)
    end
  ...(略)...
  end
end

さっそく動作確認してみましょう。次のようなプログラムを用意してください。

def add(x, y)
  x + y
end
p(add(1, 1))

これをprogram1.rbのような名前でファイルに保存し、おそるおそる完成したMinRubyインタプリタで実行してみてください。

C:¥Ruby > ruby interp.rb program1.rb ⏎
2
C:¥Ruby >

こんなふうに2が出たら成功です！

変数のスコープ

実は、現状のMinRubyにおける関数の実装は、本物のRubyの関数とは少し意味が違っています。

少しややこしいのですが、変数は関数ごとに定義されます。 例えば次のRubyプログラムでは、xという名前の変数が関数fooの定義の中と外でそれぞれ使われていますが、これらは本物のRubyでは別々の変数です。

def foo()
  x = 0
  p(x)
end
x = 1
foo() #=> 0
p(x)  #=> 1

プログラムとしては、まず関数fooを定義し、その外側にあるxに1を代入して、それから関数fooを呼び出します。 呼び出された関数fooでは、xに0が代入され、直後にそれを出力します。

本物のRubyでは、0を代入する「foo内のx」と、「foo外のx」とが、まったくの別変数です。 したがって、最初に1を代入した「foo外のx」には、foo内でxに0を代入しても影響がありません。 関数fooの呼び出しから帰ってきた後で出力されるのは、「foo外のx」です。 これは最初に代入した通り、1となります。

一方、現状のMinRubyインタプリタで上記と同じプログラムを実行すると、0が2回出力されてしまうことでしょう（ぜひ確かめてみてください）。

原因は、関数fooの中の代入x = 0で、関数の外側の変数xが書き換えられてしまっていることです。 MinRubyインタプリタでは、今のところ、関数の中のxと外のxが同じ変数として扱われてしまっているのです。 変数が参照できる範囲のことを変数のスコープといいますが、現状のMinRubyでは変数のスコープが関数定義の中で閉じていないのです。

ではどうすればよいかというと、関数の中で新たに変数名のための環境を用意します。 関数定義の中と外で変数のための環境を変えればいいというわけです。

def evaluate(tree)
  case tree[0]
  when "func_call"
    args = []
    i = 0
    while tree[2][i]
      args[i] = evaluate(tree[2][i], genv, lenv)
      i = i + 1
    end
    mhd = genv[tree[1]]
    if mhd[0] == "builtin"
      minruby_call(mhd[1], args)
    else
      new_lenv = {}                     # 挿入
      params = mhd[1]
      i = 0
      while params[i]
        new_lenv[params[i]] = args[i]   # lenv を new_lenv に変更
        i = i + 1
      end
      evaluate(mhd[2], genv, new_lenv)  # lenv を new_lenv に変更
    end
  ...(略)...
  end
end

今までの実装では、関数呼び出しの文脈における変数の環境lenvを、そのままevaluateに渡していました。 これを上記では変更して、new_lenvという新しい環境を作ってから、それに仮引数をセットした上でevaluateに渡すようにしています。

こうすることで、関数の外の環境はlenv、関数の中の環境はnew_lenvというように環境を分けることができます。 変数のスコープを区別することは、インタプリタの実装の観点から言えば、関数を呼び出すたびに新しい環境を作って渡すという意味にほかなりません。

なお、関数名の環境はどの関数の中でも共通です。 MinRubyの実装では関数名の環境をgenvと名づけましたが、先頭のgはglobal（大域的）のg（つまりどこでも共通）を表しています。 一方、変数名の環境lenvの先頭のlは、local（局所的）のl（つまり関数という局所ごとで異なる）を表しています。

まとめ

ついに関数の定義と呼び出しをひととおり実装できました。

本連載の最終目標は、自分で作ったMinRubyインタプリタを使って、自分で作ったMinRubyインタプリタを動かすこと（ブートストラップ）です。 そのためには、MinRubyインタプリタで使っている言語機能をすべて実装する必要があります。 まだ未実装なのは、残すところ配列とハッシュだけです。 次回はこれらを実装し、ブートストラップまでやる予定です。ということで、次回、最終回。こうご期待。

練習問題

1. フィボナッチ関数

次の数列を見てください。

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

これは、最初の2つが0と1で、それ以降は「直前2つの値の和」になっています（例えば2は直前2つの1と1の和、3は1と2の和、5は2と3の和）。これをフィボナッチ数列といいます。

フィボナッチ数列のx番目を計算する次のような定義の関数を「フィボナッチ関数」といいます。

def fib(x)
  if x <= 1
    x
  else
    fib(x - 1) + fib(x - 2)
  end
end

MinRubyインタプリタでフィボナッチ関数を動かしてみてください。

フィボナッチ関数は、プログラミング言語処理系の実装のテストおよびベンチマークプログラムとして有名です。また、プログラミング言語の入門書においても再帰呼び出しの典型的な例題です。

ヒント：第4回の練習問題1で出てきた比較式の実装が必要です。

2. 相互再帰

ある関数と別の関数がお互いを呼び出し合うことを、相互再帰といいます。 たとえば、次の関数even?とodd?は相互再帰しています。

def even?(n)
  if n == 0
    true
  else
    odd?(n - 1)
  end
end
def odd?(n)
  if n == 0
    false
  else
    even?(n - 1)
  end
end

MinRubyインタプリタでeven?(2)やeven?(3)の結果を見てみてください。 そして、これらの関数がどのように動いているかを考えてみてください。

even?とodd?は、関数名の最後に?がついていますが、 この?は何か特殊な言語機能というわけではありません。 実は、Rubyの関数名は?や!で終わることができます。 したがって、even?やodd?は、それ全体で単なるふつうの関数名です。

Rubyでは、真偽を判定する関数には、?で終わる名前を付ける慣習があります。 ここでもその慣習にならって、「偶数か否か」を判定する関数にはeven?、 「奇数か否か」を判定する関数にはodd?という名前を付けました。

なお、何かしらの注意が必要な関数（たとえば、何かを破壊的に書き換える関数）には !を付けるという慣習があります。

第7回の練習問題の答え

1. 組み込み関数raiseの追加

genvにraiseのエントリを追加するだけです。

genv = {
  "p" => ["builtin", "p"],
  "raise" => ["builtin", "raise"],
}

2. 独自の組み込み関数の追加

(略)