Golang でプログラミング言語を作る__Part18

Tuyoshi Akiyama
Aug 23, 2017 · 12 min read

今回は関数タイプを評価する(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.Buffer
params := []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
}

処理内容としては次の通りになります。

  1. ast.CallExpressionが渡された時に、Eval関数に再度、ノード内の関数フィールドを渡して呼び出す。その際にエラーがあれば、その時点でエラーを返す。
  2. 次に、ノード内の引数フィールドを処理する。
    つまり、引数を先に解釈して、その後に関数内の処理に移る必要がある。
  3. 最後に、上の1, 2, を通過した関数と引数を applyFunction に渡す。

まず、処理2で使われる、引数を評価する関数 evalExpression は次のようになります。

func evalExpressions(exps []ast.Expression, env *object.Environment) []object.Object {
var result []object.Object
for _, 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内でも関数が機能しているのが確認できます。

クロージャーが本当に機能しているのを見ると、ちょっと感動します。

)
Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade