Brainf*ckというプログラミング言語をご存じでしょうか。ご存じの方はこの節を飛ばして「Brainf*ckでプログラミングする」に進んでいただいて構いません。
ご存知でない方に簡単に説明すると、Brainf*ckはなるべくコンパイラが小さくなるように設計されたプログラミング言語で、最低限の手続き型言語の機能を実装しており、わずか8命令だけ*1でプログラミングできるという、まさに手続き型言語のエッセンスを凝縮したプログラミング言語です。

Brainf*ckの言語仕様

プログラムは最初、0で初期化された無限長の配列*2が用意され、その先頭を指すポインタ(プログラム中に出てくることは無いですが、ここではptr呼ぶことにします)が用意されます。ポインタがわからない場合も、この場合は配列の添字だと思えばよいでしょう。

使用出来る命令

ソースコードの可読性が高まるように命令記号が選ばれています。

+ : ポインタの指す値を1増やす。C言語の++(*ptr);に相当。
- : ポインタの指す値を1減らす。C言語の--(*ptr);に相当。
> : ポインタをインクリメントする(ひとつ進める)。C言語の++ptr;に相当。
< : ポインタをデクリメントする(ひとつ戻る)。C言語の--ptr;に相当。
[ : もしポインタの指す値が0なら、対応する]にジャンプする。C言語のwhile(*ptr){に相当。
] : もしポインタの指す値が0でないなら対応する[にジャンプする。C言語の}に相当。
. : ポインタの指す値を文字として標準出力に出力する。C言語のputchar(*ptr);に相当。
, : 標準入力から1バイト読み込み、ポインタの指す場所に代入する。C言語の*ptr=getchar();に相当。

Hello worldは次のように書けます。

+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.------------.<++++++++.--------.+++.------.--------.>+.

Brainf*ckでプログラミングする

Brainf*ckには我々が普段使うような命令はほとんど用意されていないので実際にプログラムを書く際はちょっとした工夫が必要となります。
昨年私が作った資料がWeb上の資料では日本で一番詳しいんじゃないかと思います。（自画自賛）

実用Brainf*ckプログラミング from 京大マイコンクラブ

Brainf*ckの問題点

実際にプログラムを書いてみるとわかると思いますが、Brainf*ckには関数がないので大規模なプログラムになるに連れ可読性が低下し、コード量が爆発的に増えてしまいます。
また、リテラル値をソースコード中に埋め込めないので、いちいち動的に生成しなければなりません。これはさらなるコードの増長とともに可読性の低下をもたらします。

既存のBrainf*ckの拡張・派生言語には主に2通りあります。

命令記号の置き換え可読性を上げる・下げるために命令記号を他の文字列に置き換える方法です。
KQ Ook! ごちうさ
挙げていくとキリがないし、Brainf*ckの命令を置換した言語を作るgemが存在しているので、詳しいことは省略しますが、どちらにせよ表現力は上がらないし可読性も大して上がりません。
命令の拡充表現力を増すために使える命令を増やす方法です。
代表的なものとしてはBrainCrashがあります。
私も以前Brainf*ck風言語Prime(ver 0.0.1)インタプリタ · GitHubというBrainf*ckに命令を追加した言語を作ったことがあります。
BrainCrashではビット演算を行う4命令が追加されていますが、それでもまだまだ表現力は低いですし、Brainf*ckの持つ言語の美しさを損なってしまいます。

BFmetaという解決策

私はBrainf*ckのシンプルな言語仕様を損なうことなく、Brainf*ckに強い表現力を与えることを考えました。その結論がBFmetaです。

Brainf*ckからの変更点は2つだけ、「配列中にソースコードをマップし、命令の読み取りも配列から行う」、「プログラム終了条件は読み込んだ命令がヌル文字だったとき」です。

たったこれだけの変更ですが、これにより、プログラム実行中にプログラムを書き換える、リフレクションが可能になります。
また、プログラム中からソースコードの内容を参照できるので、文字列リテラルが簡単に使えるようになります。

しかも、Brainf*ckの特徴であるシンプルな命令体系と命令記号はそのままです。

詳しい言語仕様(といっても紙1枚に余裕で収まる程度ですが)はBFmetaのページを見てください。処理系はhttps://github.com/primenumber/BFmetaから入手できます！

サンプル

Hello, World!

[>]<<<<<<<<<<<<<<[.[-]>]Hello, World!

Brainf*ckと比較すると相当短いコードになっていることがわかります。(このコードには最後に改行が必要です。ファイル末尾に自動的に挿入される改行に注意。)

