トップ > go > Go言語でGo言語のインタプリタを作る

Go言語でGo言語のインタプリタを作る

go プログラミング言語

東京大学理学部情報科学科の2019年アドベントカレンダー、14日目の記事です。

この記事は、Go言語でGo(のとても小さいサブセット)のインタプリタを作ってみようというものです。「Goはある程度わかるが言語の処理系のことはよく知らない」という人を想定して書きました。プログラミング言語のインタプリタが何をやっているのかが少しでも伝われば幸いです。

次のような流れで進めていきます。

  1. 構文の決定
  2. 構文解析
  3. 式の評価・文の実行
  4. 型検査など

ソースコードは https://github.com/kkty/nanogo にあります。

構文の決定

Goの全ての構文に対応しようとすると途方もない時間がかかります。（ちなみに、Go言語の仕様書はhttps://golang.org/ref/specにあります。これを実装するのは無理ですね。はい。）

そこで、大胆に機能を削ります。例えば、goroutine、構造体、ポインタ、パッケージまわりはすべて取り除きます。そして扱える型はint64、float64、boolのみにします。

また、パース（後述）しやすいようなものに構文を制限します。Go言語では返り値を持たない関数はfunc foo(...) { ... }のようにかけますが、func foo(...) () { ... }のようなものにのみ対応します（こちらも正しいGo言語の構文です）。:=のような糖衣構文もパースを楽にするためになくします。

このようにしてかなり制限を加えましたが、「これくらいのコードは動かせるようにしよう」というものを3つほど示しておきます。

まずは1つめです。

func fib(i int64) (int64) {
  if i <= 1 {
    return 1
  }

  return fib(i - 1) + fib(i - 2)
}

func main() () {
  print(fib(10))
}

言わなくてもわかると思いますが、これは10番目のフィボナッチ数を計算するプログラムです。実際に冒頭にpackage mainをつけて保存し、go run ...で実行すれば89が表示されます。

今から作るインタプリタでこのプログラムを実行できるように、すなわち、関数呼び出しやprintビルトイン関数、if文などは扱えるようにしましょう。

2つめです。

var cnt int64
func main() () {
  var i int64
  for i < 10 {
    i = i + 1
    increment()
  }
  print(cnt)
}

func increment() () {
  cnt = cnt + 1
}

グローバル変数やforループも扱えるようにしましょう。ちなみにこのプログラムは10が出力されるはずです。

そして最後です。

func main() () {
  var adder func(int64) (int64)
  adder = makeAdder(1)
  print(adder(3))
  adder = makeAdder(2)
  print(adder(4))
}

func makeAdder(i int64) (func (int64) (int64)) {
  return func(j int64) (int64) {
    return i + j
  }
}

クロージャも扱えるようにしましょう。このプログラムは(printは改行を入れないので少しわかりにくいですが)46が出力されるはずです。

テストの形にするとこのようになります。

// test/parse_and_run_test.go

package test

import (
    "bytes"
    "fmt"
    "testing"

    "github.com/kkty/nanogo"
    "github.com/stretchr/testify/assert"
)

func TestParseAndRun(t *testing.T) {
    for i, c := range []struct {
        program  string
        expected string
    }{
        {
            `
          func main() () {
              print(3)
          }
          `,
            "3",
        },
        {
            `
          var cnt int64
          func main() () {
              var i int64
              for i < 10 {
                  i = i + 1
                  increment()
              }

              print(cnt)
          }
          func increment() () {
              cnt = cnt + 1
          }
          `,
            "10",
        },
        {
            `
          func main() () {
              var add func(int64) (int64)
              add = makeAdder(1)
              print(add(3))
              add = makeAdder(2)
              print(add(4))
          }
          func makeAdder(i int64) (func (int64) (int64)) {
              return func(j int64) (int64) {
                  return i + j
              }
          }
          `,
            "46",
        },
      /* 略 */
    } {
        t.Run(fmt.Sprintf("Case%d", i), func(t *testing.T) {
            program := nanogo.Parse(c.program)
            buf := &bytes.Buffer{}
            program.Run(buf)
            assert.Equal(t, c.expected, buf.String())
        })
    }
}

