読者です 読者をやめる 読者になる 読者になる
ようこそ。睡眠不足なプログラマのチラ裏です。

判別共用体で型付きDSL。弾幕記述言語BulletMLのF#実装、FsBulletML作りました。

プログラミング F# BulletML DSL 弾幕 Advent Calendar MonoGame

この記事はF# Advent Calendar 2013の20日目です。



遅ればせながらThe Last of Usをちびちびとプレイ中。FF14のパッチ2.1が先日リリースされ、メインジョブ弱体化にもめげず引き続き光の戦士としてエオルゼアの平和を守り続けている今日この頃。艦これは日課です。はてなブログに引っ越してきて一発目(ブログデザイン模索中)です。気付けば半年もブログを書いていませんでした(テイタラク)。今年はあまり.NET関係の仕事に携わることができずに悶々としておりましたが、急遽C#の仕事が舞い込んできました。年末はいろいろとバタバタするものです。少しの間ホテル暮らしなのでゲーム(据置機)できなくてつらいです。わたしは大晦日にひとつの節目を迎えます。記憶力、体力、集中力...多くのものを失ったように思います。アラフォーいい響きです(白目)。


上の動画の弾幕は次のBulletml判別共用体で記述されています(MonoGameで動いています)。

 1: 
 2: 
 3: 
 4: 
 5: 
 6: 
 7: 
 8: 
 9: 
10: 
11: 
12: 
13: 
14: 
15: 
16: 
17: 
18: 
19: 
20: 
21: 
22: 
23: 
24: 
25: 
26: 
27: 
28: 
29: 
30: 
31: 
32: 
33: 
34: 
35: 
#r @"bin\Debug\FsBulletML.Core.dll"
open FsBulletML

/// ぐわんげ、二面ボス by 白い弾幕くん
/// [Guwange]_round_2_boss_circle_fire.xml
let ``round_2_boss_circle_fire`` = 
  "ぐわんげ二面ボス by 白い弾幕くん",
  Bulletml
    ({bulletmlXmlns = Some "http://www.asahi-net.or.jp/~cs8k-cyu/bulletml";
      bulletmlType = Some BulletVertical;},
      [BulletmlElm.Fire
        ({fireLabel = Some "circle";},
          Some (Direction (Some {directionType = DirectionType.Sequence;},"$1")),
          Some (Speed (None,"6")),
          Bullet
            ({bulletLabel = None;},None,None,
            [Action
                ({actionLabel = None;},
                [Wait "3";
                  Fire
                    ({fireLabel = None;},
                    Some (Direction (Some {directionType = DirectionType.Absolute;},"$2")),
                    Some (Speed (None,"1.5+$rank")),
                    Bullet ({bulletLabel = None;},None,None,[])); Vanish])]));
      BulletmlElm.Action
        ({actionLabel = Some "fireCircle";},
          [Repeat
            (Times "18",
              Action
                ({actionLabel = None;},
                [FireRef ({fireRefLabel = "circle";},["20"; "$1"])]))]);
      BulletmlElm.Action
        ({actionLabel = Some "top";},
          [Action.ActionRef ({actionRefLabel = "fireCircle";},["180-45+90*$rand"]);
          Wait "10"])])
名前空間 FsBulletML
Multiple items
共用体ケース Bulletml.Bulletml: BulletmlAttrs * BulletmlElm list -> Bulletml

--------------------
type Bulletml =
  | Bulletml of BulletmlAttrs * BulletmlElm list
  | Action of ActionAttrs * Action list
  | ActionRef of ActionRefAttrs * Params
  | Fire of FireAttrs * Direction option * Speed option * BulletElm
  | FireRef of FireRefAttrs * Params
  | Wait of string
  | Vanish
  | ChangeSpeed of Speed * Term
  | ChangeDirection of Direction * Term
  | Accel of Horizontal option * Vertical option * Term
  ...

完全名: FsBulletML.DTD.Bulletml
共用体ケース Option.Some: 'T -> Option<'T>
共用体ケース ShootingDirection.BulletVertical: ShootingDirection
type BulletmlElm =
  | Bullet of BulletAttrs * Direction option * Speed option * ActionElm list
  | Fire of FireAttrs * Direction option * Speed option * BulletElm
  | Action of ActionAttrs * Action list