Brainf*ckインタプリタ

[>],[>,]

Brainf*ckで実装するとこんなに長くなってしまうBrainf*ckインタプリタがなんと8バイトです！

実用的な例も見てみましょう。与えられた文字列中の指定した文字列を別の文字列に置き換えて、更にその結果生成された文字列をBFmetaのプログラムとして実行します！
（多少時間がかかります）

文字列置換により動的にコード生成を行うBFmetaプログラム

この例では、ソースコード中の一番最後の文字に囲まれた範囲で、最初の改行までの文字列(この場合はinc)を次の改行までの文字列(この場合は>)に置き換える、という事をその後の文字列全体(この場合は[inc]<<<<<<<<<<<<<<[.[-]inc]Hello, World!)に対し繰り返し適用します。文字列置換部分は、http://www.slideshare.net/KMC_JP/brainfckで紹介したポインタ付き配列のイディオムを応用して実装されています。

文字列置換したプログラムの中でさらに文字列置換を行うネストもできます。しかし、2重にした時点で1時間半以上実行に時間がかかったので、実用するにはより高速な処理系が必要になるでしょう。

ソースコード置換を二重に掛けるテスト · GitHub

なんだかBFmetaでまともなプログラムが書ける気がして来ませんか？してきましたね！ぜひどんどんかっこいいBFmetaプログラムを書いて@_primenumberに送りつけましょう！！泣いて喜びます！！！

BFmetaインタプリタ・デバッガについて

GitHub - primenumber/BFmeta: Brainf*ckでリフレクションができるようにしたプログラミング言語BFmetaのインタプリタ・デバッガ

このBFmetaインタプリタ・デバッガはRubyで書かれており、デバッガモードではCursesを用いて、実行途中の配列の様子を見ることが出来るなど、詳しいデバッグを行うことができます。デバッグモード時には入力をファイルで与えますが、名前付きパイプを渡すことができるのでインタラクティブなプログラムのデバッグも可能です。まだ不十分な部分もあるのでPullRequest等どんどん募集しています！

KMCM

KMCこと京大マイコンクラブでは、難解プログラミング言語を通して自己を新たなステージに導きたい方を募集しています。KMCには入部制限はありません。年齢や学歴、人種、宗教、信条、性別、社会的身分、門地、国籍、経験などは不問です。また活動に関する制約もありません。IRCのチャット越しに会話に参加することだけでも大丈夫です。詳細は下記Webページを御覧ください。

これにてKMCアドベントカレンダーは無事（？？？）最終回を迎えました！皆さん有難う御座いました！！！

*1:Lazy Kは3関数、IotaやJotは2関数でプログラミングできるので最小ではありません

*2:実際に無限長の配列は用意できないので、十分大きな長さにするか、動的配列にして必要に応じて拡張する

2014-10-21

ICPC アジア地区予選東京大会 2014 参加記

競技プログラミング

結果

5完17位(University rank14位)でした。 Colorful Jumbo ChickenがおそらくWF出場権を得ます。今回の結果を考えると、仮に台湾大会でWF出場権を得てもおそらくWFは辞退することになります。

コンテスト中にしたこと

筆箱を忘れる
.Xmodmapを書く
.vimrc, .emacsを書く
テンプレートを書く
Bをバグらせる
- ゴミ実装力
Gをバグらせる
- ライブラリをちゃんと整備しておけばここまでバグらなかったはず(データ構造は自分の担当)
- 引退したチームのライブラリを持ってきていて、その中にあった。ちゃんと確認しておかないとダメだった

感想

なにもかもダメだった
引退

昨日の結果がダメダメだったので引退です
— そすうぽよ (@_primenumber) 2014年10月19日

あまりにも辛いので額にJAGシールを貼って引退宣言。

来年度どうするかはまた考えるとして、一応経験を積むためにとりあえず台湾大会は出る予定です。

2014-07-14

ICPC 国内予選 2014 参加記

競技プログラミング

ICPCの国内予選に出たことについての感想を書きます。

チームと結果

チーム名: Primasta

メンバー: @asi1024 @TakiTakiTakise @_primenumber

6問正答/全7問, ペナルティ: 23875

全体で5位、大学別4位、大学内1位

国内予選が始まるまで

京大から他にAlkachu,Colorful Jumbo Chickenという強いチームが出るので、ツイッターでは

絶対全完して学内一位取ろうな
— そすうぽよ (@_primenumber) 2014年7月10日