目標が見えてきましたね？それではこれらのプログラム（+α）を正しく実行できるようなインタプリタの作成していきましょう。

構文解析

プログラムは文字列で書きますが、それをプログラムで扱いやすい形に変換してあげる必要があります。それを担うのがレキサーとパーサーを用いた構文解析です。

レキサー

レキサーはfoo = bar(1) + 3などの文字列を

IDENTIFIER(foo) EQUAL IDENTIFIER(bar) LEFT_PARENTHESIS INT_VALUE(1) RIGHT_PARENTHESIS PLUS INT_VALUE(3)

に変換するといった要領で、文字列を「トークン」に置き換えていきます。

実装については、

"=" -> EQUAL
"==" -> EQUAL_EQUAL
"[0-9]+" -> INT_VALUE
"\(" -> LEFT_PARENTHESIS

といったような正規表現からトークンへの変換テーブルを用意しておいて、最長一致するものを常に選んでいく、といったような方法を用います。

実際の実装はこのような雰囲気になります。

// parser.go

func atoi(s string) int64 {
    i, err := strconv.Atoi(s)

    if err != nil {
        log.Fatal(err)
    }

    return int64(i)
}

func atof(s string) float64 {
    f, err := strconv.ParseFloat(s, 32)

    if err != nil {
        log.Fatal(err)
    }

    return float64(f)
}

func (l *lexer) Lex(lval *yySymType) int {
   // i文字プログラムを読みすすめる
    advance := func(i int) {
        l.program = l.program[i:]
    }

   // プログラムの冒頭がsと一致していたらtrue
    hasPrefix := func(s string) bool {
        return strings.HasPrefix(l.program, s)
    }

   // 空白を読み飛ばす。もしも一つ以上読み飛ばしたらtrueを返す
    skipWhitespaces := func() bool {
        modified := false
        for hasPrefix(" ") || hasPrefix("\n") || hasPrefix("\t") {
            modified = true
            advance(1)
        }
        return modified
    }

   // 次の文字が空白でなくなるまで読み飛ばす
    for skipWhitespaces() {
    }

   // プログラムをすべて読んだら終了
    if len(l.program) == 0 {
        // 0 stands for EOF.
        return 0
    }

    patterns := []struct {
        pattern string
        token   int
      // "123" -> INT_VALUE(123) や、"foo" -> IDENTIFIER("foo") に必要
        f       func(s string)
    }{
        {"func", FUNC, nil},
        {"{", LEFT_BRACE, nil},
        {"}", RIGHT_BRACE, nil},
        {"\\(", LEFT_PARENTHESIS, nil},
        {"\\)", RIGHT_PARENTHESIS, nil},
        {",", COMMA, nil},
        {"int64", INT64, nil},
        {"float64", FLOAT64, nil},
        {"bool", BOOL, nil},
        {"true", BOOL_VALUE, func(s string) { lval.boolval = true }},
        {"false", BOOL_VALUE, func(s string) { lval.boolval = false }},
        {"[0-9]+", INT_VALUE, func(s string) { lval.intval = atoi(s) }},
        {"[0-9]+(\\.[0-9]*)?([eE][\\+\\-]?[0-9]+)?", FLOAT_VALUE, func(s string) { lval.floatval = atof(s) }},
        {"-", MINUS, nil},
        {"\\+", PLUS, nil},
        {"\\*", ASTERISK, nil},
        {"/", SLASH, nil},
        {"=", EQUAL, nil},
        {"==", EQUAL_EQUAL, nil},
        {"!=", EXCLAMATION_EQUAL, nil},
        {"<", LESS, nil},
        {"<=", LESS_EQUAL, nil},
        {">", GREATER, nil},
        {">=", GREATER_EQUAL, nil},
        {"if", IF, nil},
        {"for", FOR, nil},
        {"return", RETURN, nil},
        {"var", VAR, nil},
        {"print", PRINT, nil},
        {"[a-z][0-9a-zA-Z_]*", IDENTIFIER, func(s string) { lval.stringval = s }},
    }

    longestMatch := struct {
        pattern string
        found   string
        token   int
        f       func(s string)
    }{}

   // 最長一致を探す
    for _, pattern := range patterns {
        found := regexp.MustCompile("^" + pattern.pattern).FindString(l.program)

        if len(found) > len(longestMatch.found) {
            longestMatch.pattern = pattern.pattern
            longestMatch.token = pattern.token
            longestMatch.found = found
            longestMatch.f = pattern.f
        }
    }

    if longestMatch.pattern == "" {
        log.Fatal("no matching token")
    }

    if f := longestMatch.f; f != nil {
        f(longestMatch.found)
    }

    advance(len(longestMatch.found))

    return longestMatch.token
}

