Crystal言語がどのようにして動作するのか調べてみた（前編）

## はじめに

Crystal言語というものが一体どのように動いているのかを調べてみようと思いました。しかし情報科学のバックグラウンドのない人間が少し調べたぐらいではCrystalがなぜ動いているのかはわかりませんでした。理解できた部分について書いていきます。

:::note info
元々はCrystalのアドベントカレンダーのために準備した記事でした。後半は勉強不足により未完になっているのですが、近日中に完成する見込みが立たないのでこのまま公開します。（前編と書いてありますが、後編は出ない可能性が高いです）
:::

## Crystal言語とは？

Crystalは、Ruby言語に非常によく似た文法を持つ静的型付け言語です。文法はRubyによく似ており、実行速度は非常に高速です。メタプログラミングはマクロによって実現しています。型推論のおかげで型を宣言しなくても、かなりの程度までRubyと似たコードを書くことができます。

## いきなり元資料

<iframe src="//www.slideshare.net/slideshow/embed_code/key/efm7Tuz5vpYSU2" width="595" height="485" frameborder="0" marginwidth="0" marginheight="0" scrolling="no" style="border:1px solid #CCC; border-width:1px; margin-bottom:5px; max-width: 100%;" allowfullscreen> </iframe> <div style="margin-bottom:5px"> <strong> <a href="//www.slideshare.net/crystallanguage/crystal-internals-part-1-70673255" title="Crystal internals (part 1)" target="_blank">Crystal internals (part 1)</a> </strong> from <strong><a href="//www.slideshare.net/crystallanguage" target="_blank">Crystal Language</a></strong> </div>

Crystalの動作する仕組みについては、上記のスライドが公開されています。
この記事はこのスライドの前半について、情報を要約、整理、追加したものです。

## Crystalのコードが実行されるまでの仕組み

### コンパイラはテキストファイルから、実行可能なファイルを作成する

Crystalのコードはどのようにして実行されるのでしょうか。
テキスト形式でコードを書き、`crystal` コマンドを利用してビルドすると、実行可能ファイルが生成されます。


```mermaid
flowchart LR
    subgraph コンパイラ
    すごい何か
    end
    テキストファイル --> すごい何か --> 実行ファイル
```


最も簡単なCrystalのプログラム、`x=0` をコンパイルします。

```crystal:最も簡単なCrystalのプログラム : test.cr
x = 0
```

ビルドします。

```
crystal build test.cr
```

実行ファイルを [GHex](https://gitlab.gnome.org/GNOME/ghex) で見てみましょう。こんな感じです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144608/16f3bb2c-4ade-1545-1ff5-7f609fd256d6.png)


これは人間が見てもよくわかりません。

かわりにアセンブリ言語のコードを出力してみましょう。アセンブリ言語は、機械語を人間がわかるように文字列で表現するものです。`--emit asm` オプションを指定することで、実行ファイルの変わりに、アセンブリ言語のコードを出力することができます。

```
crystal build --emit asm --prelude empty test.cr
```

prelude は、事前に読み込むファイルの指定です。emptyを指定すると、何も読み込まれないために小さなアセンブリ言語のコードが生成されます。こんな感じです。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144608/744584fd-fc64-4e32-677d-0f7c7ec620dd.png)

CPUに対する命令が並んでいます。コンパイラはテキストファイルから、CPUに対する命令のリストを作成しています。Crystalは最終的にはアセンブリ言語のコードを生成すればいいわけですね。

```mermaid
flowchart LR
    subgraph コンパイラ
    すごい何か
    アセンブリ言語
    end
    テキストファイル --> すごい何か --> アセンブリ言語 --> 実行ファイル
```

### コンパイラはCPUの命令セットによって異なる実行ファイルを生成する

生成される実行可能ファイルは、プラットフォームによって異なります。たとえば、Ubuntu(x86-64)で作成された実行ファイルと、Raspberry Pi(AArch64)上で生成される実行は異なります。Ubuntuの実行ファイルをRaspberry Piにコピーアンドペーストしても動きません。これは、CPUの命令セットアーキテクチャに互換性がないからです。

<img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144608/16bfae58-5e35-4e1f-57f1-79a7d24d940e.png" height="20%" width="20%"><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144608/16bfae58-5e35-4e1f-57f1-79a7d24d940e.png" height="20%" width="20%"><img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144608/16bfae58-5e35-4e1f-57f1-79a7d24d940e.png" height="20%" width="20%">

だから、コンパイラはCPU環境に合わせた実行ファイルを出力する必要があります。

## CrystalのコンパイラはLLVMに実行可能ファイルの作成を委託している

