自作Nimインタプリタにコンパイラを実装し始めた件について

2019/7/19のtryangle勉強会の資料

言語処理系の大まかな概要と、概念の説明など

アジェンダ

開発の動機

言語処理系の大まかな流れ

スタックマシン

バイトコード

opcode, operand

動いている様子

発表の動機

最近3つの言語処理系を並行して作り始めてる

Rytl

Rust実装の自作言語

インタプリタとコンパイラ

Rytl→??? (まだ決まっていない)

hcc

Haskell実装のC言語の処理系

コンパイラ

C→アセンブリ言語

monkey-nim

Nim実装のmonkey言語の処理系

インタプリタとコンパイラ

monkey→バイトコード

気分といくつかの理由により並行に開発してる

ので、各進捗は🐢🐢🐢

最近こんな本を読んでいる

『Writing An Compiler In Go』.icon

『Writing An Compiler In Go』

『Go言語でつくるインタプリタ』の続編

初めての洋書

知っている単語も多いのでまだマシ

もし哲学書なら知らない言葉多すぎて死んでる

これを読みながらNimで実装していく

そもそもCompilerってなに？？

高級言語で書かれたプログラムを、機械が解釈できるプログラムへ翻訳するプログラム

「高級言語」はPythonとかTypeScriptとかCとか、僕らが普段書いてるやつを指して言ってる

「コンパイラ」もプログラムなので高級言語で作ることができる

プログラムが変換される大まかな流れの例

字句解析 ┐

構文解析 │ フロントエンド

意味解析 │

翻訳 ┘

コード最適化 ─ ミドルエンド

コード生成 ─ バックエンド

一つずつ軽く見ていきます

字句解析

高級言語をTokenに分割

Tokenというのは意味のある最小単位のこと

例えば、数値とか変数とか識別子とか

変換するプログラムをLexerと呼ぶ

monkeyではこんな感じに分解する

code:example

let 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を作ると以下のような感じになる

https://gyazo.com/4d5ce5d808205935b9ef6adbd3fad9d5

その後

意味解析

型検査とかしたり

翻訳

IR (中間表現)に翻訳したり

コード最適化

無駄を省いたり

コード生成

機械語を出力したり

ここまでは復習

monkey-nimは何を何にコンパイルして実行するのか

「monkey高級言語」→「バイトコード」にコンパイル

このバイトコードは自作のVM上で動作する

バイトコードってなんですか

後述

VMってなんですか

後述

コンパイラとVMを自分で実装する

要するにこんな感じ

monkey高級言語を

code:monkey

1 + 2

自作VMが解釈できるバイトコードに変換する

code:bytecode

// イメージ. constantsの型とかが実装と少し異なる

Bytecode = {

instruction: 0, 0, 0, 0, 0, 1, 1

constants: 1, 2

}

0とか1とか一見意味のない数値にの羅列に見えるが、ちゃんとした並びです

このページの最後まで読めば「意味」がわかる

スタックマシンとは

スタック領域をデータ保存領域として動作する機械

基本操作は、pushとpopの2つ

スタックに一つ積み上げるか

スタックから一つ取り除くか

アクセス可能な場所は一番上のみ

シンプル、プログラムサイズが小さい傾向がある

レジスタマシンと比較した時の話

https://cdn.tutsplus.com/gamedev/uploads/2013/10/fsm_stack_possible_scenes.gif

画像引用元

プロセスVMとは

抽象化されたコンピュータ

有名所ではJVMとかYARVとか

VMを使って何が嬉しいか

移植性が高い

$ n個のアーキテクチャ、$ m個の言語がある時に、

本来なら$ n\times m通り実装しなければいけないが、$ n+ m個で実現できる

複数言語での相互利用なども可能

IR (中間表現)は最適化がしやすい

高級言語よりは

既存技術の再利用ができる

逆に、既存技術に機能追加ができる

セキュリティチェック機構の追加とか

バイトコードとは

プロセスVMが実行するために設計された実行可能なプログラムのバイト表現

特定のOSやハードウェアに依存しない設計

一つ一つの命令が1バイト

高級言語と比較して

ファイルサイズが小さい

処理速度が高速

JVMはバイトコードを使っているが、YARVはワードコード

イメージとしてはこんな感じ

code:bytecode

CONSTANT 1 // 定数の1

CONSTANT 2 // 定数の2

ADD // 加算の命令

は？どこが「バイトコード」やねん？？

と思ったそこのあなた、そうなんですこれはイメージです

実際はこれらをバイトコードで表現します

さっきも書いたが、こんな感じの表現

code:bytecode

Bytecode = {

instruction: 0, 0, 0, 0, 0, 1, 1

constants: 1, 2

}

命令をバイトコードで表現する、とはどういうことか

命令と引数をバイトコードで表現する

PUSH、POPみたいなやつが命令

PUSH 1の1とかが引数

以下の2つの概念を知る必要出てくる

Opcode

Operand

Opcodeとはなにか

operation code、「おぺこーど」と読む

機械語の命令の種類を表すもの

例えば「PUSHは40にして、POPは23にしよう！」みたいな感じ

各命令がユニークな数値なら機能する

おい、機械さんよ、「40」をしてくれ、わかるだろ？「40」だ。PUSHって意味だよ！！

各命令は1byteのバイトコード

つまり命令の数の最大は$ 2^8=256種類

逆に言えば、数値であるopcodeに名前をつけたものが「PUSH」とか

この名前のことを「ニーモニック」という

CPythonのOpcodeの定義を見てみよう

https://github.com/python/cpython/blob/master/Include/opcode.h

数値がどころどころ飛んでて120種類くらいで足りている

あんなに大きな言語でもそれぐらいの命令数で全てを表現できる

Operandとは

日本語では「被演算子」

opcodeの引数に相当するもの

例えばPUSH 2の2

operandもバイトコードに変換されたときは何かしらの数値にエンコードされている

ただし、必ずしも1byte幅ではない

大きな数値を表現したいときは1byteでは足りないよね

エンコードされた後の数値の並び方は重要

エンディアンの話

リトルエンディアンとビッグエンディアン

複数のバイトの並び順のこと

16進数で "11223344" と表される4byteのデータをメモリに保存する時

リトルエンディアン

下から「44」「33」「22」「11」という順番で書き込む

主流のCPUとかで採用されている

ビッグエンディアン

上から「11」「22」「33」「44」という順番で書き込む

ネットワーク上でのデータ転送とかで採用されている

以上を踏まえるとmonkeyVMでは以下のように解釈できる

code:bytecode

Bytecode = {

① ② ③ ④ ⑤ ⑥ ⑦

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が返ってくる

code:bytecode

CONSTANT 1 // 定数の1

CONSTANT 2 // 定数の2

ADD // 加算の命令

動いている様子

現状、コンパイラの実装は加算までしか行っていないので

ここだけ見ても、へぇ〜、、すごい、、んだね。。。

みたいな微妙な反応になりそう

https://gyazo.com/13c6bdf07e02be1992b52bf76bc382ee

おわり

ゆっくり作っていきますmrsekut.icon