脱・初級者のための自作GBエミュレータ開発

30.1K Views

March 24, 23

#OCaml #関数型プログラミング #ゲームボーイエミュレータ #Functor #GADT

スライド概要

第四回関数型プログラミング（仮）の会

Lin Oshitani

@linoscope

スライド一覧

都内在住のエンジニア

またはPlayer版

埋め込む »CMSなどでJSが使えない場合

ダウンロード

ダウンロード(pdf - 1.79MB)

関連スライド

進化する自己修復型ブロックチェーンTezos

Lin Oshitani 7.4K

猫でも分かるUnreal Engineの学び方 - 超初心者向け編 - 2023 v1.0

ue4 ue5 ue-beginner

エピックゲームズジャパン 1.3M

Unreal Engine5 Lumenの仕組みと肝心なところ

ue5 ue-rendering ue-lumen

エピックゲームズジャパン 1.1M

SQL滅ぶべし

株式会社ホクソエム 850.1K

猫でも分かる UE5.0, 5.1 におけるアニメーションの新機能について【CEDEC+KYUSHU 2022】

ue5 cedec+kyushu ue-animation ue-optimize ue-bp ue-physics ue-sequencer

エピックゲームズジャパン 799.5K

各ページのテキスト

脱・初級者のための自作GBエミュレータ開発押谷倫 Lin Oshitani @linoscope 第四回関数型プログラミング（仮）の会

新しいプログラミング言語を勉強する際、このように感じたことはありませんか？

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

● 簡単なプログラムなら書けるが、中規模以上のプログラムをどうやって書けばよいのか分からない ● 高度な言語機能を勉強しなんとなく理解した気になったが、実践のなかでどのように活用すればいいのかが分からない一年半前にを本格的に勉強しはじめたときの自分

このときの心情

初級者本趣味自分簡単なプログラム

初級者中級者本趣味自分簡単なプログラム業務オープンソース活動

初級者中級者本趣味自分簡単なプログラムいまやってることの延長線上でたどりつける気がしない。。業務オープンソース活動

初級者中級者本趣味自分簡単なプログラム業務いまやってることの延長線上でたどりつける気がしない。。中級の谷オープンソース活動

10.

どうする？

11.

とりあえず実践をつむためになにか実装してみよう

12.

ゲームボーイエミュレータ！

13.

OCaml で書かれたゲームボーイエミュレータ js_of_ocaml というライブラリを使って JS にコンパイル https://github.com/linoscope/CAMLBOY

https://github.com/linoscope/CAMLBOY

14.

僕は CAMLBOY の実装を通して、前述の「谷」をある程度乗り越えることができたと感じました。本発表の目標は、その経験を少しでも共有することです。

15.

なぜGBエミュレータ？

16.

仕様がはっきりしていて「何を実装するか」を考える必要がない競技プログラミングに近い。「テストケースが通るかどうか」＝「ゲームのカートリッジが動くかどうか」

17.

「中規模以上」のコード「中規模以上」＝「テストなしでは開発しづらく、その結果、テストを書きやすいように設計をしなければいけないコード」

18.

思い入れがある家族が寝静まってから、布団に潜って、ゲームボーイライトでポケモンを遊んだ記憶

19.

実装

20.

そもそもエミュレータって？

21.

ゲーム機ハードウェアマシンコード ... VRAM LD A, B CPU JMP 0x1200 ADD A, 0x12 LD A, C 入力 RAM JMP 0x1201 出力 ADD A, 0x12 LD A, 0x12 カートリッジ挿入口 ... https://www.suruga-ya.jp/produ ct/detail/165005345 https://item.fril.jp/76e17f08bf11abdf5d244a3dde1c3079 https://www.copetti.org/writings/consoles/game-boy/

22.

エミュレータハードウェアマシンコード ... VRAM LD A, B CPU JMP 0x1200 ADD A, 0x12 入力 LD A, C RAM JMP 0x1201 出力 ADD A, 0x12 LD A, 0x12 カートリッジ挿入口 ... https://www.suruga-ya.jp/produ ct/detail/165005345 https://item.fril.jp/76e17f08bf11abdf5d244a3dde1c3079 https://www.copetti.org/writings/consoles/game-boy/ 入ハードウェアを「模倣」するから「エミュレータ」力ソフトウェア出力

23.

実装の概略図

24.

RAM Timer Joypad CPU Bus Registers Cartridge GPU Serial Port

25.

