Brainfuckの短いインタプリタの話

この記事はEsolang(難解プログラミング言語) Advent Calendar 2016の12日目です。

はじめに

Brainfuck、難解プログラミング言語としては有名ですよね。開発コンセプトは「コンパイラがなるべく短く作れる言語」とされています。日本語版Wikipediaによれば、コンパイラは123Byte、インタプリタは98Byteでできると書いてあります(この記述は一部取り違えているところがあるような気もしますが)。しかし、世の中にはたくさんのBFコンパイラやらインタプリタが存在するため、実際に見たことがある人は少ないのではないでしょうか？
実際にインタプリタのソースコードが簡単に手に入るので、見てみましょう。

98Byteインタプリタのソースコード

BFI2.COMとBFI2.ASM

0000   4B             CLEAR:  dec         bx
0001   88 2F                  mov   byte[bx],       ch
0003   80 FF 7F               cmp         bh,       7F
0006   75 F8                  jnz       0000  ;CLEAR
0008   BE 61 01               mov         si,     0161  ;offset M-1
000B   46             DO:     inc         si
000C   8A 04                  mov         al,  byte[si]
000E   3C 40                  cmp         al,       40  ;'@'
0010   75 01                  jnz       0013  ;O1
0012   C3                     ret          0
0013   3C 3E          O1:     cmp         al,       3E  ;'>'
0015   75 01                  jnz       0018  ;O2
0017   43                     inc         bx
0018   3C 3C          O2:     cmp         al,       3C  ;'<'
001A   75 01                  jnz       001D  ;O3
001C   4B                     dec         bx
001D   3C 2B          O3:     cmp         al,       2B  ;'+'
001F   75 02                  jnz       0023  ;O4
0021   FE 07                  inc   byte[bx]
0023   3C 2D          O4:     cmp         al,       2D  ;'-'
0025   75 02                  jnz       0029  ;O5
0027   FE 0F                  dec   byte[bx]
0029   3C 2E          O5:     cmp         al,       2E  ;'.'
002B   75 06                  jnz       0033  ;O6
002D   B4 02                  mov         ah,       02
002F   8A 17                  mov         dl, byte[bx]
0031   CD 21                  int         21
0033   3C 5D          O6:     cmp         al,       5D  ;']'
0035   75 02                  jnz       0039  ;O7
0037   5E                     pop         si
0038   4E                     dec         si
0039   3C 5B          O7:     cmp         al,       5B  ;'['
003B   75 19                  jnz       0056  ;O8
003D   56                     push        si
003E   38 2F                  cmp   byte[bx],       ch
0040   75 C9                  jnz       000B  ;DO
0042   5E                     pop         si
0043   33 C9                  xor         cx,       cx
0045   80 3C 5B       AGAIN:  cmp   byte[si],       5B  ;'['
0048   75 01                  jnz       004B  ;NOTLSB
004A   41                     inc         cx
004B   80 3C 5D       NOTLSB: cmp   byte[si],       5D  ;']'
004E   75 03                  jnz       0053  ;NOTRSB
0050   49                     dec         cx
0051   E3 B8                  jcxz      000B  ;DO
0053   46             NOTRSB: inc         si
0054   EB EF                  jmp       0045
0056   3C 2C          O8:     cmp         al,       2C  ;','
0058   75 B1                  jnz       000B
005A   B4 08                  mov         ah,       08
005C   CD 21                  int         21
005E   88 07                  mov   byte[bx],       al
0060   EB A9                  jmp       000B  ;DO
0062                  M:

USAGE: COPY BFI2.COM + sourcefile outputfile.com /B

実は、このインタプリタは特殊で、最後に自分のソースコードを連結することで動くというものです。また、そのソースコードの末端が@(アットマーク)で終端されている必要があります。このように、短くするためにちょっとセコい技を使っています。
ちなみに、DOSBOX上でこのプログラムを動かしてみたのですが、Hello, world!すら出力できませんでした。これは、int21h ah=02hでの一文字出力システムコールがalを書き換えてしまうため、','を出力するとalが','に書き換わってしまい、BF命令の','だと勘違いしてしまうことによるようです。

98Byteインタプリタに使われているショートコーディングの技法

