Pythonで作る奇妙なプログラミング言語 その２(Brainfuck)

Pythonで作る奇妙なプログラミング言語　その１(HQ9+)
の続きです。

今回取り上げるのはおそらくEsoteric Languageのなかで最も有名なBrainfuck（本では伏字にしてBrainf*ckと表記していますが、アスタリスク入力するのが面倒臭いので伏字なしで書きます）。

説明面倒なのでWikipediaをどうぞ↓
Brainfuck - Wikipedia

Brainfuck（ブレインファック）は難解プログラミング言語のひとつ。なお名称に卑語が含まれるため、Brainf*ckなどと表記されることがある。
...
Brainfuck プログラムは非常に可読性・記述性が低いため実用性は期待できないが、それでもチューリング完全な（チューリングマシンで実行可能なあらゆるプログラムが記述できる）言語であり、理論上はC言語などの普通のプログラミング言語と同等の表現力を持つ。その簡潔から多くの派生言語を生み出すこととなった。
メモリを指す暗黙のポインタを「>」「<」命令で移動させながら、そのポインタが指す値を増減させて処理を進めていく。
...
実行可能な命令は次の8つのみである。
1. > ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。
2. < ポインタをデクリメントする。C言語の「ptr--;」に相当。
3. + ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。
4. - ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。
5. . ポインタが指す値を出力する。C言語の「putchar(*ptr);」に相当。
6. , 1バイトを入力してポインタが指す値に代入する。C言語の「*ptr=getchar();」に相当。
7. [ ポインタが指す値が0なら、対応する ] の直後までジャンプする。C言語の「while(*ptr){」に相当。
8. ] ポインタが指す値が0でないなら、対応する [ にジャンプする。C言語の「}」に相当。

というわけで、サンプルコードをPythonに移植したのがこちら

brainf_ck.py

# coding: utf-8

import sys

class Brainf_ck():
    
    class ProgramError(StandardError): pass
    
    def __init__(self, src):
        self._tokens = src
        self._jumps = self._analyze_jumps(self._tokens)
    
    def run(self):
        tape = []
        pc = 0
        cur = 0
        
        while pc < len(self._tokens):
            if cur >= len(tape):
                tape.append(0)
            if self._tokens[pc] == '+':
                tape[cur] += 1
            elif self._tokens[pc] == '-':
                tape[cur] -= 1
            elif self._tokens[pc] == '>':
                cur += 1
            elif self._tokens[pc] == '<':
                cur -= 1
                if cur < 0: raise self.ProgramError(u'開始地点より左には移動できません')
            elif self._tokens[pc] == '.':
                print chr(tape[cur]),
            elif self._tokens[pc] == ',':
                tape[cur] = ord(raw_input().strip())
            elif self._tokens[pc] == '[':
                if tape[cur] == 0:
                    pc = self._jumps[pc]
            elif self._tokens[pc] == ']':
                if tape[cur] != 0:
                    pc = self._jumps[pc]
            pc += 1
    
    def _analyze_jumps(self, tokens):
        jumps = {}
        starts = []
        
        for i, c in enumerate(tokens):
            if c == '[':
                starts.append(i)
            elif c == ']':
                if not starts: raise self.ProgramError(u'「]」が多すぎます')
                frm = starts.pop()
                to = i
                
                jumps[frm] = to
                jumps[to] = frm
        if starts: raise ProgramError(u'「[」が多すぎます')
        
        return jumps

try:
    src = open(sys.argv[1]).read()
except IOError:
    src = sys.argv[1]
except IndexError:
    src = raw_input()

try:
    Brainf_ck(src).run()
except Brainf_ck.ProgramError:
    print u'Brainf_ckプログラムの実行に失敗しました'

Brainfuckインタプリタの完成です。早速ハロワ表示させてみましょう。
helloworld.bf

+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.+++.------.--------.>+.

前回のHQ9+とはエラい違いですねｗ

C:\hogehoge>python brainf_ck.py helloworld.bf
H e l l o , w o r l d !

動きました。が、Pythonのprint命令の仕様で文字の間にスペースが入っちゃってなんとも間抜けな感じに…

それでは、Rubyとの比較で気付いた点

• Rubyのcase〜whenに相当するものがないので、 elif self._tokens[pc] == ... と１つずつ書かないといけない。面倒っちゃ面倒
• Rubyの配列では、未定義の要素にアクセスしようとすると（長さ1の配列にa[1]ってやるとか）nilが返ってくる。一方Pythonのリストだとエラーになる。これは（たぶん）一長一短だけど、今回はちょっと面倒だった

Pythonにswitchがないのは有名ですよね。「んなもんelifでできるんだかわざわざ新しいの作らんでもいいだろ」というのはPythonらしい部分かと。前回のfor文でも
「each とか upto とか downto とかあると便利だから入れちゃおうぜ」
なRubyに対して
「全部forでできるからいらん」
なPython。思想の違いが現れてるよなあ。

さて、次回はこれも有名なWhitespace。プログラムがすべて空白文字だけで構成されるという恐ろしい言語なのです。

Rubyで作る奇妙なプログラミング言語 ~Esoteric Language~