難解プログラミング言語の一つであるBrainf*ckのオンラインデバッグ環境を作った話をします。debugger👈👈👈👈👈Brainf*ckデバッガについてBrainf*ckはその仕様上、極めてバグを埋め込みやすいです。<命令はよく連続して使われて数え間違えやすく、しかも使う個数を1個でも間違えるとバグるしたがって、(特に大規模な)Brainf*ckプログラムを作成する上ではデバッガの存在はとても大切です。いうことで数年前にmoon.kmc.gr.jpというデバッガを作ったのですが、如何せん古くなってきたので新しく作り直すことにした、というのが今回の内容です。現在の機能インタプリタBrainf*ckのコードを実際に実行することができます。標準入力を与えることもできます。デバッグモードを有効にすると、100msごとなど指定した時間間隔で命令を実行させられます。入出力をUTF-8の文字列と解釈するか、16進数と解釈してバイナリを扱うかを選択できます。Brainf*ckではEOFに達したときに入力命令を実行した場合の値は規定されていませんが、これを0と-1(255)で選択できます。デバッグ機能プログラムカウンタとデータポインタの位置を表示します。@命令に達するとそこで実行を停止させることができます。停止させた後はステップ実行などで細かくプログラムの動作を追うことが可能です。:命令に達すると標準エラー出力に今のポインタの指す値を出力します。.の標準エラー出力版です。指定した範囲のメモリの内容を見ることができます。adventar.org4日目の記事はmatsu7874さんによる「RustでBrainfuckインタプリタを実装した話を書けるだろうか?」の予定です。/-500/さんによるunidentifiedexe.hatenablog.comです。この記事はadventar.org5日目の記事でもあります。空いていたので埋めました。4日目の記事はnakarioさんによるqiita.com6日目の記事はdnek_さんによるwww.dnek.appでした。Brainf*ck処理系同士の非互換性Brainf*ckの処理系(コンパイラおよびインタプリタ)にはもとの言語仕様の曖昧さ等から、様々な細かい仕様の違いが存在します。実行したときにEOFに到達していた場合は0または-1が格納されます。これについては、予め実行する処理系がわかっていれば、比較的簡単に対処することができる場合が多いです*1。他にも用意されるセルサイズや、負番地への進入・アクセスができるか、文字コードの扱いなどの違いもあります。対処が大変な差異の一つが、一つのセルに格納できる値の範囲と、セルの値がオーバーフローした際の挙動です。オーバーフローでランタイムエラーになるといった違いがあります。符号の有無とオーバーフローの挙動を表にするとこんな感じで少なくとも8通りが考えられるわけです。bionicのデフォルト挙動とか。errorにすることもできる。0初期化とムーブ、コピーここで問題になるのが、あるセルに対して、その値を0にしたい、あるいはコピーやムーブといった基本操作がしたいというときです。ムーブはあるセルの値を他のセルに代入し、元のセルの値は0にするという操作です。コピーはあるセルの値を他のセルに代入し、かつ元のセルの値はそのまま保持する操作です。brainf*ckでは大抵の操作が破壊的操作なため、ムーブよりコピーのほうが複雑で、値のコピーはかなり重要なテクニックになります。これらの処理はwrap-around環境では簡単で、0初期化なら[-]あるいは[+]で0初期化できます。符号なしの場合はどの仕様でも(最適化がしょぼくて時間がかかるかもしれませんが)[-]で常に0初期化できます。隣のセルへの値のムーブも[>+<-]で行うことができ、それを応用して[>+>+<<-]>>[<<+>>-]などで隣のセルへ値をコピーできます。問題は符号ありでwrap-aroundでない場合で、たとえばセルの値が負の数の場合に[-]を実行すると永久に終わらないか実行時エラーになってしまいます。これに対する対策はいくつかあります。0初期化なら符号に応じて[-]と[+]を使い分ける。ムーブなら[>+<-]と[>-<+]を使い分ける。符号なしの場合は[-]と[>+<-]だけでできるのはこれの特殊な場合。aを引くことで非負の値にすることができ、あとは0初期化なら[-]を実行し、ムーブなら[>+<-]を実行し、aを足せば良いです。これにより、saturate環境での0初期化が行えます(最小値の絶対値(あるいはそれ以上の値)を足す)。saturate環境では、aの減算でsaturateが起こる可能性があるので、このままではムーブはできませんが、そもそもsaturate環境で情報を失わずに値を更新することが不可能なため、これはあきらめて、自前で値の範囲を管理して、saturateが起こらない範囲で計算すべきです。問題はこのどちらの仮定も満たさない場合です。Brainf*ckにはセルの値の符号を直接確認する方法がないため、1つめの方法に帰着するのは難しそうです。bignum環境ではセルの値の範囲は全くわからないため、2つめの方法に帰着するのも難しそうです。error環境やsaturateまたはwrap-aroundだが値の範囲が232とか264とかめちゃくちゃでかく、かつ値の0初期化やムーブ、コピーに対する最適化がない場合、saturateより更に厳しく、絶対値の大きい値をいじると死にうる*2ので、でかい値にしないように値の範囲の制御を常に頑張る以外の選択肢はないです。特定の範囲内に値があるかを判定するBrainf*ckではうまく工夫することによって、あるセルの値が指定した範囲内にあるか判定することができます。いま、隣り合う2セルがあり、左側のセルの値が正であることがわかっているとしましょう。0この例では3番地と4番地の値x,yについて、0<=y<xであるかを判定したく、3番地の値xが正であるとしましょう。[->]>>+<<<<<[<]>>>]>>>これを実行すると最終的にポインタは6番地に移動し、もし0<=y<xであるならば6番地の値が正(x-y)になり、そうでなければ0になります。本質は[->]で、「ポインタの指す先が0でないなら1を引き、ポインタを1進める」という処理になります。このループの開始直前はポインタは3番地にあり、その値は正(0<x'<=x)です(0になっていれば外側のループを抜けるため)。そのため、まずx'から1を引き、ポインタは4番地に移動します。4番地の値y'が0ならそこでループが終了し、そうでないなら1を引いて5番地に進みます。ここで、ループ終了時のアドレスがずれているのがポイントで、その後の+の足す先がずれます。これによりループ中で4番地の値y'が0になったかどうかを検出することが可能になります。単純なBrainf*ckプログラミングでは、ループ内でポインタが徐々に移動させるとループ終了時にポインタの指す先がずれて、この後のプログラムの実行が大変になるので、そのようなコーディングは避けられがちですが、こういう場面では非常に役に立ちます。その後、[<]の直前ではポインタは1番地または2番地を指しており、1,2番地が1で0番地が0なので[<]の直後ではポインタはどちらの場合でも0番地になり、分岐していたアドレスが統一されます。これにより外側のループの中身の終了時に3番地にいることが保証され、0<x'<=xの間ループを回すことが可能になります。いうことで、任意の値yが範囲0<=y<xにあるかどうかを判定することができました。これを任意の範囲a<=y<bにしたいときは、式変形をして0<=(y-a)<(b-a)、つまりyからaをひき、かつx=b-aとすればよいです。bignum環境における0初期化もし仮にyがa<=y<bを満たすなら、2番目の方法の通り、y-aは非負なので、[-]によって0初期化できます。bignum環境では値の範囲がわからないので予めa,bを決めてしまうと、もし範囲内になかったときにどうしようもなくなってしまいます。そこで、次のように考えます。...のような条件式を無限に作り、もしこれを満たすa_n,b_nがあればy-anに対して[-]をすれば0初期化できます。b_0<b_1<b_2<...かつa_nは負の無限大に発散し、b_nは正の無限大に発散すれば良いです*3。Brainf*ckでこのような列を作る方法として簡単な方法として、値に1を引く/足す、あるいは定数倍するという方法があります。b_nを指数的に変化させる方が良いでしょう。これを踏まえた実装は次のとおりです。4番地を0初期化したいとします。>>>[<<<+>>>-]<<<]1回ループを実行するとyがy-a-(b-a)=y-bに変化しますが、aやbを毎回4倍しているので、判定範囲は正と負の両方に単調増大し、結果的にyがどんな値でも0初期化が可能です。yが0になった瞬間にループを抜けられるような作りになっています。ムーブやコピーもこのテクニックを応用することで可能です。非負整数ペアによる整数表現ここまで符号も範囲もわからない数を相手になんとかプログラムする方法を扱ってきましたが、整数を扱う方法は直接セルに値を格納するだけではありません。ここでは非負整数のペア(二つ組)によって整数を扱う方法を紹介します。b)は整数a-bを表すことにします。このようにすることによって、整数演算を非負整数の演算に帰着することができます。ここで、a,b,c,d同士の演算として足し算と掛け算しか出てきていないことに着目すると、(オーバーフローがなければ)これらの計算によってペアの中身が負になることはなく、非負整数で演算が閉じている、つまりちゃんと整数演算を非負整数の演算に帰着できていることがわかります。非負整数同士の演算はBrainf*ck界でもよく知られているように、そんなに大変ではないので、だいぶ楽になると思います。この方法により負の数を登場させなければ、符号なし環境のように単純なコードでプログラミングすることができます。足し算と掛け算しか出てこないため、演算のたびに数値はどんどん大きくなります。したがって、オーバーフローのある環境では演算を繰り返すうちに(たとえ真の値a-bの絶対値が小さくても)オーバーフローが起こる可能性があります。b-a)と"標準化"することで回避できます(そのぶんコードは増えますが、生の整数を扱うよりは楽ではないでしょうか)。このへんはコード長やメモリ消費量、プログラミングのしやすさなどを見極めながら適宜選択していくことになるでしょう。adventar.org2日目はみみねこさんによるmmnkblog.hatenablog.comでした。4日目はmatsu7874さんによる「RustでBrainfuckインタプリタを実装した話を書けるだろうか?」の予定です。今回はBrainf*ckの素直な派生言語で、かつメタプログラミングが可能な自作言語、BFmetaの紹介をします。Brainf*ck派生言語の惨状Brainf*ckは言語仕様が単純で、コンパイラやインタプリタが作りやすいという特徴があります。そのため、巷にはBrainf*ckの仕様をちょっといじった派生言語がいっぱいあります。多いのが8種類の命令を別の文字列に置き換えただけの派生言語で、Ook!やジョジョ言語などがあります。これらの言語は単なる文字列の置き換えに過ぎないため、ソースコードの見栄えが異なる以上の違いはなく、プログラミングする上ではあまり面白くないです。ほかにも、命令の追加でプログラミングの難易度を下げた言語もあり、ビット演算命令を追加するなどしたBrainCrashが代表的な例です。普通に命令を追加しただけでは多少プログラミングが簡単になるだけであまり面白くありません。命令数を増やした分Brainf*ckのシンプルさから来る美しさが失われてしまいます。して、ほとんどのBrainf*ck派生言語はプログラミング言語としてはちっともおもしろくないわけで、その惨状にひどくうなされた私は、夜しか眠れない日々が続きました。なんとかBrainf*ckの美しさを継承しつつ、本質的な差異をもつ言語が作れないか考えた結果、ついに生み出されたのが、Brainf*ckでメタプログラミング*1を可能にする派生言語、BFmetaです。命令数はBrainf*ckと同じ8種類です。Brainf*ckとBFmetaの最も大きな違いはプログラム空間とデータ空間が統合されていることです。これにより柔軟なメタプログラミングが可能になります。8bit(1Byte)*2符号なし整数*3の双方向に無限長*4の配列が用意され*5、0番地からプログラムのソースコードが順に格納され、配列のそれ以外の領域は0で初期化される。データポインタとプログラムポインタという二つのポインタがあり、どちらも最初は0番地を指している。命令の意味は次の通り、オリジナルのBrainf*ckとほとんど変更されていません。プログラムポインタは毎ステップの最後に1進められ、プログラムポインタの指す値が次の9種類の文字のいずれかのASCIIコードに等しい場合、それに対応する処理が行われます。それ以外の場合、何も行わず(単にプログラムポインタを1進めて)そのステップを終了します。プログラムを終了するBrainf*ckの仕様をご存じの方なら、Brainf*ckとほとんど同じ仕様であることがわかると思います。実際のBFmetaはBrainf*ckよりかなり表現力に長けた*6プログラミング言語になっています。次節ではその表現力の一部をお見せいたします。Worldソースコード中に書いたデータを実行中に読むことができるので、ソースコード中に文字列を埋め込んでそれを表示するだけです。World!の文字数分だけ戻って、そこから1文字ずつ出力しています。ソースコードにヌル文字を許せば*7、次のように更に短く書けます。インタプリタ標準入力から最初にヌル文字に到達するまでをソースコード、それ以降を標準入力とみなすことにします。[>],[>,]>まずBFmetaソースコードの末尾まで移動し、そこからBrainf*ckのソースコードを読み込み、1Byteデータポインタを進めます(これがないとBrainfckプログラムの終了時にBrainfckプログラムの配列の先頭が0でないときに誤作動してしまう)。最初のソースコードはここまでですが、連続してさっき読み込んだBrainf*ckプログラムが格納してあり、データポインタはここからそれ以降はすべて0で初期化されているため、このままプログラムを実行し続ければ、読み込んだBrainf*ckプログラムをBrainf*ckプログラムとして実行したときの実行結果が得られます。これくらいありますが、それより遥かに短く書けました。BFmetaでBFmeta自身のインタプリタを書くのはもう少し難しいです。(配列が負の方向に伸びないと仮定するなら、Brainf*ckインタプリタとほぼ同じにはなるのですが...)Quine空のソースコードをQuineと言い張ればBFmeta以外にもBrainf*ckやRubyでも0ByteのQuineが書けたことになりますが、それでは面白くないので、大抵は正の長さのソースコードであることが求められます。keisukenakano.hatenablog.comでは404BytesのBrainf*ckのQuineが紹介されています。これでも十分短いのですが、BFmetaではなんと1文字のQuineが存在します。.まあソースコードをデータとして保持しているので、当たり前ではあります。このソースコードには改行を含んではいけないことに注意してください。そのため、環境によってはうまく表示されないことがあります。改行を含めたソースコードをQuineしたい場合は次のようにしてください。[.>]これでもBrainf*ckに比べてコード長が1/80です。思って予めインタプリタ(及びデバッガ)をRubyで書いたものがこちらになります。github.com実行速度があまり速くないので、今度C++かRustで速いインタプリタを書きたいと思っていますが、それはまた別の記事にしたいと思います。その速いインタプリタによって、Brainf*ckに対して本質的な計算量の改善ができる可能性についても、また別の記事にしたいと思います。3日目】Tweet広告を非表示にするもっと読むコメントを書く2019-05-27「サイゼリヤで1000円あれば最大何kcal摂れるのか」を全探索で解いてみた概要qiita.comこの記事や後述の先行研究に触発されて、「サイゼリヤで1000円あれば最大何kcal摂れるのか」を最も単純に全探索で解いてみました。先人たちがいろいろな方法で解決を試みています。qiita.comqiita.comqiita.comqiita.comqiita.comqiita.comqiita.comanqou.net実装あらかじめ実装したものがこちらになります。github.comメニューデータはgithub.comにあるmenu.csvをダウンロードしてきました(make時に自動でダウンロードされます)実装の注意点としては、探索の途中で合計金額があらかじめ指定した金額(1000円)を超えるような組み合わせは調べないようにしています。*1実際に計算してみます。kcal先行研究の結果と一致しているので正しく計算できているようです。私の手元のPCでは0.4秒弱で計算が終わりました。全探索しても大したことなかったですね。数々のアルゴリズムはすべて無駄だったわけです。...というわけではなく、この方法だと上限金額を大きくするとあっという間に計算時間が爆発します。試しに1500円で計算させたところ、30秒弱かかりました。1000円から1700円程度までの実行時間を元に予測すると、おおよそ指数的に計算時間が増えて、2000円だと30分程度、3000円だと100日程度かかってしまう計算になります。手法によっては10000円でも現実的な時間で解くことができているので、サイゼリヤで豪遊したい場合はアルゴリズムを学ぶことが必須なことがわかります。感想もっと計算時間がかかるかと思っていたので拍子抜けしています。Adventarの2日目の記事です。Computing社のPEZY-SC/SC2を使わせてもらいました。性能とか使いやすさについて感想とか知見を述べます。Data)プロセッサであることが特徴です。MIMDなので各コアで全く異なる命令を独立に実行できる点でGPUなどのSIMDプロセッサと異なります。使えるようになるまで理研に設置されているスーパーコンピューター、菖蒲(Shoubu)は一般の人でも申請して認められれば無料で使うことができます。Computing社の社長(当時)が逮捕された頃です)に、並列オセロ終盤ソルバーの開発の名目で申請しました。申請して通ったら書類にサインしたのをスキャンして送ったりsshの公開鍵を送ったりといった手続きをすればアカウントが作成されて使えるようになります。申請して使えるようになるのはPEZY-SCを搭載した菖蒲ですが、PEZY-SC2でしか使えない機能(アトミックなど)を使いたい場合はPEZY-SC2を搭載した菖蒲SystemBを使わせてもらえるようです。使ってみる基本的な使い方はGPUと同じで、ホストとなるCPU側のコードとデバイス(アクセラレータ)側のコードの両方を書きます。デバイス側のプログラムはclangに食わせるので普通のC++14が書けます(標準ライブラリは使えませんが)。この点は古いOpenCLで書かざるを得ない環境と比べるとだいぶ楽だと思います。Memoryのようなことはいまのところできない)。今回はサンプルとしてMIMDの恩恵が受けられるN-Queen問題を実装してみます。チェスのクイーンは上下左右と斜めに動ける(飛車と角行を合わせたような動き)。この問題は各行についてどこに置けるかを試すバックトラックで解けることが知られています。駒の利きをビット列で管理することで、ビット演算を用いて高速に解けることも知られています。並列化は数行を全探索し、その結果を各スレッドに分配して計算させることでできます。flush();}GPUなどのSIMDアーキテクチャと違って、PEZYプロセッサでは分岐のペナルティーがとても小さいという特徴があるので、このように再帰の中で分岐をするコードを書いても素直かつ高速に動きます。GPUで高速に動かそうとすると再帰をスタックを用いたループで書くなどコードを変形する必要があり、プログラミングが困難になります。ホスト側では数行分の全探索をするコードとデバイス側のプログラムを呼び出すコードを書きます。デバイス側のプログラムを呼び出すのはOpenCLとほぼ同じです。コードCPU/GPU版はこちら。github.comGPU版は再帰をスタックを用いたループで書き直す最適化をしてあります(solve_nonrec関数)。マイコンクラブwww.slideshare.netを見てください(102ページ目から)。PEZY-SC/SC2版はこちら。2.891分岐ペナルティーの小ささなどからPEZY-SC2が最も高速という結果になりました。さらなる最適化GPU/PEZY-SC/SC2版ともに、タスク(計算する盤面)によって計算量が異なることにより、後半は遊んでしまうコアが出てきます。GPUやPEZY-SC2ではアトミック命令が使えるので、アトミック命令を使うなどして動的にタスクを割り振ることでさらに高速化することができます。アトミック命令の使い方などはNDAを結ばないと教えてもらえませんが、ソースコードは公開OKなので、私の公開しているオセロソルバーのソースコードgithub.comなどから類推することでおおよそはわかるのではないでしょうか。実際、PEZY-SC2上でアトミック命令を用いて最適化したところ、2.40199秒まで高速化されました。sc2オセロソルバーの実装オセロソルバーとはあるオセロの局面が与えられたときにそこから両者が最善を尽くしたときの試合結果(何石差か)を求めるプログラムのことです。基本的にはαβ法という再帰的なアルゴリズムを用いて解きます。CPU/GPU版を実装していたので、簡単にPEZY-SC/SC2版も実装できると思っていました。github.comしかし、N-Queen問題と同じようにオセロソルバーも実装しようとしたのですが、空きマスが多くなると(=再帰の深さが深くなると)エラーが出て正しく動きませんでした。原因を探ってみると、どうやらスタックオーバーフローしているようです。実は、PEZY-SCにはローカルメモリが16KBあり、これを1コア内の8スレッドで分割してスタック領域として使います(ちなみに、スタック領域を縮小して余ったローカルメモリをコア内の共有メモリとして使うこともできます)。そのため、スタック領域は各スレッドにつき2KBしかありません。PEZY-SC2でローカルメモリが20KBになりましたが、それでもスレッドあたりは2.5KBです。N-Queenより複雑なオセロソルバーではスタック領域が不足してしまっていたのです。(再帰で書いているのも一因ですが、スタック消費量を気にせずコードを吐くLLVM側も悪い気はします)そこで、泣く泣くスタック領域を大量に消費する再帰で書くことを諦めて、自分で実装したスタックをグローバルメモリ上に置いてループで解くことにしました。これで解けるようにはなりましたが、プログラミングが非常に難解になってしまいました。このあたりのプログラミングの難しさが解消されるともっと良いと思うのですが...(スタック領域は基本グローバルメモリに置かれて、キャッシュで高速化するなど、難しそうではありますが)何とかプログラミングの困難さを乗り越えて実装した結果がgithub.comです。Heuristic(速さ優先探索)を行っています(複数段に適用しようとするとスタックが足りなかった)。orderingNegaScout法の適用になります(まだパラメータ調整をちゃんとしていなくて速度が出ない場面もありますが...)。V100でも測るべきですが、クラウドで8GPUとかぶん回すと結構高いのでやってません、あとGPU版はいくつかの改良を取り入れてないです)。菖蒲SystemBでは最大1週間のジョブを投げられるので、22~23石空きまでは1ノードで読ませることができそうです(1石空きマスが増えるごとにだいたい3倍ぐらいかかる時間が増える)(ちなみにノード数を増やしてもゲーム木の大きい局面が律速になるのでそんなに高速化しない)。orderingを実装して更なる高速化を果たして、24石空き程度まで読ませたいと考えています。感想PEZY-SC/SC2はメニーコアのMIMDプロセッサという他にはあまりないアクセラレータです。V100を超えるパフォーマンスを出せることを示せました。次世代のPEZY-SC3も近いうちに登場するみたいなので楽しみですね。一方で、スタック領域の制約にはかなり苦しめられました。再帰的なタスクに有利なので、たくさんスタック領域が使えるとプログラミングがしやすくてよいと思うので、この辺が改善されてほしいです。さんの「ぷよぷよのプレイ動画を解析して棋譜を生成する」です。22日目】この記事はKMCアドベントカレンダー22日目の記事です。adventar.orgこの記事では全国一億三千万のビット演算マニアのために、AVX512命令セットからビット演算に使えそうなものを紹介します。Extensions(AVX)というx86/x64のベクトル演算拡張命令を512ビット幅に拡張したものです。普通のCPUではSkylake-SP/X/Wから使えるようになりました。512bitのデータを一括で処理できます。ビット演算なら512並列ですよ512並列。各種ビット操作・バイト操作命令の追加AVX512の命令セットAVX512は複数の要素から構成されており、プロセッサによってサポートの状況が異なります。以下に書くサブセットとその説明を書きます。AVX512をサポートするプロセッサは必ずこれをサポートする。Hist処理とかがベクトル化できる。32bit/64bit単位での処理。8bit/16bit単位での処理。128bit(XMM)/256bit(YMM)レジスタを操作する。最新のCPU(Skylake-SP/X/W)でもまだ使えない拡張もたくさんあります。