読者です 読者をやめる 読者になる 読者になる

【お知らせ】プログラミング記事の投稿はQiitaに移行しました。

Brainf*ckでループ展開

第3回 コンパイラ実装会@uho_iiotokoさんがBrainf*ckのトランスレータを実装されているとき、ちょっと面白いことが起きました。

元はC言語で実装されたBrainf*ckからアセンブラへのトランスレータです。トランスレート対象がC言語でも同じ結果となるため、Pythonで再実装した再現コードを掲載します。

【注】無限ループや入力は想定していません。

インタプリタトランスレータの両方が実装されています。トランスレータではループ( [ と ] )を実装していないにも関わらず、トランスレートされたコードは正常に動作します。

$ ./bf.py helloworld.bf
Hello World!
$ gcc bf.c
$ ./a.exe
Hello World!

これはなぜなのか首をひねりました。結論から言うと、インタプリタを実行しながらトランスレートしているため、結果的にループを展開したコードが出力されていました。

たとえば次のようなBrainf*ckのコードを変換してみます。

ループを2回繰り返しますが、それが展開されます。

用語

参加者の@furandon_pigさんより、このようなループの展開を loop unrolling と呼ぶことを教えていただきました。調べるとWikipediaにも書いてありました。

最適化でループに細工をするような事例は知っていましたが、用語があることまでは知りませんでした。