goyacc(後述)に食わせるための形式になっていてその箇所はわかりにくいかもしれませんが、雰囲気は伝わるでしょうか。

パーサー

レキサーの次はパーサーです。パーサーはトークンの列を受け取り、抽象構文木を作ります。今回の場合は、プログラムを表す(ネストのたくさんある)構造体をつくります。

次のような構造体を用いてプログラムを表すことにしましょう。Type(型)とExpression(式)とStatement(文)というインターフェイスが登場していますが一旦これは空のインターフェイス(interface{})であるとしておきましょう。

// program.go, expression.go, statement.go, type.go

// プログラム本体
type Program struct {
    Assignments  []*Assignment
    Declarations []*Declaration
}

// 型

type IntType struct{}
type FloatType struct{}
type BoolType struct{}

type FunctionType struct {
    Args   []Type
    Return []Type
}

// 式 (expression)

// 即値
type Int struct{ Value int64 }
type Float struct{ Value float64 }
type Bool struct{ Value bool }

// 変数の参照
type Variable struct{ Name string }

// 四則演算
type Add struct{ Left, Right Expression }
type Sub struct{ Left, Right Expression }
type Mul struct{ Left, Right Expression }
type Div struct{ Left, Right Expression }

// 比較
type Equal struct{ Left, Right Expression }
type Not struct{ Inner Expression }
type LessThan struct{ Left, Right Expression }

// 関数呼び出し(関数適用)
type Application struct {
    Function Expression
    Args     []Expression
}

// 文 (statement)

// ブロック
type Block []Statement

// 宣言
type Declaration struct {
    Name string
    Type Type
}

// 代入
type Assignment struct {
    Left  string
    Right Expression
}

// if文
type If struct {
    Condition Expression
    Block     Block
}

// for文
type For struct {
    Condition Expression
    Block     Block
}

// 関数のreturn
type Return struct {
    Expression Expression
}

// print関数の呼び出し
type Print struct{ Arg Expression }

具体的に次のようなプログラムを考えてみましょう。

var i int64
func main() () {
  i = 5
    var j int64
    j = double(i)
    print(j)
}
func double(i int64) (int64) {
  return i * 2
}

これを次のようにパースする、といった感じです。(go-spewを用いてプリントしています)

