Go言語でGo言語のインタプリタを作る(前編)

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

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

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

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

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

構文の決定

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

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

また、パース(後述)しやすいようなものに構文を制限します。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として解釈可能である」ということを言っています。|は「または」みたいな意味だということですね。また、$$は結果のようなものを表していて、INT64typeとしてパースした結果が&IntType{}であると示しているわけです。

ちなみに、{ ... }ではGo言語のプログラムがそのまま書け、いろいろな処理を挟むこともできます。(expressionFUNC 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を用いて、上でやったような環境の管理をできるようにしています。

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

// 環境の拡張
// ブロックに入った時などに使われることを想定
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通りの可能性があるので、型アサーションが必要になっています。

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

// 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には型があるのですが、(パースできるようにはしていたものの)それ以外で型は無視してきました。

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

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


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

少し凝ったことを(簡単に)できるリバースプロキシサーバーをGoで書いてみた

リバースプロキシで少し凝ったことをする際、Nginx+Luaで頑張るなど、いくつか手法があります。しかし、(個人の意見ですが)どれも使い勝手がいいとは言えません。そこで、「使い勝手のよく、少し凝ったことのできるリバースプロキシサーバー」を作ってみました。

実装はGoで、レポジトリはここです。

github.com

名前はScript+ProxyでScriproxyです。安直ですね。

特徴

  • スクリプトを用いて、アップストリームサーバー(プロキシ先)を動的に設定できるリバースプロキシサーバーです。リクエストヘッダーの値や、URLクエリの値、リクエストパスなどをスクリプト内で用いることができます。
  • Tengoを使っており、Goのような直感的な文法でスクリプトを書くことができます。また、よくできた標準ライブラリもあります。
  • アップストリームを指定するだけでなく、リクエストヘッダーの値やクエリの値、リクエストパスを書き換えることもできます。

インストール

$ go install github.com/kkty/scriproxy

使い方

$ scriproxy --help
Usage:
  scriproxy [OPTIONS]

Application Options:
      --script=    The path to a tengo script for rewriting requests
      --libraries= The tengo libraries used in the script, separated by commas

Help Options:
  -h, --help       Show this help message

--scriptコマンドライン引数で、スクリプトへのパスを指定します。スクリプトの例は、次のセクションで紹介します。

Tengoを内部で使っています. Tengoには質の良い標準ライブラリがあり、それをスクリプト内で用いることもできます。その際は、--librariesコマンドライン引数で、使用しているライブラリを指定する必要があります。例えば、textライブラリとfmtライブラリを用いたい場合には--libraries=text,fmtのようにします。

つまり、具体的な起動コマンドは以下のようになります。

$ scriproxy --script /path/to/script.go --libraries fmt,text

スクリプト例

(実際のシチュエーションを想定したものというよりも、)Scriproxyによって何が可能なのかがわかりやすいものを紹介します。もちろん、これらを組み合わせて更に複雑なこともできます。

スクリプト内で使える値や関数については次のセクションで補足しています。

シンプルなプロキシ

// req.urlは、プロキシ先のURLに対応します
req.url.scheme = "https"
req.url.host = "example.com"

// req.hostは、リクエストヘッダの`Host: ...`に設定される値に対応します
// 通常はこれを設定する必要があります(多くの場合、req.url.hostと同じ値になります)
req.host = "example.com"

このスクリプトによって、プロキシサーバーに対して送られたリクエストはhttps://example.comに流されます。リクエストヘッダの値やクエリパラメータの値は変更されずにプロキシ先に送られます。

クエリパラメータを用いる場合

アップストリームサーバーの選択にクエリパラメータを用いることができます。

// クエリパラメータから値を取得する
req.url.host = req.url.query.get("host")
req.url.scheme = req.url.query.get("scheme")

// アップストリームサーバーへのリクエストにはそれらのパラメータが含まれないようにする
req.url.query.del("host")
req.url.query.del("scheme")

// これは多くのケースで必要!
req.host = req.url.host

このスクリプトを用いると、 /foo?host=example.com&scheme=httpへのリクエストはhttp://example.com/fooに、/foo?host=example.org&scheme=httpsへのリクエストはhttps://example.org/fooへと流されます。

Hostヘッダーを用いる場合

リクエストヘッダーのHostの値を用いてプロキシ先を指定することもできます。

// `--libraries=text`をコマンドライン引数で指定する必要があることに注意!
text := import("text")

// "example.com.local"や"example.com.secure.local"のような値がHostヘッダーとして指定されていることを前提としている

splitted := text.split(req.host, ".")
l := len(splitted)

if splitted[l-2] == "secure" {
  req.url.scheme = "https"
  req.url.host = text.join(splitted[:l-2], ".")
} else {
  req.url.scheme = "http"
  req.url.host = text.join(splitted[:l-1], ".")
}

req.host = req.url.host

(Scriproxyに対するリクエストの)リクエストヘッダにHead: example.com.secure.localが指定されていればhttps://example.comに、example.com.localが指定されていればhttp://example.comにリクエストがプロキシされます。

リクエストヘッダを用いる場合

Host以外のリクエストヘッダを用いることもできます。

// `--libraries=text`をコマンドライン引数で指定する必要があることに注意!
text := import("text")

// "User-Agent"ではなく"user-agent"とすることも可能
// 関数の挙動は https://golang.org/pkg/net/http/#Header.Get に沿っている
ua := req.header.get("user-agent")
ua = text.to_lower(ua)

if text.contains(ua, "iphone") {
  req.url.host = "example.com"
} else {
  req.url.host = "example.org"
}

// ユーザーエージェントの値を上書き
req.header.set("user-agent", "my-proxy")

req.url.scheme = "https"
req.host = req.url.host

このスクリプトを用いると、iPhoneからのリクエストはhttps://example.orgに、それ以外のリクエストはhttps://example.comに流されます。

req.header.set("host", "...")は機能しません。Hostヘッダーを書き換える際にはreq.hostを書き換える必要があります。これは、Goのhttp.Requestの挙動に沿っています。

補足

  • req.host, req.url.scheme, req.url.host and req.url.pathが値として使え、書き換えることもできます。
  • req.url.query.get("key"), req.url.query.set("key", "value"), req.url.query.del("key")の4つの関数がクエリパラメータの参照/書き換えに使用できます。
  • req.header.get("key"), req.header.set("key", "value"), req.header.add("key", "value"), req.header.del("key")の4つの関数がリクエストヘッダの参照/書き換えに使用できます。
  • 以上の値/関数の挙動はGoのhttp.Requestと似せています。
  • 4コアマシンで秒間数千リクエスト通せるはずです。
  • ロギングの機能も入れています。

tcコマンドとDockerコンテナを用いて遅いネットワークをシミュレートする

「手元で、できるだけ実際の環境に近い環境でプログラムの挙動を確認したい」ということがあるかと思います。そこで今回は、遅い(レイテンシの高い)ネットワークをDockerコンテナを用いてシミュレートする具体的な方法を紹介します。

準備

以下のファイルを作成していきます。

  • docker-compose.yml
  • client/Dockerfile
  • server/Dockerfile
  • server/main.go

docker-compose.yml

ネットワーク周りをいじるため、cap_addNET_ADMINを指定する必要があります。

version: "3.0"
services:
  client:
    container_name: client
    build: ./client
    tty: true
    cap_add:
    - NET_ADMIN
  server:
    container_name: server
    build: ./server
    cap_add:
    - NET_ADMIN

client/Dockerfile

クライアント側のコンテナを用意します。

後にtcコマンドを用いるので、そのためにiproute2を入れておきます。また、検証用として使うためにpingコマンドも入れておきます。

FROM ubuntu:18.04
WORKDIR /work
RUN apt-get update && \
    apt-get install iproute2 iputils-ping -y

server/Dockerfile

サーバー側を用意します。Nginxとかでもいいんですが、なんとなくGo言語でサーバープログラムを用意することにします。こちらにおいてもtcコマンドを使えるようにします。

FROM ubuntu:18.04
WORKDIR /work
RUN apt-get update && \
    apt-get install software-properties-common -y && \
    add-apt-repository ppa:longsleep/golang-backports && \
    apt-get update && \
    apt-get install golang-go iproute2 -y
ADD main.go .
CMD ["go", "run", "main.go"]

server/main.go

net/httpパッケージを用いた、単純なGoのhttpサーバーです。

package main

import (
    "log"
    "net/http"
)

func main() {
    http.HandleFunc("/", func(w http.ResponseWriter, r *http.Request) {
        w.Write([]byte("Hello, World!"))
    })

    log.Fatal(http.ListenAndServe(":80", nil))
}

レイテンシを追加する

準備ができたので、実際にレイテンシを追加し、それを確認します。

まず、以下のようにして2つのコンテナを起動します。

docker-compose up -d

次に、以下のtcコマンドを実行します。これによって、各コンテナのアウトバウンドトラフィックに100msのレイテンシが追加されます。なお、docker-compose.ymlNET_ADMINを指定していないと、ここでRTNETLINK answers: Operation not permittedと怒られるはずです。

$ docker exec client tc qdisc add dev eth0 root netem delay 100ms
$ docker exec server tc qdisc add dev eth0 root netem delay 100ms

実際に確認してみましょう。RTTは200ms+αになるはずです。

今回作られたコンテナでは、serverというホスト名がserverコンテナのIPアドレスに解決されます。なので以下のようにしてクライアント側からサーバー側に対してpingコマンドが打てます。

$ docker exec client ping server
PING server (172.19.0.3) 56(84) bytes of data.
64 bytes from server.tc_default (172.19.0.3): icmp_seq=1 ttl=64 time=202 ms

正しく設定できていることがわかります。

何が起きているのか

Dockerコンテナを立ち上げる際、仮想ネットワークインターフェイスが作成されます。

仮想ネットワークインターフェイスはペアとして作成され、片方はホストに、片方はコンテナに属することになります(ネットワーク名前空間というものが使われます)。また、ホスト側のネットワークインターフェイスは仮想のブリッジに接続されます。これにより、コンテナ間の通信などができるようになっています。Dockerのネットワーク関係の話についてはこちらが詳しいです(英語です)。

ところで、Linuxで外向きにトラフィックを送ろうとするとき、それはキューに入ります。通常では、キューに入った順から可能な限り速いスピードで外部へと送られていきます(FIFO)。しかし、Linuxではそのキューの動作を変更することが可能になっています。例えば、レイテンシを追加したり、ある確率でデータを破棄したりといった具合です。この機構をQueueing Discipline、略してqdiscと言います。tc qdisc ...コマンドは、まさにそのキューを設定するためのものだったわけです(ここで上げたエミュレーション以外にも様々なことが設定できます)。

ネットワークインターフェイス毎にqdiscの設定ができます。上のコマンドでは、eth0ネットワークインターフェイスに対応するqdiscに100msのレイテンシを追加しています。eth0というのは、Dockerにおいてホスト側とつながっている仮想ネットワークインターフェイスです。

ちなみに、今回はクライントとサーバー、双方でtcコマンドを実行しました。これは、qdiscは(原則として)外向きのトラフィックに関係するものだからです。双方向に100msかかるネットワークを作るために、それぞれでqdiscの設定をしたということです。

Prologの処理系をTypeScriptで書いてみた

言語仕様の一部しか実装していませんが、一応動くものができたので公開してみます。(v10以降の)Node.jsが必要です。

github.com

Prologとは

論理型プログラミング言語の一つです。論理学をプログラミング言語に落とし込んだようなもので、「ある論理式の集合からある論理式が導けるか」みたいなものが判定できます。もう少し広げて、(論理式内に自由変数を導入し)「論理式の集合が与えらたとき、その中の各自由変数をどのような項で代入するとゴールとなる論理式が導けるか」というクエリの処理が可能です。

Wikipediaの記事が恐ろしいほど詳しいです。よく使われる処理系としてSWI-Prologがあります。

使い方

npmパッケージとして公開しています。以下のようにして使えます。

$ npm install ts-prolog -g
$ ts-prolog

使用例

以下のようなファイルをrules.plとして保存します。足し算の定義や掛け算の定義、自然数の定義などが書いてあります。

mult(z, X, z).
add(z, Y, Y).
add(s(X), Y, s(Z)) :- add(X, Y, Z).
mult(s(X), Y, Z) :- mult(X, Y, P), add(P, Y, Z).
nat(z).
nat(s(X)) :- nat(X).

以下のような形で使用できます。足し算してみたり、掛け算してみたり、自然数の集合を取得してみたり、足し算と掛け算の2つ式を連立方程式としてその解を求めたり、ということをしています。

$ ts-prolog
> ['rules.pl'].
fact added: mult(z, X, z)
fact added: add(z, Y, Y)
rule added: add(s(X), Y, s(Z)) :- [add(X, Y, Z)]
rule added: mult(s(X), Y, Z) :- [mult(X, Y, P), add(P, Y, Z)]
fact added: nat(z)
rule added: nat(s(X)) :- [nat(X)]

> add(s(z), s(s(z)), X).
[X -> s(s(s(z)))]  (ENTER)
search finished

> add(s(z), X, s(s(s(z)))).
[X -> s(s(z))] (ENTER)
search finished

> mult(s(s(z)), s(s(s(z))), X).
[X -> s(s(s(s(s(s(z))))))] (ENTER)
search finished

> nat(X).
[X -> z] (ENTER)
[X -> s(z)] (ENTER)
[X -> s(s(z))] (ENTER)
[X -> s(s(s(z)))] (ENTER)
[X -> s(s(s(s(z))))] (Ctrl-C)

> add(X, Y, s(s(z))).
[X -> z, Y -> s(s(z))] (ENTER)
[X -> s(z), Y -> s(z)] (ENTER)
[X -> s(s(z)), Y -> z] (ENTER)
search finished

> add(X, Y, s(s(z))), mult(X, Y, s(z)).
[X -> s(z), Y -> s(z)] (ENTER)
search finished

実装について

パーサ

特にライブラリは使わずに、自分で簡単なものを実装してみました。LR構文解析器などを作っても良かったのですが、比較的文法が単純なことから、正規表現などをつかってゴリゴリやってしまっています。完璧ではないはずです。

本体

  • ファンクタ(「使用例」のadd, natなど)を表すFunctorクラス
  • 定数(「使用例」のzなど)を表すConstantクラス
  • 変数(「使用例」のX, Yなど)を表すVariableクラス
  • ファンクタの項への適用(add(X, Y, Z)など)を表すApplicationクラス

を定義し、項を表すTerm型をtype Term = Functor | Constant | Variable | Applicationのようにして定義しています。

また、次のようなクラスも用意しています。

  • 述語を表すPredicateクラス
  • ファクト(例: nat(z).でゼロは自然数であることを表現する)を表すFactクラス
  • ルール(例: nat(s(X)) :- nat(X).でXが自然数ならばXに1を足したものが自然数であることを表現する)を表すRuleクラス
  • ゴール(例: nat(X).で自然数であるようなものを探したいことを表現する)を表すGoalクラス

ゴールとファクト/述語を単一化(unification)するために制約を表すConstraintクラスを用意しており、Constraint.unify(terms: Term[])によって、単一化ができるようになっています(自由変数への項の代入を表すSubstitutionクラスを返します)。

一番メインとなるのがSpaceクラスで、これはルールの集合とファクトの集合です。Space.query(goals: Goal[])によって、その空間内での探索が始まります。これは基本的には「自由変数から項へのマッピング」の列を返します。例えば上の例だとnat(X)[[X -> z], [X -> s(z)], ...]のようなものを返します。これは無限列になることがしばしばあるため、イテレータを返すようにしています。

SWI-PrologなどはDFSですが今回はキューを用いてBFSでやってみています。無限ループに陥るゴールの集合が少し変わります。自分はこちらのほうが直感的な気がします。

CLI

インターフェイスについては特にユーザーランドのライブラリなどは用いず、Node.jsコアのreadlineモジュールを利用しました。Ctrl-Cのキャプチャなど、案外いろいろなことができます。

ユーザーからのインプットを受け取り、次のようなことをします。

  • ファイルの読み込みが要求されたらそのファイルを開いてルールとゴールを追加する
  • クエリ(ゴールの集合)が入力されたらそれに対する答え(自由変数から項へのマッピング)を一つずつ(すべての探索が終了するかCtrl-Cが押されるまで)出力する

ソースコード

こちらで公開しています。なにか質問や疑問、バグなどあれば教えていただけると嬉しいです。

github.com

Dockerイメージのビルド時にシンボリックリンクの実体を含める

タイトルがわかりにくいですが...

事の発端

以下のような構成のディレクトリがあったとします。

  • /foo (共有したいファイル)
  • /bar/foo (/fooへのシンボリックリンク)
  • /bar/Dockerfile
  • /baz/foo (/fooへのシンボリックリンク)
  • /baz/Dockerfile

そして、{bar,baz}/DockerfileCOPY foo ...のような記述があったとします。

そのとき、fooとbarの各ディレクトリにおいてdocker build .のようなコマンドで(そのディレクトリをコンテキストとして)dockerイメージをビルドしようとするとエラーが出ます。具体的にはCOPY failed: Forbidden path outside the build contextと言われます。

「それはそう」という感じなのですが、このような場面において「ファイルを追加する際、それがシンボリックリンクならばそれをたどって実体をイメージに追加する」といったことができても便利なのではないかと思ったりすることがありました。

解決策

ここでなるほどと思う解決策を見つけました。

docker build .の代わりにtar -czh . | docker build -ようにすればよい」というものです。

具体的にはこのような感じのことが起こっています。

  • tar -czh .で、カレントディレクトリをgzipにアーカイブする。その際、シンボリックリンクが存在した場合はそれをたどり、辿った先のファイルの内容でそのリンクを置き換える(-hオプション)。
  • それをコンテキストとしてdocker buildにわたす。

なるほどなあという感じですね。

実際にやってみると、このようにうまくいきます。

$ echo 'foo' > foo
$ mkdir bar
$ cd bar
$ ln -s ../foo foo
$ cat <<EOF >Dockerfile
FROM busybox
WORKDIR /work
COPY foo .
EOF
$ tar -czh . | docker build -
Sending build context to Docker daemon  10.24kB
Step 1/3 : FROM busybox
 ---> e4db68de4ff2
Step 2/3 : WORKDIR /work
 ---> Using cache
 ---> 2daef8292bd0
Step 3/3 : COPY foo .
 ---> Using cache
 ---> 1ec7cbed7c90
Successfully built 1ec7cbed7c90
$docker run -it 1ec7cbed7c90
/work # cat foo
foo

tar -czh . | docker build -docker build .におきかえるとエラーがでることも確認できます。


ちなみに執筆時点でのdockerのバージョンは以下の通りでした。

$ docker --version
Docker version 18.09.2, build 6247962

Docker上のUbuntuでmanページなどを見れるようにする

問題

コンテナにおいてイメージサイズの小ささは正義です。 そのため、UbuntuのDockerイメージはいろいろなものを削り落としています。その削り落とされているものの一つとして、manページが挙げられます。

例えば、次のようにUbuntuのイメージからコンテナを起動してmanコマンドを実行するとエラーがでます。

$ docker run -it ubuntu:18.04
root@[...]:/# man read
bash: man: command not found

「Mac上のDockerコンテナでLinuxのシステムプログラミングをしたい」という状況にあり、どうにかならないかと思っていました。

解決策

つまらないのですが、コンテナ内でunminimizeというプログラムを実行することにより解消することができます。

実際にコンテナ内のシェルでunminimizeを実行すると次のようになります。「インタラクティブな使用がメインでないシステムに不要なパッケージやコンテンツは削除されているよ。このコマンドはそれを復活させるよ。少し時間かかるけれどそれでもよければyを入力してね。」(超意訳)みたいなことを言われます。

$ unminimize
This system has been minimized by removing packages and content that are
not required on a system that users do not log into.

This script restores content and packages that are found on a default
Ubuntu server system in order to make this system more suitable for
interactive use.

Reinstallation of packages may fail due to changes to the system
configuration, the presence of third-party packages, or for other
reasons.

This operation may take some time.
Would you like to continue? [y/N]y

yを入力し、処理が終了すると実際にmanコマンドが使えるようになっていることがわかります。

$ which man
/usr/bin/man

unminimize済みのイメージを作るともちろんサイズはかなり大きくなります。普通のUbuntuのイメージは100MBくらいなのですが、以下のようなDockerfileを作成してイメージをビルドしてみると400MBくらいになりました。

FROM ubuntu:18.04
RUN apt-get update && yes | unminimize

安全で軽量なコンテナランタイム「gVisor」について

f:id:k-kty:20190505233414p:plain
gVisorのロゴ

「少し聞いたがことある」程度だったのですが、Software Engineering Dailyというポッドキャストのエピソードで耳にしたのを機に、gVisorについて調べてみました。そして日本語の情報もあまり多くなかったので軽く記事にしました。

gVisorとは

gVisorは、安全かつ軽量なコンテナのランタイムです。2018年のKubeConでGoogleから発表されました。

この記事では

  • なぜgVisorが開発されたのか
  • gVisorの仕組み・特徴

などを見ていきます。

なぜgVisorが開発されたのか

分離された環境を簡単に用意できるコンテナ技術は、開発においてもデプロイにおいても大変便利ですが、セキュリティ面での分離はできません。

カーネル(+仮想的なマシンリソース)を複数用意することになる仮想マシンに比べ、「一つのカーネルをうまく共有して使う」ようになっているコンテナにはパフォーマンス面でのメリットがあります。しかし、そのメリットと表裏一体となってセキュリティ面でのデメリットが存在します。カーネルの脆弱性の影響をもろにうけてしまうわけです。

実際、CVE-2016-5195というLinuxカーネルの脆弱性のPoCの中に、Dockerコンテナ内からホストマシンのrootを奪取してしまうというものがあったようです。

よって、悪意のある処理が含まれうるコンテナを実行する必要のある組織(例えばIaaSを提供している企業)は「ホストマシン上で直でコンテナを動かす」ということはできません。そして、各コンテナに対して仮想マシンを用意するなどしなくてはならず、リソース利用の効率やパフォーマンスの面で問題がありました。

そのジレンマへの一つのアプローチとしてgVisorが開発されました。

gVisorの仕組み・特徴

gVisorは「ユーザー空間で動くカーネル」のようなものです。コンテナ内のアプリケーションが出したシステムコールをインターセプトして処理します。

Linuxの各システムコールの実装に対応する実装がgVisor内にあり、アプリケーションが出したシステムコールは(gVisorによって横取りされ)その実装によって処理されます。そして、gVisorが必要に応じてホストOSに対してシステムコールを投げるようになっています。gVisorからホストOSに対して発行されるシステムコールの種類は意図的に絞られています。(Linuxのseccompというのがありますね)。

アプリケーションから「数多くの種類の」システムコールを「ホストのカーネルに直接」発行することができてしまう通常のコンテナランタイムと比べると、明らかに安全になっていることがわかります。システムのうちアプリケーションから直接アクセス可能な部分を最小限にする、すなわちアプリケーションとシステムの分離のレベルを上げることでセキュリティを向上させているわけです。

また、(仮想的なマシンリソースを用意する必要がある)仮想マシンを用いた仮想化に比べるとオーバーヘッドは小さく、そして柔軟性が高まっています。仮想マシンだと起動時にメモリの容量などを決めないといけないですが、gVisorを用いると(普通のプロセスと同様で)そんなことはありません。

使い方

おなじみのDockerやKubernetesで簡単に使えます。公式のガイドも整っています。

gVisorが提供するコンテナのランタイムはOpen Container Initiativeの仕様に準拠していて、docker run --runtime=runsc ...のように指定すれば使えるようです。

現在はx64上のLinuxのみのサポートのようです。(詳しい数値は少しわかりませんが...)エンタープライズのクラウドの世界では大多数ですよね?

実用例

GCPのCloud Runが先月発表されて盛り上がっています。(自分も少し触ってみて感動しています。)

そのCloud Runですが、ドキュメントによるとgVisorが用いられているみたいです。

パーフェクトマッチな用途ですね。

また、gVisorの発表(2018年)以前からGoogleの内部では使われてきたようです。

参考

この記事では大枠のみになってしまいましたが、いろいろと参考になるリソースがありますので、興味のある人は覗いてみてください。

公式ページでは使い方のほか、アーキテクチャや開発のモチベーションなども触れられています。

GoogleでPMをされているYoshi Tamuraさんのインタビューも参考になりました。憧れます。

冒頭でも紹介しましたがSoftware Engineering Dailyのエピソードも参考になりました。実はこちらもYoshi Tamuraさんのインタビューです。

レポジトリはこちら。メモリ安全性や型安全性が評価され、Goを用いて実装されたようです。Dockerの実装もGoですしKubernetesの実装もGoですし大人気ですね。

おまけ: Kata Containers

コンテナとセキュリティに関連するプロジェクトとしてはKata Containersというのも有名なようです。こちらではKata Containers is an open source container runtime, building lightweight virtual machines that seamlessly plug into the containers ecosystem.と謳っていて、「軽量な仮想マシン」を用いることで安全なコンテナの実行環境を用意できるようです。gVisorとは少し違ったアプローチでとても興味深いので気が向いたときに調べてみようかと思います。