Zenn
株式会社スタメンPublicationへの投稿
🔨

自作インタプリタに入門してみた

kondo
2024/04/14に公開
JavaScript
Ruby
tech

はじめに

「インタプリタの作り方」という本を読みました。
Loxという独自の言語[1]を想定して、インタプリタを作成する方法について解説されています。

https://amzn.asia/d/cjcYymH

私は普段の業務では、JavaScriptやRubyといったインタプリタ言語を扱っています。インタプリタについて学ぶことで、これらの言語をより深く理解することを目的に、本書を読みました。

この記事では、C言語で実装されたcloxというインタプリタについて紹介します。本書を読むことでこういうことが理解できるようになる、というを何となく感じていただければ幸いです。

アーキテクチャ

cloxのアーキテクチャを以下の図に示します。

コンパイラはソースコードからバイトコードを生成します。
生成されたバイトコードを仮想マシン(VM)が実行するというのが基本的な構成です。

コンパイラ

ソースコードからバイトコードを生成するのがコンパイラの役割です。その手順は次の通りです。

  • ソースコードを解釈して、トークンを生成する
  • トークンからバイトコードを生成する

トークンを生成するのは、スキャナの仕事です。
scanner.cを眺めると、いくつもの条件分岐を用いてソースコードを解釈して、トークンを生成していることが分かるでしょうか。

例えば、identifierType関数の148行目に着目してみます。"p"という文字を発見したら"rint"という文字列が続くことを確認して、"TOKEN_PRINT"というトークンを生成している様子が伺えます。トークンの種類はscanner.hで確認できます。

// scanner.cのidentifierType関数
static TokenType identifierType() {
  switch (scanner.start[0]) {
    case 'a': return checkKeyword(1, 2, "nd", TOKEN_AND);
    case 'c': return checkKeyword(1, 4, "lass", TOKEN_CLASS);
    // 省略
    // pという文字を発見したら、TOKEN_PRINTを返す
    case 'p': return checkKeyword(1, 4, "rint", TOKEN_PRINT);
    //省略
  }
}

スキャナで生成したトークンを用いて、compiler.cがバイトコードを生成します。

// print関数の場合
static void printStatement() {
  expression();
  // 文末のセミコロンを消費する
  consume(TOKEN_SEMICOLON, "Expect ';' after value.");
  // OP_PRINTをバイトコードとして書き込む
  emitByte(OP_PRINT);
}

バイトコード

cloxでは、バイトコードをChunk構造体に格納しています。

// https://github.com/munificent/craftinginterpreters/blob/master/c/chunk.c
typedef struct {
  int count; // バイトコードの数
  int capacity;
  uint8_t* code; // バイトコードを格納
  int* lines;
  ValueArray constants;
} Chunk;

uint8_t型は、8ビットの符号なし整数型(つまり、1バイト)です。
バイトコードは以下のように書き込まれます。

// https://github.com/munificent/craftinginterpreters/blob/master/c/chunk.c
void writeChunk(Chunk* chunk, uint8_t byte, int line) {
  // 省略
  chunk->code[chunk->count] = byte;
}

codeメンバはポインタ型ですが、配列のように扱うことが可能です。[2]
引数byteに渡ってくる値は、chunk.hに定義されているOpCodeというenumです。

// https://github.com/munificent/craftinginterpreters/blob/master/c/chunk.h
typedef enum {
  OP_CONSTANT,
  OP_PRINT,
  OP_NIL,
  // 省略
} OpCode

バイトコードとは、すなわち1バイト(uint8_t型)の配列であることが分かります。
print 100;というコードのバイトコードを出力してみます。

> print 100;
== <script> ==
0000    1 OP_CONSTANT         0 100
0002    | OP_PRINT
0003    2 OP_NIL
0004    | OP_RETURN
100

上記出力の見方を補足します。

  • 0000~0004は、codeのオフセット(番地)
  • OP_CONSTANT、OP_PRINT、、はバイト命令
  • "100"は、バイト命令で使用する定数

前述したコンパイラが、ソースコードを解釈して、このバイトコードをChunk構造体に適切な順番で書き込んでいるのです。

仮想マシン(VM)

