Go言語でつくるインタプリタを読み終えて，独自拡張した話
Go言語でつくるインタプリタを漸く読み終わりました．といっても実際には1月末には終わっていて単純に記事にするのを忘れていただけなんです．
実際にコードを書きながら読んでいたのですが，リポジトリのログを遡るとファーストコミットは2018/6/24になってました． およそ半年と1ヶ月ほどでしょうか．合間合間にすすめていたのですごい時間かかってますね．
でも本当に良い本でした． 本書でも述べられている通り，Brainf*ckとかじゃなく割とちゃんとした，でもそこまでヘヴィじゃない言語仕様のインタプリタをフルスクラッチで作るというのは中々ありませんでしたから．
独自拡張の話
で，本題なんですが本書では最終的にハッシュと組み込み関数の実装で終わっています（付録としてマクロの実装もある）
その時点で動くプログラムはこんな感じ
let map = fn(arr, f) {
let iter = fn(arr, accumulated) {
if (len(arr) == 0){
accumulated
} else {
iter(rest(arr), push(accumulated, f(first(arr))));
}
};
iter(arr, []);
};
let a = [1,2,3,4];
let double = fn(x) { x * 2 };
map(a, double);
配列要素をmap関数で2倍ずつしていくというプログラムです． これでも結構プログラムっぽいですが，次のようなコードは動きません.
let fizzbuzz = fn(n) {
for (let i=1;i<n+1;++i) {
switch {
case i % 3 == 0 && i % 5 == 0:
puts("FizzBuzz");
break;
case i % 3 == 0:
puts("Fizz");
break;
case i % 5 == 0:
puts("Buzz");
break;
}
}
};
fizzbuzz(15);
典型的なFizzBuzzです．このプログラムを動かすのに何が足りないかというと for文, switch case文, インクリメント演算子(++), バイナリ演算子(&&) です. あと % 演算子もなかった気がする
結構足りないですね．本のコードを写経して動きを理解するだけでもインタプリタの言語処理系の実装を理解するには十分だとは思いますが，折角なので以上の要素を頑張って実装してみました．
これらの要素を説明していくのに二段階に分けます．1つ目はASTの生成である構文解析と実際に処理を行う評価の部分です
For文
構文解析
まず, ASTの定義コードを示します
// ForExpression // original expression // for(<statement>;<expression>;<statement>) { // <Block Statements> // } type ForExpression struct { Token token.Token // 'for token InitStatement Statement // FinishCondition Expression LoopStatement Statement Consequence *BlockStatement }
初期化部分がstatementになっているのは let i = 1 みたいなのを許容したいからです.
逆に終了条件のところは必ず式にするように制限しています. ここはお好みで変更できるので実装者によるでしょう．
ループ条件も初期化部分と同様です．
中括弧の中にはループ中に実行される文が配列で格納されます．
評価
func evalForExpression(node *ast.ForExpression, env *object.Environment) object.Object { forEnv := object.NewEnclosedEnvironment(env) initEvalResult := Eval(node.InitStatement, forEnv) var result object.Object if isError(initEvalResult) { return initEvalResult } for { isFinishObj := Eval(node.FinishCondition, forEnv) isFinish, ok := isFinishObj.(*object.Boolean) if !ok { return newError("finish condition is not boolean") } if !isFinish.Value { return result } result = evalBlockStatement(node.Consequence, forEnv) loopEvalResult := Eval(node.LoopStatement, forEnv) if isError(loopEvalResult) { return loopEvalResult } } }
env変数はスコープ外の変数などを保持しているマップです． 先程のastで取得した初期化条件，終了条件ループ条件を元に実際にforループを回します. for文が終わった際にはresult変数に最後のループで実行された文の結果が格納されて返されます.
SwitchCase文
本書ではIf文を実装していますが，else ifのような無限に続けていく書き方はサポートしていませんでした．そちらを拡張しても良かったのですが折角なので綺麗に見えるSwitchCaseを実装してみました.
構文解析
まずはASTの定義を見ます
type SwitchStatement struct {
Token token.Token
Expression Expression
Case []*CaseStatement
}
type CaseStatement struct {
Token token.Token
Condition Expression
Statements []Statement
}
さて，Switch文はSwitchとCaseそれぞれに分けました． なぜこうしたかは若干おぼろげですが，確か一つの構造体に詰め込むと解析がすごい面倒くさいことになりそうだったからだと思います．すいません
で，解析処理は以下のようになります
func (p *Parser) parseSwitchStatement() ast.Statement { stmt := &ast.SwitchStatement{ Token: p.curToken, Case: []*ast.CaseStatement{}, } if !p.peekTokenIs(token.LBRACE) { exp := p.parseExpression(LOWEST) stmt.Expression = exp } else { stmt.Expression = nil } p.nextToken() for !p.peekTokenIs(token.RBRACE) { p.nextToken() switch { case p.curTokenIs(token.CASE): s := p.parseCaseStatement() caseStmt, ok := s.(*ast.CaseStatement) if !ok { return nil } stmt.Case = append(stmt.Case, caseStmt) } } p.nextToken() return stmt } func (p *Parser) parseCaseStatement() ast.Statement { stmt := &ast.CaseStatement{ Token: p.curToken, Statements: []ast.Statement{}, } p.nextToken() exp := p.parseExpression(LOWEST) stmt.Condition = exp if p.peekTokenIs(token.COLON) { p.nextToken() } for !p.peekTokenIs(token.BREAK) { p.nextToken() caseStmts := p.parseStatement() stmt.Statements = append(stmt.Statements, caseStmts) } return stmt }
Switch文は switch <expression> { [case statement] } のようになっていて最初のexpressionに関してはあってもなくても良いです.
単純にGoっぽくしたくて入れました
case文はbreakなしだと終了の判定が若干面倒くさかったので甘えて入れました．それ以外は基本的にFor文やIf文と解析の手法は変わりません.
評価
func evalSwitchStatement(node *ast.SwitchStatement, env *object.Environment) object.Object { for _, c := range node.Case { conditionValue := Eval(c.Condition, env) condition, ok := conditionValue.(*object.Boolean) if !ok { return newError("case condtion value is not boolean. got=%T", conditionValue) } if condition.Value { var result object.Object for _, s := range c.Statements { result = Eval(s, env) } return result } } return nil }
こちらの評価処理は全然難しくなかったです． C言語よろしく，Case文の条件を上から判定してマッチしていたらCaseAST内部のBlockStatementを評価していくという感じです．
その他の演算子
++ 演算子は上記のFizzBuzzのように ++<Integer Object> とするようにしています. 前置にした理由は後置にすると実質中置演算になって演算子の優先順位を考慮しなきゃいけなくて面倒くさかったからです．ごめんなさい
&& 演算子の解析もAST生成は既存のコードに条件を足すだけなので難しくありません
評価に関しては若干追加したので載せておきます.
func evalInfixExpression(operator string, left, right object.Object) object.Object { switch { case left.Type() == object.INTEGER_OBJ && right.Type() == object.INTEGER_OBJ: return evalIntegerInfixExpression(operator, left, right) case left.Type() == object.STRING_OBJ && right.Type() == object.STRING_OBJ: return evalStringInfixExpression(operator, left, right) case operator == "==": return nativeBoolToBooleanObject(left == right) case operator == "!=": return nativeBoolToBooleanObject(left != right) case operator == "&&" && left.Type() == object.BOOLEAN_OBJ && right.Type() == object.BOOLEAN_OBJ: return evalBinaryOperand(operator, left, right) case left.Type() != right.Type(): return newError("type mismatch: %s %s %s", left.Type(), operator, right.Type()) default: return newError("unknown operator: %s %s %s", left.Type(), operator, right.Type()) } }
この処理は中置演算式の評価部分ですが，&& の左辺右辺は絶対にBoolオブジェクトであると制限して評価します.
あとは簡単で,
func evalBinaryOperand(operator string, left, right object.Object) object.Object { leftVal := left.(*object.Boolean).Value rightVal := right.(*object.Boolean).Value switch operator { case "&&": return &object.Boolean{Value: leftVal && rightVal} default: return newError("unknown operator: %s %s %s", left.Type(), operator, right.Type()) } }
こんな感じで実際の値を評価します. || 演算子とか足したければtokenを追加してcase文も追加すればOK
% 演算子も追加しましたが他の +-*/ と同様なので省きます.
実際に実行してみる
これらを実装して，先程のFizzBuzzを実行してみると次のようになります
いい感じに出力されていますね. 最後のnullはputsの評価値を表示しているものです.
まとめ
非常に参考になり，翻訳も丁寧で原著のテンポの良い文章がそのまま楽しめた気がします. また，実際のコードもインタフェースを十全に使っているおかげで自前の拡張もかなりスムーズに行えました． 言語処理系を実際に作るというのは結構ハードルが高そうに見えますが，コンパイラとかはともかく，インタプリタは実装する言語でそのまま実行するので入門としてはかなり良い教材なのではないでしょうか？
作っている最中に普段「どうしてこんな構文なんだろ？」と思うプログラミング言語の仕様も実は実装者の苦悩の果に辿り着いたものなのだという一種の共感すら湧くようになりました.
皆さんも良ければインタプリタを作って見てください
最後に書籍のリンクと今回自分が実装したコードへのリンクを張っておきます.