完全名: FsBulletML.DTD.BulletmlElm
共用体ケース BulletmlElm.Fire: FireAttrs * Direction option * Speed option * BulletElm -> BulletmlElm
Multiple items
共用体ケース Direction.Direction: DirectionAttrs option * string -> Direction

--------------------
type Direction = | Direction of DirectionAttrs option * string

完全名: FsBulletML.DTD.Direction
type DirectionType =
  | Aim
  | Absolute
  | Relative
  | Sequence

完全名: FsBulletML.DTD.DirectionType
共用体ケース DirectionType.Sequence: DirectionType
Multiple items
共用体ケース Speed.Speed: SpeedAttrs option * string -> Speed

--------------------
type Speed = | Speed of SpeedAttrs option * string

完全名: FsBulletML.DTD.Speed
共用体ケース Option.None: Option<'T>
共用体ケース BulletElm.Bullet: BulletAttrs * Direction option * Speed option * ActionElm list -> BulletElm
Multiple items
共用体ケース ActionElm.Action: ActionAttrs * Action list -> ActionElm

--------------------
type Action =
  | ChangeDirection of Direction * Term
  | Accel of Horizontal option * Vertical option * Term
  | Vanish
  | ChangeSpeed of Speed * Term
  | Repeat of Times * ActionElm
  | Wait of string
  | Fire of FireAttrs * Direction option * Speed option * BulletElm
  | FireRef of FireRefAttrs * Params
  | Action of ActionAttrs * Action list
  | ActionRef of ActionRefAttrs * Params

完全名: FsBulletML.DTD.Action
共用体ケース Action.Wait: string -> Action
共用体ケース Action.Fire: FireAttrs * Direction option * Speed option * BulletElm -> Action
共用体ケース DirectionType.Absolute: DirectionType
共用体ケース Action.Vanish: Action
共用体ケース BulletmlElm.Action: ActionAttrs * Action list -> BulletmlElm
共用体ケース Action.Repeat: Times * ActionElm -> Action
Multiple items
共用体ケース Times.Times: string -> Times

--------------------
type Times = | Times of string

完全名: FsBulletML.DTD.Times
共用体ケース Action.FireRef: FireRefAttrs * Params -> Action
共用体ケース Action.ActionRef: ActionRefAttrs * Params -> Action

FsBulletMLリリースしました

弾幕記述言語BulletMLF#実装、FsBulletMLを作りました。Unity 4.3では新たに2Dがサポートされたりで、少なからず需要がないこともないのかもしれず。せっかくなので FsBulletML.Core(内部DSLを提供) および、FsBulletML.Parser(外部DSLを提供) をNuGetに放流してみました(Beta版)。実際に使える(使われる)ライブラリに成長するかどうかはわかりません。

詳しくはこちらをご覧ください

BulletMLとは

BulletMLとは、シューティングゲームにおける弾幕を記述するための言語(外部DSL)で、多くのハイクオリティなシューティングゲームを開発なさっている ABA Games の 長健太氏が作りました。BulletMLが初めて公開されたのは2002年頃でしょうか? もう10年以上前ということになります。シンプルな記述で多彩な弾幕を表現することができ、有限オートマトン的に弾を管理しなくてもよいので楽チン。ということで多くの人から注目を集めました。わたしが存在を知ったのはもう少し後のことですが、当時かなりインパクトを受けて感動したのを覚えています。

本家BulletMLのパーサおよび処理系はJavaで実装されています。RELAX定義DTD定義など弾幕定義自体の簡易的な仕様については公式に公開されているものの、弾幕の処理系の詳細については「ソース嫁」状態という非常に漢気溢れる感じになっています*1。にもかかわらず、多くの人によって様々な言語で移植/実装/改良されていますBulletSML は、BulletMLのS式版(内部DSL)で、ひとつひとつの弾が継続になっているらしいです(あたまおかしい)。最近では、bulletml.js が内部DSLも提供していて、enchant.js用、tmlib.js用のプラグインもあって、ブラウザで動く弾幕ゲーが簡単に作れるようになっているようです。

特定の「何か」を達成するために、最適化された言語を作ることは簡単なことではありません。シンプルで且つ表現力が高くて実用的なドメイン固有言語を作る(デザインする)のはとても難しいことです。BulletMLはとてもよくデザインされていて面白くて魅力的なDSLだと思いました。

DSLについて

以前以下のような記事を書きました。

F#3.0で加速する言語指向プログラミング(LOP)。コンピューテーション式はもはやモナドだけのための構文ではない!!!