(*nanogo.Program)(0xc00012e090)({
 Assignments: ([]*nanogo.Assignment) (len=2 cap=2) {
  (*nanogo.Assignment)(0xc00026e460)({
   Left: (string) (len=4) "main",
   Right: (*nanogo.Function)(0xc000168700)({
    Type: (*nanogo.FunctionType)(0xc0002696e0)({
     Args: ([]nanogo.Type) <nil>,
     Return: ([]nanogo.Type) {
     }
    }),
    Args: ([]string) {
    },
    Body: ([]nanogo.Statement) (len=4 cap=4) {
     (*nanogo.Assignment)(0xc0001e8340)({
      Left: (string) (len=1) "i",
      Right: (*nanogo.Int)(0xc00012b158)({
       Value: (int64) 5
      })
     }),
     (*nanogo.Declaration)(0xc0001e8860)({
      Name: (string) (len=1) "j",
      Type: (*nanogo.IntType)(0x15cdc98)({
      })
     }),
     (*nanogo.Assignment)(0xc0001e9a20)({
      Left: (string) (len=1) "j",
      Right: (*nanogo.Application)(0xc000229d40)({
       Function: (*nanogo.Variable)(0xc000240470)({
        Name: (string) (len=6) "double"
       }),
       Args: ([]nanogo.Expression) (len=1 cap=1) {
        (*nanogo.Variable)(0xc000240450)({
         Name: (string) (len=1) "i"
        })
       }
      })
     }),
     (*nanogo.Print)(0xc000241c90)({
      Arg: (*nanogo.Variable)(0xc000241c80)({
       Name: (string) (len=1) "j"
      })
     })
    }
   })
  }),
  (*nanogo.Assignment)(0xc0002f6a80)({
   Left: (string) (len=6) "double",
   Right: (*nanogo.Function)(0xc000168b00)({
    Type: (*nanogo.FunctionType)(0xc00031a360)({
     Args: ([]nanogo.Type) (len=1 cap=1) {
      (*nanogo.IntType)(0x15cdc98)({
      })
     },
     Return: ([]nanogo.Type) (len=1 cap=1) {
      (*nanogo.IntType)(0x15cdc98)({
      })
     }
    }),
    Args: ([]string) (len=1 cap=1) {
     (string) (len=1) "i"
    },
    Body: ([]nanogo.Statement) (len=1 cap=1) {
     (*nanogo.Return)(0xc0002edcd0)({
      Expression: (*nanogo.Mul)(0xc0002f67a0)({
       Left: (*nanogo.Variable)(0xc0002ed0c0)({
        Name: (string) (len=1) "i"
       }),
       Right: (*nanogo.Int)(0xc00025d618)({
        Value: (int64) 2
       })
      })
     })
    }
   })
  })
 },
 Declarations: ([]*nanogo.Declaration) (len=3 cap=4) {
  (*nanogo.Declaration)(0xc0001427a0)({
   Name: (string) (len=1) "i",
   Type: (*nanogo.IntType)(0x15cdc98)({
   })
  }),
  (*nanogo.Declaration)(0xc00026e440)({
   Name: (string) (len=4) "main",
   Type: (*nanogo.FunctionType)(0xc0002696e0)({
    Args: ([]nanogo.Type) <nil>,
    Return: ([]nanogo.Type) {
    }
   })
  }),
  (*nanogo.Declaration)(0xc0002f6a40)({
   Name: (string) (len=6) "double",
   Type: (*nanogo.FunctionType)(0xc00031a360)({
    Args: ([]nanogo.Type) (len=1 cap=1) {
     (*nanogo.IntType)(0x15cdc98)({
     })
    },
    Return: ([]nanogo.Type) (len=1 cap=1) {
     (*nanogo.IntType)(0x15cdc98)({
     })
    }
   })
  })
 }
})

このようなことができるパーサーを作成するために、goyaccというパーサージェネレータを使います。古き良き(?)yaccというパーサジェネレータのGo言語版です。

パーサージェネレータというのは、文法のファイルからパーサーを作ってくれるというツールです。ちなみに、簡単な言語であればパーサーを直書きすることも可能ですが、少し複雑な言語になると直書きは厳しいです。

それでは、文法の定義の一部を見てみましょう。

/* grammar.y */

/* 型のパース */

type: INT64
  { $$ = &IntType{} }
| FLOAT64
  { $$ = &FloatType{} }
| BOOL
  { $$ = &BoolType{} }
| FUNC LEFT_PARENTHESIS types_optional RIGHT_PARENTHESIS LEFT_PARENTHESIS types_optional RIGHT_PARENTHESIS
  { $$ = &FunctionType{$3, $6} }

/* 式のパース */

expression: expression PLUS expression
  { $$ = &Add{$1, $3} }
| expression MINUS expression
  { $$ = &Sub{$1, $3} }
| expression ASTERISK expression
  { $$ = &Mul{$1, $3} }
