この記事は Go Advent Calendar 2014、16日目の記事です。

はじめに

Matz さんが streem という、ストリーム指向言語の開発を始めるらしいです。

まだ文法の設計段階ではあるけど、それなのにかなりの量の pull-req がバンバンと来てて凄いなーと思いつつも「この pull-req 量だと僕には出番無いなー」と思ったので、README.md に書かれているサンプルだけを頼りに streem を golang で実装してみました。

先日はネタで streem のマネをして yacc 定義部分だけ公開していましたが、本日ネタが無い中にTLがヒートアップして焦りに焦って勢いで実装してみました。いやはや異様な追い込みを感じます。。。

まずは streem を知る

streem は README.md に書かれている通り並列実行を行いつつストリームを処理する言語です。
README.md の例によると以下の様な言語です。

seq(100) | {|x|
 if x % 15 == 0 {
   "FizzBuzz"
 }
 else if x % 3 == 0 {
   "Fizz"
 }
 else if x % 5 == 0 {
   "Buzz"
 }
 else {
   x
 }
} | STDOUT

seq は 100 までのシーケンス番号をダラダラと吐き続ける連番生成器を作成する関数。
{|x| ... } は関数オブジェクトを表し、入力を引数として受け取って戻り値を出力として扱うフィルタ関数。
STDOUT は入力を標準出力に吐くオブジェクトとなり、この3つを並列(concurrency)で実行します。現在その言語仕様について issues で議論が白熱していますが今回の実装は上記が動くまでとします。
golang は concurrency が得意な言語です。スレッド間通信も chan を使えば楽に実装出来ます。golang の為の仕様と思える程です。
本記事では streem を golang に移植(といっても本体はまだ実装がありませんが)しつつ、こういったプログラミング言語を golang で実装していくにはどの様にすれば良いかを簡単ながら解説して行きたいと思います。

プログラミング言語に必要な物

プログラミング言語はおおよそ、構文解析器、字句解析器、処理系と分かれます。
構文解析器はソースを命令や式に分解する物、字句解析器はソースに埋め込まれた数値や文字列等を実際の処理部が扱えるデータに置き換える物になります。
処理系はコンパイル型言語とそうでない物(スクリプト言語)で大きく異なりますが、今回の場合だとスクリプト言語で良さそうです。

構文解析器・字句解析器を作る

実はプログラミング言語を作る際のこの工程が一番難しく(少なくとも僕は)、リテラルに対してどの様に言語が働きかけるか、どの様にデータを保持すべきかを考えながら作らないといけませんし、根幹部分である為あとから仕様を変更するとなると修正が大規模になり破綻します。
例えば streem の場合、関数ブロックの中で

x = 1 | 2

という記述が出来る(様になる)はずですが、パイプラインの構文

seq(100) | STDOUT

とバッティングしてしまいます。この辺を上手く書いていかないと破綻する訳ですね。詳しくは YACC について調べて下さい。

streem は yacc で構文解析器が定義されていますが golang でも yacc を使います。
golang には YACC ツールが標準で付属しています。詳しくは go tool yacc コマンドのヘルプを参照下さい。
実際は、anko のパーサ部分から必要そうな物をまるっとコピーしているので使われていない無駄な定義が残っていたりしますが、これは今後 Matz さんが streem に入れてくるだろうなーと思われる物を残している意図もあります(ウソです。雑なだけです)。ただ変態的な文法でない限り四則演算や文字列判定といった処理は同じはずなので実装は使いまわせるのです。1.2 とソースに書いてあって、とある言語では浮動小数点と解釈し、とある言語では文字列として解析する、なんて事はめったに遭遇しませんからね。
一から構文解析器を作成する際は、その命令に対して必要な情報を全て格納する為の箱を作ります。そしておおよそこの箱はツリー上に展開されます。これが AST (抽象構文木) と呼ばれる物です。

C言語でプログラミング言語を書いてみたい人は手前味噌ですが

Big Sky :: プログラミング言語の作り方

この辺を参考にするか、mruby のソースを見ると勉強になります。ただし mruby (というか ruby) の文法はとても複雑なので少し気合が必要です。
具体的な話をします。例えば三項演算子を考えてみます。三項演算しを処理したい場合

条件(Expr)
条件が正の場合の値(Lhs)
条件が負の場合の値(Rhs)

