More than 1 year has passed since last update.

ML (Meta Languages)Advent Calendar 2021

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

Last updated at 2021-12-27Posted at 2021-12-12

はじめに

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

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

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

スクリーンショット

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

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

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

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

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

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

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

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

本記事の目標

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

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

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

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

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

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

実装

実装の概略図

CAMLBOY の実装の概略図³は以下のようになります。

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

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 を進めるという方法⁴でメインループを実装しました

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を以下のように定義します⁵⁶。

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ではこんな感じです。

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は以下と同じであるということです：

(** 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 を拡張することができます。

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 を使って以下のように書けます。

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）の実装は以下のようになりました。

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 モジュールのインターフェースだけ載せておきます（実装は省略）。

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の実装に関しては後述します。

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

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 の実装です。

test_cpu.ml

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

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

もし 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 命令のバージョンの足し算があります。

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

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

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

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

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を定義しようとしたところ、うまくいかないことに気が付きました。

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 式の返す値の型が変わってしまい、そのせいで関数全体の返り値の方が一意に定まらないことがわかります。

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

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

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

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

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について、これはヴァリアントの定義

| 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 式においてコンストラクタごとに 返す値の型も変化させることができるのです⁷。

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

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を書けます。（インターフェースだけ。実装の詳細は省略します。）

detect_cartridge.mli

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

JS へのコンパイル

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

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

最適化

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

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

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

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

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

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

最適化

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

oam_table.mlの高速化 (コミット):
- 14fps -> 24fps
tile_data.mlの高速化 (コミット):
- 24fps -> 35fps
timer.ml の高速化(コミット):
- 35fps -> 40fps
tile_map.mlの高速化(コミット):
- 40fps -> 50fps
Bigstringaf.getのかわりにBigstringaf.unsafe_getを使う(コミット):
- 50fps -> 60fps

インラインを無効化する

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

ベンチマーク

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

終わりに

エミュレータ開発の感想

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

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

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

OCaml の感想

OCaml の良かったところ

エコシステム

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

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

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

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

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

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

OCaml の微妙だったところ

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

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

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

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 を満たすモジュールを受け取るファンクタとして定義する

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

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 を満たすモジュールを受け取るファンクタにしなければなりません。

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 でゲームボーイエミュレータを書いた話

はじめに

スクリーンショット

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

本記事の目標

実装

実装の概略図

メインループ

Addressable_intf.S と Word_addressable_intf.S

Addressable_intf.S

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

Word_addressable_intf.S

Bus

CPU

レジスタ

CPU の実装

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

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

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

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

カートリッジ

JS へのコンパイル

最適化

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

最適化

インラインを無効化する

ベンチマーク

終わりに

エミュレータ開発の感想

OCaml の感想

OCaml の良かったところ

エコシステム

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

OCaml の微妙だったところ

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

おすすめの資料

OCaml について

ゲームボーイについて

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

はじめに

スクリーンショット

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

本記事の目標

実装

実装の概略図

メインループ

Addressable_intf.S と Word_addressable_intf.S

Addressable_intf.S

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

Word_addressable_intf.S

Bus

CPU

レジスタ

CPU の実装

命令セット及び executeの実装

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

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

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

カートリッジ

JS へのコンパイル

最適化

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

最適化

インラインを無効化する

ベンチマーク

終わりに

エミュレータ開発の感想

OCaml の感想

OCaml の良かったところ

エコシステム

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

OCaml の微妙だったところ

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

おすすめの資料

OCaml について

ゲームボーイについて

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

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