| expression SLASH expression
  { $$ = &Div{$1, $3} }
| INT_VALUE
  { $$ = &Int{$1} }
| FLOAT_VALUE
  { $$ = &Float{$1} }
| BOOL_VALUE
  { $$ = &Bool{$1} }
| IDENTIFIER
  { $$ = &Variable{$1} }
| LEFT_PARENTHESIS expression RIGHT_PARENTHESIS
  { $$ = $2 }
| IDENTIFIER LEFT_PARENTHESIS expressions_optional RIGHT_PARENTHESIS
  { $$ = &Application{&Variable{$1}, $3} }
| expression EQUAL_EQUAL expression
  { $$ = &Equal{$1, $3} }
| expression EXCLAMATION_EQUAL expression
  { $$ = &Not{&Equal{$1, $3}} }
| expression LESS expression
  { $$ = &LessThan{$1, $3} }
| expression LESS_EQUAL expression
  { $$ = &Not{&LessThan{$3, $1}} }
| expression GREATER expression
  { $$ = &LessThan{$3, $1} }
| expression GREATER_EQUAL expression
  { $$ = &Not{&LessThan{$1, $3}} }
| FUNC LEFT_PARENTHESIS name_and_types_optional RIGHT_PARENTHESIS LEFT_PARENTHESIS types_optional RIGHT_PARENTHESIS LEFT_BRACE statements RIGHT_BRACE
  {
    typ := &FunctionType{Return: $6}
    args := []string{}
    for _, nameAndType := range $3 {
      args = append(args, nameAndType.Name)
      typ.Args = append(typ.Args, nameAndType.Type)
    }

    $$ = &Function{typ, args, $9}
  }

上に出てくるtype, types, expressionというのは変数のようなもので(非終端記号といいます)、文法の再帰的な記述を可能にするなどしています。ファイルではさらに多くの非終端記号が定義されています。

一部分をもう少し詳しく見てみましょう。

type: INT64
  { $$ = &IntType{} }
| FLOAT64
  { $$ = &FloatType{} }
| BOOL
  { $$ = &BoolType{} }
| FUNC LEFT_PARENTHESIS types_optional RIGHT_PARENTHESIS LEFT_PARENTHESIS types_optional RIGHT_PARENTHESIS
  { $$ = &FunctionType{$3, $6} }

というのは、「INT64, FLOAT64, BOOL, FUNC LEFT_PARENTHESIS types_optional RIGHT_PARENTHESIS LEFT_PARENTHESIS types_optional RIGHT_PARENTHESISという4つのトークン列（と非終端記号の組み合わせ）がtypeとして解釈可能である」ということを言っています。|は「または」みたいな意味だということですね。また、$$は結果のようなものを表していて、INT64をtypeとしてパースした結果が&IntType{}であると示しているわけです。

ちなみに、{ ... }ではGo言語のプログラムがそのまま書け、いろいろな処理を挟むこともできます。(expressionのFUNC LEFT_PARENTHESIS ...の箇所が顕著です。この箇所は関数のリテラルをパースするためのものですが、型情報とそれ以外の情報をパース時に分けるために少し複雑になっています)

また、

| expression MINUS expression
  { $$ = &Sub{$1, $3} }

の箇所を考えてみましょう。これは、(式A) - (式B)のような引き算の形の式に対応するケースですが、ここでは式Aが$1に、式Bが$3に対応しています。再帰的な式の構造を表しているわけです。

雰囲気はわかったでしょうか？もちろんほかにもいろいろな記述が必要なのですが(例えば演算子の優先順位など)、それはここでは踏み込みません。yaccの文法(+goyaccの仕様)は調べると出てくるので、気になる人は調べてください。

また、先ほど紹介したGoの仕様においても文法が似たような方式(「終端記号 -> 「トークン列と非終端記号の組み合わせ」の集合」の集合)で書かれています。

文法ファイルはgrammar.yに記述しています。goyaccをインストールし、goyacc grammar.yのようにしてコマンドを実行すると実際のパーサーのプログラムy.goをジェネレートしてくれます。生成されたファイルもVCS下に置くのが慣例のようです。

