はじめに

新卒でCARTA HOLDINGSに入社しDIGITALIOに配属された25卒のやせと申します！

普段の業務ではTypeScriptやGoを使ってシステム開発を行っています。最近は趣味と勉強を兼ねて、「TypeScriptをアセンブリに変換するコンパイラ」をTypeScript+Denoで作っているので今回はその話をしたいと思います。

特に何かの役に立つとかでもないのですが、普段何気なく使っているものが、裏側でどのように動いているのかを知りたいなと思い始めてみました！

今回できたもの

今回作ったコンパイラでは、TypeScriptのコードをアセンブリ（x86）に変換します。

通常、TypeScriptはJavaScriptにトランスパイルされて、V8やJavaScriptCoreのようなJSエンジンによって処理されますが、今回はTypeScriptのコードをアセンブリに変換して、実行ファイルを作成するといったことをやっています。

現状、対応していること

四則演算
単項演算子（単項プラス, 単項マイナス）
比較演算子（<, >, <=, >=, ==, !=)
ローカル変数定義
ブロック文
制御構文（if/else, while, for）
関数定義・呼び出し

この辺ができるようになると、以下のように関数を再帰で呼び出すコードを処理できるようになります。

// 関数の再帰でフィボナッチ数列を計算するコード
function main() {
  return fib(10);
}

function fib(n) {
  if (n == 1) return 1;
  if (n == 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

（まだ一部TypeScriptっぽくないですがご容赦を、、、）

実行までの流れ

TypeScriptのコードからアセンブリに変換するまでの流れは大まかに以下のようになっています。

一般的なコンパイラは、以下のような論理的構造を持っていることが多いです。

字句解析
構文解析
意味解析
中間語生成
最適化
コード生成

今回は簡易的に、以下の3つだけの構造を持っています。

字句解析
構文解析
コード生成

字句解析

字句解析では、読みこんだプログラムの文字列を解析して、言語的に意味のある最小の単位（トークン）に分解していきます。

以下のようなプログラムがあったとすると

const hoge = 2*(3+4);

字句解析をすることでただの文字列から、const hoge 2 * ( 3 + 4 ) ;のように分解したトークンを得ることができます。

構文解析

構文解析では、字句解析した結果と構文規則を元に、トークン間の関係性を決定します。構文解析の結果は、抽象構文木（AST）などの木構造で表現されることが多いです。

例えば先ほどのプログラムでは、「2*(3+4)という式は3+4が先に計算されて2を掛けるといった計算順序がある」ということを解釈する必要があります。このような計算順序を表現する方法として抽象構文木（AST）がよく用いられます。

このように木構造として扱うことで、プログラムの複雑な文法構造を自然に表現することができ、プログラム上で扱いやすくなります。

コード生成

構文解析で得たASTをもとに、目的とするコード生成を行います。今回目的とするコードはアセンブリのため、出力結果は以下のようなコードになります。

// 2*(3+4)を計算する例
main:
    mov     rax, 3
    add     rax, 4
    imul    rax, 2
    ret

出力したアセンブリをアセンブラに渡して機械語に変換することで、実際にCPUが実行できる命令データになります。

技術スタック

今回作ったコンパイラの技術スタックです。

TSのランタイム：Deno
- Nodeを使わないという強い意志のもと、DenoかBunを使おうと思いDenoを使うことにしました
- ゼロコンフィグでTSを実行できるのがとても良いです
- 余談ですが、実行時に権限制御ができるのでAI時代にDenoは相性が良いと個人的に思ってます
アセンブラ：GNUアセンブラ
- アセンブリはIntel記法やAT&T記法などの記法がある
- GNUアセンブラでは基本AT&T記法を扱うが、.intel_syntaxディレクティブを使えばintel記法でも使える
- gccコマンドでアセンブルやリンクできたりする
実行環境：Docker
- Ubuntuのイメージを作成し、その中で実行しています

TSの型システムを最大限活用して型安全に開発しました。switch文やif文が多用されているのですが、タグ付きユニオン型とNarrowingが威力を発揮して、非常に開発体験の良い開発ができました。

実行してみる

試しに以下のコードをコンパイルしてみます

// sample.ts
function main(){ 
  return 2*(3+4);
}

すると、以下のアセンブリが出力されます

.intel_syntax noprefix
.globl main
main:
  push rbp
  mov rbp, rsp
  sub rsp, 0
  push 2
  push 3
  push 4
  pop rdi
  pop rax
  add rax, rdi
  push rax
  pop rdi
  pop rax
  imul rax, rdi
  push rax
  pop rax
  jmp .Lreturnmain
.Lreturnmain:
  mov rsp, rbp
  pop rbp
  ret

2*(3+4)を処理しているのは以下の部分になります。複数の途中結果のある式でも計算できるようにするために、スタックを用いています。（今回は実装をシンプルにするため、レジスタ割り当て最適化などは行わず、スタックマシンとして計算を行うコードを出力しています）

  push 2
  push 3
  push 4
  pop rdi
  pop rax
  add rax, rdi
  push rax
  pop rdi
  pop rax
  imul rax, rdi
  push rax

このように計算の途中結果をスタックにプッシュして保持するようにすることで、複数の途中結果がある式でも計算できるようになります。

この例では以下のようにスタックにプッシュ・ポップされて計算されます。

最終的な計算結果がスタックのトップにあるはずなので、ポップをすると計算結果が得られるといった仕組みになっています。

先ほど出力されたアセンブリファイルをgccで機械語に変換すると実行できるようになります。実行してみると、、、

echo $?を実行してプログラムの終了コードを表示していますが、14になっているので正しく計算できていそうです🎉🎉

（警告が出てますがいったん無視）

次に、フィボナッチ数列を再帰関数で計算する以下のコードも実行してみましょう！

function main(){
  return fib(10);
}

function fib(n) {
  if (n == 1) return 1;
  if (n == 2) return 1;
  return fib(n-1) + fib(n-2);
}

計算結果が55（10番目）になっているので正しく計算できてそうです🎉🎉

フィボナッチ数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...

おわりに

初めてゼロからコンパイラを自作してみたのですが、コンパイラを作る過程でJS/TSの知らない演算子・文法だったり、言語によるメモリ管理の特性を学ぶことができたので、とてもよかったです！

コンピュータ史の中でもコンパイラの歴史は古く、多くの背景を持っています。コンパイラを自作する過程で、そういった過去の歴史に触れることができ、先人たちの試行錯誤の足跡を一歩ずつ辿るような感覚が新鮮でワクワクしました。また現代のプログラミング言語の設計思想にも想いを馳せる機会となり、より多くの言語を触ってみたいと感じるようになりました。

普段はTypeScriptを使ったアプリケーション開発をすることが多いため、これらの低レイヤの知識が業務に直結することはあまり無いかもしれません。ですが、これからのAI時代では表面的なコーディング能力や知識は淘汰され、より本質的な技術理解が求められる時代になると考えています。そういった時代でも価値を発揮し、事業を推進できるエンジニアになるべく基礎的な技術理解も深めていきたいです！

補足

まだTypeScriptの文法じゃないという突っ込みが聞こえるのですが、ここら辺はちゃんとやっていきたい所存です、、、
今回は直接アセンブリを出力していますが、近年のコンパイラは、LLVMを代表とするコンパイラ基盤や独自の中間表現（IR）を利用し、プラットフォームに依存しない形でコードの最適化や生成を行う方式が主流です