バイトコードを実行するのが仮想マシン(VM)の役割です。cloxはおなじみのスタックベースのVMです。バイトコードがスタックを用いてどのように実行されるのか、確認したいと思います。

0000    1 OP_CONSTANT         0 100
0002    | OP_PRINT

仮想マシン(VM)は、上記のバイトコードを以下の手順で解釈・実行します。

  1. OP_CONSTANTという命令であれば、次の番地には定数が存在する
  2. 定数の値をスタックにプッシュする
  3. OP_PRINTというであれば、スタックにprintする値が格納されているはず
  4. スタックの値をポップする
  5. ポップした値をC言語のprint関数で標準出力する

vm.cを確認すると、雰囲気が掴めるかもしれません。

スタックというデータ構造を利用することで、バイトコードを上手に実行することができるのです。

ctinyの紹介

言うは易く行うは難しです。コンパイラ→バイトコード→インタプリタの流れや、各々の実装のロジックは非常に複雑です。私はこのアーキテクチャを理解するために、cloxの大枠の処理を抽出したインタプリタ(ctiny)を作成しました。

//できるのは、ただ数字を出力することのみ
> print 100;
100

cloxの2578行に対して、ctinyは297行しかありません。
言語として何も成立してはいませんが、インタプリタのプリミティブな仕組みを理解するには有効なコード量です。

https://github.com/kondo97/ctiny

学習方法

776ページ及び3.1cmの厚みのある本書を丁寧に読み進めるのは非常に根気がいることでしょう。
私なりの本書のハックの仕方を紹介しておきます。

大枠のアーキテクチャを理解できれば、その後の学習はcloxに備わっている機能(変数、関数、クラス、GC、、)がどのように実装されているのか、根気強くソースコードを読むのがおすすめです。理論的な部分が気になれば、本を読むことでより理解が深まります。

まずは下記のリポジトリをcloneします。オンラインで公開しているというのは素晴らしい取り組みです。

https://github.com/munificent/craftinginterpreters

デフォルトでは、デバッグ用の出力がOFFになっています。common.hの以下の記述をコメントアウトします。

// #undef DEBUG_TRACE_EXECUTION

Makefileを用いてビルドします。

make clox

ソースファイルの実行、REPLのどちらも対応しています。
試しにprint "this is lox code";を実行してみました。

./clox
> print "this is lox code";
          [ <script> ]
0000    1 OP_CONSTANT         0 'this is lox code'
          [ <script> ][ this is lox code ]
0002    | OP_PRINT
this is lox code
          [ <script> ]
0003    2 OP_NIL
          [ <script> ][ nil ]
0004    | OP_RETURN

[ ]で囲まれた部分はスタックの状態を表しています(スタックトレース)。
OP_CONSTANTによって、"this is lox code"がスタックにプッシュされた後、OP_PRINTによってポップされて標準出力されるという流れが、分かりやすいのではないでしょうか。

自分が興味のあるコードを入力してみてログを出力したら、cloxのコードを粘り強く読みます。
以下の観点で切り分けると良さそうでしょうか。

  • どのようなバイトコードが生成されるのか(コンパイラ)
  • そのバイトコードがどのように処理されるのか(仮想マシン)

ここからは、私がそのようにして学習したcloxの実装をいくつかに取り上げることにします。

ハッシュ表

次のような変数を定義するコードがあったとします。

var lox = 100;

loxという変数が既に定義されているか確認する必要があるでしょう。こうした変数名を効率よくルックアップ(探索)するための手法がハッシュ表です。

ハッシュ表は以下のような構造体で構成されています。
変数が既に定義済かどうかをハッシュ表で管理しているのです。

type struct {
  Table strings;
} VM;

typedef struct {
  int count;
  int capacity;
  Entry* entries; 👈
} Table; // ハッシュ表

typedef struct {
  ObjString* key; 
  Value value; 
} Entry;

struct ObjString {
  Obj obj;
  int length;
  char* chars; // 文字列
  uint32_t hash; // ハッシュ値
};

文字列のインターン化

文字列のインターン化は多くのプログラミング言語で採用されている手法です。簡単に言えば、同じ文字列を毎回生成するのではなく共有するテクニックです。これは、メモリの節約や文字列比較のパフォーマンスにおいて有利に働きます。[3]

