Golang でプログラミング言語を作る__Part18
今回は関数タイプを評価する(evaluate)機能をつけていきます。
前回の記事は、以下になります。
追加する処理は次の2つです
- オブジェクトシステムに、関数タイプの値(function expression)の追加
- Evalへの関数呼び出しのサポートを追加
まずは、関数を内部的に表すもの、つまりAST内に関数構造を表すノードを作ります。
ast/ast.go
type FunctionLiteral struct {
Token token.Token
Parameters []*Identifier
Body *BlockStatement
}// [...]
更に関数をラップする、次のオブジェクトを設定します。
object/object.go
type Function struct {
Parameters []*ast.Identifier
Body *ast.BlockStatement
Env *Environment
}func (f *Function) Type() ObjectType { return FUNCTION_OBJ }
func (f *Function) Inspect() string {
var out bytes.Bufferparams := []string{}
for _, p := range f.Parameters {
params = append(params, p.String())
}out.WriteString("fn")
out.WriteString("(")
out.WriteString(strings.Join(params, ", "))
out.WriteString(") {\n")
out.WriteString(f.Body.String())
out.WriteString("\n}")return out.String()
}
object.Function フィールド内に、Envがあることによって、クロージャー(有効範囲)を設定することができます。
これでASTに関数の定義を、また関数を扱うオブジェクトを作成しました。
次は、テストケースをつくります。関数を含むテスト入力値から、今までのテスト同様に作っていきます。今回は、これに加えてCallExpression(関数の呼び出し)のテストも行います。
evaluator/evaluator_test.go
func TestFunctionObject(t *testing.T) {
input := "fn(x) { x + 2 }"evaluated := testEval(input)
fn, ok := evaluated.(*object.Function)
// [...]
}
func TestFunctionApplication(t *testing.T) {
tests := []struct {
input string
expected int64
}{
{"let identity = fn(x) { x; }; identity(5);", 5},
{"let identity = fn(x) { return x; }; identity(5);", 5},
{"let double = fn(x) { x * 2; }; double(5);", 10},
{"let add = fn(x, y) { x + y; }; add(5, 5);", 10},
{"let add = fn(x, y) { x + y; }; add(5 + 5, add(5, 5));", 20},
{"fn(x) { x; }(5)", 5},
}for _, tt := range tests {
testIntegerObject(t, testEval(tt.input), tt.expected)
}
}
一つ目のテスト TestFunctionObject は、ASTの関数ノードが渡された時に、関数オブジェクトが返ってくるかどうかを確認します。
また二つ目のテスト、 TestFuntionApplication は、関数の呼び出しが実際に機能しているかを確認しています。
このテストがfailすることを確認したら、次はevaluatorの実装になります。
まずは関数(function literal)に対してつくり、 TestFunctionObject をパスさせます。
evaluator/evaluator.go
func Eval(node ast.Node, env *object.Environment) object.Object {
switch node := node.(type) {
// [...] case *ast.FunctionLiteral:
params := node.Parameters
body := node.Body
return &object.Function{Parameters: params, Env: env, Body: body}
}
return nil
}
TestFunctionLiteral がpassすることを確認したら、次はcall Expressionに対しての処理を作ります。
その前に、まずAST内にcall Expressionを内部的に表すノードをつくります。
ast/ast.go
type CallExpression struct {
Token token.Token
Function Expression
Arguments []Expression
}// the code under this are almost the same as FunctionLiteral
次に、Eval関数に、ASTのCall関数ノードが渡されたときの処理を加えます。
evaluator/evaluator.go
func Eval(node ast.Node, env *object.Environment) object.Object {
switch node := node.(type) {
// [...]
case *ast.CallExpression:
function := Eval(node.Function, env)
if isError(function) {
return function
}
args := evalExpressions(node.Arguments, env)
if len(args) == 1 && isError(args[0]) {
return args[0]
}
return applyFunction(function, args)
}
return nil
}処理内容としては次の通りになります。
- ast.CallExpressionが渡された時に、Eval関数に再度、ノード内の関数フィールドを渡して呼び出す。その際にエラーがあれば、その時点でエラーを返す。
- 次に、ノード内の引数フィールドを処理する。
つまり、引数を先に解釈して、その後に関数内の処理に移る必要がある。 - 最後に、上の1, 2, を通過した関数と引数を
applyFunctionに渡す。
まず、処理2で使われる、引数を評価する関数 evalExpression は次のようになります。
func evalExpressions(exps []ast.Expression, env *object.Environment) []object.Object {
var result []object.Objectfor _, e := range exps {
evaluated := Eval(e, env)
if isError(evaluated) {
return []object.Object{evaluated}
}
result = append(result, evaluated)
}
return result
}
また、実際に処理3で使われる applyFunction を行う前に、environmentに対して考えていく必要があります。
というのも、今このまま関数本体の処理を評価しようとしても、本体から引数の参照は出来ない状態になっています。
ここで必要になってくることは、関数が評価される環境を変更することで、関数本体の引数の参照が、正しくなるようにすることです。
では、実際にenvironment.goファイルに次のコードを加えます。
この追加の目的は、新しいバインディングを作成すると同時に、以前のバインドを保持することです。これは、「環境の拡張」と呼ばれます。
object/environment.go
package objectfunc NewEncloseEnvironment(outer *Environment) *Environment {
env := NewEnvironment()
env.outer = outer
return env
}func NewEnvironment() *Environment {
s := make(map[string]Object)
return &Environment{store: s, outer: nil}
}type Environment struct {
store map[string]Object
outer *Environment
}func (e *Environment) Get(name string) (Object, bool) {
obj, ok := e.store[name]
if !ok && e.outer != nil {
obj, ok = e.outer.Get(name)
}
return obj, ok
}func (e *Environment) Set(name string, val Object) Object {
e.store[name] = val
return val
}
つまり、あるenvironment内で、新しくもう一つのenvironmentを作成しています。
これは、関数の内部・外部スコープを反映したものになりますね。
これによって、値と名前がバインディングする際は毎度新しい環境(内側のスコープ)が作られて、その中でバインディングが行われます。
ここまでのEnvの設定を終えたら、次は、applyFunction を書いていきます。
applyFunction はcallExpression内の、関数、引数フィールドを最終的に評価する(evaluation)する関数でしたね。
evaluator/evaluator.go
func applyFunction(fn object.Object, args []object.Object) object.Object {
function, ok := fn.(*object.Function)
if !ok {
return newError("not a function: %s", fn.Type())
}
extendedEnv := extendFunctionEnv(function, args)
evaluated := Eval(function.Body, extendedEnv)
return unwrapReturnValue(evaluated)
}func extendFunctionEnv(fn *object.Function, args []object.Object) *object.Environment {
env := object.NewEncloseEnvironment(fn.Env)for paramIdx, param := range fn.Parameters {
env.Set(param.Value, args[paramIdx])
}return env
}func unwrapReturnValue(obj object.Object) object.Object {
if returnValue, ok := obj.(*object.ReturnValue); ok {
return returnValue.Value
}return obj
}
上の一つ目の関数、 applyFunction は実際に関数のオブジェクトを扱います。
と同時に、関数の引数(コード内における、fnの引数を指す)と、関数オブジェクト の中身(ポインター)とを結びつけています。
これによって、関数の引数に、.Envと.Bodyフィールドから参照できるようになります。
また二つ目の関数、 extendFunctionEnv では、関数の中身(Body)が評価されます。先程environment.go内で作成した NewEncloseEnvironment で新しい環境が作られ、その中で評価が行われます。
更には、この新しい環境内では、関数呼び出しの引数を関数のパラメータ名にバインドします。
最後の関数、 unwrapReturnValue は、評価処理の最中にreturn文があった時には、その値だけを取り出します。これによって、通常のreturnの処理による、そのあとの評価が止まることを防ぎます。
最終的に、関数が呼ばれた時に評価が止まる様にしたいので、関数の{}ブロックステートメントにreturn文のオブジェクトを値に戻しています。
これで、関数の中に(“{}”内に)関数を入れても、機能するようになります。
以上の処理を踏まえて、テストを走らせpassすることを確認したら、関数及び関数の呼び出しの実装が完了です。
また、実際に go run main.go で、REPL内でも関数が機能しているのが確認できます。
クロージャーが本当に機能しているのを見ると、ちょっと感動します。
