prime's diary

そすうの日々を垂れ流しちゃうやつだよ

Brainf*ck + リフレクション = BFmeta 【KMCアドベントカレンダー26日目】

おはようございます!! KMC2回生のprimeです!!

この記事は今年もやります!KMCアドベントカレンダー!! - KMC活動ブログの26日目の記事です。昨日の記事は、primeさんのお詫び 【KMCアドベントカレンダー25日目】 - KMC活動ブログでした。

はじめに

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の問題点

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

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

  • 命令記号の置き換え 可読性を上げる・下げるために命令記号を他の文字列に置き換える方法です。
    KQ Ook! ごちうさ
    挙げていくとキリがないし、Brainf*ckの命令を置換した言語を作るgemが存在しているので、詳しいことは省略しますが、どちらにせよ表現力は上がらないし可読性も大して上がりません。

  • 命令の拡充 表現力を増すために使える命令を増やす方法です。
    代表的なものとしてはBrainCrashがあります。
    私も以前Brainf*ck風言語Prime(ver 0.0.1)インタプリタという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時間半以上実行に時間がかかったので、実用するにはより高速な処理系が必要になるでしょう。

ソースコード置換を二重に掛けるテスト(未検証)

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

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

primenumber/BFmeta · GitHub

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

KMCM

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

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

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

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