Brainf*ck でマンデルブロ集合を描く

# Brainf*ck でマンデルブロ集合を描く

## はじめに

* 2 年ぐらい前に [Brainf*ck のコンパイラをシェルで作った](https://qiita.com/yoshi389111/items/133078e38e9e84ba87b9) 後にしばらく Brainf*ck でプログラムを組んでいたのだけど、しばらくぶりに掘り起こして、忘れないようにメモ
* 自力で、Brainf*ck をつかってマンデルブロ集合を描いてみました。残念ながらあまり速くはないです。
* あまり役に立つ情報はないと思いますが、これから Brainf*ck でコーディングしようとしている人の参考になれば幸いです（必要としているのは Qiita の読者１億人当たり数人ぐらい？）
* 無駄に長いです

![mandelbrot(color)](https://raw.githubusercontent.com/wiki/yoshi389111/brainfuck-compiler-c/images/mandelbrot_color.gif)


## Brainf*ck 言語仕様

Brainf*ck には 8 種類の命令があります

* `>` ポインタをインクリメントする。ポインタをptrとすると、C言語の「 `ptr++;` 」に相当する。
* `<` ポインタをデクリメントする。C言語の「 `ptr--;` 」に相当。
* `+` ポインタが指す値をインクリメントする。C言語の「 `(*ptr)++;` 」に相当。
* `-` ポインタが指す値をデクリメントする。C言語の「 `(*ptr)--;` 」に相当。
* `.` ポインタが指す値を出力に書き出す。C言語の「 `putchar(*ptr);` 」に相当。
* `,` 入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「 `*ptr=getchar();` 」に相当。
* `[` ポインタが指す値が0なら、対応する `]` の直後にジャンプする。C言語の「 `while(*ptr){` 」に相当。
* `]` ポインタが指す値が0でないなら、対応する `[` の直後にジャンプする。C言語の「 `}` 」に相当。

説明は wikipedia の [Brainfuck(ja)](https://ja.wikipedia.org/wiki/Brainfuck) の項からお借りしています。

Brainf*ck には少なくとも 30000 個のセルの配列と、入力・出力のバイトストリームがあり、これを操作することで処理を実現します。

## Brainf*ck の移植性の問題

英語版の wikipedia の [Brainfuck(en)](https://en.wikipedia.org/wiki/Brainfuck) によると、Brainf*ck の移植性の問題として以下の 4 つがあるとされています。

### Cell size

ポインターの指す先のセルのサイズは、8bit が一般的ですが、ほかのサイズも存在するとのこと。

16bit, 32bit, あるいはそれ以外の実装もあるようです。

### Array size

古典的な実装では、配列は 30000 個のセルからなり、最初ポインターは左端（0の位置）にいます。

しかし、さらに左側（配列の添え字が負）のセルを持つ実装もあるようです。

また配列の範囲を超えて移動する際には、エラーになる実装、配列を拡張する実装、配列の反対に移動する実装、範囲チェックしない（でコケる）実装などが存在するようです。

### End-of-line code

Brainf*ck に限りませんが、改行コードが異なることが多いです。

多くは LF( `\n` ) を改行コードとして扱いますが、CR+LF( `\r\n` )や CRのみ( `\r` )を使う実装（あるいは動作 OS ）があります。


### End-of-file behavior

ファイルの最後を読み込んだ際の動作は、実装によって（主に？）以下の 3 つがあるようです。

* 0 を書き込む
* -1 (C言語の `EOF` ) を書き込む
* 何も変化しない

## Brainf*ck コンパイラの実装

Brainf*ck である程度の機能を持ったプログラムを作る上で、いくつかコンパイラに機能を追加したほうが良いと思い、C 言語でコンパイラ `bf2c` を作りました。
コンパイラというか、正確には Brainf*ck のソースを C 言語に変換するトランスレータです。コードの最適化は C コンパイラにお任せです。

https://github.com/yoshi389111/brainfuck-compiler-c

以下のような特徴があります

* 上記の移植性の問題のいくつか（セルサイズやEOFの動作）などを選択可能
* 入力元を、標準入力以外に、ファイルやコマンドラインから直接文字列を指定可能
* 出力先を、標準出力以外に、ファイルを指定可能
* バージョン情報やヘルプメッセージを指定可能

`bf2c` には以下のようなオプションが指定できます。

* `-o` or `--output` : 出力ファイル(Cソース)を指定します
* `-F` or `--force-flush` : １文字ごとに強制 flush するようにします
* `-O` or `--output-default` : 実行コマンドのデフォルト引数を出力パスとします
* `-I` or `--input-default` : 実行コマンドのデフォルト引数を入力パスとします
* `-M` or `--message-default` : 実行コマンドのデフォルト引数をメッセージとします
* `-s` or `--size` : メモリ配列の数を指定します(デフォルト 30000)
* `-1` or `--cell-chear` : メモリ配列を char の配列とします(デフォルト)
* `-2` or `--cell-short` : メモリ配列を short の配列とします
* `-4` or `--cell-int` : メモリ配列を int の配列とします
* `-z` or `--eof-zero` : EOF を 0 とします
* `-m` or `--eof-minus` : EOF を -1 とします(デフォルト)
* `-n` or `--eof-no-effect` : EOF は読み込まないようにします
* `-C` or `--copyright` : 著作権表示、あるいはライセンス表示を指定します
* `-V` or `--version-string` : バージョン情報を指定します
* `-v` or `--version` : コンパイラのバージョンを表示します
* `-h` or `--help` : ヘルプメッセージを表示します

`-2` や `-4` を指定しても、セルサイズが 16bit, 32bit になるかどうかはCコンパイラ次第です。仕様としてはそれぞれ `short` , `int` を使います。

`-V` でバージョン情報を指定しなかった場合には、ソースファイル名、現在日付、ログイン名などをもとにデフォルトの情報を埋め込みます。ログイン名は環境変数を `LOGNAME` `USER` `LNAME` `USERNAME` の順序でチェックして、最初の空ではない文字列が設定されていたものを使います（チェックする環境変数は python の `getpass.getuser()` を参考にしています）。もし、なにも設定されていない場合には `"noname"` を使います。

`-F` の強制フラッシュは、最初の頃に作った自作のマンデルブロ集合のプログラムはかなり遅くて、1 行単位のフラッシュだと動いているかどうかわからなかったため、1 文字づつ表示可能なように追加しました。

コンパイルした実行コマンドは以下のオプションを受け付けます

* `-f` or `--file` : 入力ファイル
* `-m` or `--message` : 入力メッセージ
* `-o` or `--output` : 出力ファイル
* `-v` or `--version` : バージョン情報を表示します
* `-h` or `--help` : ヘルプメッセージを表示します

ただし、Brainf*ck のソースファイルに、 `,` コマンドが使われていない場合、入力ファイルおよび入力メッセージのオプションは指定できません。

同様に、 `.` コマンドが使われていない場合、出力ファイルのオプションは指定できません。

また、バージョン情報とヘルプメッセージは同じ表示になります。

入力ファイル、入力メッセージが指定されていない場合には、標準入力から読み込みます。
同様に、出力ファイルが指定されていない場合には、標準出力に書き込みます。

コンパイル時に実行コマンドのデフォルト引数を指定していた場合( `-I` or `-M` or `-O` )には、１つだけオプションなしで引数を指定可能です。

## Brainf*ck でのプログラム開発入門

Brainf*ck の命令は単純ですが、いくつかを組み合わせることで一通りの処理ができるようになります。
このレベルの内容は Qiita の記事にもいろいろ記載がありますので、駆け足で軽く説明します。

### 値の設定

セルに値を直接設定することはできませんが `+` や `-` を組み合わせることで任意の値を設定できます。

`[-]` のようにすると、現在指しているセルの値を 0 クリアすることができます。

### ループ処理

一般的な言語の `while` 文に相当する機能を実現するには、制御用のセルを用意することで実現できます。
例えば、一つ左隣を制御用のセルとすれば、 `<[>(ループ内の処理)<]>` のようにすれば、ループの処理ができます。
ただし、「ループ内の処理」の終了時には、ポインタを開始時点の位置に戻す必要があります。

指定回数ループする `for` 文に相当する機能も同様に、カウンタが左隣りとすれば `<[->(ループ内の処理)<]>` となります。
この場合、カウンタは処理中にデクリメントされており、ループ終了時点では 0 になっています。
カウンタを破壊しないようにするには、事前にコピーしておく必要があります。

### データの移動、加算、コピー

例えば現在のポインタの指す先の値を、その隣の値に加算するには `[->+<]` のようにすればできます。
1
これを応用すると、例えば 2 倍するには `[->++<]` となります。

2か所（右隣と、そのさらに右隣）に加算するには `[->+>+<<]` とすればできます。

右側がすべて 0 である想定であれば、値のコピーができます。まずは  `[->+>+<<]` として１つ隣と２つ隣に同じ値を入れます。
その後、２つ隣に移動して `>>` 、もとに位置に値を加算(破壊版)すれば `[-<<+]<<` 、値のコピーができます。

Brainf*ck の処理は、基本的に破壊的にしか処理できないため、データのコピーは非常に頻繁に使用します。

### 条件分岐

一般的な言語でいう `if` 文などの条件分岐も、1回だけのループという形で実現します。

例えば、現在の値が 0 以外なら(then)処理1を、0 なら(else)処理2をしたい場合、ワークとして1つのセルを用意してフラグとして使用します。
ここでは、一つ隣をelse用フラグとして使用して、値は 0 であると想定します。

まずは else 用フラグに 1 を設定します `>+<` 。
そして現在の値でループします `[` 。現在の値が 0 以外ならループ内に入り、0 の場合にはループには入りません。
ループ内では、現在の値を 0 クリアして `[-]` 、さらに else用フラグもクリアします `>-<`。その後、処理１を実施して、ループを抜けます `]` 。

次に else 用フラグをもとにループします `>[` 。else 用のフラグをクリアして `-` 、処理２を実施して、ループを抜けます `]<` 。

これで `if` と同様の処理になります。処理が終わった状態では、現在値とフラグはどちらも 0 になっています。

まとめると `>+<[[-]>-<(処理１)]>[-(処理２)]<` このような形になります。

## マクロを活用した Brainf*ck プログラミング

上記のような内容を組み立てていけばいろいろな処理ができるようになります。

が、正直やってられないですよね？

そこで、ある程度のまとまった処理をマクロとして用意しておき、それを活用してプログラミングすることにしました。

とりあえず、ある関数（あるいはメソッド）を呼び出したら、それに対応する Brainf*ck の命令を返してくれるようなマクロを考えます。

### 基本的なマクロ

マクロは、とりあえず Python で書いてみました。

例えば、ポインタを移動するマクロならこんな感じです。

```python
def move_ptr(pos: int) -> str:
    """
    ポインターを移動

    >>> move_ptr(0)
    ''
    >>> move_ptr(2)
    '>>'
    >>> move_ptr(-3)
    '<<<'
    """
    return ">" * pos if 0 <= pos else "<" * (-pos)
```

こうすれば、指定の位置で処理をして、終わったら元の位置に戻るマクロ（仮）はこんな感じになると思います。

```python
def exec_pos(pos: int, statement: str) -> str:
    "指定位置で処理を実行"
    return move_ptr(pos) + statement + move_ptr(-pos)
```

ただし、マクロ同士を組み合わせてプログラミングすると、無駄な処理が発生することがあります。
例えば、 `exec_pos(3, "+") + exec_pos(4, "-")` のような処理では `>>>+<<<>>>>-<<<<` という結果が出力されてしまいます。途中の `<<<>>>` は無駄ですよね。

そこで、まずいくつか基本的なマクロを作ります。

```python
import re


def delete_useless(statement: str) -> str:
    """
    無駄な移動/計算を相殺、削除

    >>> delete_useless("+++--<<>>>")
    '+>'
    >>> delete_useless("---++>><<<")
    '-<'
    >>> delete_useless(">++++[-][-]")
    '>[-]'
    >>> delete_useless(">--[-]++[-]")
    '>[-]'
    """
    while True:
        if "<>" in statement:
            # 無駄な移動の相殺・その１
            statement = statement.replace("<>", "")
            continue
        if "><" in statement:
            # 無駄な移動の相殺・その２
            statement = statement.replace("><", "")
            continue
        if "+-" in statement:
            # 無駄な加減算の相殺・その１
            statement = statement.replace("+-", "")
            continue
        if "-+" in statement:
            # 無駄な加減算の相殺・その２
            statement = statement.replace("-+", "")
            continue
        if "+[-]" in statement or "-[-]" in statement:
            # ゼロクリアの前の加減算の削除
            statement = re.sub(r'[-+]+\[-\]', "[-]", statement)
            continue
        if "[-][-]" in statement:
            # 複数回のゼロクリアを１回に
            statement = statement.replace("[-][-]", "[-]")
            continue
        break
    return statement


def delete_useless_all(statement: str) -> str:
    """
    無駄な移動/計算を相殺、削除。最後の無駄な処理も削除する

    >>> delete_useless_all("[+>-<]>++++[-][-]")
    '[+>-<]'
    >>> delete_useless_all("[-<+>][-]>>++")
    '[-<+>]'
    >>> delete_useless_all("[-<+>][-]<<--")
    '[-<+>]'
    """
    statement = delete_useless(statement)
    while statement:
        if statement[-1] in "-+><":
            # 末尾の "+" "-" ">" "<" は削除
            statement = re.sub(r'[-+><]+$', "", statement)
            continue
        if statement.endswith("[-]"):
            # 末尾の "[-]" は削除
            statement = re.sub(r'\[-\]$', "", statement)
            continue
        break
    return statement


def block_of(*statements: str) -> str:
    """
    複数の命令をまとめる

    >>> block_of("[", "-", "]")
    '[-]'
    """
    return delete_useless("".join(statements))


def program_of(*statements: str) -> str:
    source = delete_useless_all("".join(statements))
    source = re.sub(r'(.{1,72})', "\\1\n", source)
    return source
```

なんだか、頭悪そうなロジックがありますが、どうせ使い捨てのコードなので気にしません。
関数名も意味不明ですが、英語わからないので仕方ないです。

要は、簡単にわかる無駄な移動・計算を削除するマクロと、マクロをまとめて書きやすくするブロック化のマクロです。

これらを使うと先ほどの `exec_pos` も以下のように書き直せます。

```python
def exec_pos(pos: int, statement: str) -> str:
    """
    指定位置で処理を実行

    >>> exec_pos(3, "+")
    '>>>+<<<'
    >>> exec_pos(3, "<+>")
    '>>+<<'
    """
    return block_of(
        move_ptr(pos),
        statement,
        move_ptr(-pos)
    )
```

### 値設定系のマクロ

値の設定系のマクロは以下のような感じ。

```python
def inc_pos(pos: int) -> str:
    """
    指定位置をインクリメント

    >>> inc_pos(2)
    '>>+<<'
    """
    return exec_pos(pos, "+")


def dec_pos(pos: int) -> str:
    """
    指定位置をデクリメント

    >>> dec_pos(3)
    '>>>-<<<'
    """
    return exec_pos(pos, "-")


def clear_pos(pos: int) -> str:
    """
    指定位置をクリア

    >>> clear_pos(3)
    '>>>[-]<<<'
    """
    return exec_pos(pos, "[-]")


def set_value(pos: int, value: int) -> str:
    """
    指定の値を設定

    >>> set_value(2, 3)
    '>>[-]+++<<'
    >>> set_value(2, -1)
    '>>[-]-<<'
    """
    (op, value) = ("+", value) if 0 < value else ("-", -value)
    return block_of(
        clear_pos(pos),
        exec_pos(pos, op * value)
    )
```

`set_value` のロジックもちょっと頭悪そうですが、ワークを使えない前提だとこんな感じかと。

たとえば初期値を設定するような場合（右側はすべて 0 でワークに使ってよいとする）、もう少し考えた設定も可能です。

```python
import math


def _init_value_sub(value: int) -> str:
    "初回の値設定. 隣以降はワークに使ってよい前提"
    (op1, op2) = ("+", "-")
    if value < 0:
        value = -value
        (op1, op2) = ("-", "+")
    if value < 16:
        return op1 * value
    len0 = value
    str0 = op1 * value
    xmin = int(math.sqrt(value))
    xmax = int(math.ceil(value / 2.0))
    for x in range(xmin, xmax + 1):
        strx = _init_value_sub(x)
        lenx = len(strx)
        # len0 = x * y1 + c1 の形に分割
        y1 = value // x
        c1 = value % x
        len1 = lenx + y1 + c1 + 7
        if len1 < len0:
            len0 = len1
            str0 = ">" + strx + "[<" + op1 * y1 + ">-]<" + op1 * c1
        if c1 != 0:
            # len0 = x * y2 - c1 の形に分割
            y2 = y1 + 1
            c2 = x - c1
            len2 = lenx + y2 + c2 + 7
            if len2 < len0:
                len0 = len2
                str0 = ">" + strx + "[<" + op1 * y2 + ">-]<" + op2 * c2
    return str0


def init_value(pos: int, value: int) -> str:
    """
    初回の値設定.
    隣以降はワークに使ってよい前提. 初期化順に注意
    """
    return delete_useless(exec_pos(pos, _init_value_sub(value)))
```

ただ、C言語にトランスレートしてから最適化を掛ける前提だと、もしかすると頭悪そうな `set_value()` の方が効率が良いかもしれませんね。

### ループ系マクロ

ループ系です。

```python
def while_loop(pos: int, *statements: str) -> str:
    """
    whileループ.
    >>> while_loop(3, ">>+<<")
    '>>>[<+>]<<<'
    """
    return block_of(
        exec_pos(pos, "["),
        block_of(*statements),
        exec_pos(pos, "]")
    )


def for_loop(pos: int, *statements: str) -> str:
    """
    繰り返し. 破壊版
    >>> for_loop(3, "+")
    '>>>[-<<<+>>>]<<<'
    """
    return block_of(
        exec_pos(pos, "[-"),
        block_of(*statements),
        exec_pos(pos, "]")
    )


def for_safe(pos: int, work1: int, statement: str) -> str:
    """
    繰り返し. 非破壊版(ただしループ中にposを参照更新してはダメ)
    >>> for_safe(3, 4, "+")
    '>>>[->+<<<<+>>>]>[-<+>]<<<<'
    """
    return block_of(
        for_loop(pos, inc_pos(work1), statement),
        move_data(work1, pos)
    )
```

非破壊版の `for` ループは、破壊してから最後に戻しています。

ワークが2つあれば、値をコピーしてからコピー先でループできるのですが、とりあえずループ中に値を見なければ良いだけなので、まずはこれで。

### コピー・移動系マクロ

データを移動したり、コピーしたりします。

```python
def move_data(source: int, destination: int) -> str:
    "1byteの移動/あるいは加算."
    return for_loop(source, inc_pos(destination))


def copy_data(source: int, destination: int, work1: int) -> str:
    "1byteのコピー."
    return block_of(
        clear_pos(destination),
        for_safe(source, work1, inc_pos(destination))
    )


def override_data(source: int, destination: int) -> str:
    "1byteの移動."
    return block_of(
        clear_pos(destination),
        move_data(source, destination)
    )


def swap_data(target1: int, target2: int, work1: int) -> str:
    "1byte同士の値の入れ替え"
    return block_of(
        move_data(target1, work1),
        move_data(target2, target1),
        move_data(work1, target2)
    )
```

### 条件分岐系マクロ

簡単な `if` 文のマクロです。

else節をつけるにはワークが必要なので、とりあえず then のみ。

```python
def if_nz_then(pos: int, then_statement: str) -> str:
    "if_nz の破壊版. thenのみの簡易版"
    return while_loop(
        pos,
        clear_pos(pos),
        then_statement
    )


def if_one_then(pos: int, then_statement: str) -> str:
    "posの位置が 1 か 0 のどちらが前提. 1 の場合に処理する (破壊版)."
    return while_loop(
        pos,
        dec_pos(pos),
        then_statement
    )
```

`if_one_then` は `if_nz_then` とほぼ同じですが、値が 0 か 1 のどちらかしかないケースだと、ちょっとだけソースサイズが小さくなるので用意しています。
あまり意味ないかも。

### ちょっとトリッキーなマクロ

少し変なマクロも用意しています。
ふと思いついた非破壊版の `if` 文とそれを使った演算処理(繰り上げありの加減乗算)です。

ただし、変な位置にワークが必要なので、 `then` 節の場合と `else` 節の場合とで、ポインタの動きが異なる（最終的には同じになる）という、ちょっとわかりにくいマクロです。

もしかしたら、C言語での最適化の足を引っ張っているかもしれません。

```python
def if_nz_tricky(
        pos: int,
        n: int,
        m: int,
        then_statement: str,
        else_statement: str = "") -> str:
    """
    if_nz の非破壊版. ちょっとトリッキー
    前提条件
      *(ptr + pos + n) == 0
      *(ptr + pos + m) == 0
      *(ptr + pos + n + m) == 0
    ※ n == m でもOK
    """
    return block_of(
        move_ptr(pos),
        inc_pos(n),  # pos+n = else用フラグ
        "[",  # NZ の場合
        dec_pos(n),  # else用フラグをクリア
        exec_pos(-pos, then_statement),
        move_ptr(m),  # NZ は pos+m / Z は pos のまま
        "c]",
        move_ptr(n),  # NZ は pos+n+m / Z は pos+n
        "[-",  # Z の場合
        exec_pos(-pos - n, else_statement),
        move_ptr(m),  # NZ は pos+n+m のまま / Z も pos+n+m に移動
        "c]",
        move_ptr(-pos - n - m)
    )


def if_z_tricky(
        pos: int,
        n: int,
        m: int,
        then_statement: str,
        else_statement: str = "") -> str:
    """
    if_z の非破壊版. ちょっとトリッキー
    前提条件
      *(ptr + pos + n) == 0
      *(ptr + pos + m) == 0
      *(ptr + pos + n + m) == 0
    ※ n == m でもOK
    """
    return if_nz_tricky(pos, n, m, else_statement, then_statement)


def inc_data_tricky(pos: int, digit: int) -> str:
    """
    繰り上がりありのインクリメント. ちょっとトリッキー
    前提条件
      *(ptr + pos + 1) == 0
      *(ptr + pos + 2) == 0
    """

    if 1 < digit:
        # 繰り上がり必要
        return block_of(
            inc_pos(pos),
            if_z_tricky(pos, 1, 1,
                        inc_data_tricky(pos - 1, digit - 1))
        )
    else:
        # 繰り上がり不要
        return inc_pos(pos)


def dec_data_tricky(pos: int, digit: int) -> str:
    """
    繰り下がりありのデクリメント. ちょっとトリッキー
    前提条件
      *(ptr + pos + 1) == 0
      *(ptr + pos + 2) == 0
    """
    if 1 < digit:
        return block_of(
            if_z_tricky(pos, 1, 1,
                        dec_data_tricky(pos - 1, digit - 1)),
            dec_pos(pos)
        )
    else:
        return dec_pos(pos)


def add_data_tricky(source: int, pos: int, work: int, digit: int) -> str:
    """
    1byte加算. pos += source. 繰り上がりあり. 非破壊版. ちょっとトリッキー
    前提条件
      *(ptr + pos + 1) == 0
      *(ptr + pos + 2) == 0
    """
    return for_safe(source, work, inc_data_tricky(pos, digit))


def multi_data_tricky(
        source1: int,
        source2: int,
        pos: int,
        digit: int) -> str:
    """
    1byte乗算. pos = source1 * source2. 繰り上がりあり. 非破壊版. ちょっとトリッキー
    前提条件
      *(ptr + pos + 1) == 0
      *(ptr + pos + 2) == 0
      *(ptr + pos + 3) == 0
      *(ptr + pos + 4) == 0
    """
    return for_safe(
        source1,
        pos + 3,
        add_data_tricky(source2, pos, pos + 4, digit)
    )
```

### Brainf*ck シミュレータ

最初の方のマクロは doctest が記載されていましたが、途中から記載されていないことに気が付いたかもしれません。

基本的なマクロに関しては、単純なコードになるので doctest でも簡単に結果の確認ができましたが、動きを伴うマクロに関しては出力するコードがどんな内容かというよりは、ちゃんと動くかを検証する必要があります。

そのため、python で Brainf*ck のシミュレータ（インタプリタもどき）を作成して、動作の検証を unittest で実施しています（だんだん複雑になっていくと、マクロが正しく動かないとどこがおかしいかわからないので）。

単体テスト重要。

## Brainf*ck スタックマシン化計画

上記マクロでいろいろとプログラムを組んでみました。

* 色付きの Hello, World.
* マイナンバー検証プログラム
* マンデルブロ集合表示

実際に組んだ感じ、気になるのがワークをどこに置くのかが考えるのが面倒、ということでした。
あんまり遠いところだとソースコードが無駄に大きくなるし。

いろいろ考えた結果、スタックマシン（スタック処理言語）にするのが良いのではないか、というアイデアです。
まあ、なんちゃってスタック処理言語風のマクロですが。

また、マンデルブロ集合の場合、小数の加減算・乗算が必要なのですが、当初は二の補数表現の固定小数点小数を使っていました。
しかし、計算速度が非常に遅かったので（ロジックの問題の可能性も高いが）、今回は符号＋絶対値の固定小数点小数にしてみました。

固定小数点小数は、整数部に 1byte 、小数部に 1byte としました（つまり 1/256 の精度しかない）。

### 基本的なスタック操作マクロ

固定小数点小数を、符号＋整数部(1byte)＋小数部(1byte)にしてしまったので、スタックの 1 要素は 4byte にしてみました。

1byte 整数は、4byte 中の先頭に格納します。

固定小数点小数は、先頭 1byte は空、2byte 目が整数部、3byte 目が小数部、4byte 目が符号（0 の場合は正、1 の場合は負）としました。

…なんで昔の私は、符号を後ろにしたんだろう？

また、前述のマクロ群は `bf_core.py` というファイルに登録してある想定です。

```python
import bf_core as c

# 数字は以下の2種類
# ・1byte整数(符号なし) {VALUE, 0, 0, 0}
# ・3byte固定小数点小数. {0, 整数部, 小数部, 符号0/1} 符号＋絶対値

# スタックの1要素は4byte固定
ELEMENT_SIZE = 4
# スタックのトップは1要素前
TOP = ELEMENT_SIZE * (-1)
# スタックの2番目は2要素前
SECOND = ELEMENT_SIZE * (-2)
# 現在のスタック位置は空
NOW = 0
# スタックに積んだら1要素後ろに移動
NEXT = ELEMENT_SIZE * (1)

# 1byte整数の配置 { 整数値, 0, 0, 0 }
IDX_BYTE = 0
IDX_DMY1 = 1
IDX_DMY2 = 2
IDX_DMY3 = 3

# 固定小数点小数の配置 { 0, 整数部, 小数部, 符号(0=+/1=-) }
IDX_DMY = 0
IDX_INT = 1
IDX_DEC = 2
IDX_SGN = 3

def push_byte(value: int) -> str:
    "1byteの整数をスタックの先頭に積む"
    value = int(value) & 0xff
    return c.block_of(
        c.init_value(NOW + IDX_BYTE, value & 0xff),
        c.move_ptr(NEXT)
    )


def push_decimal(value: float) -> str:
    "3byteの固定小数点をスタックの先頭に積む"
    (sign, value) = (0, value) if 0 <= value else (1, -value)
    value = int(value * 256) & 0xffff
    return c.block_of(
        c.init_value(NOW + IDX_INT, (value >> 8) & 0xff),
        c.init_value(NOW + IDX_DEC, value & 0xff),
        c.init_value(NOW + IDX_SGN, sign),
        c.move_ptr(NEXT)
    )


def drop() -> str:
    "スタックの先頭を破棄"
    return c.block_of(
        c.clear_pos(TOP + 3),
        c.clear_pos(TOP + 2),
        c.clear_pos(TOP + 1),
        c.clear_pos(TOP + 0),
        c.move_ptr(TOP)
    )


def dup(num: int) -> str:
    "スタックの要素をコピーしてスタック先頭に積む. num=0が先頭をコピー"
    pos = -ELEMENT_SIZE * (num + 1)
    return c.block_of(
        c.copy_data(pos + 0, NOW + 0, NOW + 1),
        c.copy_data(pos + 1, NOW + 1, NOW + 2),
        c.copy_data(pos + 2, NOW + 2, NOW + 3),
        c.copy_data(pos + 3, NOW + 3, NEXT),
        c.move_ptr(NEXT)
    )


def swap(num: int) -> str:
    "スタックの先頭要素と、スタックの該当要素を交換. 1<=numであること"
    pos = -ELEMENT_SIZE * (num + 1)
    work = NOW
    return c.block_of(
        c.swap_data(pos + 0, TOP + 0, work),
        c.swap_data(pos + 1, TOP + 1, work),
        c.swap_data(pos + 2, TOP + 2, work),
        c.swap_data(pos + 3, TOP + 3, work)
    )


def override(num: int) -> str:
    "スタックの先頭要素で、スタックの該当要素を上書き. 1<=numであること."
    pos = -ELEMENT_SIZE * (num + 1)
    return c.block_of(
        c.override_data(TOP + 3, pos + 3),
        c.override_data(TOP + 2, pos + 2),
        c.override_data(TOP + 1, pos + 1),
        c.override_data(TOP + 0, pos + 0),
        c.move_ptr(TOP)
    )
```

* `push` で、スタックのトップにデータを積む
* `drop` で、スタックの先頭を削除
* `dup` で、スタックの指定位置の要素を、スタックのトップに積む
* `swap` で、スタックの先頭と、指定位置の要素を入れ替え
* `override` で、スタックの先頭を、指定位置の要素に上書き（スタック先頭は削除）

といった感じです。

### スタック版ループ系マクロ

スタックの先頭に 1byte 整数を積んである状態で、その回数分ループします。

ループが終了すると、スタックの先頭の 1byte 整数は破棄されます。

`loop_last` は、ループ処理を中断するときに使うのですが、一般的な `brake` と異なり、処理自体はループの終了 `]` まで実施します（終了フラグが立つだけだと思えばよいかと。実際には制御変数を 0 クリアしてるだけです）。

```python
def loop_of(*statements: str) -> str:
    "TOPの1byte整数分ループする"
    return c.block_of(
        c.for_loop(TOP, *statements),
        c.move_ptr(TOP)
    )


def loop_last(num: int) -> str:
    "ループを終了できる状態にする. num はループの制御変数の位置. 処理は続行する"
    pos = -ELEMENT_SIZE * (num + 1)
    return c.clear_pos(pos + IDX_BYTE)
```

### byte版加減算系マクロ

1byte の加減算です。

2つの 1byte 整数がスタックに積んである場合に、その 2 つを加算あるいは減算します。
計算後は、元の 2 つの要素が削除され、代わりに計算結果が入ります（つまり、スタックの 1 要素分減る）。

```python
def add_byte() -> str:
    "1byteの加算"
    return c.block_of(
        c.for_loop(TOP + IDX_BYTE, c.inc_pos(SECOND + IDX_BYTE)),
        c.move_ptr(TOP)
    )


def sub_byte() -> str:
    "1byteの減算"
    return c.block_of(
        c.for_loop(TOP + IDX_BYTE, c.dec_pos(SECOND + IDX_BYTE)),
        c.move_ptr(TOP)
    )
```

### byte版条件分岐系マクロ

1byte の `if` 文です。

`if` 文終了後、スタックの先頭の 1byte 整数は破棄されます。

また、ワークは 1byte の要素のほかの部分（残り 3byte ）を利用しているため、
スタックの深さは変わりません。

```python
def if_nz(then_statement: str, else_statement: str = "") -> str:
    "スタック先頭 1byteが NZ の場合. 終了後スタック先頭は捨てる"
    else_statement = c.delete_useless(else_statement)
    if else_statement != "":
        else_flag = TOP + IDX_DMY1
        return c.block_of(
            c.set_value(else_flag, 1),
            c.if_nz_then(
                TOP + IDX_BYTE,
                c.dec_pos(else_flag) + then_statement),
            c.if_one_then(
                else_flag,
                else_statement),
            c.move_ptr(TOP)
        )
    else:
        return c.block_of(
            c.if_nz_then(
                TOP + IDX_BYTE,
                then_statement),
            c.move_ptr(TOP)
        )


def if_z(then_statement: str, else_statement: str = "") -> str:
    "スタック先頭 1byteが Z の場合. 終了後スタック先頭は捨てる"
    return if_nz(else_statement, then_statement)


def if_eq(value: int, then_statement: str, else_statement: str = "") -> str:
    "スタック先頭 1byteが value と等しい場合. 終了後スタック先頭は捨てる"
    return c.block_of(
        push_byte(value),
        sub_byte(),
        if_z(then_statement, else_statement)
    )
```

### 固定小数点小数系マクロ

固定小数点小数の計算（加算、減算、乗算）と `if` 文です。

符号＋絶対値表現にしたせいで、意外と加減算がめんどくさいです。

乗算はカラツバ法を使ったほうが良いかもしれないと思いつつ、意外と加減算も遅そうなので変わらないかも、と悩みながら今は筆算方式で計算しています。

```python
def if_nz_decimal(then_statement: str, else_statement: str = "") -> str:
    "3byte固定小数点が NZ の場合. 終了後スタック先頭は捨てる"
    nz_flag = TOP + IDX_DMY
    else_flag = TOP + IDX_INT
    then_flag = TOP + IDX_DEC
    return c.block_of(
        c.clear_pos(TOP + IDX_SGN),
        c.if_nz_then(TOP + IDX_DEC, c.inc_pos(nz_flag)),
        c.if_nz_then(TOP + IDX_INT, c.inc_pos(nz_flag)),
        c.inc_pos(else_flag),
        c.if_nz_then(nz_flag, c.dec_pos(else_flag) + c.inc_pos(then_flag)),
        c.if_one_then(then_flag, then_statement),
        c.if_one_then(else_flag, else_statement),
        c.move_ptr(TOP)
    )


def if_z_decimal(then_statement: str, else_statement: str = "") -> str:
    "3byte固定小数点が NZ の場合. 終了後スタック先頭は捨てる"
    return if_nz_decimal(else_statement, then_statement)


def if_negative_decimal(then_statement: str, else_statement: str = "") -> str:
    "3byte固定小数点が負数の場合. 終了後スタック先頭は捨てる"
    then_flag = TOP + IDX_DEC
    else_flag = TOP + IDX_INT
    return c.block_of(
        c.clear_pos(then_flag),
        c.set_value(else_flag, 1),
        c.if_nz_then(
            TOP + IDX_SGN,
            c.dec_pos(else_flag) + c.inc_pos(then_flag)
        ),
        c.if_one_then(then_flag, then_statement),
        c.if_one_then(else_flag, else_statement),
        c.move_ptr(TOP)
    )


def _add_abs() -> str:
    "3byte固定小数点の絶対値の加算"
    # SECOND/TOP の符号は同じであることを想定
    return c.block_of(
        c.clear_pos(TOP + IDX_SGN),
        c.for_loop(SECOND + IDX_DEC, c.inc_data_tricky(TOP + IDX_DEC, 2)),
        c.for_loop(SECOND + IDX_INT, c.inc_pos(TOP + IDX_INT)),
        c.override_data(TOP + IDX_DEC, SECOND + IDX_DEC),
        c.override_data(TOP + IDX_INT, SECOND + IDX_INT)
    )


def _dec_both_abs_int() -> str:
    "整数部を片方が0になるまで両方をデクリメント"
    count = NOW
    work1 = NOW + 1
    return c.block_of(
        c.copy_data(SECOND + IDX_INT, count, work1),
        c.for_loop(
            count,
            c.if_z_tricky(
                TOP + IDX_INT,
                ELEMENT_SIZE,  # work2 = NOW + IDX_INT
                ELEMENT_SIZE,  # work3 = NEXT + IDX_INT
                then_statement=loop_last(count),
                else_statement=c.block_of(
                    c.dec_pos(SECOND + IDX_INT),
                    c.dec_pos(TOP + IDX_INT)
                )
            )
        )
    )


def _dec_both_abs_decimal() -> str:
    "小数部を片方が0になるまで両方をデクリメント"
    count = NOW
    work1 = NOW + 1
    return c.block_of(
        c.copy_data(SECOND + 2, count, work1),
        c.for_loop(
            count,
            c.if_z_tricky(
                TOP + IDX_DEC,
                ELEMENT_SIZE,  # work2 = NOW + IDX_DEC
                ELEMENT_SIZE,  # work3 = NEXT + IDX_DEC
                then_statement=loop_last(count),
                else_statement=c.block_of(
                    c.dec_pos(SECOND + IDX_DEC),
                    c.dec_pos(TOP + IDX_DEC)
                )
            )
        )
    )


def _if_nz_int_swap() -> str:
    "SECONDの整数部が0以外なら、TOP/SECONDをひっくり返す"
    work = NOW
    return c.if_nz_tricky(
        SECOND + IDX_INT,
        ELEMENT_SIZE * 2,  # work2 = NOW + IDX_INT
        ELEMENT_SIZE * 2,  # work3 = NEXT + NEXT + IDX_INT
        then_statement=c.block_of(
            c.swap_data(SECOND + IDX_INT, TOP + IDX_INT, work),
            c.swap_data(SECOND + IDX_DEC, TOP + IDX_DEC, work),
            c.swap_data(SECOND + IDX_SGN, TOP + IDX_SGN, work)
        )
    )


def _if_top_decimal_is_nz_then_override() -> str:
    "TOPの小数部が0以外なら、TOPをSECONDに移動"
    return c.if_z_tricky(
        TOP + IDX_DEC,
        ELEMENT_SIZE,  # work1 = NOW + IDX_DEC
        ELEMENT_SIZE,  # work2 = NEXT + IDX_DEC
        then_statement=c.clear_pos(TOP + IDX_SGN),
        else_statement=c.block_of(
            c.override_data(TOP + IDX_SGN, SECOND + IDX_SGN),
            c.move_data(TOP + IDX_DEC, SECOND + IDX_DEC)
        )
    )


def _top_minus_second() -> str:
    "SECONDの小数部の分、TOPから減算して、SECONDの位置に移動"
    return c.block_of(
        # 符号を移動(tricky対策で、先に移動)
        c.override_data(TOP + IDX_SGN, SECOND + IDX_SGN),
        # SECONDの小数部だけデクリメント
        c.for_loop(
            SECOND + IDX_DEC,
            c.dec_data_tricky(TOP + IDX_DEC, 2)
        ),
        # 結果を SECONDに移動
        c.move_data(TOP + IDX_DEC, SECOND + IDX_DEC),
        c.move_data(TOP + IDX_INT, SECOND + IDX_INT)
        # TODO -0.0 を 0.0 に変換すべき？
    )


def _sub_abs() -> str:
    "3byte固定小数点の絶対値の減算"
    # どちらかが0になるまでdecする. 残ったほうが答え(符号も含め)
    return c.block_of(
        # 整数部を片方が0になるまで両方をデクリメント
        _dec_both_abs_int(),
        # SECONDの整数部が0以外なら、TOP/SECONDをひっくり返す
        _if_nz_int_swap(),
        c.if_nz_tricky(
            TOP + IDX_INT,
            ELEMENT_SIZE,  # work1 = NEXT + IDX_INT
            ELEMENT_SIZE,  # work2 = NEXT + NEXT + IDX_INT
            then_statement=_top_minus_second(),
            else_statement=c.block_of(
                # TOP/SECONDの両方とも整数部が0の場合
                _dec_both_abs_decimal(),
                _if_top_decimal_is_nz_then_override()
            )
        )
    )


def add_decimal() -> str:
    "固定小数点小数の加算"
    # 符号が同じなら、絶対値の加算
    # 符号が異なるなら、絶対値の減算
    work = SECOND + IDX_DMY
    diff_work = TOP + IDX_DMY
    same_flag = SECOND + IDX_DMY
    return c.block_of(
        c.for_safe(SECOND + IDX_SGN, work, c.inc_pos(diff_work)),
        c.for_safe(TOP + IDX_SGN, work, c.dec_pos(diff_work)),
        c.inc_pos(same_flag),
        c.if_nz_then(diff_work, c.dec_pos(same_flag) + _sub_abs()),
        c.if_nz_then(same_flag, _add_abs()),
        drop()
    )


def sub_decimal() -> str:
    "固定小数点小数の減算"
    # 符号を反転して加算(A-B => A+(-B))
    plus_flag = NOW + IDX_DMY
    return c.block_of(
        c.inc_pos(plus_flag),
        c.if_one_then(TOP + IDX_SGN, c.dec_pos(plus_flag)),
        c.if_one_then(plus_flag, c.inc_pos(TOP + IDX_SGN)),
        add_decimal()
    )


def _multi_decimal_abs() -> str:
    "3byte固定小数点の絶対値の乗算"
    # 整数部と小数部は筆算と同様に、byte単位で計算する
    #             A1. A2
    #           x B1. B2
    # ---------------------
    #               .A1xB2 A2xB2
    #       +  A1xB1.A2xB1
    # ----------------------
    #            R1 .  R2    R3
    #          <---------> 必要な範囲
    idx_a1 = SECOND + IDX_INT
    idx_a2 = SECOND + IDX_DEC
    idx_b1 = TOP + IDX_INT
    idx_b2 = TOP + IDX_DEC
    idx_r1 = NOW + IDX_INT
    idx_r2 = NOW + IDX_DEC
    idx_r3 = NOW + IDX_DEC + 1

    # 繰り上がり処理の関係で、上の桁から計算する
    return c.block_of(
        c.multi_data_tricky(idx_a1, idx_b1, idx_r1, 1),  # AxC (1byte 分)
        c.multi_data_tricky(idx_a1, idx_b2, idx_r2, 2),  # AxD (繰り上げ含め2byte)
        c.multi_data_tricky(idx_a2, idx_b1, idx_r2, 2),  # BxC (繰り上げ含め2byte)
        c.multi_data_tricky(idx_a2, idx_b2, idx_r3, 3),  # BxD (繰り上げ含め3byte)
        c.clear_pos(idx_r3),  # R3 は繰り上げ分のみが必要なのでクリア
    )


def _xor_sign() -> str:
    # 符号は同じなら＋、異なるならマイナス
    idx_as = SECOND + IDX_SGN
    idx_bs = TOP + IDX_SGN
    idx_rs = NOW + IDX_SGN
    sign_work = NEXT
    return c.block_of(
        c.for_loop(idx_as, c.inc_pos(sign_work)),
        c.for_loop(idx_bs, c.dec_pos(sign_work)),
        c.if_nz_then(sign_work, c.inc_pos(idx_rs))
    )


def multi_decimal() -> str:
    "3byte固定小数点の乗算"
    # A * B => R
    return c.block_of(
        _multi_decimal_abs(),  # R の絶対値を求める
        _xor_sign(),  # R の符号を求める
        c.move_ptr(NEXT),  # スタックの状態は {A, B, R}
        override(2),  # R を A の位置に上書き
        drop()  # B を削除
    )


def if_lt_decimal(then_statement: str, else_statement: str = "") -> str:
    return c.block_of(
        swap(1),  # {A, B} -> {B, A} の順にする. then/else実行時のスタック数を変えないため
        dup(1),  # {B, A, B}
        sub_decimal(),  # {B, R (= A - B)}
        # R が負数なら A < B
        if_negative_decimal(then_statement, else_statement),
        drop()  # drop B
    )


def if_ge_decimal(then_statement: str, else_statement: str = "") -> str:
    return if_lt_decimal(else_statement, then_statement)


def if_gt_decimal(then_statement: str, else_statement: str = "") -> str:
    return c.block_of(
        swap(1),
        if_lt_decimal(then_statement, else_statement)
    )


def if_le_decimal(then_statement: str, else_statement: str = "") -> str:
    return if_gt_decimal(else_statement, then_statement)
```

一か所手抜きをしていて、0 が `+0.0` と `-0.0` の二種類存在しています。
そのため `if_negative_decimal` で `-0.0` を負数と判断してしまいます。

実は、マンデルブロ集合の発散の判定でこの機能を使っているので、たまに間違えて判定しているかもしれません。
ま、誤差の範囲内ですよね？

### 文字出力系のマクロ

1文字出力と、（頭悪そうな）文字列出力マクロです。

```python
def put_char() -> str:
    "スタック先頭の1byte(1文字)を出力"
    return c.block_of(
        c.exec_pos(TOP, "."),
        drop()
    )


def put_str(message: str) -> str:
    result = c.clear_pos(NOW)
    for ch in message:
        result += c.init_value(NOW, ord(ch))
        # TODO ↑前の値との差分のほうが短いかどうかチェックしたほうが良い
        result += c.exec_pos(NOW, ".")
        result += c.clear_pos(NOW)
    return c.delete_useless(result)
```

## マンデルブロ集合を描画

ようやく本題です。

マンデルブロ集合の詳細は、以下を参照。

* wikipedia [マンデルブロ集合](https://ja.wikipedia.org/wiki/%E3%83%9E%E3%83%B3%E3%83%87%E3%83%AB%E3%83%96%E3%83%AD%E9%9B%86%E5%90%88)

仮に C 言語で書くとしたらこんな感じでしょうか？

```c
#include <stdio.h>

#define X_BEGIN -2.0
#define X_END 1.0
#define Y_BEGIN -0.9375
#define Y_END 0.9375

// 繰り返し回数
#define C_MAX 26
// 発散するしきい値(2.0 の2乗値)
#define THRESHOLD2 4

void main(void)
{
    int columns = 128;
    int rows = 40;
    // X軸の加算値
    float x_step = (X_END - X_BEGIN) / (columns - 1);
    // Y軸の加算値
    float y_step = (Y_END - Y_BEGIN) / (rows - 1);

    float y0 = Y_BEGIN;
    for (int y = 0; y < rows; y++)
    {
        float x0 = X_BEGIN;
        for (int x = 0; x < columns; x++)
        {
            float cx = x0;
            float cy = y0;
            float zx = 0;
            float zy = 0;
            char ch = ' ';
            char count = 'A' - 1;
            for (int c = 0; c < C_MAX; c++)
            {
                float zx2 = zx * zx;
                float zy2 = zy * zy;
                float size2 = zx2 + zy2;

                if (size2 > 4.0)
                {
                    // 発散
                    ch = count;
                    break;
                }
                else
                {
                    float zx_next = zx2 - zy2 + cx;
                    float zy_next = zx * zy * 2 + cy;
                    if (zx_next == zx && zy_next == zy)
                    {
                        // 収束
                        break;
                    }
                    else
                    {
                        zx = zx_next;
                        zy = zy_next;
                        count++;
                    }
                }
            }
            putchar(ch);
            x0 += x_step;
        }
        putchar('\n');
        y0 += y_step;
    }
}
```

小数は `float` でいいのかとか、 `float` 同士の比較を `==` でやるなとか、ほかにもいろいろ指摘がある気がしますが、とりあえず置いておくとして。

できるだけ、Brainf*ck で書きやすくするため、複素数の絶対値が `2.0` を超えているかの判定は、`sqrt` を使わず二乗された値をそのまま `4.0` を超えているかの判定に置き換えています。

これを Brainf*ck で書いてみます。

ちなみに、スタック系マクロは `bf_stack.py` に保存してある想定です。

```python
import bf_core as c
import bf_stack as s


# X軸の範囲
(X_BEGIN, X_END) = (-2.0, 1.0)
# Y軸の範囲
(Y_BEGIN, Y_END) = (-0.9375, 0.9375)

# 繰り返し回数
C_MAX = 26
# 発散するしきい値(2.0 の2乗値)
THRESHOLD2 = 4


def mandelbrot(columns: int, rows: int) -> str:
    # X軸の加算値
    x_step = (X_END - X_BEGIN) / (columns - 1)
    # Y軸の加算値
    y_step = (Y_END - Y_BEGIN) / (rows - 1)

    return c.program_of(

        # #0: y0 = y_begin
        s.push_decimal(Y_BEGIN),

        # #1: y = rows
        s.push_byte(rows),
        s.loop_of(  # for(y)

            # #2: x0 = x_begin
            s.push_decimal(X_BEGIN),

            # #3: x = columns
            s.push_byte(columns),
            s.loop_of(  # for(x)

                s.dup(1),  # #4: cx = x0
                s.dup(4),  # #5: cy = y0
                s.push_decimal(0),  # #6: zx = 0
                s.push_decimal(0),  # #7: zy = 0
                s.push_byte(ord(" ")),  # #8: ch = ' '
                s.push_byte(ord("A") - 1),  # #9: count = 'A'-1

                s.push_byte(C_MAX),  # #10: c = 26
                s.loop_of(  # for(c)

                    # #11: zx2 = zx * zx
                    s.dup(4),
                    s.dup(0),
                    s.multi_decimal(),

                    # #12: zy2 = zy * zy
                    s.dup(4),
                    s.dup(0),
                    s.multi_decimal(),

                    # #13: size2 = zx2 + zy2
                    s.dup(1),
                    s.dup(1),
                    s.add_decimal(),

                    # #14: THRESHOLD2
                    s.push_decimal(THRESHOLD2),
                    # if size2 > 4.0
                    s.if_gt_decimal(
                        then_statement=c.block_of(
                            # 発散

                            # ch = count
                            s.dup(5),  # #15
                            s.override(7),

                            # for_c break
                            s.loop_last(4)
                        ),
                        else_statement=c.block_of(
                            # #15: zx_next = zx2 - zy2 + cx
                            s.dup(3),
                            s.dup(3),
                            s.sub_decimal(),
                            s.dup(11),
                            s.add_decimal(),

                            # #16: zy_next = zx * zy * 2 + cy
                            s.dup(9),
                            s.dup(9),
                            s.multi_decimal(),
                            s.dup(0),
                            s.add_decimal(),
                            s.dup(11),
                            s.add_decimal(),

                            # #17: if zx_next == zx && zy_next == zy
                            s.dup(1),  # zx_next
                            s.dup(11),  # zx
                            s.sub_decimal(),
                            # #17: 0(zx_next == zx) or 1(zx_next != zx)
                            s.if_nz_decimal(
                                s.push_byte(1) + s.swap(1),
                                s.push_byte(0) + s.swap(1)),
                            s.dup(1),  # zy_next
                            s.dup(11),  # zy
                            s.sub_decimal(),
                            # #18: 0(zx_next == zx) or 1(zx_next != zx)
                            s.if_nz_decimal(
                                s.push_byte(1) + s.swap(1),
                                s.push_byte(0) + s.swap(1)),
                            # #17: 0(zx_next == zx && zy_next == zy) or other
                            s.add_byte(),
                            s.if_z(
                                then_statement=c.block_of(
                                    # 収束
                                    s.swap(1),
                                    s.drop(),  # drop zy_next
                                    s.swap(1),
                                    s.drop(),  # drop zx_next
                                    s.loop_last(5)  # last c
                                ),
                                else_statement=c.block_of(
                                    # zx = zx_next
                                    s.swap(1),
                                    s.override(10),

                                    # zy = zy_next
                                    s.swap(1),
                                    s.override(10),

                                    # count += 1
                                    s.dup(6),
                                    s.push_byte(1),
                                    s.add_byte(),
                                    s.override(7)
                                )
                            )
                        )
                    ),
                    s.drop() * 2  # drop zy2, zx2
                ),
                s.drop(),  # drop count
                s.put_char(),  # putchar(ch)
                s.drop() * 4,  # drop zy, zx, cy, cx

                # #4: x0 += x_step
                s.dup(1),
                s.push_decimal(x_step),
                s.add_decimal(),
                s.override(2)
            ),
            # drop x0
            s.drop(),

            # #2: putchar("\n")
            s.push_byte(ord("\n")),
            s.put_char(),

            # #2: y0 += y_step
            s.dup(1),
            s.push_decimal(y_step),
            s.add_decimal(),
            s.override(2)
        )
    )


if __name__ == '__main__':
    program = mandelbrot(128, 40)
    print(program)

```

実際にスタック処理のマクロを使ってみると、スタックの要素を示すのが相対位置で書かないといけないので、難しいですね。

ともかくこれを `mandelbrot.py` の名前で保存して実行します。

```shell-session
python3 -B mandelbrot.py > mandelbrot.bf
./bf2c -F mandelbrot.bf
gcc -O2 -o mandelbrot mandelbrot.c
./mandelbrot
```

コンパイルはすぐに終わると思いますが、実行には大体 5～7 秒ぐらいかかります。遅い。

ちなみに、一般的な Brainf*ck コンパイラでも普通にコンパイルできるんじゃないかと思いますが、できるだけ最適化が効くコンパイラを使ってください。

また、Brainf*ckインタプリタではかなり時間がかかるんじゃないかと思います。最低でも、最適化が効くインタプリタを使ったほうが良いと思います。

![mandelbrot](https://raw.githubusercontent.com/wiki/yoshi389111/brainfuck-compiler-c/images/mandelbrot.gif)

[有名な Brainf*ck でのマンデルブロ集合の実装](https://github.com/pablojorge/brainfuck/tree/master/programs) がありますが、それだと 1～2 秒で終わるので、まだまだ改良の余地はありそうですね。


### マンデルブロ集合に色付け

正確に言えば、マンデルブロ集合は発散しない複素数の集合のため、結果の黒い部分こそがマンデルブロ集合です。

が、一般的なマンデルブロ集合の描画アプリにならい、発散するまでの回数に応じて色を付けてみます。

ソースは単純なので省略（コンパイラの sample として、github には登録済）。
ANSI エスケープシーケンスの使える端末で動かすと色がつくと思います。

![mandelbrot(color)](https://raw.githubusercontent.com/wiki/yoshi389111/brainfuck-compiler-c/images/mandelbrot_color.gif)

### 応用

あとはちょっと修正するだけで、ジュリア集合なども描けますね。

![julia(color)](https://raw.githubusercontent.com/wiki/yoshi389111/brainfuck-compiler-c/images/julia_color.gif)