関数を実装する（前編）

2016年12月07日 12時00分更新

文● 遠藤侑介、イラスト●hirekoke、編集●鹿野桂一郎

こんにちは。 RubyでRubyを実装していく連載もいよいよクライマックスが近づいてきました。

前回までに完成したのは、四則演算ができて、変数を扱えて、分岐やループがあるプログラムを書けるインタプリタです。前回は、そのインタプリタを使って、それなりにプログラムらしいプログラム、たとえばFizzBuzzのようなプログラムを書いて実行する段階までこぎつけました。ここまでくれば、どんなプログラムだって書けそうに思えるかもしれません。

しかし、現状のインタプリタで現実的に書けるプログラムは、実はFizzBuzzくらいが限界です。さらに複雑なプログラム、それこそインタプリタのようなプログラムを書くには、まだまだ足りない機能がたくさんあります。

そのような機能のうち、それなりに複雑なプログラムを書くときに特に必須になるのは「関数」です。関数がないと、この連載ではすっかりお馴染みの「木をたどるプログラム」すら簡単には書けませんでしたね。

そこで次はMinRubyインタプリタに関数を実装していきましょう。この連載でいちばんの難所になると思うので、ちょっと気合を入れて読んでください。記事としても長くなるので、前編と後編の2回に分けてお届けします。

今回と次回で関数の実装を終えてしまえば、これまで出てきた「Rubyの機能」がだいたい実装できたことになります（残るはハッシュと配列くらいです）。つまり、連載の目標としてきたMinRubyインタプリタの完成までもう一息です。さらにいうと、本物のRubyインタプリタの代わりにMinRubyインタプリタ自体を使ってMinRubyインタプリタを実行する、そんな不思議な世界までもう一歩です！

ユーザ定義関数と組み込み関数

ひとくちに関数と言っても、実は2種類あります。 1つは、defから始まる文を使って自分で定義する関数です。これは「ユーザ定義関数」と呼ばれます。連載の第3回で学んだのは、このユーザ定義関数です。

もう1つは、インタプリタに最初から用意されている「組み込み関数」です。組み込み関数も、実は初めて見るものではありません。第1回から何度となく使ってきたpは、本物のRubyに最初から用意されている組み込み関数のひとつです。

pは、Rubyに最初から定義されている点を除けば、他の関数となんら変わるところがないただの関数です。過去の記事では、説明をぼかして「命令」のような呼び方をしていたこともありますが、関数と違う何か特別なものというわけではありません。

インタプリタに実装するという観点では、関数を定義する部分と使う部分の両方を実装しないといけないユーザ定義関数のほうが少しだけ説明する内容が多いので、まずは組み込み関数のほうから実装していきます。

関数名の環境

連載の第3回でユーザ定義関数を学んだときは、定義する関数に名前をつけて、その名前をプログラムの中で使いました。組み込み関数にも、たとえばpのような名前がついていて、使うときにはその名前で呼び出します。ということは、インタプリタには、関数の名前を定義されている中身と一緒に覚えておく仕組みが必要だということです。

インタプリタで名前と中身の対応を覚えておく仕組みといったら、第5回に出てきた環境です。変数についての環境は、変数名と値とを対応付けるハッシュでした。同じように、関数名の環境は、関数名と関数定義を対応付けるハッシュです。

第5回では、MinRubyインタプリタに変数を実装するため、evaluateの引数にenvという名前をつけた環境を追加しました。関数名を管理する環境もevaluateの引数に追加すればいいのですが、変数名の環境と区別できなければなりません。関数名の環境にはgenvという別の名前をつけ、変数名の環境もenvからlenvという名前に改名しておきましょう。

def evaluate(tree, genv, lenv)
  case tree[0]
  ...(略)...
  when "+"
    evaluate(tree[1], genv, lenv) + evaluate(tree[2], genv, lenv)
  when "-"
    evaluate(tree[1], genv, lenv) - evaluate(tree[2], genv, lenv)
  ...(略)...
  end
end

上記では一部だけを示していますが、evaluateのなかでevaluateを再帰的に呼んでいる箇所をすべて変更してください。これでMinRubyインタプリタに関数を導入する準備ができました。