RAM Timer Joypad CPU Bus Registers Cartridge GPU Serial Port

26.

RAM Timer Joypad CPU Bus Registers Cartridge GPU Serial Port

27.

CPU と IO デバイスをつなぐの「仲介役」 RAM Timer Joypad CPU Bus Registers Cartridge GPU Serial Port

28.

RAM Timer Joypad CPU Bus Registers read 0x0000~0x3FFF カートリッジからデータを読み出す Cartridge GPU Serial Port

29.

メモリにデータを読み書きする RAM Timer Joypad read/write 0xC000~0xCFFF CPU Bus Registers Cartridge GPU Serial Port

30.

タイマーのスピードを変更する RAM CPU Timer Joypad write 0xFF07 Bus Registers Cartridge GPU Serial Port

31.

CPU と Bus の実装

32.

最初の実装 cpu.ml bus.ml type t = { type t = { bus : Bus.t; ... : Cartridge.t; ram : Ram.t; ... } ... cartridge } let x = Bus.read t.bus addr in ... let read t addr = (* read を中継 *) let write t addr data = (* write を中継 *) ...

33.

最初の実装 cpu.ml bus.ml type t = { type t = { bus ... } : Bus.t; cartridge : Cartridge.t; ram : Ram.t; 問題がある！... ... } let x = Bus.read t.bus addr in ... let read t addr = (* read を中継 *) let write t addr data = (* write を中継 *) ...

34.

問題： CPU→Bus→Cartridge/… が密結合していてCPUを単体でテストできない bus.ml cpu.ml type t = { type t = { bus : Bus.t; ... } cartridge : Cartridge.t; ram : Ram.t; ... 依存 } ... let x = Bus.read t.bus addr in ... let read t addr = ... let write t addr data = ... ... 依存 cartridge .ml ram.ml ...

35.

そういえば Functorってのがあったな。。

36.

[beta]

解決法： Functor でCPUをBusの実装ではなく
インターフェースに依存させることができる。
cpu.ml

bus_intf.ml

module Make (Bus : Bus_intf.S) = struct
type t = {
bus

: Bus.t;

...
}
...
let x = Bus.read t.bus addr in

...
end

module type S = sig

依存

type t
val read
val write

: t -> addr -> uint16
: t -> addr -> uint16 -> unit

...
end

実装
bus.ml

実装
mock_bus.ml

37.

CPUの単体テスト内では実際の Bus の実装ではなく Mock_bus をつかう test_cpu.ml module Cpu = Cpu.Make(Mock_bus) ...

38.

Functorを使えば、「実装」ではなく「インターフェース」に依存する疎結合でテスタブルなコードがかける

39.

CPUの実装（より詳しく）

40.

CPUには 8-bit レジスタと 16-bit レジスタがある 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

41.

命令セットには 8-bit命令と 16-bit命令がある # 8-bit バージョン。 # A レジスタの中身 (8-bit) に 0x12 を足し、結果を Aレジスタに保存する ADD8 A, 0x12 # 16-bit バージョン。 # AF レジスタの中身 (16-bit) に 0x1234 を足し、結果を AFレジスタに保存する ADD16 AF, 0x1234 では、この命令セットはどのようにして定義すればよい？

42.

43.

44.

なんで？ → 命令を実行する execute の実装でつまる！ cpu.ml let execute t (inst : Instruction.t) = let read_arg arg = match arg with | R r -> Registers.read_r r | RR rr -> Registers.read_rr rr | ... 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 ...

45.

なんで？ → 命令を実行する execute の実装でつまる！ cpu.ml let execute t (inst : Instruction.t) = let read_arg arg = match arg with | R r -> Registers.read_r r ここでつまる！ | RR rr -> Registers.read_rr rr | ... 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 ...

46.

問題：マッチしたコンストラクタによって返り値が変わって型がつかない cpu.ml (* 返り値の型は??? *) let read_arg (arg : Instruction.arg) -> ??? = match arg with | R r -> (* R にマッチしたときの返り値は uint8 *) Registers.read_r r | RR rr -> (* RR にマッチしたときはの返り値は uint16 *) Registers.read_rr rr | ... in

47.

そういえば GADTってのがあったな。。

48.

49.

解決法： GADT (Generalized Algebraic Data Type) をつかう instruction.ml type arg = | R : Registers.r | RR : Registers.rr -> uint16 arg | Immediate8 : uint8 | Immediate16 : uint16 -> uint8 -> uint8 arg arg -> uint16 arg | ... type t =... (* type t はヴァリアントのときと一緒 *) どういう意味？