cloxでは、クラス名・関数名・変数名などソースコードの全ての文字列が対象です。それらはVM構造体のstringsメンバで管理されています。変数名の場合を例にすると、その挙動は以下のような流れです。

まず、コンパイラは変数名をハッシュ値に変換します。そのハッシュ値からVM.stringsというハッシュ表において、既に同じハッシュ値がないかを探索するのです。もし同じハッシュ値がなければ、新たにオブジェクトを生成します。そして、ハッシュ表を更新してそのポインタを返却します。もし同じハッシュ値がある場合は、そのオブジェクトのポインタを返却します。

// https://github.com/munificent/craftinginterpreters/blob/master/c/object.c
ObjString* copyString(const char* chars, int length) {
  // 文字列(chars)からハッシュ値を生成する
  uint32_t hash = hashString(chars, length);

  // ハッシュ値が既にハッシュ表に存在するか確認する
  ObjString* interned = tableFindString(&vm.strings, chars, length,
                                        hash);
  // ハッシュ表に既に定義済であれば、その値を返却する    
  if (interned != NULL) return interned;

  // ハッシュ表に存在しなければ、新たにメモリに割り当てる
  char* heapChars = ALLOCATE(char, length + 1);
  memcpy(heapChars, chars, length);
  heapChars[length] = '\0';
  
  // ハッシュ表に値を追加する
  return allocateString(heapChars, length, hash);
}

ハッシュというデータ構造のメリットは、変数名の数が増えたり、変数名が長くても、探索時間は変わらないことです。文字列のインターン化のメリットは前述しました。

グローバル変数とローカル変数

プログラムの実行について学ぼうとすると、次のような説明をよく目にします。
「グローバル変数はヒープ領域に格納され、ローカル変数はスタック領域に格納される」
cloxの実装を確認することで、より解像度の高い理解を得たいと思います。

loxというグローバル変数を定義して、print関数を実行してみました。

> var lox = 100; print lox;
          [ <script> ]
0000    1 OP_CONSTANT         1 '100'
          [ <script> ][ 100 ]
0002    | OP_DEFINE_GLOBAL    0 'lox'
          [ <script> ]
0004    | OP_GET_GLOBAL       2 'lox'
          [ <script> ][ 100 ]
0006    | OP_PRINT
100
          [ <script> ]
0007    2 OP_NIL
          [ <script> ][ nil ]
0008    | OP_RETURN

OP_CONSTANT命令でスタックに"100"をPushした後、OP_DEFINE_GLOBAL命令で"100"をPOPして、グローバル変数を定義しています。
グローバル変数はVM構造体に格納されます。この際、格納するメモリ領域が不足していれば、動的に拡張されます。
globalsメンバは、前述のハッシュ表と同様です。既にグローバル変数が定義済であるかどうかを管理しています。

typedef struct {
  // 省略
  Table globals;
} VM

次にローカル変数についても確認します。

> { var lox = 100; print lox; }
          [ <script> ]
0000    1 OP_CONSTANT         0 '100'
          [ <script> ][ 100 ]
0002    | OP_GET_LOCAL        1 👈 (A)
          [ <script> ][ 100 ][ 100 ]
0004    | OP_PRINT
100
          [ <script> ][ 100 ]
0005    | OP_POP
          [ <script> ]
0006    2 OP_NIL
          [ <script> ][ nil ]
0007    | OP_RETURN

ローカル変数では、スタックに"100"を格納しています。print関数はそのスタックの値を利用するのです。つまり、ローカル変数の場合は新たにメモリを割り当てません。
上記出力の(A)に着目してください。1という数字は、スタックのオフセット(番地)を示しています。ローカル変数は、スタックのトップから順番に積まれるのです。ローカル変数を複数定義してみることで、その挙動を確認します。

> { var lox = 100; print lox; var lox2 = 200; print lox2; }
          [ <script> ]
0000    1 OP_CONSTANT         0 '100'
          [ <script> ][ 100 ]
0002    | OP_GET_LOCAL        1 👈 スタックの2番目
          [ <script> ][ 100 ][ 100 ]
0004    | OP_PRINT
100
          [ <script> ][ 100 ]
0005    | OP_CONSTANT         1 '200'
          [ <script> ][ 100 ][ 200 ]