自前の`p`を組み込む

さっそく組み込み関数pをMinRubyインタプリタに追加してみましょう。 genvに、関数名"p"に対応するエントリを最初から入れておくだけです。（lenvのほうは、いままでのenvと同様に空のままでかまいません。）

genv = { "p" => ["builtin", "p"] }
lenv = {}
evaluate(tree, genv, lenv)

"p"が関数名、["builtin", "p"]が関数pの決め打ちの定義です。

"builtin"というラベルは、この関数定義が「組み込み関数」であることを表しています。当然、「ユーザ定義関数」に対応するラベルもありますが、それは次回の記事でユーザ定義関数を実装するときにお話します。

関数定義に出てくる"p"は、定義されるMinRubyの関数と同じ名前なので紛らわしいかもしれませんが、本物のRubyのほうの関数pを表しています。つまり、この関数定義は、「MinRubyで組み込み関数pを呼んだときの処理は、本物のRubyの関数pに実行させる（つまり丸投げする）」という意味です。（「そんなのいかさまだ！」と感じたなら、第6回を読み直しましょう。）

MinRubyでは、変数名のための環境と関数名のための環境を別にしました。これは、本物のRubyがそうなっているからです。

変数名と関数名の環境が違うということは、同じ名前の変数と関数が同居できるということを意味します。つまりRubyでは、

def foo(x, y)
  x + y * 2
end
foo = foo(1, 1)           # 1 と 1 を関数 foo に与えて、返り値を変数 foo に入れる
foo = foo(foo, foo(1, 1)) # 変数 foo と、関数 foo(1, 1) の返り値を関数 foo に与えて、
                          # その返り値を変数 foo に上書きで入れる
p(foo)                    # 変数 foo を出力する（何が出力されるでしょうか？）

というようなプログラムが書けてしまいます。ややこしいですね。

一方、PythonやC言語などでは変数名と関数名の環境が同一です。つまり、同名の変数と関数は同居できません。同名の変数と関数が同居できない言語のことを、俗にLisp-1と呼んでいます。同居できる言語はLisp-2です。もともとLISPというプログラミング言語の方言を分類する言葉だったのでこんな呼び方になっていますが、他の言語について言及するときもそのまま使われています。

関数呼び出しを実装する

ここまでやったことを整理しておきましょう。

関数名のための環境を用意した
その環境に、組み込み関数を追加した（いまのところpのみ）

次は、組み込んだ関数pをプログラムで使えるようにする必要があります。つまり、関数pがプログラムに出てきたときにMinRubyインタプリタがそれを評価できるように、evaluateにルールを書いていきます。

過去の連載と同様に、まずは関数呼び出しの抽象構文木を見てみましょう。それを見ながら実装を考える作戦です。

pp(minruby_parse("p(1)"))    #=> ["func_call", "p", ["lit", 1]]
pp(minruby_parse("p(1, 2)")) #=> ["func_call", "p", ["lit", 1], ["lit", 2]]

いままで（本物の）Rubyの組み込み関数pには引数を1つしか渡してきませんでしたが、実はpは上記の2つめの例のように複数の引数が取れることになっていて、その場合には引数として渡した各値が行区切りで出力されることになっています。

図にすると、それぞれ次のとおり。

関数呼び出しの抽象構文木は、["func_call", 関数名, 引数（, さらに引数が続く場合もある...）]という構造になっているようです。ということは、evaluateのcase文に、"func_call"というラベルに対応する処理を書けばよさそうですね。

ところが、前の記事で、"func_call"というラベルに対応する部分にはすでに以下のような仮実装をデバッグのために入れていました。

def evaluate(tree, genv, lenv)
  case tree[0]
  when "func_call"
    p(evaluate(tree[2]), genv, lenv) # 仮実装
  ...(略)...
  end
end

この仮実装では、「ラベルが"func_call"のときに、抽象構文木の3つめの枝（先ほどの例だと["lit", 1]）を評価した結果を、Rubyのpで表示する」という動作になっています。この動作は、「MinRubyのpに引数を1つだけ渡した場合」にそうなっていてほしい結果ですよね？