の3つの情報が必要になります。よって定義は以下の様になります。

    … 省略 …
	| expr '?' expr ':' expr
	{
		$$ = &ast.TernaryOpExpr{Expr: $1, Lhs: $3, Rhs: $5}
		$$.SetPosition($1.Position())
	}
    … 省略 …

そして格納する箱は以下の様になります。

type TernaryOpExpr struct {
	ExprImpl
	Expr Expr
	Lhs  Expr
	Rhs  Expr
}

上記で書いた3つの要素をフィールドに保持しています。三項演算子の中に三項演算子が書かれる事もあります。ですので Expr の中に Expr が埋め込まれます。
さらに一般的な手続き型プログラミング言語の構文は「式」と「命令」に分解でき、おおよそ「命令」は「式」の集合で出来ています。例えば streem のパイプライン foo | bar | baz は foo と bar と baz という式の集合から構成されていますので定義は以下の様になります。

stmt : expr '|' expr
	{
		$$ = &ast.PipeLine{Exprs: []ast.Expr{$1, $3}}
		$$.SetPosition($1.Position())
	}
	| stmt '|' expr
	{
		$1.(*ast.PipeLine).Exprs = append($1.(*ast.PipeLine).Exprs, $3)
		$$.SetPosition($1.Position())
	}
	| expr
	{
		$$ = &ast.ExprStmt{Expr: $1}
		$$.SetPosition($1.Position())
	}

expr :
    … 省略 …
	| expr '|' expr
	{
		$$ = &ast.BinOpExpr{Lhs: $1, Operator: "|", Rhs: $3}
		$$.SetPosition($1.Position())
	}
    … 省略 …

定義が変則的に見えますが、これは stmt がパイプラインよりも先にビットOR演算子を先に解釈してしまわない為のトリックです。
stmt は命令、expr が式となります。解析は上位(stmt:命令)から行いますので、命令として式の集合が先に見つかる場合は PipeLine を、純粋に式として認識出来る場合はビットORオペレータとなります。
そしてここから他の言語に比べて golang が有利な部分が出てきます。構文解析器がソースを解析すると、式(Expr)を含む命令(Stmt)の配列が得られるのですが、C言語で書く場合は全てがポインタで処理されてしまうので

次の AST は三項演算子を表す構造体だよ

という情報を構造体自身に保持しなければなりません。しかし golang の場合はリフレクションが可能です。必要な情報だけを格納する構造体を宣言すれば良い事になりソースがとても見渡し良くなります。switch 文 stmt := stmt.(type) が各型でバインドされるのもとても便利です。
さて、構文解析が出来たら実行部分を作ります。おおよそ anko からコピーしてきているので四則演算や文字列結合などはそのまま使い回します。
問題は PipeLine 部分です。

type PipeLine struct {
	StmtImpl
	Exprs []Expr
}

PipeLine 自身は式ではなく命令として定義しています。この内包ですが実はとても便利な機能なのです。

ちょっと横道にそれて golang の構造体について

例えば、ある Web API に JSON を POST する際にユーザから

{
  "key1": "value1",
  "key2": "value2"
}

という構造を受け取りたいとしますしかし、実際には

{
  "key1": "value1",
  "key2": "value2",
  "authentication": "XXXXX"
}

をポストしたいとします。2つ構造体を作るのは嫌ですし、かといってユーザに authentication のフィールドを触らせたくはありません。
そこで構造体の内包を使います。

type UserInput struct {
    Key1 string `json:"key1"`
    Key2 string `json:"key2"`
}

type postData struct {
    UserInput
    Authentication string `json:"authentication"`
}

ユーザからは UserInput 構造体で貰い、ポスト時には

var data postData
data.UserInput = userInput
data.Authentication = "XXXXX";

といった具合に上書きします。これでユーザに authentication を触らせる事なく欲しいデータのみをユーザから入力して貰えます。
この手法はgolangで実装した雑談対話botでも使われています。

繋げる

さて、解析結果を実行する部分は anko に既にあるのでそれを使い、一気に組み上げます。
PipeLine は複数の式から構成されているのでこの Exprs を channel で繋げ、各要素を goroutine で並列実行してやる事になります。必要なインタフェースは以下の通りです。

type ReadWriter interface {
	Connect(chan interface{}) chan interface{}
	Close()
	ReadWrite() error
}

type IO struct {
	ReadWriter
	R chan interface{}
	W chan interface{}
}

