![24 評価プロセス(関数呼び出し式) [オリジナル言語インタプリタを作る]](https://webbibouroku.com/wp-content/uploads/eye_gorilla.png)
関数と関数呼び出し式
関数と関数呼び出し式の評価を実装します。ここまで字句解析、構文解析、そして評価と実装を進めてきましたが、この実装で最後です。
関数の単純な呼び出しはもちろん、引数で関数を渡したり、クロージャも動作します。
このような動作を実現するにはまず、インタプリタにおける関数の内部表現を定義しなければなりません。整数や真偽値と同じようにオブジェクトの1つとして扱います。
それから Eval() に関数呼び出し式の対応を追加します。
これまでのやり方と同じく1歩1歩進めていきましょう。
関数
まずは関数を定義するコードを評価できるようにしていきます。
関数の内部表現
関数はプログラミング言語 Gorilla において、オブジェクトして扱います。つまり IObject を実装するクラスとして定義するということです。
そうすることで整数や真偽値と同じように変数に束縛でき、式として振る舞います。ほかの関数の引数にしたり、関数から評価結果として返すことも可能になります。
では関数の内部表現はどのように定義すればよいでしょうか。真偽値や整数値であれば C# のプリミティブ型を用いて実装しました。関数のASTの定義からもわかる通り、引数とブロック文が関数に必要な情報です。
Objects/FunctionObject.cs
using Gorilla.Ast.Expressions;
using Gorilla.Ast.Statements;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Gorilla.Objects
{
public class FunctionObject : IObject
{
public List<Identifier> Parameters { get; set; } = new List<Identifier>();
public BlockStatement Body { get; set; }
public Enviroment Enviroment { get; set; }
public string Inspect()
{
var parameters = this.Parameters.Select(p => p.ToCode());
var builder = new StringBuilder();
builder.Append("fn");
builder.Append("(");
builder.Append(string.Join(", ", parameters));
builder.Append(")");
builder.Append(this.Body.ToCode());
return builder.ToString();
}
public ObjectType Type() => ObjectType.FUNCTION_OBJ;
}
}
Objects/IObject.cs
public enum ObjectType
{
// ..
FUNCTION_OBJ,
}
まずは、IObject を実装する FunctionObject を定義します。ObjectType は新しく FUNCTION_OBJ を定義してこれを利用する。
関数の内部表現として引数と本文をASTの状態で保持するようにします。関数の呼び出しはこのASTを評価することになります。
また注目すべきはプロパティで環境そのものの参照を保持する点です。Gorilla の関数はそれ自体で閉じた独自の環境を持ちます。つまり関数内部のみで有効なローカル変数を定義できるのです。これを実現するために独自の環境をプロパティで持つ必要があるのです。
テストの作成
ではテストを書いてみましょう。
[TestMethod]
public void TestEvalFunctionObject()
{
var input = "fn(x) { x + 2; }";
var evaluated = this._TestEval(input);
var fn = evaluated as FunctionObject;
if (fn == null)
{
Assert.Fail($"オブジェクトが関数ではありません。({fn?.GetType()})");
}
Assert.AreEqual(fn.Parameters.Count, 1);
Assert.AreEqual(fn.Parameters[0].ToCode(), "x");
Assert.AreEqual(fn.Body.ToCode(), "{(x + 2) }");
}
評価結果が関数オブジェクトであること、引数の数が一致し識別子の名前が一致すること、そして本文のコードが一致することを確認しています。これで環境以外については、正しく関数オブジェクトが生成されることを確認できます。
ブロック文の ToCode() は {} 含めて出力されます。また、文については半角スペース区切りで出力されるようになっているので、末尾に余計な空白が出てしまっています。まあこれはテスト、エラー表示用の処理なので不細工ですがあまり気にしないでください。
このテストを通すコードは簡単です。
実装
Evaluating/Evaluator.cs
public class Evaluator
{
// ..
public IObject Eval(INode node, Enviroment enviroment)
{
switch (node)
{
// ..
case FunctionLiteral functionLiteral:
return new FunctionObject()
{
Parameters = functionLiteral.Parameters,
Body = functionLiteral.Body,
Enviroment = enviroment,
};
}
return null;
}
}
関数ASTを評価する条件分岐を追加し、そこでASTの一部を使ってオブジェクトを生成しています。これだけでテストが通ります。
環境は現在の環境をそのまま渡します。
続けてこの関数を呼び出せるようにしていきましょう。
関数呼び出し
テストの作成
関数を定義できるようになりました。次はこれを呼美出世るようにします。
まずはテストを書きます。
[TestMethod]
public void TestFunctionApplication()
{
var tests = new(string, int)[]
{
("let identity = fn(x) { x }; identity(10);", 10),
("let identity = fn(x) { return x; }; identity(10);", 10),
("let double = fn(x) { x * 2; }; double(10);", 20),
("let add = fn(x, y) { x + y; }; add(10, 20);", 30),
("let add = fn(x, y) { x + y; }; add(add(10, 20), 30 + 40);", 100),
("fn(x) { x; }(10);", 10),
};
foreach (var (input, expected) in tests)
{
var evaluated = this._TestEval(input);
this._TestIntegerObject(evaluated, expected);
}
}
このテストは関数を定義し、それを呼び出してその結果をテストします。
関数は暗黙の戻り値(最後に評価された値)とreturn文による明示的な戻り値のどちらも有効です。したがってこの2パターンをテストします。また、複数の引数や引数の中での関数評価、関数の即時実行もテストします。引数は関数呼び出しの前に評価されることになります。
これですべてのパターンではありませんが、いくつかの重要なケースをテストできます。
このテストを通すための実装は難しくない。識別子や整数リテラルを評価するように、CallExpression についての評価を実装します。
実装
関数呼び出し式の評価を実装する前にまず、関数呼び出し式の構造を思い出してみます。
add(1, 2);
こんな式でした。そして構文規則にすると以下のようになります。
<expression>(<expression>, .. , <expression>)
関数呼び出しの識別子も式でしたね。したがってこの関数呼び出し式を評価するということは、まず括弧の左側の式を評価して呼び出したい関数(オブジェクト)を取得します。そのあと引数を順に評価し、そして最後にその関数オブジェクト自体を評価する、という運びになります。
まずは呼び出したい関数オブジェクトを取得して、引数を評価するところまでを実装してみます。
public class Evaluator
{
// ..
public IObject Eval(INode node, Enviroment enviroment)
{
switch (node)
{
// ..
case CallExpression callExpression:
var fn = this.Eval(callExpression.Function, enviroment);
if (this.IsError(fn))
{
return fn;
}
var args = this.EvalExpressions(callExpression.Arguments, enviroment);
if (this.IsError(args.FirstOrDefault()))
{
return args.First();
}
break;
}
return null;
}
public List<IObject> EvalExpressions(List<IExpression> arguments, Enviroment enviroment)
{
var result = new List<IObject>();
foreach (var arg in arguments)
{
var evaluated = this.Eval(arg, enviroment);
if (this.IsError(evaluated))
return new List<IObject>() { evaluated };
result.Add(evaluated);
}
return result;
}
// ..
}
CallExpression を評価する分岐で、呼び出す関数自体を示す式の評価を行います。式の評価なので結果がエラーかどうかチェックなければなりません。
引数も同様にすべてループして評価します。もちろん1つでもエラーになればその時点で処理を切り上げエラーを返します。
呼び出す関数、引数、いずれの評価でも現在の環境を使って評価します。
関数本体を評価する
ここまでで関数と引数のリストを手に入れることができました。あとはこれらを組み合わせて関数の本体を評価するだけです。
関数の本体はブロック文です。すでにブロック文の評価は実装済なので問題なく評価できそうですが、問題は引数の存在です。関数の本文に現在の環境を用いて評価を行うと、引数で渡された値への参照時に未知の値としてエラーが発生してしまいます。
したがって関数本文の評価では単純に現在の環境を使ってはいけないのです。もちろん現在の環境に引数の参照を追加するのもいけません。これでは既存の変数を破壊する恐れがあります。
期待する動作は以下のようになります。
let x = 1;
let printNum1 = fn(x) {
puts(x);
}
let printNum2 = fn() {
puts(x);
}
puts(x);
printNum1(2);
printNum2();
puts() はデータを表示する処理として考えてください。出力を期待されるのは 1 と 2 と 1 の3つのデータです。
x という識別子が関数の内側と外側それぞれで定義されることになり、それぞれが別の値を参照しなければなりません。つまり関数の内と外で閥の環境を作ることになります。
また、まったく別の新しい環境というわけではありません。もし関数の内側で定義がなければさらに外側の環境を確認し、変数を参照しなければなりません。つまり元の環境をラップした環境を持つということになります。
Enviromentクラスを拡張し、外側の環境を持てるようにしましょう。そして変数の参照処理を変更します。
public class Enviroment
{
// ..
public Enviroment Outer { get; set; }
public static Enviroment CreateNewEnclosedEnviroment(Enviroment outer)
{
var enviroment = new Enviroment();
enviroment.Outer = outer;
return enviroment;
}
public (IObject, bool) Get(string name)
{
var ok = this.Store.TryGetValue(name, out var value);
if (!ok && this.Outer != null)
{
(value, ok) = this.Outer.Get(name);
}
return (value, ok);
}
// ..
}
1つ外側の環境を保持するプロパティを追加しました。
そして Get() で参照する際に、今の環境に値が存在しない場合は、さらにその外側の環境へ値が存在しないかを確認するようにしています。このようにすることで、値が存在しない場合にはより外側の環境をどんどんたどっていくようになります。変数のスコープが何重にも入れ子になるようなイメージです。
このように外側の環境への参照を持った環境を新しく作成する静的関数 CreateNewEnclosedEnviroment() を用意しました。
これで準備は完了です。
ではいよいよ最後の実装です。関数の処理を呼び出しましょう。
public class Evaluator
{
// ..
public IObject Eval(INode node, Enviroment enviroment)
{
switch (node)
{
// ..
case CallExpression callExpression:
var fn = this.Eval(callExpression.Function, enviroment);
if (this.IsError(fn))
{
return fn;
}
var args = this.EvalExpressions(callExpression.Arguments, enviroment);
if (this.IsError(args.FirstOrDefault()))
{
return args.First();
}
return this.ApplyFunction(fn, args);
}
return null;
}
public IObject ApplyFunction(IObject obj, List<IObject> args)
{
var fn = obj as FunctionObject;
if (fn == null)
{
return new Error($"function ではありません。: {obj?.GetType()}");
}
var extendedEnviroment = this.ExtendEnviroment(fn, args);
var evaluated = this.EvalBlockStatement(fn.Body, extendedEnviroment);
return this.UnwrapReturnValue(evaluated);
}
public Enviroment ExtendEnviroment(FunctionObject fn, List<IObject> args)
{
var enviroment = Enviroment.CreateNewEnclosedEnviroment(fn.Enviroment);
for (int i = 0; i < fn.Parameters.Count; i++)
{
enviroment.Set(fn.Parameters[i].Value, args[i]);
}
return enviroment;
}
public IObject UnwrapReturnValue(IObject obj)
{
if (obj is ReturnValue returnValue)
{
return returnValue.Value;
}
return obj;
}
// ..
}
Eval() に関数本文の評価処理 ApplyFunctin() を呼び出すようにしました。
ApplyFunction() では、関数内部で使う新しい環境を作成(ExtendEnviroment())し、その環境を使って関数本体のブロック文を評価します。
関数内部で使う新しい環境は ExtendEnviroment() で作成しています。まず外側の環境を保持する新しい環境のインスタンスを CreateNewEnclosedEnviroment() で作ります。作った環境には引数を登録しておく必要があるので、パラメータの名前と引数の値をセットにして追加していきます。
こうすることで引数の参照ができる新しい環境が作られています。
最後に、評価結果が ReturnValue の場合はアンラップする必要があるので、その処理も切り出して別関数で対応しています。なぜすぐにアンラップして値を取り出すかというと、より外側のブロック文で戻り値としてどんどん処理を切り上げてしまうためです。
これですべてのテストが通るようになります。
つまり完成です！！！
高階関数 と クロージャ
プログラミング言語 Gorilla は 高階関数もクロージャもサポートします。高階関数は Wikipedia によると以下のように説明されます。
高階関数（こうかいかんすう、英: higher-order function）とは、第一級関数をサポートしているプログラミング言語において、関数（手続き）を引数にしたり、あるいは関数（手続き）を戻り値とするような関数のことである。
関数リテラルは式なので引数にも戻り値にもできます。
以下の例を見てみます。
Hello Gorilla Script!
>> let newAdder = fn(x) { fn(y) { x + y; } };
>> let addTwo = newAdder(2);
>> addTwo(3);
5
>> addTwo(1);
3
newAdder() 関数を返します。ただの関数でなくクロージャです。newAdder(2) と引数2を与えて呼び出されたときにクロージャが作られ、値2がクロージャの環境に x で束縛されます。したがって、addTwo() が呼ばれるとき、引数 y だけでなく x クロージャ生成時の環境から参照できるようになっているのです。
この例では3つのスコープが存在しています。外側から順に、トップレベルのスコープ(newAdder, addTwo)、newAdder に束縛された関数内部でのスコープ(x)、newAdderが生成する関数内部のスコープ(y)です。クロージャである関数は内側から外側の変数を参照できます。定義時に外側の環境を取得しているからです。
これがわかればなぜ以下のような動きをするかもわかります。
Hello Gorilla Script!
>> let addX = fn(n) { x + n; }
>> addX(1);
識別子が見つかりません。: x
>> let x = 100;
>> addX(1);
101
Javascriptも同じような動きをするようです。なんだかすごい。
フィボナッチ数を求めるような再帰的な呼び出しも実装可能です。
Hello Gorilla Script!
>> let fib = fn(n) { if(n == 0) { return 0; } if(n == 1) { return 1;} else { fib(n-1) + fib(n-2) }
>> fib(20);
6765
色々と遊んでみてください。これで完成です。もし不満点があればこれまでの実装のように拡張してみるとよいでしょう。
ちなみに参考にした書籍だとこの時点で全体の6割くらいで、さらなる拡張機能として文字列、配列、組み込み関数、ハッシュマップ、マクロシステムの実装が続きます。面白かったので時間があれば続きを実装してみようと思います。
ここまでのソース
mntm0/Gorilla at fb147676d1cb5d795771ab280f2ce432e76cc097
以上。