式の評価と文の実行

さて、構文解析ができたら式の評価と文の実行をできるようにします。山場というわけではないですが、インタプリタの本体のような箇所です。

ここで、「環境」というものを考える必要が出てきます。環境というのは、名前と値の対応付けです。例えば、

func main() () {
  var i int64
  i = 3
  print(i)
}

のようなプログラムのmain関数の実行において

  • 空の環境が作られる
  • 環境に変数iが追加する
  • 環境における変数iの値を3に書き換える
  • 環境から変数iの値を取り出し、出力する

といったことが行われます。

もう少し複雑なものをみてみましょう。

var i int64
func main() () {
  i = 1
  print(i)
  var i int64
  i = 2
  print(i)
  {
    print(i)
    var i int64
    i = 3
    print(i)
  }
  print(i)
}

この場合は

  • グローバルな環境(e1とします)を作成する
  • e1にiを追加する
  • (関数に突入し)環境が拡張される(e1, e2としましょう)
  • e1のiの値を1に書き換える
  • e1のiの値を出力する
  • e2にiを追加する
  • e2のiの値を2に書き換える
  • e2のiの値を出力する
  • (ブロックに突入し)環境が拡張される(e1, e2, e3としましょう)
  • e2のiの値を出力する
  • e3にiを追加する
  • e3のiの値を3に書き換える。
  • e3のiの値を出力する
  • (ブロックから出る)
  • e2のiの値を出力する

といった形になります。出力は12232となるはずです。

このような環境の管理ができるように、次のような構造体を定義してみましょう。

// environment.go

type Environment map[string]interface{}
type Environments []Environment

func (e Environments) Get(name string) interface{} {
    for i := len(e) - 1; i >= 0; i-- {
        if v, exists := e[i][name]; exists {
            return v
        }
    }
    return nil
}

func (e Environments) Set(k string, v interface{}) {
    for i := len(e) - 1; i >= 0; i-- {
        if _, exists := e[i][k]; exists {
            e[i][k] = v
            return
        }
    }
}

func (e Environments) Add(k string, v interface{}) {
    e[len(e)-1][k] = v
}

type Environment map[string]interface{}と、そのスライスtype Environments []Environmentを用いて、上でやったような環境の管理をできるようにしています。

そして、environmentsをEnvironments型として、次のような動作をできるようにしています。

// 環境の拡張
// ブロックに入った時などに使われることを想定
environments = append(environments, Environment{})

// 環境のもっとも最後に拡張された箇所に値を追加
// 宣言文の実行などに使われることを想定
environments.Add("foo", 3)

// 環境の（できるだけ最後に拡張された部分から）変数の値を取得する
// 変数参照の式の評価などに使われることを想定
environments.Get("foo")

// 環境の（できるだけ最後に拡張された部分において）変数の値を更新する
// 代入文の実行などに使われることを想定
environments.Set("foo", 5)

次のような簡単なテストが作っておきます。

// environment_test.go


package nanogo

import (
    "testing"

    "github.com/stretchr/testify/assert"
)

func TestEnvironments(t *testing.T) {
    environments := Environments{Environment{}}

    environments.Add("foo", 1)
    assert.Equal(t, 1, environments.Get("foo"))

    environments = append(environments, Environment{})
    assert.Equal(t, 1, environments.Get("foo"))

    environments.Add("foo", 2)
    assert.Equal(t, 2, environments.Get("foo"))

    environments.Set("foo", 3)
    assert.Equal(t, 3, environments.Get("foo"))

    environments = environments[:len(environments)-1]
    assert.Equal(t, 1, environments.Get("foo"))
}

$ go test . -run TestEnvironments
ok      github.com/kkty/nanogo  0.357s

次に、式の評価を実装しましょう。

空にしていたExpressionインターフェイスを次のように書き換えます。

// expression.go