起きれたしICPC勝利も同然。
— そすうぽよ (@_primenumber) 2014年7月11日

みたいなことを言っていたが、模擬国内予選の結果を鑑みるにアジア地区予選に出られる望みは薄いなあという感じでいた。

特に前日深夜のTopcoder SRMで0完してしまい気分が最悪な感じな上に、ICPCが始まるまでに起きれるかが不安になる程度に生活習慣も崩れまくっていてダメダメっぽい感じ。

競技開始直前

チーム内で担当をどうするか決めた。私は模擬国内予選の時に他人の書いたコードのバグを見つけるのが上手いらしいことがわかったので主にデバッグ担当をすることに。

デバッグ担当は実装担当が実装してる後ろでバグってそうな場所を突っ込んだりする。ペアプログラミングの要領。

競技中

私が実装した問題のみソースコードを載せます。 asiさんが実装した問題のソースコードはhttp://asi1024.hatenablog.com/entry/2014/07/14/034221から見れます。

A問題

実装: @asi1024 デバッグ: @TakiTakiTakise

私は問題を読んでない。5分程度でAC。この間にB問題を読んでどういうふうにコードを書くか考えた。

B問題

実装: @_primenumber デバッグ: @TakiTakiTakise

制約が緩いので単純にシュミレートするだけだけどちょっとバグりやすかった。15分程度でAC。

C問題

実装: @asi1024 デバッグ: @_primenumber

シルエットの座標が整数しか取らないことを利用すると実装が簡単になることをasiさんが見抜いていたので早かった。10分程度でAC。

D問題

実装: @asi1024 デバッグ: @_primenumber

各文字について変換が高々一回しか起こらないので、候補となる文字列を全列挙できることをasiさんがすぐに見ぬいた。パフォーマンスを重視してmapではなくvectorを使うことにしたが、重複が起こりうることを忘れていてWAしてしまったので裏目に出た。17分程度でAC。

E問題

実装: @TakiTakiTakise デバッグ: @_primenumber

ほぼ同じ問題を解いたことがあったので、解法はすぐにわかった。実装を楽にするために(辺の重みの3倍)-(葉についている辺の重みの2倍)-(葉を除いた木の直径)という求め方をした。DFSを2回して木の直径を求める方法を忘れていたので各頂点からDijkstraをした。実装をどうするか詰めている間にasiさんにDijkstraのライブラリを写してもらった。

23分程度でAC。それなりに上位にいたが、残り2時間弱あることを考えると十分に抜かされうるので、時間をかけてでも必ずどちらかは通そうという事を考えた。

G問題

実装: @asi1024 デバッグ: @_primenumber, @TakiTakiTakise

Fはサイコロのやばそうな問題に見えたので、まだわからんこともないGを考えた。幾何ライブラリにお世話になりながら、いろいろなバグに苦戦を強いられたが、1時間半弱かけてAC。この間にぼんやりとF問題の解法を思いつく。ACした瞬間のうれしさは半端無かった。ここでアジア地区予選に行けることを確信。

F問題

辞書順とか関係なく、与えられた6つの数を持つサイコロが作れるかがO(t)で判定できれば解けることに気づいたので、asiさんに言ったら作れるかの判定が割と簡単にできるとわかり、実装しようとしたがさすがに時間がなかった。

全体的な感想

今年の問題セットは考えれば実装がかなり楽になる問題が多かったように思う。実装が苦手な傾向のあるPrimastaにとって有利に働いた気がする。

うーん、でもこの結果はさすがにうまく行き過ぎに思えるなぁ。チーム戦略がうまくハマったのも大きそう。

今後について

JAGの夏合宿に参加したかったけど運転免許の教習とかぶってしまったので出れなくて悲しい。

それはともかく、精一杯World Finalに行けるように頑張りたいけど、数学にそろそろ本腰を入れないとやばいので困ってしまう。

2013-12-30

Lenovo ideapad s210上のDebian wheezyで無線LANを使えるようにするには

その他

必要な作業は多くないけど、日本語の情報もないので備忘録程度に書いておきます。

症状

Lenovo ideapad s210上のDebian wheezyで無線LANが使えない
NetworkManagerの画面にそもそも無線接続の選択肢が出てこない

無線LANデバイスの型番を調べる

なにはともあれ、とりあえず必要な情報を集めます。

端末上で

$ lspci

と入力すると、PCIにつながっているデバイスがぞろぞろと出てきます。その中に
02:00.0 Network controller: Atheros Communications Inc. AR9565 Wireless Network Adapter (rev 01)