1. この.comファイルは実行ファイルなのですが、ファイルシグネチャがないため、普通には最も短い実行ファイルが作れます。
2. このプログラムが始まるときにbx, cx(2016/12/26修正: chでした)は0クリアされていることを使って、初期化をせずにプログラムを書き始めています。
3. cmp al, immという命令は、他のレジスタを使うより1Byte短くなるので積極的に使っています。
4. else ifの形にしないで、全部並列のif文にしているので、jmp命令を使う数が減らせています(しかしさっきのバグの原因になっています)。
5. push siなどによって、[]のループの実現が簡潔になっています。
6. cmp byte[bx], chはcmp byte[bx], 0の代わりに使っているのですが、定数を書かずにレジスタを使う命令は1Byte短くなります。しかし、chに繰上りが起きると正しく動作されないため、[]のループのネストが255回までしか許されなくなります。(2016/12/26修正: ここの記述は誤りでした)
7. jcxz という珍しい命令を使っています。cxレジスタが0であればジャンプするという、cmp命令とjz命令を組み合わせたような命令です。

改造してみた

とりあえず、バグは直しておきたいところです。また、alレジスタに読み込んでからsiレジスタをインクリメントする、というのはそのものずばりのlodsb命令があるので、これを使うとさらに縮みそうです。
とりあえずバグを修正して93Byteまで縮みました。

93byte.comと93byte.asm

0000   4B             CLEAR:  dec         bx
0001   88 2F                  mov   byte[bx],       ch
0003   85 DB                  test        bx,       bx
0005   78 F9                  js        0000  ;CLEAR
0007   BE 5D 01               mov         si,     015D  ; offset M
000A   AC             DO:     lodsb
000B   3C 40                  cmp         al,       40
000D   75 01                  jnz       0010  ;O1
000F   C3                     ret          0
0010   3C 3E          O1:     cmp         al,       3E  ;'>'
0012   75 01                  jnz       0015  ;O2
0014   43                     inc         bx
0015   3C 3C          O2:     cmp         al,       3C  ;'<'
0017   75 01                  jnz       001A  ;O3
0019   4B                     dec         bx
001A   3C 2B          O3:     cmp         al,       2B  ;'+'
001C   75 02                  jnz       0020  ;O4
001E   FE 07                  inc   byte[bx]
0020   3C 2D          O4:     cmp         al,       2D  ;'-'
0022   75 02                  jnz       0026  ;O5
0024   FE 0F                  dec   byte[bx]
0026   3C 5D          O5:     cmp         al,       5D  ;']'
0028   75 02                  jnz       002C  ;O6
002A   5E                     pop         si
002B   4E                     dec         si
002C   3C 5B          O6:     cmp         al,       5B  ;'['
002E   75 15                  jnz       0045  ;O7
0030   56                     push        si
0031   80 3F 00               cmp   byte[bx],       00
0034   75 D4                  jnz       000A  ;DO
0036   5E                     pop         si
0037   B1 01                  mov         cl,       01
0039   AC             AGAIN:  lodsb
003A   3C 5B                  cmp         al,       5B  ;'['
003C   75 01                  jnz       003F  ;NOTLSB
003E   41                     inc         cx
003F   3C 5D          NOTLSB: cmp         al,       5D  ;']'
0041   75 F6                  jnz       0039  ;AGAIN
0043   E2 F4                  loop      0039  ;AGAIN
0045   3C 2C          O7:     cmp         al,       2C  ;','
0047   75 08                  jnz       0051  ;O8
0049   B4 08                  mov         ah,       08
004B   CD 21                  int         21
004D   88 07                  mov   byte[bx],       al
004F   EB B9                  jmp       000A  ;DO
0051   3C 2E          O8:     cmp         al,       2E  ;'.'
0053   75 B5                  jnz       000A  ;DO
0055   B4 02                  mov         ah,       02
0057   8A 17                  mov         dl,   byte[bx]
0059   CD 21                  int         21
005B   EB AD                  jmp       000A  ;DO
005D                  M:

(改造した点)

1. lodsb命令を使ってalへの読み込みとプログラムポインタ(si)の移動を同時に行って短縮
2. jcxz命令ではなく条件が逆転する代わりにcxレジスタのデクリメントも行うloop命令を使って短縮
3. js命令で分岐することで定数を書かなくて済むようになるので1Byte削減
4. '.'で,の入力を受けた時にバグるのをjmp命令を追加して修正(順番を変えて末尾のjmp命令と共通にさせようとしたが','命令の面倒を見る羽目になって結局jmp命令を省けず+2Byte)
5. []のネストが256回を超えても大丈夫なようにchレジスタを0と仮定しない(+1Byte)

おわりに

いかがだったでしょうか。esolangは書くだけではなくて処理系の方も面白さがありますね。
なんかesolangじゃなくてショートコーディングの話題に終始してしまったような気がする……
本当はコンパイラの方もやる予定でしたが時間もやる気も尽きてしまったのでこれで終わりたいと思います。
それではよいBrainfuckライフを！