つまり、ある意味でこの仮実装は、「pという名前の関数に引数を1つだけ渡す場合」に特化した関数呼び出しの実装になっていたと言えます。この仮の実装を、しかるべき数の引数を伴って呼び出されたどんな関数に対してもきちんと動作する実装にしていきましょう。

引数をすべて評価する

まずは引数の評価の改修です。関数によっては、1つだけでなく複数の引数を指定できると便利なこともあるでしょう。先ほどの抽象構文木を見ると、複数の引数はtree[2]、tree[3]、...の位置に入るので、まずはwhile文を使って各引数を順番にevaluateしていくようにします。

def evaluate(tree, genv, lenv)
  case tree[0]
  when "func_call"
    args = []
    i = 0
    while tree[i + 2]
      args[i] = evaluate(tree[i + 2], genv, lenv)
      i = i + 1
    end
    # 埋める
  ...(略)...
  end
end

各引数の評価結果は、argsという配列へ順番に入れるようにしました。

ここでは、引数を前から順番に評価しています。 Rubyの場合、引数が複数あるときは前から評価されると決められているので、この実装でもそれに従っています。たとえばfoo(bar(), baz())というコードがあったら、「まず関数barが呼ばれ、次に関数bazが呼ばれる」というようにRubyの言語仕様で定められているのです。

なお、世の中には引数の評価順序が決められていない（「不定」）という言語もあります。代表的なところではC言語がそのような言語です。この場合、インタプリタの実装では自由な順序で引数を評価してかまいません。

一方、その言語のプログラマは、どのような順序で評価されても動くようにプログラムを書く義務があります。あるインタプリタの実装で前から順番に引数が評価されるからといって、その評価順序に強く依存するようなプログラムを書いたら、それはその言語の妥当なプログラムとは言えないのです。

言語の振る舞いを規定する「言語仕様」と、実際に動かせるインタプリタの「実装」とは、常に一致しているとは限りません。このことはプログラミング言語を学ぶときには常に心に留めておいてください。たとえば、この連載のテーマは「(Min)Rubyインタプリタの開発を通してRuby言語を学ぼう」ですが、その逆の「（すでにある）Rubyインタプリタの動作からRuby言語を学ぶ」のは危険だといえます。なぜなら、何かしら不定な動作があって、あるインタプリタを実際に動かして得られた結果は、そのインタプリタの実装者が自由に決めた結果かもしれないからです。

組み込まれている定義を関数名から取ってくる

次に、関数名を管理している環境genvから、評価すべき関数の定義を引っ張ってきます。 genvは次のような形をしたハッシュでした。

genv = { 《関数名》 => ["builtin", 《本物のRubyにおける関数の名前》] }

ハッシュからエントリの値を取り出すには、たとえばgenv["p"]のようにすればよいのでした（忘れた人は第5回の記事を見ましょう）。いま、genvから定義を引っ張り出してきたい関数の名前は、抽象構文木の2つめの枝（tree[1]）に入っているので、次のようにすれば関数名に対応する関数定義を取り出してこれます。

mhd = genv[tree[1]]

これで、呼び出そうとしているのが組み込み関数なら、その定義である["builtin", 《本物のRubyにおける関数の名前》]という配列をmhdに取り出せたことになります。つまり、mhdの先頭が"builtin"なら、いま処理している抽象構文木は組み込み関数です。

evaluateに手を入れて、mhdの先頭（mhd[0]）を見て動作を変えるようにしておきましょう。

def evaluate(tree, genv, lenv)
  case tree[0]
  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"
      # 埋める
    else
      # 埋める（次回）
    end
  ...(略)...
  end
end

評価した引数に、指示されたRubyの関数を適用する

ふたたび、ここまでやったことを整理しておきます。

関数名のための環境を用意した
その環境に、組み込み関数を追加した（いまのところpのみ）
MinRubyプログラムで組み込み関数が使われていると、抽象構文木は["func_call", 関数名, 1つめの引数, 2つめの引数...]のような形になるので、"func_call"というラベルに対する処理をevaluateに追加した
evaluateでは、まず引数を順番に評価して、それをargsという配列に入れた
関数の定義を、関数名のための環境から取り出してきて、それをmhdに入れた

