ゲーム用のオレオレ言語を作るためにPratt Parserを勉強している

ゲーム製作も佳境に入っているといいたいところだが、全然進んでおらず、むしろ完成からかなり遠のいている。なぜならば、ゲームを作るためのオレオレ言語を今作っているからである。

動機

WebGLを念頭においてゲームコードをJSで書くとどうしても型の問題にぶち当たる。WebGLはわりと厳密に型を要求するし、バイト単位のオフセット指定なども必要なので、JSでは普段気にしない変数型やメモリ配置に気を遣わなくてはならなくなる。JSは動的型付けなので、数値か文字列かくらいを気に留めておけばよいくらいのお気楽な言語で、私はだから好きなのだが、WebGLは少し気難しくていろいろJS側でケアしてやらなくてはいけない。
ケアといってもArrayBufferやTypedArrayを使うくらいで型変換を抑制することはJSでは明示的にできない。型変換というのはコストが比較的高い処理であることをC++で学んでいるので、何かWebGL APIに対してJSから処理をお願いするたびに型変換が入ることを考えるとちょっと「ぞっと」するのである。C言語のキャストのように単純なポインタ変換（これをC++では破壊的キャストと呼ぶが。。）であれば気にはならないのだが、JSは動的型付けなので変換には変数の型判定と、状況によっては倍精度から単精度への浮動小数の変換が入るだろうし、その処理コストが気になってくるのである。そしてその処理コストはあちこちで発生するから、脳内が型変換の暗黒面で侵されてしまい何も手をつけられなくなるのである。

このことはJSを使う以上は避けられないことで、ブラウザゲームを作るうえでJSしかない状況であればあきらめもつくのだが、Web Assembly(wasm)の登場によって状況は変わった。例えば静的型付け言語のC/C++で書いてllvm経由でwasmに落とせば、実行時の型変換コストの問題は気にしなくてもよいレベルになる。C/C++は静的型付けの言語であるから、変数型を厳密に指定できるので型変換コストは最小にできる。

でまあC言語が現存する言語では最も私の希望をかなえてくれるものではないかと考えた。C言語であればllvmでサポートされているしね。でも私の場合C++な手癖がついてしまっているので、CとC++の言語仕様差にストレスがたまること必至な気もしてちょっと萎えるのである。

で結局、C言語に近くてWebGLのハンドリングがやりやすい言語はGLSLだ、という結論に至ったのである。GLSLはベクトルと行列の演算がすっきりかけるし、型についても必要十分に厳密である。とはいえGLSLはシェーダー用の言語だからそのままではなくて、この仕様からシェーダーサポートの仕様を外し、私の好きなコルーチン（Fiber/MicroThread）を加えることにする。そうすれば私にとって理想的な言語になるではないか。

オレオレ言語

しかし、オレオレ言語というのはそれはそれで、かなりの知識・実装技術・時間が必要である。

JSの世界ではJSの仕様に不満を感じて、最終的にはJSを吐くトランスパイラというものが発生した。例えばcoffeeとかTypeScriptとかである。es2015になってそれまでの不満はかなり解消されたので少し鎮静化した感はあるが。トランスパイラ自身はJSで書かれていて、解析や改造も容易になっている。なのでこのようなコードを参考に自分の仕様を注入し、トランスパイル部分をwasmを吐くようにすれば割と簡単・短期間に実現できるのではないかと考えたのである。

その方向でgithubをまさぐっていたら、AssemblyScriptというのをまず見つけた。これはTypeScriptの構文でwasmを直接吐くものである。変数がwasmの変数型に限定されている点が特徴的で私の用途には都合がよさそうだ。が、TypeScript自体がまたこれ複雑かつ汎用的な言語仕様で、改造するのもちょっと難しい。また現バージョンではMathライブラリもないのでそこから作らないといけないというのもハードルが高い。 がこの言語のおかげでTypeScriptを知り、なかなかよくできた言語なのでオレオレ言語はTypeScriptで書こうと思ったくらいである。

でもうちょっと直接的にglslをサポートするものがないのかと探し求めた結果見つけたのが、glsl-tokenizer,glsl-parser,glsl-transpilerであった。

• glslify/glsl-tokenizer: r/w stream of glsl tokens
• stackgl/glsl-parser: transform streamed glsl tokens into an ast
• stackgl/glsl-transpiler: Transpile GLSL to JS

これはずばりglslのソースコードを「トークナイズ」し、それを「パース」し、さらにJSコードに「トランスパイル」するものである。私はこれをTypeScript化しようと試みて、parserのコードまで進めたところで手を止めている。手を止めた理由はpratt parserというものに対する私の知識不足が原因である。

Pratt Parser

Pratt Parserとは「Top Down Operator Precedence」を用いたパーサーのことである。日本語では「下向き演算子順位解析」というらしい。でこのparserのコードを読むところで停滞してしまった。このコードだけはいくら読んでも頭にイメージがまったくといっていいほどわいてこないのである。おそらく言語パーサに関する知識がなさすぎるからだと思われるが、それにしても入ってこない。何かこうキーになる概念が頭の中でイメージできればすんなり理解できそうな気もするのだが。

最初にこの「Top Down Operator Precedence」（TDOP）の文字を見つけたのはglsl-parserのreadme.mdである。glsl-parserはDouglas CrockfordさんのTop Down Operator PrecedenceのJS実装がベースとなっているとのことだ。よってこのページを読むことにした。が英語なのでなかなか読み進めることができず、このページは理屈の解説よりはJSの実装の解説に重きを置いたページであった。

でもともとこのページは、ビューティフル・コードという本のエッセイであることがわかり、この本を購入し読んだ。が、まあ内容はほぼ同じだし、私の脳内翻訳がまずいわけでもなかった。結果この「Top Down Operator Precedence」の原典を読み、本質を理解しなければこのコードも理解できないとの結論に達した。

そしてVaughan R. PrattさんのTop Down Operator Precedenceに行きついて今訳しながら読み進めているところである。しかしこの論文、機械翻訳の結果がひどくて、ほとんど理解できないため、昔のように一文一文ハンドで訳しながら読んでるのでなかなか進まない。一応githubで上がっているのでforkして成果を反映させるようにしてみた。

https://sfpgmr.github.io/tdop.github.io/

今後

Pratt Parserを何とか理解して、wasmコードを吐くところまで持っていきたいなあと。

でまあここまで読んでわかったのは、JSの柔軟さと動的型付けによってTDOPベースのパーサーはスマートに実装できるのであって、強い型付けの言語を使うとこのパーサーの良さをスポイルしかねないということ。つまり私がこれをTypeScript化するのはあまりよろしくないアプローチなのである。なので元コードをそのまま使い、es2015化するくらいでとどめることにした。

parserまでTypeScript化したが、そのコードは泣く泣く捨てることにする。。