func (io *IO) Connect(r chan interface{}) chan interface{} {
	io.R = r
	io.W = make(chan interface{})
	return io.W
}

func (io *IO) Close() {
	if io.W != nil {
		close(io.W)
	}
}

PipeLine に並んだ複数の式の内、一つ前の式が書き込んで来る channel と現在の式を接続する関数 Connect、channel を閉じる Close、そして R から入力値を得て W に書き込む ReadWrite という関数を定義しています。
そしてそれを実装した IO という構造体は、各要素の共通インタフェース実装となります。さらにそれを内包した実装が streem のサンプルに書かれている seq 関数の戻り値や STDOUT となる訳です。
例えば seq(100) という関数を実行すると Seq 構造体ポインタを返す事とします。

type Seq struct {
	vm.IO
	current int
	max     int
}

func (seq *Seq) ReadWrite() (err error) {
	if seq.current < seq.max {
		seq.current += 1
		seq.W <- seq.current
		return nil
	}
	return io.EOF
}

ReadWrite() が呼ばれると、内部の値をインクリメントした後に書き込み専用の channel に値を投げます。関数ブロックも処理は同様です。ReadWrite() が呼ばれると、読み取り専用 channel から得た値を引数として関数を実行し、戻り値を書き込み専用 channel に書き込みます。
STDOUT は以下の様に入力をコンソールに書き込みます。

type STDOUT struct {
	vm.IO
}

func (o *STDOUT) ReadWrite() (err error) {
	if o.R == nil {
		return io.EOF
	}
	v, ok := <-o.R
	if ok {
		_, err = fmt.Println(v)
		return err
	}
	return io.EOF
}

上層部から値が得られなくなったら io.EOF を返してやります。
これを繋げて並列実行します。C言語でこれをやるとなるとかなり頭を捻りますが golang だと以下程度の短いコードになります。

pl := []ReadWriter{}
var oc chan interface{}
for _, item := range stmt.Exprs {
	var rw ReadWriter
	// 式を解釈する
	rv, err := invokeExpr(item, env)
	if err != nil {
		return NewError(stmt, err)
	}
	switch rv.Kind() {
	case reflect.Func:
		// 関数ブロックの ReadWriter を作成
		rw = &FuncIO{IO{}, rv}
	case reflect.Slice:
		// 配列要素を逐次返す ReadWriter を作成
		rw = &ArrayIO{IO{}, 0, rv}
	default:
		if iv, ok := rv.Interface().(ReadWriter); ok {
			// ReadWriter を実装しているならそのまま使う
			rw = iv
		} else {
			return NewError(stmt, errors.New("invalid ReadWriter"))
		}
	}
	// 一つ前の ReadWriter の書き込み channel を今回の
	// 読み取り channel に割り当てる
	oc = rw.Connect(oc)
	pl = append(pl, rw)
}

// 全ての goroutine が終了するまで待つ
var wg sync.WaitGroup
for _, rw := range pl {
	wg.Add(1)
	var ge error
	go func(item ReadWriter) {
		defer wg.Done()
		for {
			err = item.ReadWrite()
			if err != nil {
				if err != io.EOF {
					ge = err
				}
				item.Close()
				break
			}
		}
	}(rw)
}
wg.Wait()

上図の枠線部分が goroutine で並列実行され、黒丸部分の channel を介して値が上層部から下層部へ伝搬します。上層部が io.EOF を返すと channel が閉じられるので下層の部分も次々に io.EOF を返すといった仕組みです。
先日チャラ書きしたメモとおおよそ近い実装になりました。
コマンドラインから

$ streeem fizzbuzz.stream

といった感じにファイル名を指定出来る様にしてあります。

とりあえず実装はしてみましたが今後、受け渡された値に配列自身や辞書等が混じってくると、各 goroutine 間で排他制御も必要になります。

まとめ

golang で言語処理系を書くのは難しい(というかあまり前例が無いので難しいと思われている?)と思われがちですが、実は他の言語よりも言語的なアドバンテージがあり、かつ channel や goroutine といった機能により難しい並列処理が簡単に書ける様になります。
C言語だといろんな人が既にネタを出し尽くした感がありますが、golang はまだ未開拓な部分が沢山あるので先やったもん勝ちなのです。どんどん書いてみて下さい。
streeem のソースは以下に置いてあります。PR もお待ちしています。