50.

-> の左側：ヴァリアントの of のあとの部分に対応コンストラクタをマッチしたときに手に入る値の型 | R : Registers.r -> uint8 arg | R of Registers.r let read_arg = function | R r -> .. (* r の型は Registers.r *) | RR rr -> .. (* rr の型は Registers.rr *) ...

51.

| R : Registers.r -> uint8 arg | R of Registers.r let read_arg = function | R r -> .. (* r の型は Registers.r *) | RR rr -> .. (* rr の型は Registers.rr *) 右側は？ ... ヴァリアントに対応するものはない。

52.

-> の右側：コンストラクタをマッチしたときに返す値の型 | R : Registers.r -> uint8 arg | RR : Registers.rr -> uint16 arg let read_arg = function | R r -> Registers.read_r r (* uint8 を返す *) | RR rr -> Registers.read_rr r (* uint16 を返す *) ...

53.

ヴァリアントはパターンマッチで手に入る値の型をパラメータ化できる。 GADT はパターンマッチで返す値の型もパラメータ化できるだから、"Generalized" Algebraic Data Type （多分）

54.

cpu.ml let execute t (inst : Instruction.t) = let read_arg : type a. a Instruction.arg -> a = fun arg -> | R r -> Registers.read_r r | RR rr -> Registers.read_rr rr | ... 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

55.

実装のタイムライン

56.

タイムライン (git log から) ● 2021/8/15: カートリッジからの命令の読み込み・命令の実行を実装しはじめる ○ テストロムを使って最終テスト。結果はシリアルポートに出力されるので、 GPUが実装されていなくても動く。 ● 2021/9/19: 命令セットの実装を完了、GPU の実装を開始 ● 2021/10/5: Tetris の開始画面の描画に成功、Joypad や Cartridge の実装を開始 ● 2021/10/23: ポケモンが動く ● 2021/10/24: JS にコンパイル、ブラウザで動くが、めちゃくちゃ遅い。最適化に取り組む。 ● 2021/11/14: スマホブラウザで動くくらいの速度がでる。

57.

まとめ

58.

なにか実装してみる問題本やドキュメントで勉強そういえばあれが使えるかも... 解決自分の理解に落とし込む勉強した内容を思い出す

59.

なにか実装してみる問題本やドキュメントで勉強言語機能だけではなく、テストフレームワーク・ビルドシステム・ライブラリの理解も同様にすすんだ！そういえばあれが使えるかも... 解決自分の理解に落とし込む勉強した内容を思い出す

60.

最後に

61.

初級者中級者本趣味簡単なプログラム業務中級の谷オープンソース活動

62.

初級者中級者「谷」どう越える？本趣味簡単なプログラム業務中級の谷オープンソース活動

63.

初級者中級者「谷」どう越える？本趣味簡単なプログラム中規模以上のプログラムを書いて「問題」「解決」を繰り返す中級の谷業務オープンソース活動

64.

僕にとってこの「中規模以上のプログラム」は CAMLBOY でした

65.

ほかには？

66.

おすすめする三つの条件 1. 適度に複雑 ○ ○ ある程度以上の複雑性からのみ出現する「問題」がある（テスタビリティ、保守性、など）書く自信がないくらいがちょうどいい。 2. 仕様が決まっている ○ 「何を書くか」と「どう書くか」を同時に考えるのは大変。 ○ ゴールがわかりやすい。例：自作エミュレータ上でポケモンを動かす 3. 楽しい ○ テストプレイと称して何時間も溶かした。例：ゲームエミュレータ（ゲームボーイ、ファミコン、chip8、…）、既存言語（のサブセット）のコンパイラ、ISUCON移植、など

67.

リンク集 ● ● ブログ記事： ○ https://qiita.com/linoscope/items/244d931aaae07df2c27e ○ https://linoscope.github.io/writing-a-game-boy-emulator-in-ocaml/ CAMLBOY のレポジトリ: ○ ● https://github.com/linoscope/CAMLBOY CHIP8 エミュレータ: ○ https://yukinarit.github.io/cowgod-chip8-tech-reference-ja/1_about_chip8.html ● Build your own X: https://github.com/codecrafters-io/build-your-own-x ● 発表者の Twitter (質問・コメントなどがあればこちらまで！） ○ https://twitter.com/linoscope