という記述を発見。どうもこれっぽい。

※一般に、無線LANデバイスにはPCI接続するもの以外に、USB接続するもの、PCカード接続するものなどがあり、特にノートPCではどれであるかを見分けるのが難しいです。PCIにつながっているデバイスにそれっぽいものがない場合はUSB接続されている場合などがありえます。

HowToIdentifyADevice/PCI - Debian Wiki

HowToIdentifyADevice/USB - Debian Wiki

などでそれっぽいデバイスがないかどうか調べましょう。どれにもない場合、そもそもOSがデバイスの存在を認識していない可能性があります。その場合は多分結構大変です。頑張ってください。

ググる

とりあえず無線LANデバイスの型番がAtheros AR9565であることはわかったので適当にググります。

すると、

Debian User Forums • View topic - [SOLVED] Getting Atheros AR9565 wireless to work

要は「Atheros AR9565を動くようにしたい」という内容で、症状もほぼ同じです。

どうやらLinux カーネルを新しいものにするとデバイスドライバが入って使えるようになるよ、という話らしい。

Linux kernelのバックポート

DebianはLinux Kernalがメジャーアップデートされてもそれに追随せず、今入っているバージョンのマイナーアップデートとバグフィックスが適用されるだけなので、新しいバージョンを入れるためには少し作業が必要になる。

リポジトリの追加

/etc/apt/sources.listに次の行を追加する。(管理者権限が必要)

deb http://dennou-k.gfd-dennou.org/debian/ wheezy-backports main
(http://dennou-k.gfd-dennou.org/ は自分の使っているミラーサーバーに変えたほうが良い)

さらに、端末上で、

$ sudo aptitude update

$ sudo aptitude -s install linux-image-3.11-0.bpo.2-amd64

としてやると新しいカーネルがインストールされる。このとき、依存関係の問題でなにか質問されるので、一回目はn、二回目はyと答えると正しくインストールされたはず。

このあと再起動してやればちゃんと無線LANに接続できます。

参考文献

WiFi - Debian Wiki

Debian User Forums • View topic - [SOLVED] Getting Atheros AR9565 wireless to work

2013-08-20

ブラウザ上でBrainf*ckを実行･デバッグできるサービスを作りました.

難解プログラミング言語

Brainf*ckインタプリタ

デバッグモードをONにして,｢1ステップの実行時間｣を0より大きい値にするとプログラム実行中のメモリの様子や今どこを実行しているかがリアルタイムでわかります.コード中に@があると,そこでプログラムが一時停止するので,簡易的なブレークポイントとして使えます.｢追跡するメモリのサイズ｣で先頭から何バイト目までトレースさせるかを調節できます.あまり大きくすると実行が遅くなります.

デバッグモードがONで｢1ステップの実行時間｣が0だと@に到達するまでの状態は表示されませんが,高速に実行されます.

デバッグモードをOFFにすると@を無視して最後まで実行します.

｢入力の形式｣はテキストエリアに入力した文字列をそのまま入力として扱うか16進数のデータ列とみなすかを選択できます.16進数を選択するとキーボードからは入力できないデータも入力として与えることができます.

このインタプリタは特に最適化などは施していないのであまり速くありません.とてもたくさんのステップ数のかかるプログラムを入れると固まります.それから,括弧の対応がおかしい場合も無限ループにはまって固まるかもしれません.

これでみなさんも快適にBrainf*ckプログラミングを楽しみましょう!

2013-08-08

実用Brainf*ckプログラミング

難解プログラミング言語

高校生の頃にBrainf*ckでFibonacci数を計算して表示するプログラムを書いて以来,何度かBrainf*ckのコードを書く機会があった.受験生の頃には,受験勉強をするふりをしてHanoiの塔を解くBrainf*ckのコードを書いた.

京大生になってKMCに入って,いろいろな面白いことをしている人はいたけど,Brainf*ckのコードを書く人は見当たらなかったので,自分の持っているテクニックをまとめてみたら面白いのではと思って,KMC内で「実用Brainf*ckプログラミング入門編」という内容でBrainf*ckの初歩的な内容を発表したら,わりとウケたので入門編だけでなく全編作ることにした.

projectpn - brainf*ckでbrainf*ckインタプリタ

とかはこのために書いたもので,今のところ初級編で扱う予定.

一応Brainf*ckである程度のプログラムが書けるくらいには網羅的に様々なトピックを取り扱いたいと思っているが,一人で書いているので色々と抜け落ちていそう.