type Expression interface {
    // Evaluate returns int64, float64, bool or *Closure.
    Evaluate(io.Writer, Environments) interface{}
}

Enviromentsを受け取って何らかの値を返すEvaluate関数を持つということをExpressionインターフェイスとするわけです。

io.Writerは無視しても大丈夫です。(printによる出力先を設定するために使います。出力を含んだテストのために入れています)

足し算の式のEvaluateの実装は

// expression.go

func (e *Add) Evaluate(w io.Writer, environments Environments) interface{} {
    if left, ok := e.Left.Evaluate(w, environments).(int64); ok {
        return left + e.Right.Evaluate(w, environments).(int64)
    }

    return e.Left.Evaluate(w, environments).(float64) + e.Right.Evaluate(w, environments).(float64)
}

のようになるかと思います。まずは左辺の式を評価し、その結果と不変の式の評価結果を足し合わせるということです。整数の足し算と浮動小数の足し算の2通りの可能性があるので、型アサーションが必要になっています。

また、変数の参照を表すVariableのEvaluateの実装は次のようになります。

// expression.go

func (e *Variable) Evaluate(w io.Writer, environments Environments) interface{} {
    return environments.Get(e.Name)
}

ただ環境から名前に対応する値を取ってくるだけです。

さて、気をつけなくてはならないのは、関数の評価(関数の作成)と関数適用の評価(関数に引数を渡して実行する)です。

冒頭で書いたプログラムに

func main() () {
  var add func(int64) (int64)
  add = makeAdder(1)
  print(add(3))
  add = makeAdder(2)
  print(add(4))
}

func makeAdder(i int64) (func (int64) (int64)) {
  return func(j int64) (int64) {
    return i + j
  }
}

というものがありました。makeAdder関数の実行において、関数が評価され、それが返り値となっています。そのとき、

  • 空の環境を作成する
  • 変数iが環境に追加される
  • 変数iの値が関数の呼び出し元から引数で渡された値に書き換えられる
  • 関数func ... { return i + j }が評価される

という事が起こっていると考えることができます。

当たり前だと思う人も多いかもしれませんが、関数が評価されたときの環境は関数適用時(上の例ではadd(...)が呼ばれるとき)にアクセスできないといけません。そうしないとiの値を関数適用時に見つけられないですよね？

そこで、関数を評価したときの値を関数と環境のペア、「クロージャ」とします。クロージャを表す構造体定義、それを用いた関数の評価・関数適用の評価は次のようになります。

// expression.go

type Closure struct {
    Function     *Function
    Environments Environments
}

func (e *Function) Evaluate(w io.Writer, environments Environments) interface{} {
    return &Closure{e, environments}
}

func (e *Application) Evaluate(w io.Writer, environments Environments) interface{} {
    closure := e.Function.Evaluate(w, environments).(*Closure)
   // クロージャに入っていた環境をもとに、それを拡張
    environments = append(closure.Environments, Environment{})
   // 引数を環境に追加
    for i, arg := range e.Args {
        environments.Add(closure.Function.Args[i], arg.Evaluate(w, environments))
    }
   // 関数本体の実行
    for _, statement := range closure.Function.Body {
        if v := statement.Run(w, environments); v != nil {
            return v
        }
    }
    return nil
}

次に、文の実行の定義をしていきます。

// statement.go

func (s *Declaration) Run(w io.Writer, environments Environments) interface{} {
    switch s.Type.(type) {
    case *IntType:
        environments.Add(s.Name, int64(0))
    case *FloatType:
        environments.Add(s.Name, float64(0))
        case *BoolType:
        environments.Add(s.Name, bool(false))
    case *FunctionType:
        environments.Add(s.Name, new(Closure))
    }

    return nil
}

func (s *Assignment) Run(w io.Writer, environments Environments) interface{} {
    environments.Set(s.Left, s.Right.Evaluate(w, environments))
    return nil
}

func (s *If) Run(w io.Writer, environments Environments) interface{} {
    if s.Condition.Evaluate(w, environments).(bool) {
        return s.Block.Run(w, environments)
    }
    return nil
}

