2019年アドベントカレンダー、14日目の記事です。この記事は、Go言語でGo(のとても小さいサブセット)のインタプリタを作ってみようというものです。「Goはある程度わかるが言語の処理系のことはよく知らない」という人を想定して書きました。プログラミング言語のインタプリタが何をやっているのかが少しでも伝われば幸いです。次のような流れで進めていきます。構文の決定Goの全ての構文に対応しようとすると途方もない時間がかかります。(ちなみに、Go言語の仕様書はhttps://golang.org/ref/specにあります。これを実装するのは無理ですね。)そこで、大胆に機能を削ります。goroutine、構造体、ポインタ、パッケージまわりはすべて取り除きます。扱える型はint64、float64、boolのみにします。パース(後述)しやすいようなものに構文を制限します。}のようなものにのみ対応します(こちらも正しいGo言語の構文です)。:=のような糖衣構文もパースを楽にするためになくします。このようにしてかなり制限を加えましたが、「これくらいのコードは動かせるようにしよう」というものを3つほど示しておきます。print(fib(10))}言わなくてもわかると思いますが、これは10番目のフィボナッチ数を計算するプログラムです。...で実行すれば89が表示されます。今から作るインタプリタでこのプログラムを実行できるように、すなわち、関数呼び出しやprintビルトイン関数、if文などは扱えるようにしましょう。1}グローバル変数やforループも扱えるようにしましょう。ちなみにこのプログラムは10が出力されるはずです。}}クロージャも扱えるようにしましょう。このプログラムは(printは改行を入れないので少しわかりにくいですが)46が出力されるはずです。テストの形にするとこのようになります。}}目標が見えてきましたね?それではこれらのプログラム(+α)を正しく実行できるようなインタプリタの作成していきましょう。構文解析プログラムは文字列で書きますが、それをプログラムで扱いやすい形に変換してあげる必要があります。それを担うのがレキサーとパーサーを用いた構文解析です。INT_VALUE(3)に変換するといった要領で、文字列を「トークン」に置き換えていきます。LEFT_PARENTHESISといったような正規表現からトークンへの変換テーブルを用意しておいて、最長一致するものを常に選んでいく、といったような方法を用います。実際の実装はこのような雰囲気になります。longestMatch.token}goyacc(後述)に食わせるための形式になっていてその箇所はわかりにくいかもしれませんが、雰囲気は伝わるでしょうか。パーサーレキサーの次はパーサーです。パーサーはトークンの列を受け取り、抽象構文木を作ります。今回の場合は、プログラムを表す(ネストのたくさんある)構造体をつくります。次のような構造体を用いてプログラムを表すことにしましょう。Type(型)とExpression(式)とStatement(文)というインターフェイスが登場していますが一旦これは空のインターフェイス(interface{})であるとしておきましょう。}具体的に次のようなプログラムを考えてみましょう。2}これを次のようにパースする、といった感じです。}})このようなことができるパーサーを作成するために、goyaccというパーサージェネレータを使います。古き良き(?)yaccというパーサジェネレータのGo言語版です。パーサージェネレータというのは、文法のファイルからパーサーを作ってくれるというツールです。ちなみに、簡単な言語であればパーサーを直書きすることも可能ですが、少し複雑な言語になると直書きは厳しいです。それでは、文法の定義の一部を見てみましょう。expressionというのは変数のようなもので(非終端記号といいます)、文法の再帰的な記述を可能にするなどしています。ファイルではさらに多くの非終端記号が定義されています。一部分をもう少し詳しく見てみましょう。RIGHT_PARENTHESISという4つのトークン列(と非終端記号の組み合わせ)がtypeとして解釈可能である」ということを言っています。|は「または」みたいな意味だということですね。$$は結果のようなものを表していて、INT64をtypeとしてパースした結果が&IntType{}であると示しているわけです。}ではGo言語のプログラムがそのまま書け、いろいろな処理を挟むこともできます。...の箇所が顕著です。}の箇所を考えてみましょう。(式B)のような引き算の形の式に対応するケースですが、ここでは式Aが$1に、式Bが$3に対応しています。再帰的な式の構造を表しているわけです。雰囲気はわかったでしょうか?もちろんほかにもいろいろな記述が必要なのですが(例えば演算子の優先順位など)、それはここでは踏み込みません。yaccの文法(+goyaccの仕様)は調べると出てくるので、気になる人は調べてください。「トークン列と非終端記号の組み合わせ」の集合」の集合)で書かれています。文法ファイルはgrammar.yに記述しています。grammar.yのようにしてコマンドを実行すると実際のパーサーのプログラムy.goをジェネレートしてくれます。生成されたファイルもVCS下に置くのが慣例のようです。式の評価と文の実行さて、構文解析ができたら式の評価と文の実行をできるようにします。山場というわけではないですが、インタプリタの本体のような箇所です。ここで、「環境」というものを考える必要が出てきます。環境というのは、名前と値の対応付けです。print(i)}のようなプログラムのmain関数の実行において空の環境が作られる環境に変数iが追加する環境における変数iの値を3に書き換える環境から変数iの値を取り出し、出力するといったことが行われます。複雑なものをみてみましょう。e3としましょう)e2のiの値を出力するe3にiを追加するe3のiの値を3に書き換える。e3のiの値を出力する(ブロックから出る)e2のiの値を出力するといった形になります。出力は12232となるはずです。このような環境の管理ができるように、次のような構造体を定義してみましょう。[]Environmentを用いて、上でやったような環境の管理をできるようにしています。environmentsをEnvironments型として、次のような動作をできるようにしています。5)次のような簡単なテストが作っておきます。0.357s次に、式の評価を実装しましょう。空にしていたExpressionインターフェイスを次のように書き換えます。interface{}}Enviromentsを受け取って何らかの値を返すEvaluate関数を持つということをExpressionインターフェイスとするわけです。io.Writerは無視しても大丈夫です。(printによる出力先を設定するために使います。environments).(float64)}のようになるかと思います。左辺の式を評価し、その結果と不変の式の評価結果を足し合わせるということです。整数の足し算と浮動小数の足し算の2通りの可能性があるので、型アサーションが必要になっています。変数の参照を表すVariableのEvaluateの実装は次のようになります。environments.Get(e.Name)}ただ環境から名前に対応する値を取ってくるだけです。気をつけなくてはならないのは、関数の評価(関数の作成)と関数適用の評価(関数に引数を渡して実行する)です。}}というものがありました。makeAdder関数の実行において、関数が評価され、それが返り値となっています。}が評価されるという事が起こっていると考えることができます。当たり前だと思う人も多いかもしれませんが、関数が評価されたときの環境は関数適用時(上の例ではadd(...)が呼ばれるとき)にアクセスできないといけません。しないとiの値を関数適用時に見つけられないですよね?そこで、関数を評価したときの値を関数と環境のペア、「クロージャ」とします。クロージャを表す構造体定義、それを用いた関数の評価・関数適用の評価は次のようになります。nil}次に、文の実行の定義をしていきます。nil}ブロックやfor文、if文の途中においてreturn文が実行されたとき、その文は途中で実行を終了し、関数に呼び出し元に値を返す必要があります。そのために返り値を用いています(nilでなければ文の実行中にreturn文が実行されたということです)。最後にプログラム全体を実行するコードを書いていきます。closure.Environments)}これで動くものが完成で、冒頭で作ったテストが通ります。github.com/kkty/nanogo/testやったね!また、パスを受け取ってファイルからソースコードを読み込み、それをパースして実行するプログラムを作成しておきます。program.Run(os.Stdout)}次のようにしてプログラムを実行できるようになりました。/path/to/program型検査など(おまけ)インタプリタだけで走らせる言語ならば型はなくてもなんとかなるのですが、コンパイル可能なほとんど全ての言語には型の概念があります。コンパイルする(実際のマシンなどで実行できるアセンブリを出力する)ためには各変数のサイズが決まる必要があったり、データの種類によって扱えるレジスタが異なるためです。Goには型があるのですが、(パースできるようにはしていたものの)それ以外で型は無視してきました。そのままだと少しもったいないので、その型情報を用いて、型検査を行うことにします。「プログラムを実行する前に、型が合っているかをチェックし、そうでなければ実行しない」ということです。プログラムのミスに事前に気づくことができ、実行時エラーを発生させないようにできます。...と思ったのですが、こちらはちょっと間に合いませんでした。いうことで、また気が向いた時に後編として書くことにします。最後まで読んでいただき、ありがとうございました。何か質問があれば気軽にコメントをいただければ幸いです。