しかし、全てのCPUの命令セットに対応するバイナリを出力するコンパイラを作成するのは大変です。プログラミング言語の開発者にとって大きな負担になります。開発者の利用しているCPUに対して最適化されていても、別のCPUに対しては効率の悪い実行ファイルが吐き出される歪な実装ができてしまうかもしれません。

そのため、Crystalでは、LLVMという「コンパイラ基盤」と呼ばれるプログラムに、下流の部分を丸投げしているそうです。LLVMがそれぞれのプラットフォームに向けて最適化された実行ファイルを出力します。

```mermaid
flowchart LR
    LLVM --> executable-Ubuntu-x64 --> Ubuntuで実行-64
    LLVM --> executable-Ubuntu-x86 --> Ubuntuで実行-32
    LLVM --> executable-Mac-arm --> M1-Macで実行
    LLVM --> executable-Mac-x64 --> Intel-Macで実行
```

それではCrsytalはLLVMにどうやってLLVMに実行可能ファイルの作成を依頼しているのでしょうか。

## Crystalは中間表現 LLVM-IR を作成する

LLVMでは LLVM IRと呼ばれる中間表現を作成しているそうです。このLLVM IRとは、一種のプログラミング言語のようなもので、理想化されたアセンブリ言語のようなものだそうです。

```mermaid
flowchart LR
    LLVM-IR --> LLVM
    LLVM --> executable-Ubuntu-x64
    LLVM --> executable-Ubuntu-x86
    LLVM --> executable-Mac-arm
    LLVM --> executable-Mac-x64
```

LLVM IR は↓のようなファイルです。（`x=0` を LLVM IR に変換したもの）

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/144608/ab0ba2bf-f626-e755-333d-5f5327a2a5f1.png)

```mermaid
flowchart LR
    subgraph コンパイラ
    すごい何か
    LLVM
    end
    subgraph LLVM
    LLVM_IR
    LLVM_IR --> アセンブリ
    end
    テキストファイル --> すごい何か
    すごい何か --> LLVM_IR
    アセンブリ --> 実行ファイル
```

アセンブリ言語のコードを準備するためにはLLVM_IRを準備すればいいわけですね。

### LLVM IR（LLVM中間表現）のコードを出力してみよう

crystal build コマンドの `--emit` オプションに `llvm-ir` を指定すると、LLVM中間表現が出力されます。先ほどのCrystal言語で書かれたスクリプトを用意します。

```crystal:test.cr
x = 0
```

```sh
crystal build --emit llvm-ir --prelude empty test.cr
```