MinRubyプログラムで呼び出されたのが組み込み関数なら、mhd[1]には、その組み込み関数の動作を丸投げすべき「本物のRubyの関数」の名前が入っています。 MinRubyの組み込み関数を処理するには、そこで指示されている本物のRubyの関数を、引数にargsを与える形で呼び出す必要があります。

そのために必要な道具は、minrubyパッケージの中にminruby_callという組み込み関数を用意したおきました（ちょっとずるいですね）。この関数を、たとえば次のように本物のRubyで呼び出すと、

minruby_call("add", [1, 2])

次のように本物のRubyで呼び出したのと同じ動きをします。

add(1, 2)

この関数を使えば、MinRubyの組み込み関数の呼び出しは以下のように実装できます。

def evaluate(tree, genv, lenv)
  case tree[0]
  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プログラムでpが呼べることを確認しておきましょう。次のプログラムをMinRubyインタプリタで実行してみてください。

p(42) #=> 42

前回までの仮実装ではpの引数を1個に限定してしまっていましたが、今回の改修でpには複数の引数を渡せるようになっているはずですから、それも試してみましょう。

p(1, 2, 3)
  #=> 1
  #   2
  #   3

それぞれの値が行区切りで出力されたでしょうか？ぜひMinRubyインタプリタで確認してみてください。

まとめ

今回は、関数の実装の第一弾として、組み込み関数の呼び出しを実装しました。具体的には、関数名のための環境をサポートし、組み込み関数（引数が1つとは限らない）の抽象構文木を評価できるようにevaluateを拡張しました。

現状の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)
pp(minruby_parse("p(1)"))
 
# ③ 抽象構文木を実行（計算）する
genv = { "p" => ["builtin", "p"] }
lenv = {}
evaluate(tree, genv, lenv)

次回はこれにユーザ定義関数の実装をします。上記のコードで「埋める（次回）」というコメントの部分を実装していきます。

練習問題

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

組み込み関数を増やしてみてください。例えば、エラーを出して終了する組み込み関数"raise"を増やしてください。

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

ターゲット言語の組み込み関数pを定義するのに、ホスト言語の組み込み関数pをそのまま使いました。しかし、ホスト言語のユーザ定義関数をターゲット言語の組み込み関数にすることもできます。たとえば、MinRubyインタプリタのソースコードを

def evaluate(tree, genv, lenv)
  ...(略)...
end
def add(x, y)
  x + y
end
genv = { "add" => ["builtin", "add"] }
lenv = {}
evaluate(tree, genv, lenv)

とすれば、次のようなプログラムを動かせるようになるはずです。

p(add(1, 2)) #=> 3

FizzBuzzを組み込み関数として用意してみてください。また、独自の面白い組み込み関数を考えてみてください。

第6回の練習問題の答え

1. 帰ってきたFizzBuzz

略

2. `begin ... end while`の実装

def evaluate(tree)
  case tree[0]
  when "while2"
    evaluate(tree[2], genv, lenv)
    while evaluate(tree[1], genv, lenv)
      evaluate(tree[2], genv, lenv)
    end
  ...(略)...
  end
end

3. `case`文の意味

構文糖を手で分解してみればわかります。

if p(42) == 0
  p(0)
else
  if p(42) == 1
    p(1)
  else
    p("others")
  end
end

caseの後に出てくる式がすべてのifの条件式に複製されてしまうので、比較式を評価するたびに関数pが呼ばれてしまいます。

これを防ぐには、いったん変数に入れるという手があります。

ret = p(42)
case ret
when 0
  p(0)
when 1
  p(1)
else
  p("others")
end

ただ、こんな構文糖は嫌ですよね。本格的にインタプリタを作るとしたら、構文糖を展開する際に自動的に変数を用意して関数呼び出しを複製しないようにする必要があるでしょう。構文糖はユーザにとっては便利で素敵なものですが、下手に設計すると意外な副作用をもたらすことがあるので、言語設計者は慎重になるべきでしょう。

ツイートする

カテゴリートップへ