きまぎらすほしゅの不定記

■ Glasopal

リプレイの乱数合わせはかなり難しいことが分かった．リプレイ時とレコード時で譜面が同一でなければならないので，プレイオプションだけではなく，BMSの条件分岐も再現させる必要がある．しかし，nazoの実装では，レコードデータのロードがBMSファイルロードの後に来ているので，このままではBMSの条件分岐を再現することは出来ない．

つまり，BMSファイルロードの前に，レコードデータをロードさせるようにパッチを当てることになるのだが，レコードデータの正当性確認に，BMSファイルに記述された値から計算される数値を用いているので，ただ単にロードの順序を入れ換えるというわけにはいかないのだ．正当性確認に巡回冗長検査やハッシュ関数を用いれば上手く解決できそうだが，これだと，過去のリプレイファイルと互換性がなくなってしまう．できれば，出入力ファイルの互換性はなくしたくないのだが……

ジュークリスト検索のショートカット追従も難しい．元のルーチンに変更を加えずにやろうと思ったら，どこぞのmとか，aとか，bとか，iとか付くゲームのESLフレームワークみたいに，ファイルシステムを摸するレイヤを挟まないといけない．はっきり言って，そこまでやるより，検索ルーチンをすべて書き換えてしまった方が早いし，低コストだ．NTFSのジャンクション（≒シンボリックリンク）機能を使えば，nazoが特別な対策を取らなくても，カンタンに追従出来るのだが，有名所のアーカイバはこれを正しくパックできるほど賢く出来ていない．また，Win9x系で使われることも想定すると，ジャンクションに頼ることは出来ないだろう．

最後に，報告を戴いている件について．実は，更新内容に記述されていないパッチが幾つか存在します．パッチの具体的な内容は，「サウンドファイル読込の成功に関係なく，サウンドオブジェクトの読み込みフラグを強制的に更新する」と，「ピクチャファイルの読み込みに失敗したとき，黒で塗りつぶした16×16のオフスクリーンサーフェスを返す」の二つです．これらは，オプションに非依存で常に適用されるようになっています．どのオプション状態で不具合が起きるかを確かめてもらおうとしたのは，そのためです．

そして，オプションに関係ないという報告を戴いたことで，前述の非文書化パッチが原因である可能性が高いことが分かりました．後日，原因と思われるパッチについて，無効化ないし修正を行い，検証版としてupしたいと思います．

■ Prolog 入門回顧抄 (1)

ふと，Prologをやりたくなったときの記憶を思い返す ．

言語の特徴としては，一階述語論理の世界をプログラミング言語に持ち込んできたモノらしい．なるほど，普通のプログラミング言語は命題の証明を記述する一方，Prolog は命題そのものを記述すると聞いたことがある．しかし，かつて一階述語論理を学ぼうとしてまったくもって習得できなかった経験がある身としては，この言語をちゃんと理解できるかの自信がまったく持てない．

まあ，自信があるかどうかは別として，とりあえずちょこっと触ってみることにした．Windows で動くフリーな処理系を探してみると， GNU Prolog，SWI-Prolog の二つが見つかった．前者はgccのフロントエンドみたいなものか？と思ってcygwinで見てみたけど，そんなコマンドは見あたらない．どうも単独動作するモノらしい．

ここは，よく知っているGNUの付いている方をインストールしてみることにした．Windows installer形式で，さくさくとインストール完了．早速立ち上げると，コンソール画面が出てきて，?- というプロンプトが表示された．

さて，ここからどうしよう……？　ヘルプを見ると，どうやら，定義するときはPrologコードファイルを読まないといけないらしい．まずは簡単な論理から読み込ませてみよう・・・と思ったけど止めた．やっぱりどばーっと動いてくれる方が面白いしね．

そういうことで，Brainfuck の構文解析器を書いてみた．こんなの．