`--prelude` オプションは、Crystalの実行時に最初に読み込むファイルを指定しています。デフォルトでは[こちらのファイル](https://github.com/crystal-lang/crystal/blob/master/src/prelude.cr)が読み込まれます。これを [empty](https://github.com/crystal-lang/crystal/blob/master/src/empty.cr) に切り替えることで出力されるファイルがずっと小さくなります。（これによって `puts` などよくあるメソッドが使えなくなりますのでご注意ください。）

`test.ll` というファイルが生成されていると思います。これが LLVM IR （LLVM中間表現）です。

### LLVM IR（LLVM中間表現）からアセンブリ言語のコードを出力する

つぎに、このLLVM IRからアセンブリ言語のコードを作成します。これは、LLVM の LLC というコマンドを用います。

```
llc --relocation-model=pic test.ll
```

私の環境では `--relocation-model=pic` オプションをつけないと次のアセンブラから実行ファイルを作る工程が動きませんでした。これはメインメモリのどこにプログラムが配置されても実行できるようになるものだそうです。

### アセンブリ言語をコンパイルする

```
clang test.s
./test
```

これで、LLVM IR 中間表現から実行ファイルが作成される様子を再現ことができました。
ちなみに `--prelude=empty` を指定しない場合、リンクするライブラリを指定する必要があります。たとえば、

```
clang test.s -levent -lgc -lm
```

といった感じです。ここでは、libevent, libgc, libmath にリンクします。エラーメッセージを参考にして適宜必要なライブラリを指定してみてください。このように、Crystal言語は、いくつかのC言語のライブラリに依存しています。したがって、マルチプラットフォーム対応もLLVMに頼るだけでは難しい場合があります。[たとえば、wasm を出力する際にはwasm用のライブラリを用意する必要があります](https://glue.im/noah/introduction-to-webassembly-in-crystal)。

今回はCrystalのコンパイラにが出力するLVM IRを観察しましたが、Crystal言語を使ってLLVM中間表現を自分で出力する時は標準添付のLLVMバインディングを利用します。

https://qiita.com/magurofly/items/61cef2973154e0fcd875

https://qiita.com/magurofly/items/c8634b3d663f26022d0d

## 上流を構成する、Lexer、Parser、Semantic

ここまで、CrystalはコードからLLVM中間表現を作成することがわかりました。ではその工程はどうなっているのでしょうか。正直にいうと、今回はよくわかりませんでした。しかし、他の多くの言語と同じく、まずは、Lexerと、Parserを利用しています。

```mermaid
flowchart LR
style id1 fill:#fcf,stroke:#333,stroke-width:1px
    subgraph Lexer
      Token
    end
    subgraph Parser
      AST
    end
    subgraph コンパイラ
      Lexer
      Parser
      Token
      AST
      id1{Semantic}
      LLVM
    end
    subgraph LLVM
      LLVM_IR
      LLVM_IR --> アセンブリ
    end
    テキストファイル --> Token
    Token --> AST
    AST --> id1{Semantic}
    id1{Semantic} --> LLVM_IR
    アセンブリ --> 実行ファイル
```

## 字句解析器（Lexer）を使ってみよう

字句解析器（Lexer）は、コードの文字列を解析して、トークン(token 単語や記号などの小さな意味を持つ単位）に分解します。下記のようなコードで、CrystalのLexerを使うことができます。

https://github.com/crystal-lang/crystal/blob/master/src/compiler/crystal/syntax/lexer.cr

```crystal
require "./src/compiler/crystal/syntax"

str = ARGF.gets_to_end
a = Crystal::Lexer.new(str)
loop do
  t = a.next_token
  p t
  break if t.type == Crystal::Token::Kind::EOF
end
```

こんな感じで、タブ区切りテキストを表示できるようにしておくと、

```crystal
require "./src/compiler/crystal/syntax"

str = ARGF.gets_to_end
a = Crystal::Lexer.new(str)
loop do
  t = a.next_token
  puts [t.type,
        t.value,
        t.number_kind,
        t.line_number,
        t.column_number,
        t.filename,
        t.delimiter_state.kind,
        t.delimiter_state.nest,
        t.delimiter_state.end,
        t.delimiter_state.open_count,
        t.delimiter_state.heredoc_indent,
        t.delimiter_state.allow_escapes,
        t.macro_state.whitespace,
        t.macro_state.nest,
        t.macro_state.control_nest,
        t.macro_state.delimiter_state,
        t.macro_state.beginning_of_line,
        t.macro_state.yields,
        t.macro_state.comment,
        t.macro_state.heredocs,
        t.passed_backslash_newline,
        t.doc_buffer,
        t.raw,
        t.start,
        t.invalid_escape,
        t.location].map { |i| i.to_s }.join("\t")
  break if t.type == Crystal::Token::Kind::EOF
end
```

test.crを解析させると

```crystal:test.cr
x = 0
```

こんな結果が得られます。一行目を見ると、INDENT, SPACE, =, NUMBER, NEWLINE, EOF などが非常に細かい単位で分類されていることがわかると思います。

```
IDENT	x	i32	1	1		STRING			0	0	true	true	0	0		true	false	false		false			0	false	:1:1
SPACE		i32	1	2		STRING			0	0	true	true	0	0		true	false	false		false			0	false	:1:2
=		i32	1	3		STRING			0	0	true	true	0	0		true	false	false		false			0	false	:1:3
SPACE		i32	1	4		STRING			0	0	true	true	0	0		true	false	false		false			0	false	:1:4
NUMBER	0	i32	1	5		STRING			0	0	true	true	0	0		true	false	false		false			0	false	:1:5
NEWLINE		i32	1	6		STRING			0	0	true	true	0	0		true	false	false		false			0	false	:1:6
EOF		i32	3	1		STRING			0	0	true	true	0	0		true	false	false		false			0	false	:3:1
```

## 構文解析器（Parser）を使ってみよう

https://github.com/crystal-lang/crystal/blob/master/src/compiler/crystal/syntax/parser.cr

ParserはLexerを継承しています。かなり不格好ですが次のようなコードを作成しました。

```crystal
require "./src/compiler/crystal/syntax"

str = ARGF.gets_to_end
a = Crystal::Parser.parse(str)

def puts_ast(ast)
  puts "\e[32m# #{ast.class}\e[0m" # green
  puts ast
  puts
end

if a.is_a?(Crystal::Expressions)
  a.expressions.each do |ast|
    puts_ast(ast)
  end
else
  puts_ast(a)
end
```

これを自分自身に対して実行すると次のような出力が得られます。コードがいくつかの単位に分割されていることがわかります。

```crystal
# Crystal::Require
require "./src/compiler/crystal/syntax"

# Crystal::Assign
str = ARGF.gets_to_end

# Crystal::Assign
a = Crystal::Parser.parse(str)

# Crystal::Def
def puts_ast(ast)
  puts("\e[32m# #{ast.class}\e[0m")
  puts(ast)
  puts
end

# Crystal::If
if a.is_a?(Crystal::Expressions)
  a.expressions.each do |ast|
    puts_ast(ast)
  end
else
  puts_ast(a)
end

```

https://github.com/crystal-lang/crystal/blob/master/src/compiler/crystal/syntax/ast.cr

Parserが作成したASTノードを渡り歩くにはビジターモデルというものが使われているようです。が、すみません。今回はそこまで理解できていません。

### コンパイラ

```crystal
    def compile(source : Source | Array(Source), output_filename : String) : Result
      source = [source] unless source.is_a?(Array)
      program = new_program(source)
      node = parse program, source
      node = program.semantic node, cleanup: !no_cleanup?
      result = codegen program, node, source, output_filename unless @no_codegen

      @progress_tracker.clear
      print_macro_run_stats(program)
      print_codegen_stats(result)

      Result.new program, node
    end
```


## Semantic

Semanticはとても難しいらしく、ここまでくると解説資料も少なくなります。ここではVisitorモデルというのが使われているらしいです。

Aryさんの資料のPart2があります（ひょっとするとこれも未完成かもしれません）
私は諦めてしまいましたが、興味がある人はご覧ください。

https://docs.google.com/presentation/d/1eS88dj6-6c4T6NpRqIFGgu9iRbsEmJucCzpOKYewLro/edit#slide=id.p

LLVM IRはこの先で出力されているのだと思いますが、去年はそこまで追いかけることはできませんでした。

## まとめ

```mermaid
flowchart LR
style id1 fill:#fcf,stroke:#333,stroke-width:1px
    subgraph Lexer
      Token
    end
    subgraph Parser
      AST
    end
    subgraph コンパイラ
      Lexer
      Parser
      Token
      AST
      id1{Semantic}
      LLVM
    end
    subgraph LLVM
      LLVM_IR
      LLVM_IR --> アセンブリ
    end
    テキストファイル --> Token
    Token --> AST
    AST --> id1{Semantic?}
    id1{Semantic?} --> LLVM_IR
    アセンブリ --> 実行ファイル
```


Crystal --> assembly

```sh
crystal build --emit asm --prelude empty test.cr
```

Crystal --> LLVM IR

```
crystal build --emit llvm-ir --prelude empty test.cr
```

LLVM IR --> assembly

```
llc --relocation-model=pic test.ll
```

assembly --> executable

```
clang test.s
```

必要に応じて、リンクするライブラリを指定

```
clang test.s -levent -lgc -lm
```

llvm .ll -> .bc

```
llvm-as test.ll
lli test.bc
```

## 今回よくわからなかったこと

今回はCrstalのコードがどのように動いているのか簡単に観察しました。

この記事を書いたモチベーションの一つは、Crystalが分割コンパイルができない問題の理由を理解したいという気持ちです。Crystalで作成した関数を共有ライブラリに出力して他のライブラリから呼び出すことは推奨されていないとされます。その理由が知りたいと思っていました。

伝聞によるとCrystalは型を数値として管理しているらしく、最初にすべてのコードを読み込んで、型を数値にするらしく、分割コンパイルすると型の整合性が取れないようです。

分割コンパイルするときに、Aのコンパイルで作成した数値と型との対応は、Bの分割コンパイルで作成した数値と型の対応と異なり、整合性が取れなくなると理解しています。しかし、これはAryさんがわかりやすく説明するために単純化したもので、実際にはもっと難しい問題なのだろうと思います。

これを理解する前にSemanticsの中身を理解する必要があるようです。Aryさんのスライドによると、Aryさんの実装も特定の論文や既存のベストプラクティスに依拠しているわけではなく、試行錯誤しながら自分で組み立てたというふうに書いてある気がします。

これについては数日調べた程度で理解するのはおこがましいというものでしょう…。今回の探索はここまでとします。

## 最後に

この記事を書くまで、私はアセンブリ言語や、LLVM中間表現などに一回も触れたことがありませんでした。Rubyでスクリプトを書いているとなかなかこういった低レベルに触れる機会は少ないので、こういった新しい世界を学習する機会を与えてくれたCrystal言語とその作者に感謝しています。Crystal言語の開発の中心はアルゼンチンにありますが、オープンソースのプログラミング言語であり、誰でもその開発に参加することは可能です。この記事を見てCrystal言語に興味を持った方は、ぜひCrystal言語そのものの開発に挑戦してみてはいかがでしょうか。

この記事は以上です。

## 参考文献

https://crystal-lang.org/2015/03/04/internals.html

https://patshaughnessy.net/2021/12/22/reading-code-like-a-compiler

https://zenn.dev/silverbirder/articles/d6ae6419ac167e