0007    | OP_GET_LOCAL        2 👈 スタックの3番目
          [ <script> ][ 100 ][ 200 ][ 200 ]
0009    | OP_PRINT
200
          [ <script> ][ 100 ][ 200 ]
0010    | OP_POP 👈 変数が不要になったらスタックからPOPする
          [ <script> ][ 100 ]
0011    | OP_POP 👈 変数が不要になったらスタックからPOPする
          [ <script> ]
0012    2 OP_NIL
          [ <script> ][ nil ]
0013    | OP_RETURN

グローバル変数は新たにメモリを割り当てました。一方で、ローカル変数はスタックを利用します。必要なメモリはずっと少ないのです。加えて、変数の探索も不要の為、高速であることが分かります。

コールスタック

例えば、関数Aから関数Bを実行する場合において、関数Bの実行後に呼び出し元である関数Aに戻るといった制御が必要です。

fun first() {
  var a = 100;
  second(a);
}

fun second(a) {
  print a;
}

first();

実行してみます。※長いので一部省略

// 省略
          [ <script> ][ <fn first> ][ 100 ]
0002    3 OP_GET_GLOBAL       1 'second'
          [ <script> ][ <fn first> ][ 100 ][ <fn second> ]
0004    | OP_GET_LOCAL        1
          [ <script> ][ <fn first> ][ 100 ][ <fn second> ][ 100 ]
0006    | OP_CALL             1
          [ <script> ][ <fn first> ][ 100 ][ <fn second> ][ 100 ]
0000    7 OP_GET_LOCAL        1
          [ <script> ][ <fn first> ][ 100 ][ <fn second> ][ 100 ][ 100 ]
0002    | OP_PRINT
100
          [ <script> ][ <fn first> ][ 100 ][ <fn second> ][ 100 ]
0003    8 OP_NIL
          [ <script> ][ <fn first> ][ 100 ][ <fn second> ][ 100 ][ nil ]
0004    | OP_RETURN
          [ <script> ][ <fn first> ][ 100 ][ nil ]
0008    | OP_POP
          [ <script> ][ <fn first> ][ 100 ]
// 省略

上記出力で着目するべきポイントは以下です。

  • <fn first>、<fn second>毎にスタックフレームが作成されている
  • <fn second>の実行後は、そのスタックフレームをPOPすることで<fn first>に制御を戻す
  • 引数("100")は、スタックフレーム毎に積まれる

cloxの実装について確認してみます。

typedef struct {
  CallFrame frames[FRAMES_MAX]; // コールフレーム(スタックフレーム)の配列
  int frameCount; // 進行中のスタックフレームの数
  // 省略
} VM

typedef struct {
  ObjClosure* closure; // クロージャについてはこの記事では割愛
  uint8_t* ip;
  Value* slots; // スタックフレーム内のローカル変数
} CallFrame;

typedef struct {
  ObjFunction* function;
  // 省略
} ObjClosure;

typedef struct {
  // 省略
  Chunk chunk;
  ObjString* name;
} ObjFunction;

VM構造体はスタックフレームを配列で保持しており、各CallFrame構造体のslotsには、前述した通り引数を含むローカル変数が保持されます。クロージャについてはここでは割愛させてください。そしてObjFunction構造体、つまり関数ごとにChunk構造体が保持されています。すなわち、バイトコードはスタックフレームごとに分割されています。

これらの構造体を用いて、インタプリタの実行の流れは以下のようになります。

  • スタックフレームの0番目を実行（仮に関数A）
  • 関数Aのバイトコードを実行
  • そのバイトコードから別の関数の呼び出し（仮に関数B）がある場合、新たにスタックフレームを生成してスタックにPUSH
  • 関数Bのバイトコードを実行
  • 関数Bの実行が完了すると、スタックからスタックフレームをPOP
  • 関数Aの実行に戻る

クラスとインスタンス

Loxはオブジェクト指向言語です。
LoxはJavascriptのような構文を持ちます。しかし、Javascriptとは異なりプロトタイプベースのオブジェクト指向ではありません。JavaやRubyのようなクラスベースのオブジェクト指向言語です。

以下は、cloxのクラスとインスタンスに関する構造体です。

struct Obj {
// 省略
};

