Brainfuck開発日誌2：メモリ管理、変数、フロー制御を改善する

Brainfuckのプログラミングをより効率的にするために、メモリ管理、変数、フロー制御の抽象化レイヤーを構築する方法を探求します。この記事では、これらの機能を追加することで、Brainfuckプログラミングがどのように簡素化され、より直感的になるかを見ていきます。

ランダムメモリアクセス：ポインタ操作からの解放

Brainfuckのポインタ操作は煩雑です。>と<だけでメモリを移動するため、目標のセルに到達するまでのステップ数を手動で計算する必要があります。

そこで、コンパイル時にポインタを追跡します。仮想ポインタを導入し、>や<の出現時に更新することで、現在位置からのオフセットを計算し、任意のメモリ位置へ直接移動できるようになりました。

これにより、コマンドのインターフェースがより直感的になります。

cmd.Add(0, 20) // バイト0に20を加算
cmd.Add(1, 28) // バイト1に28を加算
cmd.AddCell(0, 1, 2) // バイト0をバイト1に加算 (2をバッファとして使用)

ポインタの移動を意識する必要がなくなり、Goの変数を利用することで、コードがさらに明確になります。

予約されたメモリエリア：安全な内部処理

AddCellやCopyのようなコマンドは、内部処理に追加のメモリを必要とします。そこで、一時的な変数用の領域を事前に予約します。

const (
	TEMP0 = 0
	TEMP1 = 1
	TEMP2 = 2
	NIL   = 6 // 常に0
	MAIN  = 7 // ユーザメモリの開始地点
)

これにより、Copyコマンドのインターフェースが簡素化され、ユーザーは予約されたメモリ領域を上書きしないように注意するだけでよくなります。

ループの再考：正確なポインタ追跡の必要性

コンパイル時のポインタ追跡は、一見うまく機能しているように見えますが、ループ処理を含むコードでは問題が発生する可能性があります。ループ内でポインタが進むたびに、最終的なポインタの位置は正確に予測できません。

しかし、詳しく調べてみると、ループが開始位置と終了位置が同じであれば、仮想ポインタは正しく機能することが分かりました。つまり、ループの条件となるセルの値によって処理を継続するかどうかを決める場合、ポインタは常に開始位置に戻るため、ループの反復回数に関係なく安全に処理できます。

この特性を活かし、自作の言語ではルールを強制することで、ループ開始時と終了時のセルが同じになることを保証します。

// ループ開始位置と終了位置が同じセルであることを保証する
func (c *CommandHandler) While(condition int, code func()) {
	c.movePointer(condition)
	c.beginLoop()
	code()
	c.goTo(condition)
	c.endLoop()
}

このWhileの実装は、簡潔ながら、phantom pointerの利用および既存コマンドの安全な利用をループ内で可能にします。

条件分岐：if文の実装

Brainfuckには直接的な条件分岐の仕組みはありませんが、一度しか実行されないループを利用することでif文をシミュレートできます。

func (c *CommandHandler) If(cond int, code func()) {
	c.Copy(cond, TEMP1)
	c.While(TEMP1, func() {
		code()
		c.Reset(TEMP1)
	})
}

条件をコピーし、そのコピーをWhileループの条件として使用することで、コードを一度だけ実行することができます。

変数：メモリ管理を抽象化

メモリ位置を直接扱う代わりに、変数を使用することで、メモリ管理がより抽象化されます。Env構造体を使用して、変数名とメモリ位置のマッピングを管理します。

type MindfuckEnv struct {
	variables     map[string]int // ラベルと位置のマッピング
	reservedMemory common.ItemSet // 現在使用中の位置
	freedMemory    []int           // 解放された位置
}

使用済みメモリと解放済みメモリを追跡することで、メモリの再利用を最適化し、メモリ消費量を抑えることができます。これにより、コードはさらに明確になり、保守が容易になります。

変数の改善：名前空間の衝突を回避

予約語のような変数名を使用できないという問題を解決するために、Variableインターフェースを定義し、名前付き変数と匿名変数の2つの実装を作成しました。

type Variable interface {
	Position() int
	hasLabel() bool
	label() string
}

これにより、ユーザーは自由に変数名を宣言でき、内部コマンドは匿名変数を使用することで、名前空間の衝突を回避できます。

まとめ

この記事では、Brainfuckプログラミングをより扱いやすく、より直感的にするためのさまざまな改善点を紹介しました。メモリ管理の自動化、変数の導入、フロー制御の抽象化により、Brainfuckはより強力なプログラミングツールへと進化しました。

次は、antlr4を使用してASTやパーサーを構築し、これらを組み合わせる方法を説明します。