More than 1 year has passed since last update.

この記事は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], chcmp 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ライフを!