OCaml でゲームボーイエミュレータを書いた話

# はじめに

ブラウザ上で動くゲームボーイエミュレータを OCaml で書きました。以下のページで試せます。

**[デモページ](https://linoscope.github.io/CAMLBOY/)**

いくつかの homebrew ROM も一緒になっているのでいろいろ遊んでみてください。おすすめは「Bouncing ball」と「Tobu Tobu Girl」です。最近のスマホならだいたい安定して 60 FPS 出るはずなので、スマホでも遊べます。

レポジトリはこちらです。

https://github.com/linoscope/CAMLBOY

## スクリーンショット

|                 　　　　　　　　 　　　　　　　　 　　　　　　　　　　　　　　　　　　　　　　　　　                 |
| :------------------------------------------------------------------------------------------------------------------: |
| ![hoge](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675652/669ab304-85a0-8cd6-5885-0074a0575b7a.gif) |

<div align="center">
  <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675652/7b13e3f2-bac6-3f32-57dd-7827bdc9be0c.gif" alt="zelda-gif" title="zelda-gif">
  <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675652/fc55e81a-323d-ffa2-b0f7-8e313cc60f1e.gif" alt="kirby-gif" title="kirby-gif">
  <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675652/ae8fb9a3-7ab8-23a0-16ba-9491168aa4c0.gif" alt="tetris-gif" title="tetris-gif">
  <img src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675652/420cc384-2653-64e1-0a81-3de6ff983b00.gif" alt="donkykong-gif" title="donkykong-gif">
</div>

## なぜ OCaml でゲームボーイエミュレータ？

新しいプログラミング言語を学ぶ過程で以下のように思ったことはないでしょうか？

- 簡単なプログラムなら書けるが、中規模以上のコード[^1]をどうやって書けばよいのか分からない
- 発展的な言語機能[^2]も勉強しなんとなく理解した気になったが、実践のなかでどのように活用すればいいのかが分からない

[^1]: 「中規模以上のコード」のざっくりとした定義は「テストなしでは開発しづらく、その結果、テストを書きやすいように設計をしなければいけないコード」です。この「テストしやすいコードを書く」というのは、教科書や言語の入門書では触れられないが実践では重要となるものの筆頭だと思っています。
[^2]: 「発展的な言語機能」は OCaml のファンクタや GADT や第一級モジュール などを想定しています。これらの機能はどのように動作するかは理解できても、どのようなときに便利なのかがイメージつきにくかったりすると思います。

OCaml を本格的に勉強し始めてた数ヶ月前の筆者はまさにこの状態になっていました。本を読んだり簡単なアルゴリズムを実装したりすることで OCaml の基本的な文法を理解することができましたが、この二つの「分からない」のせいで 「OCaml が書ける」という気になりませんでした。このような状態を抜け出すには実践を積むしかないのだろうと思い、取り組むべきプロジェクトを探し始めたのが最初のきっかけでした。

題材としてゲームボーイエミュレータを選んだのには以下のような理由があります。

- 仕様がはっきりしていてるので「何を実装するか」を考える必要がない
- 数日・数週間では完成しないくらいには複雑である
- 数ヶ月で太刀打ちできないほど複雑ではない
- 子供の頃ずっとゲームボーイで遊んでいたので思い入れがある

また、書き始める前に立てたエミュレータとしての目標は以下の通りでした。

- OCaml のベストプラクティスを意識し、コードの可読性・保守性を重視して書く
- どうせならブラウザで遊びたいので、js_of_ocaml を使って JS にコンパイルする
- スマホでも遊べたら楽しいので、スマホのブラウザでストレスなく遊べるくらいの FPS を達成する
- ベンチマークをしっかりとって様々な OCaml コンパイラバックエンドを比較する

## 本記事の目標

筆者は CAMLBOY の実装を通して前述の二つの「分からない」をある程度は乗り越えることができたと感じました。本記事の目標はその経験を少しでも共有することです。

例えば以下のような点をカバーしたいと思っています。

- ゲームボーイのアーキテクチャやエミュレータの実装方法の概要
- どのようにモジュール及びモジュール間の関係を設計し、可読性・再利用性の高いコードを書くか
- ファンクタ や GADT や 第一級モジュール はどういうときに便利なのか
- どのようにテストしやすいコードを書くか
- どのようにしてボトルネックを見つけ、どのようにしてパフォーマンスを改善していくか

逆に、以下のような点については触れません。

- OCaml に基本的な文法
- ゲームボーイのアーキテクチャやエミュレータの実装方法の詳細

これらを学ぶための資料は最後の「おすすめの資料」でまとめてあります。

# 実装

## 実装の概略図

CAMLBOY の実装の概略図[^3]は以下のようになります。

[^3]: ゲームボーイハードウェアの概要ではないので実際のハードウェアとズレている点があると思います。また、CAMLBOY で実装されていないコンポーネント（Audio Processing Unit など）は省略しています。

![camlboy-architecture-2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675652/e018f108-abd5-56cd-9680-c00ffc711fee.png)

詳しいことは必要に応じて解説しますが、ざっくりと説明すると

- CPU・Timer・GPU はクロックに従って一定周期で動作をしている(図の時計マークの部分)。
- CPU は Bus を介して各種ハードウェアモジュール（Timer, GPU, RAM など）からデータを読み書きできる。
- Bus とつながっている各種ハードウェアモジュールは 「8-bit のデータを読み書きできる」を表すシグネチャ Addressable_intf.S を実装する (図のオレンジ色の部分)
- Bus は 「8-bit あるいは 16-bit のデータを読み書きできる」を表すシグネチャ Word_addressable_intf.S を実装する (図の赤色の部分)
- カートリッジには様々な種類があり、種類に応じて実装が切り替わっている。
- Timer・GPU・Serial Port・Joypad は割り込みを要求することができ、その割り込みは Interrupt Controller を介して CPU に通知される （割り込みに関することは本記事では割愛します）

## メインループ

実際のハードウェアにおける CPU・Timer・GPU はハードウェアクロックを共有するので、自然と同期がとれた状態で一定周期で動作しています。エミュレータはただの大きな逐次実行のループなので「同期的がとれた状態」という部分を少し工夫して再現しなければなりません。具体的には、以下のように CPU で１命令だけ実行しそこで消費したサイクル数だけ Timer と GPU を進めるという方法[^4]でメインループを実装しました

[^4]: Timer と GPU を CPU に 追いつかせている("catch up" させている)ことから"catch up method" と呼ばれることがあります。

```OCaml:camlboy.ml
let run_instruction t =
  (* CPU が１命令実行する *)
  let mcycles = Cpu.run_instruction t.cpu in
  (* 命令の実行にかかったサイクル数分だけ GPU を進める *)
  Timer.run t.timer ~mcycles;
  (* 命令の実行にかかったサイクル数分だけ Timer を進める *)
  Gpu.run t.gpu ~mcycles
```

## Addressable_intf.S と Word_addressable_intf.S

つぎに、今後の説明に必要となるのでまずデータの読み書きに関するシグネチャ `Addressable_intf.S` と `Word_addressable_intf.S` についてみていきます。

- Addressable_intf.S
  - 「8-bit のデータのやりとりができる」を表すシグネチャ
  - Bus から見た 各種ハードウェアモジュール（Timer, GPU, RAM など）のインターフェース
- Word_addressable_intf.S
  - 「8-bit に加えて 16-bit データのやりとりができる」を表すシグネチャ
  - CPU から見た Bus のインターフェース

では、それぞれを詳しく見ていきましょう。

### Addressable_intf.S

Bus は 各種ハードウェアモジュールから 8-bit のデータを読み書きすることができます。「8-bit のデータを読み書きできる」 モジュールは今後いくつも実装していくので、何らかの形でインターフェースを共有したいところです。

OOP であれば

- インターフェースを書き（Java での`public interface A {...}`）
- それを実装する（Java での`implements A`）

と思いますが、OCaml では

- シグネチャを書き（`module type S = sig .. end`）
- それをインクルードする (`include A with type t := t `)

のが常套手段であるようです。具体的にみていきましょう。

まず、「8-bit のデータを読み書きできる」ことを表すシグネチャ`Addressable_intf.S`を以下のように定義します[^5][^6]。

[^5]: ここでの `type t`は「１モジュール１データ型スタイル」から来ています。「１モジュール１データ型スタイル」に関しては[こちら](https://github.com/camlspotter/ocaml-zippy-tutorial-in-japanese/blob/master/one-data-type-one-module.rst)の記事がわかりやすいです。
[^6]: 記事内のコードにでてくる `uint8` や `uint16` は OCaml 組み込みの型ではなく、自作の unsinged int モジュール(`uints.mli`, `units.ml`)からきています。実装の詳細は省きます。

```OCaml:addressable_intf.ml
module type S = sig
  type t
  (** [read_byte t addr]
      アドレス[addr] から 8-bit のデータを読む *)
  val read_byte : t -> uint16 -> uint8
  (** [write_byte t ~addr ~data]:
      アドレス[addr] へ 8-bit のデータ [data] を書き込む *)
  val write_byte : t -> addr:uint16 -> data:uint8 -> unit
  (** [accepts t addr]:
      アドレス [addr] を読み書きできるなら [true] を返し、そうでないなら [false] を返す *)
  val accepts : t -> uint16 -> bool
end
```

そして、「8-bit のデータを読み書きできる」 モジュールを書くときはこの `Addressable_intf.S` を`include`します。例えば、RAM (ゲームボーイに内蔵あれた汎用メモリ) のインターフェース `ram.mli`ではこんな感じです。

```OCaml:ram.mli
type t
...
include Addressable_intf.S with type t := t
```

同様にして、`gpu.mli`, `joypad.mli`, `timer.mli`, などが `Addressable_intf.S` を include しています。

#### 補足: `with type t := t` について

ここでの `with type t := t` の部分は少し説明が必要かもしれません。一般に、`A with type t := s`は シグネチャ`A`の中の型`t` を 型`s` で置き換えるという意味になります。なので`include Addressable_intf.S with type t := t` は「`Addressable_intf.S`の中の 型`t` を`Ram`の型`t`で置き換えて、その上で `include` する（ここに展開する）」という意味になります。つまり`ram.mli`は以下と同じであるということです：

```OCaml
(** ram.mli *)
type t
...
(* include Addressable_intf.S with type t := t
   を”展開”すると以下のようになる *)
val read_byte : t -> uint16 -> uint8
val write_byte : t -> addr:uint16 -> data:uint8 -> unit
val accepts : t -> uint16 -> bool
```

### Word_addressable_intf.S

CPU は Bus に対して、8-bit に加えて 16-bit のデータを読み書きできます。このように「8-bit のデータを読み書きできることに加えて、16-bit のデータも読み書きできる」というインターフェースの定義は「8-bit のデータを読み書きできる」というインターフェース（`Addressable_intf.S`）を拡張することで実現したいところです。

OOP であれば

- インターフェースの継承する(Java での`extends A`)

とおもいますが、OCaml ではこれも

- シグネチャを include する(`include A with type t := t `)

ことで実現できます。

具体的には、以下のように `Word_addressable_inf.S` というシグネチャを定義し、その中で `Addressable_intf.S` を `include` することで`Addressabble_intf.S` を拡張することができます。

```OCaml:word_addressable_intf.ml
(** 8-bit の読み書きに加えて 16-bit の読み書きができるシグネチャ *)
module type S = sig
  type t
  include Addressable_intf.S with type t := t
  val read_word : t -> uint16 -> uint16
  val write_word : t -> addr:uint16 -> data:uint16 -> unit
end
```

## Bus

Bus のインターフェース（`bus.mli`）は、上で定義した シグネチャ `Word_addressable_intf.S` を使って以下のように書けます。

```OCaml:bus.mli
type t
(** Bus とつながっている モジュールを初期化のときに渡す *)
val create :
  gpu:Gpu.t ->
  timer:Timer.t ->
  wram:Ram.t ->
  ... ->
  t
include Word_addressable_intf.S with type t := t
```

そして Bus 本体（`bus.ml`）の実装は以下のようになりました。

```OCaml:bus.ml
type t = {
  gpu   : Gpu.t;
  timer : Timer.t;
  wram  : Ram.t;
  ...
}
(** Bus とつながっている モジュールを初期化のときに渡す *)
let create ~gpu ~timer ~wram ... = {
  gpu;
  timer;
  wram;
  ...
}
let read_byte t addr =
  (** 与えられたアドレスに応じて適切な モジュールの `read_byte` を呼んでいる *)
  match addr with
  | _ when Gpu.accepts t.gpu addr ->
    Gpu.read_byte t.gpu addr
  | _ when Timer.accepts t.timer addr ->
    Timer.read_byte t.timer addr
  | _ when Ram.accepts t.wram addr ->
    Ram.read_byte t.wram addr
  | ...

let read_word t addr =
  (** read_word は read_byte を二回よぶことで実現される。
      （実際のハードウェアでも二回 8-bit のデータアクセスを繰り返すことで
      16-bit のデータアクセスを実現している） *)
  let lo = Uint8.to_int (read_byte t addr) in
  let hi = Uint8.to_int (read_byte t Uint16.(succ addr)) in
  (hi lsl 8) + lo |> Uint16.of_int
...
```

## CPU

づぎに CPU についてみていきましょう。まずは CPU が内蔵するレジスタについてです。

### レジスタ

CPU は `A`, `B`, `C`, `D`, `E`, `F`, `H`, `L` の 8 つの 8-bit レジスタを持ちます。これら 8-bit レジスタは二つくっつけて `AF`, `BC`, `DE`, `HL` という 16-bit レジスタとして読み書きすることもできます。以下 `Regsiters` モジュールのインターフェースだけ載せておきます（実装は省略）。

```OCaml:registers.mli
type t
(** 8-bit レジスタの識別子 *)
type r = A | B | C | D | E | F | H | L
(** 16-bit レジスタの識別子*)
type rr = AF | BC | DE | HL
...
(** 8-bit レジスタの read/write *)
val read_r : t -> r -> uint8
val write_r : t -> r -> uint8 -> unit
(*16-bit レジスタの read/write*)
val read_rr : t -> rr -> uint16
val write_rr : t -> rr -> uint16 -> unit
```

### CPU の実装

CPU は基本的に fetch-decode-execute という３つのステップを繰り返しています。

- Fetch: プログラムカウンタに基づいて Bus から命令のバイト列をとってくる
- Decode: 命令のバイト列を命令にデコードする
- Execute: デコードした命令を実行する

CPU の実装は以下のようになりました。`run_instruction`において fetch-run-execute のサイクルが行われていることがわかるとおもいます。`execute`の実装に関しては後述します。

```OCaml:cpu.mli
module Make (Bus : Word_addressable_intf.S) : sig
  (** CPU の状態を表す値の型 *)
  type t
  (** CPU を初期化する *)
  val create : bus:Bus.t -> registers:Registers.t -> ... -> t
  (** 状態 t の元で１命令実行する *)
  val run_instruction : t -> int
end
```

```OCaml:cpu.ml
module Make (Bus : Word_addressable_intf.S) = struct
  type t = {
    registers  : Registers.t; (* レジスタ *)
    bus        : Bus.t;       (* Bus *)
    mutable pc : uint16;      (*プログラムカウンタ*)
    ...
  }
  let create ~bus ~registers ... = {
      bus;
      registers;
      ...
  }
  let execute t inst =
     ...
     (* 後ほど詳しくみていきます *)
     ...
  let run_instruction t = ...
    (* アドレス pc から１命令 fetch して decode する。
       Fetch_and_decode.f の実装は省略する。*)
    let inst = Fetch_and_decode.f t.bus ~pc:t.pc in
    (* 命令を execute する *)
    execute t inst
end
```

上の実装においてまず注目すべきは、 CPU が `Bus : Word_addressable_intf.S` を受け取るファンクタ(functor)として実装されているところです。ファンクタになっていることの利点はいくつかありますが、一番大きいのは単体テストにおいて Bus の実装をモックで置き換えられる点です。

実際にテストファイル(`test_cpu.ml`)では`Mock_bus` を使って以下のように CPU を初期化しています。`Mock_bus` は内部で一つのバイト列を持つだけの非常にシンプルな`Word_addressable_intf.S` の実装です。

```OCaml:test_cpu.ml
...
module Cpu = Cpu.Make(Mock_bus)
...
let cpu = Cpu.create ~bus:(Mock_bus.create ~size:0xFF) ~
...
```

図示するとこんな感じになっています。「実装の概略図」に載せた図に比べると依存関係がとてもシンプルになっていることが分かります。

![camlboy-arch-mocked-bus.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675652/34b6040a-7093-df15-df3b-74854dadc9e3.png)

もし CPU が直接 Bus に依存していたら、上の `Mock_bus.create ~size:0xFF`の部分で `Bus.create ~gpu ~timer ~wram ...`というように各種モジュールを使った初期化を行う必要があったでしょう。 Bus は 多くのモジュールに依存するが故に初期化処理も大変なので、ここを省略できるのはとても助かります。また、GPU, Timer, Ram, ... などとつながったちゃんとした Bus モジュールが実装されていない段階でも CPU をテストできる点も嬉しいです。

#### 命令セット及び `execute`の実装

つづいて 先程の`cpu.ml` において省略されていた `execute` の実装を見ていきます。まず `execute` が実行する命令セットについての紹介からです。

ゲームボーイの命令セットには 8-bit 命令と 16-bit 命令があります。

- 8-bit 命令:
  - 引数部分に 8-bit レジスタ (A レジスタなど)や 8-bit の値 (`0x12`など)を持つことができる
- 16-bit 命令:
  - 引数部分に 16-bit レジスタ (AF レジスタなど)や 16-bit の値(`0x1234`など)を持つことができます。

例えば足し算には以下のように 8-bit 命令のバージョンの足し算と 16-bit 命令のバージョンの足し算があります。

```assembly
# 8-bit バージョン。
# A レジスタの中身(8-bit) に 0x12 を足し、結果を Aレジスタに保存する
ADD8 A, 0x12
# 16-bit バージョン。
# AF レジスタの中身(16-bit) に 0x1234 を足し、結果を AFレジスタに保存する
ADD16 AF, 0x1234

```

では、この命令セットはどのようにして定義すればよいでしょうか？

##### ヴァリアントによる命令セットを定義

最初に試した方法は命令とその引数をヴァリアントで表現することでした。

```OCaml:instruction.ml
type arg =
  | Immediate8 of uint8   (* 8-bit の値 *)
  | Immediate16 of uint16 (* 16-bit の値 *)
  | R of Registers.r      (* 8-bit レジスタ *)
  | RR of Registers.rr    (* 16-bit レジスタ *)
  | ...
type t =
  | ADD8  of arg * arg
  | ADD16 of arg * arg
  | ...
```

##### ヴァリアントによる定義の問題点

上の定義をつかって以下のように `execute`を定義しようとしたところ、うまくいかないことに気が付きました。

```OCaml:cpu.ml
let execte t (inst : Instruction.t) =
  ...
  let read_arg = function
    | Immidiate8 x  -> x
    | Immediate16 x -> x
    | ...
  in
  match inst with
  | Add8 (x, y) ->
    (* Uint8.add の型は uint8 -> uint8 -> uint8 *)
    let sum = Uint8.add (read_arg x) (read_arg y) in
    ...
  | Add16 (x, y) ->
    (* Uint16.add の型は uint16 -> uint16 -> uint16 *)
    let sum = Uint16.add (read_arg x) (read_arg y) in
    ...
```

上のコードにおける `read_arg` の返り値の型は何になるでしょうか？よく見てみると、どのコンストラクタにマッチしたかによって match 式の返す値の型が変わってしまい、そのせいで関数全体の返り値の方が一意に定まらないことがわかります。

```OCaml
  (* 返り値の型は??? *)
  let read_arg : Instruction.arg -> ??? = function
    | Immidiate8 x  ->
      (* Immidiate8 にマッチしたときの返り値は uint8 *)
      x
    | Immediate16 x ->
      (* Immidiate16 にマッチしたときはの返り値は uint16 *)
      x
    | ...
  in
```

筆者はここで GADT という、以前勉強したけどいまいちしっくりこなかった言語機能を思い出しました。じつは GADT を使えばマッチ式の分岐によって返す値の型が違う関数も定義できるのです。

##### GADT による命令セットの定義

GADT を用いた命令セットの定義をみてみましょう。

```OCaml:instruction.ml
type  arg =
  | Immediate8  : uint8        -> uint8  arg
  | Immediate16 : uint16       -> uint16 arg
  | R           : Registers.r  -> uint8  arg
  | RR          : Registers.rr -> uint16 arg
  | ...
type t =... (* type t はヴァリアントのときと一緒 *)
```

この定義の意味するところを理解するために、二行目のコンストラクタ `Immediate8`、なかでも特に`:` の後にある `uint8 -> uint8 arg`の部分に着目しましょう。

まず、矢印の左側 `uint8 -> ...` における `uint8`について、これは ヴァリアントの定義

```OCaml
| Immediate8 of uint8
```

における`of uint8` の `uint8`と同じ機能をもち、コンストラクタをパターンマッチしたときに**手に入る値の型**をコンストラクタごとに変化させています。以下における `n8` と `n16` が別々の型を持ちうるのは、この部分(ヴァリアントにおける `of t`, GADT における `t -> ..`)がコンストラクタごとに違うからです。

```
match arg with
| Immediate8  n8  -> ..
| Immediate16 n16 -> ..
```

一方で `... -> uint8 arg` における `uint8` は何を表すのでしょうか？ヴァリアントの定義をみても対応するものはなさそうです。

これは、コンストラクタをパターンマッチしたときに**返す値の型**をコンストラクタごとに変化されるために使われます。上のマッチ式を例にとると `| Immediate8 n -> ...` における `...` の型をマッチしたコンストラクタごとに変えられるということです。

まとめると、ヴァリアントは match 式において コンストラクタごとに **手に入る値の型** を変化させられるのに対して、GADT は match 式において コンストラクタごとに **返す値の型**も変化させることができるのです[^7]。

[^7]: この意味においてヴァリアントより "General" であるから "Generalized" algebraic data type と呼ばれていると予想していますが、ちゃんと調べていないのでわからないです。

GADT によって定義された `Instruction.arg` を使って `execute` は以下のように定義できます

```OCaml:cpu.ml
let execute t (inst : Instruction.t) =
  ...
  let read_arg : type a. a Instruction.arg -> a = fun arg ->
    match arg with
    | Immediate8 n -> n
    | Immediate16 n -> n
    | ...
  in
  match inst with
  | Add8 (x, y) ->
    let sum = Uint8.add (read_arg x) (read_arg y) in
    ...
  | Add16 (x, y) ->
    let sum = Uint16.add (read_arg x) (read_arg y) in
    ...
```

`a Instruction.arg -> a`をみると与えられたコンストラクタに応じて返り値の型が変化していることがわかると思います。例えば、`Immediate8 n`を渡した場合と`Immediate16 n`を渡した場合を考えると、前者は`Immediate8 n`が `uint8 arg` 型なので `uint8`を返し、後者は`Immediate16 n`が `uint16 arg`型なので `uint16` を返す、といった具合です。

## カートリッジ

ゲームボーイのカートリッジはいくつかのタイプに分別でき、それぞれのタイプに応じて様々なハードウェアモジュールをカートリッジ内部にもっています。例えば、ROM_ONLY タイプのカートリッジ(テトリスなど)はゲームのコードを保存した ROM をもつだけである一方、MBC3 タイプのカートリッジ（ポケモン赤など）は ROM に加えて（ゲームボーイ本体にあるものとは独立した）RAM やタイマーを持ちます。

エミュレータではこれらのカートリッジを別々のモジュールとして実装することになります。よって、実行時にカートリッジのタイプに応じてモジュールを選択する機構が必要となります。

このように、「実行時にモジュールを選択する」ときに便利なのが 第一級モジュール(first class module)です。第一級モジュール を使うと実行時にカートリッジのモジュールを選択する `Detect_cartridge.f`を書けます。（インターフェースだけ。実装の詳細は省略します。）

```OCaml:detect_cartridge.mli
(** カートリッジの種類を判別し、そのカートリッジの種類を実装するモジュールを
    第一級モジュールとして返す *)
val f : rom_bytes:Bigstringaf.t -> (module Cartridge_intf.S)

```

## JS へのコンパイル

Javascript へのコンパイルは`js_of_ocaml`　(及び `dune`) を使って驚くほど簡単にできました。どれほど簡単だったかというと、 [このコミット](https://github.com/linoscope/CAMLBOY/commit/ac04c5d1ca39514cf7f34d19b2c5e702cc3d28c1)一つでブラウザ上で動くところまでいけたくらいです。

ブラウザ API を叩く部分のコードは [Brr](https://github.com/dbuenzli/brr)というライブラリを使いました。
js_of_ocaml のブラウザ API は JS のオブジェクトを OCaml のオブジェクトで表現しているため OCaml の "O" に慣れていないとつらいのですが、Brr の API は JS のオブジェクトを OCaml のモジュールシステムで表現しているのでかなりとっつきやすくてよかったです。

## 最適化

無事ブラウザ上で動かせるようになったはいいものの、動作がとても遅いという問題に直面しました。下の gif はブラウザで動かせるようになった直後の様子です（PC のブラウザで動かしています）。計測してみると~20 FPS くらいしかだせていません。

![before-optimize.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675652/dbd90497-4c32-875a-9a27-f56e1ccc8b02.gif)

このままではゲームを遊ぶことはできないので、これから頑張って最適化をしていくことになります。最終的には以下のように ~100FPS くらいまで改善することができました。

![after-optimize-2.gif](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675652/18986757-0719-61f2-a761-22a43b6f8f46.gif)

では、どのように最適化を行ったかを順を追ってみていきましょう。

### プロファイラを使ってボトルネックを見つける

まず、Chrome のプロファイラを使ってどこがボトルネックになっているかを探りました。以下がこのときのプロファイル結果です[^8]。

[^8]: このように Chrome のプロファイラが使えるというのは、JS にコンパイルすることの嬉しい副作用でした。おそらく、OCaml のネイティブのプロファイラはここまでいい感じの UI がないのではないでしょうか？（試していないのでわかりませんが）。また、js_of_ocaml がソースマップを生成してくれるおかげで OCaml コードにおけるファイル名・行番号がみれるのも助かりました。

![profile-first.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675652/c8e7536f-3f84-eab7-5fd3-0156e8332cdc.png)

この結果から GPU が ~73%の時間を消費していて、その中でもとくに`tile_data.ml`, `oam_table.ml`, `tile_map` がそれぞれ 34%, 18%, 8% の時間を消費している、ということがわかります。
同様にして、`timer.ml`や `Bigstringaf`の関数が多く時間を使っていることがわかりました。

### 最適化

ボトルネックが分かったところで、つぎはそれらの解消に取り組みました。本記事では触れていない部分の変更なので、行った最適化及びその結果を列挙するだけにとどめます。

- `oam_table.ml`の高速化 ([コミット](https://github.com/linoscope/CAMLBOY/commit/47989b77451873202268c955bc3b650420e648e8)):
  - 14fps -> 24fps
- `tile_data.ml`の高速化 ([コミット](https://github.com/linoscope/CAMLBOY/commit/bdc7c58c8ec1720eb38f59a64320d06f655f78f5)):
  - 24fps -> 35fps
- `timer.ml` の高速化([コミット](https://github.com/linoscope/CAMLBOY/commit/db49742096db50f1f52cb72b2e5136fbd4912163)):
  - 35fps -> 40fps
- `tile_map.ml`の高速化([コミット](https://github.com/linoscope/CAMLBOY/commit/7c2a6b9f694c57983da032d71a44f81f51e3cb65)):
  - 40fps -> 50fps
- `Bigstringaf.get`のかわりに`Bigstringaf.unsafe_get`を使う([コミット](https://github.com/linoscope/CAMLBOY/commit/2691a664465051eaa3b93954675e636ca4ec835a)):
  - 50fps -> 60fps

### インラインを無効化する

ここまでで PC のブラウザでは 60FPS だせるようになったのですが、スマホでは 20~40fps くらいしか出ずにゲームを遊べない状態でした。
なかなか行える最適化もそこを尽きてきたのでどうしたものかと思っていたところ、release ビルド (`dune build --profile release`) の出力する JS のほうが dev ビルド(ただの`dune build`)の出力する JS より遅いことに気が付きました(それも 3 倍以上)。ネット上でいろいろ聞いてみたところ[^9]、どうやら js_of_ocaml が行っているインライン化が JS のパフォーマンスを落としている[^10]ことがわかり、インライン化を無効化することによって無事にスマホでも 60fps 出せるようになりました。

[^9]: https://discuss.ocaml.org/t/js-of-ocaml-output-performs-considerably-worse-when-built-with-profile-release-flag/8862
[^10]: 関数が長くなりすぎると JS エンジンの JIT が行われなくなるせいだと予想しているのですが、確かなことはわかりません。

## ベンチマーク

UI なしでエミュレータを走らせる "headless benchmarking mode" を実装し、 OCaml コンパイラバックエンドを切り替えつつ FPS を測定したところ、結果は下のようになりました[^11]。

![benchmark-result.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/675652/4fc0c620-3c45-fb79-9016-53f425974f1f.png)

[^11]: このベンチマーク結果は他のゲームボーイエミュレータとの比較には使えない点には注意が必要です。エミュレータのパフォーマンスは、どこまで正確さを求めるかやどこまで機能を充実させるかになどに大きく左右されるからです。例えば、CALMBOY は APU (Audio Processing Unit)を実装していないので APU を実装しているエミュレータと比較しても意味がありません。

# 終わりに

## エミュレータ開発の感想

エミュレータ開発はある面において競技プログラミングと似ていると感じました。どちらも以下のステップの繰り返しで進むからです。

- 仕様が与えられ
  - 競プロであれば問題文、エミュレータであれば wiki などの資料
- それに沿って実装をし
- 実装できたかどうかの判定を簡単にできる
  - 競プロであればオンラインジャッジへの提出、エミュレータであれば実際の ROM を動かす

これまで「プログラミングをしたいけど作りたいものがない」という人には「何を作るか考えなくてよい」という意味で競技プログラミングをすすめてきましたが、今後はエミュレータ開発もおすすめできると思います。
作りたいものがないが、アルゴリズムを勉強することには興味がなく、どちらかというと開発手法や設計を学びたい、というひとには特におすすめだとおもいます。

## OCaml の感想

### OCaml の良かったところ

#### エコシステム

OCaml を取り巻くエコシステムは目まぐるしく発展しています。`dune`のおかげで(現代的なプログラミング言語では当たり前になりつつある) 「ファイルを適当にディレクトリに放り込んでおけば後はビルドシステムがよしなにビルドしたりテストを実行したりしてくれる」という体験が提供されています。また、エディタサポートも`merlin`などのおかげでだいぶ改善しており、エディタに コード補完やコードジャンプを導入するのもとても簡単になっています。

「何年か前に OCaml 触ってみたけど、エコシステムが微妙すぎて撤退した」みたいなひとには是非またトライしてもらいたいです。

#### "関数型"でなくても良い言語

関数型言語は「なるべく副作用を用いないプログラミングスタイルをサポートする言語」みたいに定義されることが多いですが、自分は前からこの「副作用を用いない」という部分に違和感を感じていました。定義が間違っているといいたいわけではなく、自分は"関数型言語"が好きだと思っているが別に副作用の有無にそこまでこだわりを感じていないという意味においてです。「隠蔽されていない mutable な状態が悪いのはわかるが、隠蔽されていれば別にいいんじゃない？」と思っていました。

実際、 CAMLBOY の実装は（パフォーマンスのため）にいたるところで mutable な状態を持ちます。多くのモジュールが`t -> .. -> unit` と `unit` を返す関数を持つことからもそのことがわかります。そして、このような非”関数型”な実装になっているにもかかわらず、OCaml の利点を享受しそこなっていると感じることはありませんでした。

自分は別に関数型言語が好きなのではなくて、ただヴァリアントとパターンマッチとモジュールシステムといい感じの型推論がある静的型言語が好きなのだな、ということに気がついたのは一つの収穫でした。

### OCaml の微妙だったところ

#### "抽象に依存"することのコストが高い

あんまりまだうまく言語化できていないのですが(意味不明だったら読み飛ばしてください)、OCaml は "抽象に依存"することのコストが高いと感じることがあります（コストが高いだけで、"抽象に依存"することができないわけではない点に注意）。

例えば下のように A, B, C というモジュールが A -> B -> C という依存関係を持ちながら存在するとするとします。

```OCaml
module A = struct .. B.foo () .. end
module B = struct .. C.foo () .. end
module C = struct .. end
```

このとき、B -> C の間の依存関係断ち切りたいと思ったとします。つまり、B 内において、 C の具体的な実装に依存する代わりに C の抽象(インターフェース）に依存させたいと思ったとします。これは以下のような手順で行えると思います。

- C の インターフェースを C_intf というシグネチャに抽出する
- B を C_int を満たすモジュールを受け取るファンクタとして定義する

これらの変更の結果、下のようになります。

```OCaml
module A              = struct .. B.foo () .. end
module B (C : C_intf) = struct .. C.foo () .. end
module C              = struct .. end
```

しかし、これではコンパイルが通りません。なぜなら、A 内で参照してる B はいまやモジュールではなくファンクタになってしまったからです。よって、B のインターフェースを B_intf として抽出し、 A を B_intf を満たすモジュールを受け取るファンクタにしなければなりません。

```OCaml
module A (B : B_intf)          = struct .. B.foo () .. end
module B (C : C_intf) : B_intf = struct .. C.foo () .. end
module C                       = struct .. end
```

このように、A -> B -> C において B -> C の部分だけを変更したかったのに、それが A -> B の部分にも波及してしまっています。

実際、CAMLBOY の実装において Camlboy -> Bus -> Cartridge という依存関係がある状態でカートリッジの実装を実行時に選択できるようにするときにこの問題に直面しました。

今回は依存関係が”浅い”おかげでそこまで問題になりませんでしたが、より階層の深い依存関係のときにどうなるのかは心配です。(そんな深い依存関係がある時点で設計に問題があるのかもしれませんが)

## おすすめの資料

### OCaml について

以下の workshop 資料がかなりおすすめです。

- [Learn OCaml Workshop](https://github.com/janestreet/learn-ocaml-workshop)
  - Jane Street 社内で使われている（いた？） OCaml の教材。穴あきの実装とその穴を埋めないと通らないテストという構成で書かれているので、 手を動かしながら OCaml の基礎を効率的に習得できます。後半は Snake や Lumines などの結構複雑なプログラムも題材になるので、どのようにモジュールを切り分ければよいかやどのようにビルドシステムを使えばよいのかなども学べていい感じです。

書籍としては以下がおすすめです。

- [プログラミング in OCaml](https://gihyo.jp/dp/ebook/2012/978-4-7741-5314-8)
  - OCaml 初心者にはこちらの本がおすすめです。練習問題が充実しているのが助かります。
- [Real World OCaml](https://dev.realworldocaml.org/)
  - OCaml の基本的な文法は知っていたり、他の関数型言語のプログラミング経験がある人はこちらがおすすめです。OCaml でちゃんとしたプログラムを書く上で必要になる知識（どうやって JSON をパースするか、など）が実践的な例を交えて紹介されています。

### ゲームボーイについて

- [The Ultimate Game Boy Talk](https://www.youtube.com/watch?v=HyzD8pNlpwI)
  - 一時間でゲームボーイのアーキテクチャについて一通り説明してしまっているすごい動画です。何回も見直しました。
- [gbops](https://izik1.github.io/gbops/)
  - 命令セットの表。命令をデコードするときに必要な情報がまとまっています。
- [Game Boy CPU Manual](http://marc.rawer.de/Gameboy/Docs/GBCPUman.pdf)
  - CPU のマニュアル。命令セットの実装はこれをみながらおこないました。ところどころ間違っている点に注意が必要です。
- [Pandocs](https://gbdev.io/pandocs/)
  - ゲームボーイエミュレータを実装する上で必要な情報が網羅されている Wiki。GPU や Timer などはこれを見ながら書きました。
- [Imran Nazar's blog](https://imrannazar.com/GameBoy-Emulation-in-JavaScript)
  - Javascript でゲームボーイエミュレータを実装するチュートリアル。実装の流れをなんとなく掴むのに便利です。