func (s *For) Run(w io.Writer, environments Environments) interface{} {
    for s.Condition.Evaluate(w, environments).(bool) {
        if v := s.Block.Run(w, environments); v != nil {
            return v
        }
    }
    return nil
}

func (s *Return) Run(w io.Writer, environments Environments) interface{} {
    return s.Expression.Evaluate(w, environments)
}

func (s *Print) Run(w io.Writer, environments Environments) interface{} {
    fmt.Fprint(w, s.Arg.Evaluate(w, environments))
    return nil
}

func (s *Application) Run(w io.Writer, environments Environments) interface{} {
    s.Evaluate(w, environments)
    return nil
}

ブロックやfor文、if文の途中においてreturn文が実行されたとき、その文は途中で実行を終了し、関数に呼び出し元に値を返す必要があります。そのために返り値を用いています(nilでなければ文の実行中にreturn文が実行されたということです)。

最後にプログラム全体を実行するコードを書いていきます。

// program.go

func (p *Program) Run(w io.Writer) {
    environments := Environments{Environment{}}
   // 宣言文を実行(環境に変数を追加する)
    for _, declaration := range p.Declarations {
        declaration.Run(w, environments)
    }
   // 代入文を実行(特に、関数を代入する)
    for _, assignment := range p.Assignments {
        assignment.Run(w, environments)
    }
   // 環境からmainという名前のクロージャを取り出してきて実行
    closure := environments.Get("main").(*Closure)
    closure.Function.Body.Run(w, closure.Environments)
}

これで動くものが完成で、冒頭で作ったテストが通ります。

$ go test ./test -v
=== RUN   TestParseAndRun
=== RUN   TestParseAndRun/Case0
=== RUN   TestParseAndRun/Case1
=== RUN   TestParseAndRun/Case2
=== RUN   TestParseAndRun/Case3
=== RUN   TestParseAndRun/Case4
--- PASS: TestParseAndRun (0.02s)
    --- PASS: TestParseAndRun/Case0 (0.00s)
    --- PASS: TestParseAndRun/Case1 (0.00s)
    --- PASS: TestParseAndRun/Case2 (0.00s)
    --- PASS: TestParseAndRun/Case3 (0.00s)
    --- PASS: TestParseAndRun/Case4 (0.00s)
PASS
ok      github.com/kkty/nanogo/test

やったね！

また、パスを受け取ってファイルからソースコードを読み込み、それをパースして実行するプログラムを作成しておきます。

// cmd/nanogo/nanogo.go

package main

import (
    "flag"
    "io/ioutil"
    "log"
    "os"

    "github.com/kkty/nanogo"
)

func main() {
    flag.Parse()
    b, err := ioutil.ReadFile(flag.Arg(0))
    if err != nil {
        log.Fatal(err)
    }
    program := nanogo.Parse(string(b))
    program.Run(os.Stdout)
}

次のようにしてプログラムを実行できるようになりました。

$ go run cmd/nanogo/nanogo.go /path/to/program

型検査など(おまけ)

インタプリタだけで走らせる言語ならば型はなくてもなんとかなるのですが、コンパイル可能なほとんど全ての言語には型の概念があります。コンパイルする(実際のマシンなどで実行できるアセンブリを出力する)ためには各変数のサイズが決まる必要があったり、データの種類によって扱えるレジスタが異なるためです。

そしてもちろんGoには型があるのですが、(パースできるようにはしていたものの)それ以外で型は無視してきました。

そのままだと少しもったいないので、その型情報を用いて、型検査を行うことにします。すなわち、「プログラムを実行する前に、型が合っているかをチェックし、そうでなければ実行しない」ということです。プログラムのミスに事前に気づくことができ、実行時エラーを発生させないようにできます。

...と思ったのですが、こちらはちょっと間に合いませんでした。ということで、また気が向いた時に後編として書くことにします。

最後まで読んでいただき、ありがとうございました。何か質問があれば気軽にコメントをいただければ幸いです。そして後編もお楽しみに。