自作Nimインタプリタにコンパイラを実装し始めた件について
2019/7/19のtryangle勉強会の資料
言語処理系の大まかな概要と、概念の説明など
アジェンダ
開発の動機
言語処理系の大まかな流れ
スタックマシン
VM
バイトコード
opcode, operand
動いている様子
発表の動機
最近3つの言語処理系を並行して作り始めてる
Rust実装の自作言語
インタプリタとコンパイラ
Rytl→??? (まだ決まっていない)
Haskell実装のC言語の処理系
コンパイラ
C→アセンブリ言語
Nim実装のmonkey言語の処理系
インタプリタとコンパイラ
monkey→バイトコード
気分といくつかの理由により並行に開発してる
ので、各進捗は🐢🐢🐢
最近こんな本を読んでいる
初めての洋書
知っている単語も多いのでまだマシ
もし哲学書なら知らない言葉多すぎて死んでる
これを読みながらNimで実装していく
そもそもCompilerってなに？？
高級言語で書かれたプログラムを、機械が解釈できるプログラムへ翻訳するプログラム
「高級言語」はPythonとかTypeScriptとかCとか、僕らが普段書いてるやつを指して言ってる
「コンパイラ」もプログラムなので高級言語で作ることができる
プログラムが変換される大まかな流れの例
字句解析 ┐
構文解析 │ フロントエンド
意味解析 │
翻訳 ┘
コード最適化 ─ ミドルエンド
コード生成 ─ バックエンド
一つずつ軽く見ていきます
高級言語をTokenに分割
Tokenというのは意味のある最小単位のこと
例えば、数値とか変数とか識別子とか
変換するプログラムをLexerと呼ぶ
monkeyではこんな感じに分解する
examplelet hoge = 1 + 2 * 3 / 4 + 5 - 6;
↓
[LET,
IDENT("hoge"),
ASSIGN,
INT(5),
LET,
IDENT("ten"),
ASSIGN,
INT(10)]構文解析
さっきのTokenをASTに変換
Abstract Syntax Tree
日本語では「抽象構文木」
文法に対応した木
括弧や空白など本質的な意味のない記号などは省かれている
変換するプログラムをParserという
先程のコードからASTを作ると以下のような感じになる
その後
型検査とかしたり
翻訳
IR (中間表現)に翻訳したり
無駄を省いたり
機械語を出力したり
ここまでは復習
monkey-nimは何を何にコンパイルして実行するのか
「monkey高級言語」→「バイトコード」にコンパイル
このバイトコードは自作のVM上で動作する
バイトコードってなんですか
後述
VMってなんですか
後述
コンパイラとVMを自分で実装する
要するにこんな感じ
monkey高級言語を
monkey1 + 2自作VMが解釈できるバイトコードに変換する
bytecode// イメージ. constantsの型とかが実装と少し異なる
Bytecode = {
instruction: [0, 0, 0, 0, 0, 1, 1]
constants: [1, 2]
} 0 とか 1 とか一見意味のない数値にの羅列に見えるが、ちゃんとした並びですこのページの最後まで読めば「意味」がわかる
スタックマシンとは
スタック領域をデータ保存領域として動作する機械
基本操作は、pushとpopの2つ
スタックに一つ積み上げるか
スタックから一つ取り除くか
アクセス可能な場所は一番上のみ
シンプル、プログラムサイズが小さい傾向がある
レジスタマシンと比較した時の話
プロセスVMとは
抽象化されたコンピュータ
VMを使って何が嬉しいか
移植性が高い
n個のアーキテクチャ、m個の言語がある時に、
本来ならn\times m通り実装しなければいけないが、n+ m個で実現できる
複数言語での相互利用なども可能
IR (中間表現)は最適化がしやすい
高級言語よりは
既存技術の再利用ができる
逆に、既存技術に機能追加ができる
セキュリティチェック機構の追加とか
バイトコードとは
プロセスVMが実行するために設計された実行可能なプログラムのバイト表現
特定のOSやハードウェアに依存しない設計
一つ一つの命令が1バイト
高級言語と比較して
ファイルサイズが小さい
処理速度が高速
イメージとしてはこんな感じ
bytecodeCONSTANT 1 // 定数の1
CONSTANT 2 // 定数の2
ADD // 加算の命令は？どこが「バイトコード」やねん？？
と思ったそこのあなた、そうなんですこれはイメージです
実際はこれらをバイトコードで表現します
さっきも書いたが、こんな感じの表現
bytecodeBytecode = {
instruction: [0, 0, 0, 0, 0, 1, 1]
constants: [1, 2]
}命令をバイトコードで表現する、とはどういうことか
命令と引数をバイトコードで表現する
PUSH 、 POP みたいなやつが命令 PUSH 1 の 1 とかが引数以下の2つの概念を知る必要出てくる
Opcodeとはなにか
operation code、「おぺこーど」と読む
機械語の命令の種類を表すもの
例えば「
PUSH は 40 にして、 POP は 23 にしよう！」みたいな感じ各命令がユニークな数値なら機能する
おい、機械さんよ、「40」をしてくれ、わかるだろ？「40」だ。PUSHって意味だよ！！
各命令は1byteのバイトコード
つまり命令の数の最大は2^8=256種類
逆に言えば、数値であるopcodeに名前をつけたものが「
PUSH 」とかこの名前のことを「ニーモニック」という
CPythonのOpcodeの定義を見てみよう
数値がどころどころ飛んでて120種類くらいで足りている
あんなに大きな言語でもそれぐらいの命令数で全てを表現できる
Operandとは
日本語では「被演算子」
opcodeの引数に相当するもの
例えば
PUSH 2 の 2 operandもバイトコードに変換されたときは何かしらの数値にエンコードされている
ただし、必ずしも1byte幅ではない
大きな数値を表現したいときは1byteでは足りないよね
エンコードされた後の数値の並び方は重要
エンディアンの話
複数のバイトの並び順のこと
16進数で "11223344" と表される4byteのデータをメモリに保存する時
リトルエンディアン
下から「44」「33」「22」「11」という順番で書き込む
主流のCPUとかで採用されている
ビッグエンディアン
上から「11」「22」「33」「44」という順番で書き込む
ネットワーク上でのデータ転送とかで採用されている
以上を踏まえるとmonkeyVMでは以下のように解釈できる
bytecodeBytecode = {
① ② ③ ④ ⑤ ⑥ ⑦
instruction: [0, 0, 0,| 0, 0, 1,| 1]
constants: [1, 2]
}①と④と⑦がopcodeを表す
0 のとき、operandを2つもつ定数 1 のとき、operandなしの加算命令ここで定義している
②③が2byteの数値でconstantsのindex
00なので0、だから配列constantsの0番目を見る
constants[0] なので 1 ⑤⑥も2byteの数値
01なので1
constants[1] なので 2 そんな感じでこの数値の並びはさっきみたように
こんな風に解釈されて、結果として
+ 1 2 の結果である 3 が返ってくるbytecodeCONSTANT 1 // 定数の1
CONSTANT 2 // 定数の2
ADD // 加算の命令動いている様子
現状、コンパイラの実装は加算までしか行っていないので
ここだけ見ても、へぇ〜、、すごい、、んだね。。。
みたいな微妙な反応になりそう
おわり
ゆっくり作っていきます