きっかけ

今年は例年に比べてIT系勉強会に参加できませんでしたが、夏に「コード書こうぜ!」をスローガンとしたCode2013という合宿イベントに参加しました。その中で、座談会orセミナー形式で複数グループが集まってそれぞれが異なるテーマについて話をする形の「きんぎょばち」というコーナーがありまして、「パーサコンビネータを使った構文解析およびDSLの作成などについて勉強したいです。」というテーマがありました。特定言語に限ったテーマではありませんが、他に「F# や 関数型言語の話題なら少し話せます。」というテーマもあったので、わたしが F# について話をする流れになって、判別共用体の便利さや FParsec を用いた字句解析、構文解析等についてお話してきました。本当は教えてもらいたい側だったのですが...。イベントから帰ってきてから、「何かDSL書きたいなー」と漠然とした思いを持っていました。

BulletMLを 判別共用体で 型付きの内部DSLとして表現できるようにしたらちょっと面白いんじゃあ?」という発想。アイディアとしては3年くらい前から持っていましたが、実装が面倒くさいことになりそうだったので行動に至らずでした。ゲーム開発の世界ではDSLや各ドメインエキスパートのための独自スクリプト言語などを開発/運用することは日常茶飯事で、そう珍しいことではないと風のうわさで聞いたことがあります。わたし自身は、仕事であれ趣味であれ、日頃のソフトウェア開発において本格的なDSLを設計したり実装したりする機会はほとんどありません。非常に興味のある分野/開発手法なので実際に何かを作って勉強してみたい。そう兼ねてから思っていました。良い練習になりそうだし、"評論家先生"というYAIBAに影響を受けたりで、重い腰を上げました(よっこらせ)。

やりたかったこと

弾幕を判別共用体で書きたい(型付き内部DSL)
・従来のXML形式での弾幕を再利用したい(外部DSL)
XML形式は書きにくいしちょっと古臭い。XMLとは異なる形式の外部DSLも利用できるようにしたい。

要は、「内部DSLと複数の外部DSLを両立する。」ということをやってみたい。その辺りを最終的な目標にしました。そもそもC#での実装(BulletML C# - Bandle Games)があるし、何を今さら感があるのも事実ですが、判別共用体による型付き内部DSLを提供するという点で若干のアドバンテージがあります。型付きの内部DSLが使えると何がうれしいって、弾幕を構築する際にF#の式がそのまま使えるということです。つまり、関数を組み合わせて自由に弾幕を組み立てることができるようになります。それってつまり、Bulletsmorphのようなアイディアも実装しやすくなる、と。