typedef struct {
  Obj obj; // Objのポインタ
  ObjString* name; // クラス名
  Table methods; // メソッドの定義
} ObjClass;

typedef struct {
  Obj obj; // Objのポインタ
  ObjClass* klass; // ObjClassのポインタ
  Table fields; // インスタンス変数
} ObjInstance;

メソッドはクラスに、インスタンス変数はインスタンスに定義されます。

クラスを宣言してみます。

> class Lox {}
          [ <script> ]
0000    1 OP_CLASS            0 'Lox'
          [ <script> ][ Lox ]
0002    | OP_DEFINE_GLOBAL    0 'Lox'
          [ <script> ]
0004    | OP_GET_GLOBAL       1 'Lox'
          [ <script> ][ Lox ]
0006    | OP_POP
          [ <script> ]
0007    2 OP_NIL
          [ <script> ][ nil ]
0008    | OP_RETURN

OP_CLASS命令によって、ObjClass構造体を初期化して、そのポインタをスタックにPUSHします。
そしてOP_DEFINE_GLOBAL命令が、"Lox"というクラス名の文字列とObjClass構造体のポインタのペアで、グローバル変数を定義しています。

インスタンスを生成してみます。

> Lox();
          [ <script> ]
0000    1 OP_GET_GLOBAL       0 'Lox'
          [ <script> ][ Lox ]
0002    | OP_CALL             0
          [ <script> ][ Lox instance ]
0004    | OP_POP
          [ <script> ]
0005    2 OP_NIL
          [ <script> ][ nil ]
0006    | OP_RETURN

OP_GET_GLOBAL命令によって、"Lox"という文字列からObjClass構造体のポインタをルックアップ(探索)します。そして、そのポインタをスタックにPUSHします。OP_CALLがインスタンスを生成する命令であり、ObjInstance構造体を初期化します。

クラスとインスタンスは複雑そうだという先入観がありましたが、その実装は思ったよりも理解しやすいように感じました。

おわりに

GCや最適化についても触れたかったところですが、かなり長くなってしまったのでここまでにします。まだまだ理解が浅いところはあるのですが、インタプリタの仕組みを概観することができました。
これまで、RubyのインタプリタをRubyで作るといった学習経験はありました[4]。一方で、今回のようにC言語で本格的なインタプリタを作成することで、これまでぼんやりとしていた各言語の実行環境について、解像度を上げることができたと感じています[5]。

最後にASIP氏のブログ記事を紹介して筆を擱きます。[6]
https://asip.hatenadiary.org/entry/20090425/1270707280

脚注

  1. Lox言語は、JavascriptやRubyのような「動的に型付けされる言語」であり、インタプリタで実行されます。構文はJavascriptに似ています。 ↩︎

  2. 参考：苦しんで覚えるＣ言語 配列とポインタの奇妙な関係 ↩︎

  3. ソースコードの文字列("this is lox code"、等)をインターン化するかは言語によって異なります。例えば、Rubyではシンボルを採用しています。通常の文字列の場合は、常に新たな文字列を生成するのです。Rubyのコーディングでは、シンボルを使いましょう、というのはこのような理由です。ところで、Rubyもfrozen_string_literal: trueを指定することで、ファイル内の文字列をイミュータブルにすることが可能です。文字列をデフォルトでイミュータブルにする議論もあります。こうした議論も、インタプリタを学ぶことでより深く理解することができるのではないでしょうか。
    参考：TechRacho Rubyにシンボルがある理由（翻訳） ↩︎

  4. ASCII Rubyで学ぶRuby ↩︎

  5. 同書の前半ではjavaで作るjloxというインタプリタを作成します。一方でcloxはC言語によりメモリ管理を行うことで、よりパフォーマンスに優れた実践的なインタプリタです。 ↩︎

  6. 研鑽Rubyプログラミング 実践的なコードのための原則とトレードオフも私がインタプリタを学ぶモチベーションとなった本です。インタプリタを理解したコーディングというものが存在する、と言うことができるでしょうか。 ↩︎

GitHubで編集を提案
株式会社スタメン
株式会社スタメンPublication

エンゲージメント経営プラットフォーム「TUNAG」と情報漏洩を未然に防ぐセキュリティ管理サービス「漏洩チェッカー」を開発しているメンバーによるテックブログです。

Discussion