bfbody([X|Xs])    --> bfphrase(X), bfbody(Xs).
bfbody([])        --> [].
bfphrase(incr)    --> "+".
bfphrase(decr)    --> "-".
bfphrase(next)    --> ">".
bfphrase(back)    --> "<".
bfphrase(putc)    --> ".".
bfphrase(getc)    --> ",".
bfphrase(loop(X)) --> "[", bfbody(X), "]".

これは，DCG(Definite Clause Grammar) って言う記法らしい．

コード上は，述語が１つの引数を取るように見えるけど，実際の述語は，ユーザ記述の引数＋入力のリスト＋消費した入力のリスト，計２＋α個の引数を取ることになる．また，Goalに書いた述語に対しても，二つ引数が追加されることになる．Goalに書いたリストは，入力リストを消費する述語のようなものに置き換えられるようだ．

それでは，試しに書いた述語を使ってみよう．

?- bfbody(X, ",>+[-<+>]<.", []).

と，先頭の引数を変数Xにして投げかけると，Prologが 後ろ二つの引数から，この命題（コード（＝二つ目の引数）が文法的に正しい）を満たすXを推論してくれる．回答は，

X = [getc, next, incr, loop([decr, back, incr, next]), back, putc]

コードと比較すると，正しい推論を行ってくれたようだ．

逆に，解析結果を入れて，入力リストを変数にすれば，解析結果と等価な入力を推論してくれる．

?- bfbody([getc, next, incr, loop([decr, back, incr, next]), back, putc], X, []).
X = [44, 62, 43, 91, 45, 60, 43, 62, 93|...].

ちょっと，これでは確認しづらい．string_to_list を通してみると，

?- bfbody(snip), string_to_list(Y, X).
X = [snip],
Y = ",>+[-<+>]<.".

はい，元通りになった．……流石にこれだけでは詰まらない．そこで，さらにBFインタプリタも実装してみることにした．

■ Prolog 入門回顧抄 (2)

さて，解析結果のリストには bf 命令の数だけアトムの種類を含んでいる．リストに含まれるアトムによって，動作を切り替えたいが，switch なんていう甘い物はこの言語には存在しない（述語Ifはあるけど・・・）．その代わり，Prolog にはどこぞの ML や，Haskell，C++テンプレート等と同じく，述語の探索についてパターンマッチングを行う．従って，引数に記述するリストを[Car|Cdr]に分けて，Carに特定のアトムを指定してやれば，要素が一致したとき，探索の目がそっちに向いてくれるようになる．

リストの問題はもうひとつある．それは，どうやって繰り返し処理するかということだ．ここら辺は関数型言語プログラマやってたらすぐ分かることで，末尾再帰すれば済む話だ．早速，Prolog における末尾再帰はどんなものなのか試してみたところ，１つ重大なことに気付いた．末尾最適化がヘタレなのか，それともまったく実装してないのか，スタックの底が浅いのか，カンタンにスタックオーバーフローで乙ってしまうのだ．

折角楽しんでいるところだったのに，なんたる仕打ち……仕方ないので，ここで，もう一方のフリー実装系，SWI-Prolog に乗り換えることにした．

SWI-Prolog もインストーラ付きで，さくさくインストール．立ち上げてちょこちょこいじってみたが，GNU Prolog と余り操作体系は変わりないらしい，そりゃそうか．少し調べてみると，SWI-Prolog は末尾最適化を行ってくれるとの記述があって安心した．これもうまく行かなければ，どうしようかと……

気を取り直して，実装再開．さくさくと実装を進めていくと，幾つか必要な述語が足りないことに気がついた．１つは，callocみたいなリストの生成，もう１つはリストの特定要素の入れ換え．マニュアルを読んでみると，どうも存在しないらしい．

無いものは自分で作る，これがエンジニア（？）の鉄則（？？）．

fill([], _, 0).
fill([E|Cs], E, N) :-
  N > 0, N1 is N - 1, fill(Cs, E, N1).
nth1(1, [_|Xs], E, [E|Xs]).
nth1(N, [X|Xs], E, [X|Ys]) :-
  N > 1, N1 is N - 1, nth1(N1, Xs, E, Ys).