XMLのdisり大会。こちら結局どうなったんでしょう。気になります(´・_・`)

DTD定義を判別共用体で表現する

いにしえからの言い伝えによると、「判別共用体は、ドメイン知識をモデル化するための簡潔かつタイプセーフな方法である。」らしいです。 ということで、BulletMLDTD定義を内部DSLとして判別共用体で表現する。ということについて考えてみたい。

以前、こんなやり取りがありました。



言語内に型付きDSLを構築したいようなケースでは、GADT(Generalised Algebraic Datatypes)が欲しくなるようです。つまりこれ、抽象構文木なんかを型付きで表したいときに発生する事案です。しかし、F#にはHaskellGADTsに相当するものはありません。GADT相当の表現自体はOOPスタイルで書けば可能ではありますが、判別共用体で内部DSLを表現したいというコンセプトとはズレてしまうので今回は適用できません。仕方がないので、型を細分化してどんどん型が絞られていくような型を定義します。

BulletMLのDTD定義に沿って、以下のような感じの型を定義すれば、判別共用体による内部DSLの構造(モロ抽象構文木)が表現できます。

長い。ここで定義したBulletml判別共用体は、確かに型付きDSLではあるのですが、BulletMLの仕様に準拠するかたちで型を表現するようにしたのでタイプセーフではないですね。タイプセーフではありませんが、まあそれなりです。今後、より型安全な判別共用体の提供とモナディックな弾幕構築の提供とか、弾幕コンピュテーション式...とかとか妄想しています。あとは、この型を弾幕として解釈することができる処理系を実装すればおkです(それが面倒くさい)。

というか、俺たちのF#にも牙突ください(!)

外部DSLと内部DSLを両立する

f:id:zecl:20131219212500p:plain

内部DSLであるBulletml判別共用体の構造は再帰的な構造になっていなく複雑です。上図のような構成では外部DSLを解析するためのパーサの実装コストが大きくなってしまいます。そこで、より抽象度の高い中間的なASTを用意し、下図のような構成にすることでパーサの実装コストを軽減することを考えます。

f:id:zecl:20131219212527p:plain

中間ASTとは、つまるところXmlNodeの構造そのものなので、以下のように単純な木構造の判別共用体で表現することができる。

  type Attributes = (string * string) list

  type XmlNode =
  | Element of string * Attributes * XmlNode list
  | PCData of string

外部DSLを解析するパーサは、より抽象的で単純な構造にパースするだけでよくなるので、とてもシンプルな実装で済むようになります。実際のパーサの実装例を見てみましょう。

SXML形式のパーサ

かの竹内郁雄氏は、「XMLもぶ厚いカッコのあるLisp」とおっしゃっています。
第1回 Lispの仏さま 竹内郁雄の目力

実際、XML InfosetのS式による具象表現であるところのSXMLがそれを体現していますね。

SXMLの基本的な構成要素はこんな感じです。

[1]              <TOP> ::= ( *TOP* <PI>* <Element> )
[2]          <Element> ::= ( <name> <attributes-list>? <child-of-element>* )
[3]  <attributes-list> ::= ( @ <attribute>* )
[4]        <attribute> ::= ( <name> "value"? )
[5] <child-of-element> ::= <Element> | "character data" | <PI>
[6]               <PI> ::= ( *PI* pi-target "processing instruction content string" )  

不勉強なので、Lispとかよくわかりませんが、要素はlist の car。内容は cdr。属性は @ に続く cdr という感じで表現できれば、BulletMLSXML形式で記述できるようになります。ごくごく簡易的なSXMLのパーサはFParsecを使うと次のような感じに書けます。

このパーサによって、全方位弾の弾幕をこんな感じに記述できるようにます。

スッキリ。ぶ厚いカッコを一掃できて、いい感じですね。

独自形式のパーサについて

「括弧も一掃したいんだが。」という人のためにインデント形式をご用意。インデントで構造化されたデータ表現と言えばYAMLがありますが、YAMLほどの表現力は必要がなくて、弾幕をシンプルに書けさえすればよいので独自形式をでっち上げてみました。

以下のような感じのインデント形式の弾幕も読み込めるパーサも用意してみました。 オフサイドルールな構文をパースしたい場合は、@htid46さんFParsecで遊ぶ - 2つのアンコールの記事がとても参考になりますね。ソースは省略します。

JSON形式のパーサもあってもよいのかも。

Demoプログラムで使った背景画像について

DSL繋がりということで、動画のサンプルプログラムでスクロールさせている背景画像の作成には、DSLで背景画像が作れるF#製のツール「イラスト用背景作成「BgGen」 ver 0.0.0 - ながとのソフト倉庫」を利用させてもらいました。

背景生成に使ったコマンド

rect 0 0 480 680 #f000
circles 1 0 50 #aff

これで宇宙っぽい背景が作れちゃいました。こりゃ便利。

感想

F# の判別共用体で型付きDSLをするのは無理ではないけど、段階的にケースが少なくなってどんどん絞り込まれていくような型の場合、それを解釈する処理の実装コストが大きくて結構つらぽよ感溢れました。あまりおすすめできませんね。欲しいです牙突マジ。

・頭の中ではすでに出来ている(作り方がわかっていると思っている)ことと、実際に作ってみることは、やっぱり結構なギャップがあるね。

・ 結果的に行き当たりばったりのゴリ押し実装になってしまったきらいはあるけど、判別共用体で定義した弾幕が思い通りに動いたときはちょっとした達成感が。おじさんちょっと感動しました。

GitHubに晒したソースコード。ツッコミどころ満載なのはある程度は自覚していますが、より良い方法があればアドバイスを。お気づきの点がありましたら @zecl までお願いします。


疲れた!!!でも、ものづくり楽しいし、F# 楽しい✌('ω'✌ )三✌('ω')✌三( ✌'ω')✌



あわせて読みたい

DSL開発:ドメイン駆動設計に基づくドメイン固有言語開発のための7つの提言 - Johan den Haan
言語内 DSL を考える。- togetter
GADTによるHaskellの型付きDSLの構築 - プログラミングの実験場


*1

シューティングゲームを作ったことがある人ならだいたいは勘でわかりますが