TL;DR
まじめな説明
Brainf**kについて
おはようございます。突然ですがBrainf**kという言語をご存知でしょうか。
Brainf**kはUrban Müllerという人が作ったプログラミング言語で、いわゆる「難解プログラミング言語」の代表によく挙げられます。
具体的な仕様は以下のようになっています。[出典不明]
- Brainf**kには配列およびその要素を指すポインタが一つある。
- 配列の要素は1バイト、要素数は最低でも30000個あり、0で初期化される。
- ポインタははじめは配列の先頭を指している。
- 命令は以下の8つ。
| 命令 | 意味 |
|---|---|
| > | ポインタをインクリメントする |
| < | ポインタをデクリメントする |
| + | ポインタが指している要素をインクリメントする |
| - | ポインタが指している要素をデクリメントする |
| . | ポインタが指している要素をASCIIコードとして文字を出力する |
| , | 入力された文字のASCIIコードをポインタ位置に格納する |
| [ | ポインタが指している要素が0ならば対応する"]"の直後に飛ぶ |
| ] | 対応する"["に飛ぶ |
以上です。これで全部です。
しかしこれだけ小さな言語でありながらチューリング完全であることが知られています。
上に書いた言語仕様もチューリングマシンに似せたものと考えればわかりやすいのではないでしょうか。
コンパイラを作ってみた
これだけ小さな言語ならコンパイラだって簡単に作れます。完成品がこちらになります。
- 動作環境
- Ubuntu 20.04.2 LTS(64 bit)
- GNU bash, version 5.0.17(1)-release (x86_64-pc-linux-gnu)
まず始めに、Brainf**kをアセンブリ言語に翻訳するところから考えます。
ですがその前に、後々必要になってくる変数やら関数やらを用意しておきます。これはわざわざアセンブリ言語で書くのも大変ですので、C言語で書いたものをgccに翻訳してもらいましょう。ただしせっかくなのでインラインアセンブラを駆使し、標準ライブラリ抜きで実装していきます。bfc_abs()・bfc_memset()・bfc_sbrk()がそれぞれ標準ライブラリにあるabs()・memset()・sbrk()の自前での実装になります。
コード
#include <stddef.h>
#include <syscall.h>
#include <sys/types.h>
static int64_t bfc_abs(int64_t n)
{
return n >= 0 ? n : -n;
}
static void bfc_memset(void *buf, char ch, u_int64_t n)
{
for (u_int64_t i = 0; i < n; ++i) {
*(char*)buf = ch;
buf = (void*)((char*)buf + 1);
}
}
static void* bfc_sbrk(int64_t inc)
{
char *p;
asm (
"syscall"
: "=a" (p)
: "a" (SYS_brk), "D" (NULL)
);
asm (
"syscall"
:
: "a" (SYS_brk), "D" (p + inc)
);
return p;
}
/* 確保されている領域の先頭へのポインタ */
char *alloc_ptr;
/* 確保されている領域のサイズ */
u_int64_t sz;
/* Brainfuckのポインタ */
char *bf_ptr;
/* 初期化 */
void bfc_initialize(void)
{
/* Brainfuckは最低でも30000バイトのゼロ埋めされた領域を持ち、
* ポインタは初期状態で領域の先頭を指す[要出典] */
bf_ptr = alloc_ptr = (char*)bfc_sbrk(sz = 30000);
bfc_memset(alloc_ptr, '\0', sz);
}
/* 終了処理 */
void bfc_finalize(void)
{
bfc_sbrk(-(int64_t)sz);
}
/* 領域の再確保 */
void bfc_realloc(void)
{
/* ポインタが領域をはみ出した場合、そのはみ出た分の2倍の領域を足し合わせて再確保する */
const int64_t offset = bf_ptr - alloc_ptr;
if (0 <= offset && (u_int64_t)offset < sz) {
return;
}
const u_int64_t margin = (offset >= 0 ? offset - sz + 1 : (u_int64_t)bfc_abs(offset)) * 2;
bfc_sbrk(margin);
if (offset >= 0) {
bfc_memset(alloc_ptr + sz, '\0', margin);
} else {
for (u_int64_t i = 0; i < sz; ++i) {
alloc_ptr[margin + sz - i - 1] = alloc_ptr[sz - i - 1];
}
bfc_memset(alloc_ptr, '\0', margin);
bf_ptr += margin;
}
sz += margin;
}
コメントにも書かれていますがalloc_ptrが確保されている領域の先頭へのポインタ、szが確保されている領域のサイズ、bf_ptrがBrainf**kのポインタになります。
また、bf_initialize()は名前の通り最初に呼び出す関数です。Brainf**kの言語仕様に従い30000バイトのゼロ埋めされた領域を確保します。そしてbf_finalize()も名前の通り最後に呼び出す関数です。確保していた領域を解放します。
一番活躍してくれるのがbf_reallocです。先ほど書いたようにBrainf**kの使える領域ははじめ30000バイトしかないので、ポインタがこの領域の外にあるときに読み出し・書き込みを行おうとするとセグフォります。なので、Brainf**kのポインタが領域をはみ出した場合、領域の再確保が必要となります。
これをしてくれるのがbf_reallocというわけです。こいつはポインタがはみ出してしまった分の2倍の領域を加えて確保しなおします。再確保は重い処理なので、なるべく回数を減らすために「はみ出た分の2倍」と少し余裕をもって確保しています。
このlibbf.cをオブジェクトファイルにして後で使います。
$ gcc -c libbf.c
さてBrainf**kには前述のように命令が8つしかなく、しかも各命令とそれを表すトークンは一対一で対応しています。なので字句解析・構文解析の必要は皆無に等しく、各命令を機械的にアセンブリ言語に訳していくだけでなんとかなりそうです。
ですが、いくつか工夫の余地はあります。例えば++++++++++という命令列があるとき、「ポインタ位置のデータをインクリメントする」を10回も繰り返すよりは「ポインタ位置のデータに10を足す」とした方が効率的なのは明白です。
このことを踏まえて各命令を翻訳すると以下のようになります。
>>>...(>がN個)
; bf_ptrをN個分進める
addq $N, bf_ptr(%rip)
; bf_ptr >= alloc_ptr + szだったら再確保を行う
mov alloc_ptr(%rip), %rax
add sz(%rip), %rax
cmp bf_ptr(%rip), %rax
jg LABEL
call bf_realloc
LABEL:
<<<...(<がN個)
; bf_ptrをN個分戻す
subq $N, bf_ptr(%rip)
; bf_ptr < alloc_ptrだったら再確保を行う
mov alloc_ptr(%rip), %rax
cmp bf_ptr(%rip), %rax
jle LABEL
call bf_realloc
LABEL:
余談ですが、>命令と<命令は上記のようにaddq、subqとせずにadd、subとした場合実行速度がめちゃくちゃ遅くなりました。理由がよくわからなかったのでアセンブリ言語に詳しい方はご教示いただければ幸いです…
EDIT: @fujitanozomu 様からご指摘をいただきました。コメント欄の方を参照願いますm(_ _)m
+++...(+がN個)
mov bf_ptr(%rip), %rax
addb $N, (%rax)
---...(-がN個)
mov bf_ptr(%rip), %rax
subb $N, (%rax)
ただのaddやsubだとbf_ptr(%rip)の指している位置に直接Nを足したり引いたりしたときにオーバーフローして隣接するメモリまで書き換わってしまうことがあるので、addb・subbを使います。
......(.がN個)
sys_writeを使っていきます。
mov $N, %rcx
LABEL:
push %rcx
; システムコール番号
mov $1, %rax
; ファイルディスクリプタ(1 -> 標準出力)
mov $1, %rdi
; 書き出す文字列
mov bf_ptr(%rip), %rsi
; 書き出す文字数
mov $1, %rdx
syscall
pop %rcx
loop LABEL
N=1の場合はrcxをpushしたりpopしたりするだけ無駄なのでこのようにします。
mov $1, %rax
mov $1, %rdi
mov bf_ptr(%rip), %rsi
mov $1, %rdx
syscall
,,,...(,がN個)
こちらはsys_readを使っていきます。
mov $N, %rcx
LABEL:
push %rcx
; システムコール番号
mov $0, %rax
; ファイルディスクリプタ(0 -> 標準入力)
mov $0, %rdi
; 読み込んだ文字列の格納先
mov bf_ptr(%rip), %rsi
; 読み込む文字数
mov $1, %rdx
syscall
pop %rcx
loop LABEL
こちらもN=1のときはこうします。
mov $0, %rax
mov $0, %rdi
mov bf_ptr(%rip), %rsi
mov $1, %rdx
syscall
[と]
きちんとループするには[と]の間でラベルの名前がきちんと対応していなければなりません。
ですが今回使ったC++にはstd::stackがあるので、これを使えばラベルの管理も簡単にできます。
詳しくは面倒なので端折らせていただきます。
LOOP_BEGIN:
mov bf_ptr(%rip), %rax
movzbq (%rax), %rax
cmp $0, %al
je LOOP_END
jmp LOOP_BEGIN
LOOP_END:
アセンブリソースから実行可能ファイルを作る
これでBrainf**kの翻訳ができるようになったので、プロローグ・エピローグおよびsys_exitの呼び出しと、先述のbf_initialize・bf_finalizeの呼び出しを加えてやれば立派なアセンブリソースになります。
.global _start
_start:
; 下の2行がプロローグ
push %rbp
mov %rsp, %rbp
call bf_initialize
; ここにBrainf**kの翻訳が入る
call bf_finalize
; 下の2行がエピローグ
mov %rbp, %rsp
pop %rbp
; 終了ステータス0でsys_exitを呼び出す
mov $60, %rax
mov $0, %rdi
syscall
あとはこれをさっき作ったlibbf.oと一緒にgccに渡せば実行可能ファイルができます。
$ gcc translated.s libbf.o
ですが、せっかく「コンパイラ」を作っているのですから最後の最後でgccに頼りたくないという気持ちがあります。せっかくなのでgccを使わずに実行可能ファイルを作ってみます。
まずはtranslated.sをオブジェクトファイルに変換します。これにはasコマンドが使えます。使い方は簡単です。
$ as translated.s -o translated.o
次にldコマンドでリンクを行います。こっちも簡単です。
$ ld libbf.o translated.o -o executable.out
実行例
ということでめでたく実行ファイルが作れるようになったので、動かしてみたいと思います。
詳しくはgithubの方のりどみを見てください。
+++++++++[>++++++++>+++++++++++>+++>+<<<<-]>.>++.+++++++..+++.
>+++++.<<+++++++++++++++.>.+++.------.--------.>+.>+.
$ make hello.out
$ ./hello.out
Hello World!
👑🍺優勝🍺👑
まとめ
TL;DRに乗せてたgifはマンデルブロ集合を描画するプログラムを動かしていた時のものなのですが、見ての通り重たいです。つまりまだ最適化の余地はありそうです。
あとQiitaのシンタックスハイライトってBrainf**kに対応してるんですね…なぜ…?