リストの Car，Cdr を合わせることで，推論時に要素複写の効果を得ることができる．どちらも実体を与えたときは，双方が一致したときに探索に当たることになる．こんなに手短に記述できるというのは，なかなか気持ちがいいものだ．

あとは，アトム（＝BFの命令）の意味に合わせて，述語を記述していくだけ．

bf([incr|Cs], M, X) :-
  nth1(X, M, E), E1 is E + 1, nth1(X, M, E1, M1),
  bf(Cs, M1, X).
bf([decr|Cs], M, X) :-
  nth1(X, M, E), E1 is E - 1, nth1(X, M, E1, M1),
  bf(Cs, M1, X).
bf([next|Cs], M, X) :-
  length(M, L), X < L, X1 is X + 1,
  bf(Cs, M, X1).
bf([back|Cs], M, X) :-
  X > 0, X1 is X - 1,
  bf(Cs, M, X1).
bf([putc|Cs], M, X) :-
  nth1(X, M, E), char_code(A, E), write(A),
  bf(Cs, M, X).
bf([getc|Cs], M, X) :-
  get_code(E), nth1(X, M, E, M1),
  bf(Cs, M1, X).
bf([loop(_)|Cs], M, X) :-
  nth1(X, M, 0),
  bf(Cs, M, X).
bf([loop(C)|Cs], M, X) :-
  append(C, [loop(C)|Cs], C1),
  bf(C1, M, X).
bf([], _, _).
bf(X) :-
  phrase(bfbody(R), X), 
  fill(M, 0, 256),
  bf(R, M, 1).

終端は何もないので，何もないようにする．これを書かないと，パターンマッチング失敗で延々バックトラックした挙げ句，推論失敗することになるらしい．

さて，完成したところで，早速動かしてみる．サンプルコードは K.INABAさんのところから，Hello, World．

?- bf(">+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>++++++++[<++++>-]<+.[-]++++++++++.").
Hello World!
true .

うむ，満足の行く結果が得られた．次は downcase だ．

?- bf(">>++++++++[->++++++++<]>>>>+++++++++[->++++++++++<]>[<<,[->+<<+<<+>>>]<<<[->>>+<<<]>>>>>[->+>>+<<<]>[<<[->+>>+<<<]>>>[-<<<+>>>]<<[[-]<->]>-]>>[-<<<+>>>]<<<<<<<[-<+<<+>>>]<[>>[-<+<<+>>>]<<<[->>>+<<<]>>[[-]>-<]<-]<<[->>>+<<<]>>>>><[[-]>++++++++++++++++++++++++++++++++>[[-]<-------------------------------->]<<]>>[-]<.>>]")
|: AFOTHER

ERROR: Out of local stack.

えっ．．．？

最初はまったくどうしてなのか分からなかったけど，グラフィカルデバッガを立ち上げて漸く分かった．述語を探索するたびに，選択点なるものを設けているらしい．バックトラックで戻ってきたときに，探索条件をそこで切り替えられるようにする，と．つまり，スタックフレーム全保存ということになるのだろう．そりゃ，落ちますよね，ええ．

この選択点を切り捨てるには，定義のどこかに述語"！"（そこまでよ！（AA略……じゃなくてそこまで選択点カット）を置けばいいらしい．ということで，効果のありそうなところに置いてみて，もう一度，えいっ．

?- bf(snip)
|: PARANOiA
paranoia
|: FMPSG
fmpsg

おお，スタックフレームがちゃんと切り捨てられてるのか，まったく落ちなくなった．しかし，動作がもっさりしてる……仕方ないか．メモリ内容の変更毎にメモリリストをコピーしてるし．そもそも，動いているのがインタープリタの上のインタープリタだから，速度は期待してはいけないのかも知れない．

かくして，私とPrologのみょんな出会いという劇は幕を閉じた．Brainfuck インタプリタの実装を通して，私は何かを得ることができたのだろうか？