コンパイラを書こう

もうホント、使いづらいんで、このブログでプログラミングの話したくねぇんだけど。

どーしても気になるネタがあったんで、苦しみながら書こうと思います。

一般的に、コンパイラ、と言うと、「高級言語のソースコードをマシン語に翻訳するソフトウェアだ」と思われています(ホントはマシン語じゃなくって殆どはアセンブリ言語へ、なんですけどね)。

しかし、現実的には、「ある言語Aを別の言語Bに一括翻訳するソフトウェア」を全部コンパイラ、と言います。人によってはこれを「トランスレータ」と呼んだりもするんですが、現行、マシン語レベルの上にガンガンレイヤーが積み上がっていて、そこで作業するのがフツーになってる以上、トランスレータとコンパイラって厳密な区別が既に無いんですよ。僕らは既に、CPUやメモリを直接弄る場所でフツーは作業してないのです。色んなレイヤーが最下層から重なってて、ドブに手足突っ込まなくて良くなってる、ってのが今のPCの状態なんですね。我々は下水じゃない比較的綺麗な大地の上に立っている。

しかもコンパイラって実は、通常で言う分でのソフトウェアでもない。コンパイラはREPLを持ってないんで、むしろスクリプトに近いんですよね。まぁ、スクリプトもソフトウェアの1つではあるんだけど、場合によっては、インタプリタよりも書くのが面倒くさくない可能性がある。一々ユーザーに入力を促さなくって良くって、一回何らかの入力があったら、即実行、そして終了。エラーがあったら警告出して終了。おしまい。インタプリタに比べるとユーザーとのやり取りに「気を使わんで済む」のです。

と言うわけで、ネタとして、「世界で一番実装が簡単なプログラミング言語のコンパイラ」を書いてみたいと思います。もっとも、「世界で一番実装が簡単なプログラミング言語」だけど読むのは大変。ご存知ですか?はい、そうです、「難読プログラミング言語」として有名な、Brainfuckのコンパイラを実装してみましょう。

Brainfuckの詳細はWikipediaに書いていますね。一応、ここにもどういう言語なのか、その仕様を書き写してみましょうか。

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

仕様はたったこの8つです。素晴らしいですね!

じゃあ、何の言語でこのBrainfuckのコンパイラを書いてみましょうか。

はい、例によってLispで書いてみたいと思います。なんつったって書くのが結果ラク。たった60行前後、2つの関数をでっち上げればBrainfuckのコンパイラが書けちゃうんだからLispって素敵♡これぞLispのパワーなんじゃないか、と言う良い証明になるかも。別にならんでもエエんですが(笑)。

そしてコンパイル対象の言語もLispです。言い換えればこのBrainfuckコンパイラはBrainfuck -> Lispのトランスレータですね。一旦このコンパイラでBrainfuckのソースコードをコンパイルすればLispで動かせる、と。まぁ、そういう誰得な試みです。

なお、ここでも使用するLispはRacketとします。

では。

まずは手っ取り早く、完成版のソースコードをお見せしましょう。こんなカンジです。

brainfuck.rkt

それを眺めてから解説に入っていきましょう。

ところで、Wikipediaにも書いていますが、Brainfuckの言外の仕様では、Brainfuckのメモリに付いての要請は次のようになっています。

少なくとも30000個の要素を持つバイトの配列（各要素はゼロで初期化される）

まあ、通常、配列は適当な大きさで最初に宣言してたりしなきゃいけないんで、しょーがないわけですが。

でもLispにはリストがある。リストは可変長なんで、「大きさ」を最初に考えなくて良い。また、別に要素がバイトでなくても良いわけです。これでまずは俄然実装が簡単になりますね。

例えば、Brainfuckで、初期値としてメモリの0番地をポインタが指してる場合、Lispでは単に、

'(0)

とリストで表現が可能です。じゃあ、この状態からポインタを1番地を指し示すようにする場合どうすれば良いのか?

長さが1のリストなんで、単に0をcons(コンストラクタの略)すれば良くなる。そうすればメモリとして抽象化されたリストは

'(0 0)

になります。

実際、このバージョンで考えてるのは、「Lispでメモリを如何に組み上げていくのか」に着眼してるんで、実は大してポインタ自体は・・・まぁ、仕様にもあるんで、必需なんですけど、重要ではない、って事ですかね。

ではBrainfuckの実装を通じて仕様の詳細を見ていきます。

> ポインタをインクリメントする。ポインタをptrとすると、C言語の「ptr++;」に相当する。

さて、まずはこいつを実装してみます。

Racketでここではこいつはこう書きます。

(define (inc-ptr k lst)
　(let ((n (+ k 1)))
　　(if (> n (length lst))
　　　(cons 0 lst)
　　　lst)))

関数inc-ptrはポインタkとメモリlstを受け取ります。

ポインタが指す位置が現在のメモリ、lstより大きければメモリに0をconsして返す。そうじゃなかったら単にメモリを返すだけ、です。簡単ですね。

< ポインタをデクリメントする。C言語の「ptr--;」に相当。

こいつはここでは、Racketではこう書きます。

(define (dec-ptr k lst)
　lst)

ここではこいつ、関数dec-ptrは事実上「何もしない」関数です。何故なら、ポインタをデクリメントしたトコで、メモリ自体が破壊されたり破棄されたりするわけじゃないですからねぇ。よって今あるメモリをそのまま返せば良い。

「え、こんなんで上手く動くの?」って思うかもしれませんが、動きます。さっきも書きましたが、このBrainfuckコンパイラは「メモリを組み上げる」のが目的なんで、メモリを壊したりする事はやらなくても大丈夫なのです。

ちなみに、引数を受けても使わないとC言語辺りだとWarningで文句言ってくるんで腹立つんですけどね(笑)。Racketは文句言わないんでカワイイヤツですよ。

+ ポインタが指す値をインクリメントする。C言語の「(*ptr)++;」に相当。

さてちょっとここで注意事項。

例えばここで次のようにリストで表現されたメモリがあるとします。

'(0 1 2 3)

通常、メモリの番地は左から0、1、2、...って並んでいくんですが。

ここではLispのリストをinc-ptr、もっと言うとLispの基本関数cons(コンストラクタ: リストの先頭に要素を追加する)で作っていってるんで、一番右が0番地、その左隣が1番地、....とBrainfuckや他のメモリの表現と真逆に並んでるんですね。

つまり、Brainfuckの仕様上、k番地、と指定された場合、Lispの内部表現的には(- (length lst) k 1)番地、に変換されないとならないのです(リストの長さ - k - 1、の意)。

これ忘れるとハマるんですよ(笑)。実際ハマってましたし(笑)。自分で設計したのにしょーがねぇよなぁ。

さて、ここで拡張ライブラリ、SRFI-1の関数、split-atを使います。

split-atは任意のリストを任意の位置で2つに分割します。

(split-at '(a b c d e f g h) 3) =>
　(a b c)
　(d e f g h)

これは多値関数と言われるヤツなんですが、そこは取り敢えず置いておいて、メモリを受け取ってそいつを二分割して、後半の先頭をすげ替えて、2つに分割されたリストをくっつけて返す、と。

そうすれば仕様の要求を満たせます。

(define (inc-val k lst)
　(let ((n (- (length lst) k 1)))
　　(let-values (((head tail) (split-at lst n)))
　　　(let ((val (+ (car tail) 1)))
　　　　(append head (cons val (cdr tail)))))

今までに書いたコードより若干長くなってますが、大きな理由はさっき書いた通り、split-at関数が多値関数なんで、それを受ける機構(let-values)が必要な事。ただし、それらが必要なのは、メモリの破壊的変更を避けて「新しいメモリを生成する」前提で書いてるコードだから、です。この形式で書くと「ポインタが指定したメモリに＋1に変更する」んじゃなくって「ポインタが指定したメモリを+1したものとすげ替えて新しくメモリを生成する」事になります。

要するに、ここがいわゆる「関数型プログラミング」ですね。

- ポインタが指す値をデクリメントする。C言語の「(*ptr)--;」に相当。

これは上と似たような関数ですね。次のように書きます。

(define (dec-val k lst)
　(let ((n (- (length lst) k 1)))
　　(let-values (((head tail) (split-at lst n)))
　　　(let ((val (- (car tail) 1)))
　　　　(append head (cons val (cdr tail)))))))

これでオシマイ。ここでも破壊的変更は避けています。

. ポインタが指す値を出力に書き出す。C言語の「putchar(*ptr);」に相当。

ここでも「ポインタが指す値」をリストの向きを考慮して変換しつつ、次のような関数を書きます。

(define (putchar k lst)
　(let ((n (- (length lst) k 1)))
　　(display (integer->char (list-ref lst n)))
　　lst))

関数integer->charはRacketの、と言うよりSchemeの組み込み関数で、整数を文字に変換してくれる関数です。list-ref(erence)はその名の通り、リストの任意の位置の値を返してくれる関数で、ここでは、メモリからポインタ(を変換した値)の位置が示す値を出力してくれます。displayはRacket/Schemeの基本出力関数ですね。

返り値であるメモリ、lstを返すのを忘れないように。

, 入力から1バイト読み込んで、ポインタが指す先に代入する。C言語の「*ptr=getchar();」に相当。

これはRacketで、次のように書きます。

(define (getchar k lst)
　(let ((n (- (length lst) k 1)))
　　(let-values (((head tail) (split-at lst n)))

　　　(append head (cons (char->integer (read-char)) (cdr tail))))))

これは今まで書いてきたような関数の合わせ技ですね。「メモリに読み込んだ値を書き込んで書き換える」んじゃなくって、「メモリを読み込んだ値ですげ替えて生成する」。非破壊的変更ですね。

なお、char->integerは文字を整数に変換し、read-charはそれこそC言語で言うgetcharみたいな機能を持った関数です。

さて、ここで一休み。

と言うのも、ここまで6つ関数を定義して、Brainfuckの基本的な実装の3/4は完成してるわけですが・・・こいつらはコンピュータ科学用語ではまさしく(Brainfuck内での)「手続き」ですが、残り2つは「制御機構」です。よって残りはLisp関数としては実装出来ません。コンパイラ(自体は関数として定義するにせよ)本体の方で制御せんといかんのです(一般的には、「制御機構」は関数とは役割が違うんで、単なる関数としては実装出来ない)。

ここまでLispプログラムを書いてきたんですが、ちょっと俯瞰像を見てみましょう。

例えば次のようなBrainfuckのコードがあるとします。

++++++++++

Brainfuckのコードで表現された「10」です。

これは上で定義された関数を使うと次のように表現出来ます。

(inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 '(0)))))))))))

人間、ましてやLisperならこういうバカなコードを直書きする事はありません(笑)。しかし、Lispインタプリタ、事実上今使うべき仮想マシンはそれを気にしません。これで目的は達成してるし、Racketインタプリタは問題無くこいつを解釈して実行します。

今、BrainfuckのコードからRacketのコードへとトランスレートするコンパイラを書くとして、生成すべきコードは上のような「非人間的な」コードです。これで充分。

そしてこいつの実行結果は、

'(10)

になるでしょう。ポインタをインクリメントするわけでもなし、ディクリメントするわけでもなく、場所はメモリの0番地、そこに10が保持されていれば成功です。Brainfuckが意図したコードはLisp(のリスト)としてキチンと表現されている。

また、例えばRacketインタプリタ上で、

(define *mem* '(0))

と*mem*を定義して、(inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 (inc-val 0 *mem*))))))))))を走らせてみるとしましょう。返り値は当然'(10)なんですが、じゃあ実行後の*mem*の値はどうなるか?

> *mem*
'(0)
>

はい、全く変わってないですね。何故ならinc-valを非破壊的関数として定義したから、です。大域変数を利用したとしても、その値自体を変更する事がない。いわゆる「関数型プログラミング」になっています。

関数型プログラミングはフィルタのように働きますが、返り値は常に「新規生成された」何か、です。そしてその返り値を引数として別の関数に手渡してまた同じように「新規生成した何か」を返してもらう。そうやって返り値の連鎖を利用してプログラミングしていくんで、大本のデータを書き換える必要がないのです。

このBrainfuckコンパイラはこのように、引数と返り値だけを利用して作っていくのを前提としているのです。

さて、制御機構を作る前に、コンパイラの雛形を書いてみましょう。コンパイラは通常、ソースファイルを受け取り、何らかのファイルを吐き出すので、それに合わせるとまずは、

Brainfuckで書かれたソースファイルを受け取り、Lispで書かれたソースファイルを吐き出す

仕様が必要だ、と言う事です。当然、吐き出された方のファイルは、Lispで書かれているんですが、同時に、それはテキストファイルでないとならない、と言う事です。

「えー、テキストファイルを吐き出すの?それってコンパイラって言えるの?」

って人もいるたぁ思いますが、そういう人がこれを「コンパイラじゃなくってトランスレータだ」とか言うんですよね。その辺はその人の好み。

実際は、例えば良くあるCのコンパイラでも吐き出してるブツはテキストファイルだったりするんですよね。え?って思うかもしれないですが、はい、アセンブリ言語のテキストファイルです。

正確に言うと、テキストファイルと言う実体か、と言うと必ずしもそうではないんですが、いずれにせよ、一旦テキストとしてアセンブリを吐き出して、アセンブラがそいつを実行形式にアセンブルしています。つまり、最低でも2段階で作業してる。Clangなんて言う処理系だと、仮想マシン用に一旦バイトコンパイルしてからそれをアセンブリに変えて、最後にアセンブラが実行形式に落とす、と言う、最低でも3段階作業を行っています(一見、作業数は多いんですが、その方が効率的な実行形式に落とせる、と言う研究論文があるそうです)。

いずれにせよ、「いきなりマシン語に翻訳する」とか言うコンパイラって現在ではそうそうないんですよ。それが現在のPCでの環境の殆どで、それが「レイヤーがたくさん重なっている」と言う意味です。

ここでは仮想マシンとしてRacketインタプリタを利用するので、Lispコードへとコンパイル出来ればそれで充分だし、それを実行形式にする、とかバイトコードへ落とす、ってのはRacketインタプリタの役目なんで、と割り切っていきます。

それで、Lispコードをテキストファイルとして吐き出すとして、当然書かれた内容は文字列になるわけですが。

実は今まで書いてた関数はコンパイラ本体では全く利用しません(笑)。何故か、と言うとこいつらを利用するのは「吐き出されたLispファイルに書かれたLispコードだから」ですよね。つまり、吐き出されたLispファイル側にこいつらが定義されていないと、生成されたLispコードが実行が出来ないから、です。言い換えると、当然吐き出したLispファイルは仮想マシンであるLispインタプリタで実行されるので、関数定義がされていないとエラーを起こすのは当たり前、って話になります。

いずれにせよ、今まで書かれてたLisp関数は、全部文字列としてコンパイラに埋め込まれます。まあ、実際は文字列に変換する必要はないんですが、その話をする前に、コンパイラのコードをまずはお見せしましょう。

(define (compile file0 file1)
　(with-input-from-file file0
　　(lambda ()
　　　(with-output-to-file file1
　　　　(lambda ()
　　　　　(for-each display
　　　　　　`("#!/usr/bin/env racket\n"
　　　　　　　"#lang racket\n"
　　　　　　　(require srfi/1)
　　　　　　　"\n"
　　　　　　　(define (inc-ptr k lst)
　　　　　　　　(let ((n (+ k 1)))
　　　　　　　　(if (> n (length lst))
　　　　　　　　　(cons 0 lst)
　　　　　　　　　lst)))
　　　　　　　"\n"
　　　　　　　(define (dec-ptr k lst)
　　　　　　　　lst)
　　　　　　　"\n"
　　　　　　　(define (inc-val k lst)
　　　　　　　　(let ((n (- (length lst) k 1)))
　　　　　　　　　(let-values (((head tail) (split-at lst n)))
　　　　　　　　　　(let ((val (+ (car tail) 1)))
　　　　　　　　　　　(append head (cons val (cdr tail)))))))
　　　　　　　"\n"
　　　　　　　(define (dec-val k lst)
　　　　　　　　(let ((n (- (length lst) k 1)))
　　　　　　　　　(let-values (((head tail) (split-at lst n)))
　　　　　　　　　　(let ((val (- (car tail) 1)))
　　　　　　　　　　　(append head (cons val (cdr tail)))))))
　　　　　　　"\n"
　　　　　　　(define (putchar k lst)
　　　　　　　　(let ((n (- (length lst) k 1)))
　　　　　　　　　(display (integer->char (list-ref lst n)))
　　　　　　　　　lst))
　　　　　　　"\n"
　　　　　　　(define (getchar k lst)
　　　　　　　　(let ((n (- (length lst) k 1)))
　　　　　　　　　(let-values (((head tail) (split-at lst n)))
　　　　　　　　　　(append head (cons (char->integer (read-char)) (cdr tail))))))
　　　　　　　"\n"
　　　　　　　,(brainfuck 0 ''(0) (read-char)))
　　　　　　))))))

まずは、Lisp、と言うかSchemeのファイル入出力関数から。

ここではwith-input-from-fileと言う入力関数とwith-output-to-fileと言う出力関数を用いています。が、こいつらは名前が長いし、使い方がちとややこしいんで、ここで細かい説明はしません。このページに良くまとまった説明があるんで、それを見て下さい。いずれにせよ、入力対象のfile0を開き、出力対象のfile1を生成してそれにリストを書き込んでいく。

関数for-eachはマッピング関数で、第一引数を後続のリストの要素に順次適用していきます。そしてその第一引数は返り値を持たない関数、つまり手続きです。ここで使われてる関数displayは表示用関数ですが、返り値を持ちません。

また、通常displayは表示用関数ですが、ここではwith-out-to-fileでファイル用の出力ポートを開いているので、こいつがファイルに後続のリストの要素を順次書き出していきます。なかなかに便利な組み合わせです。

さて、生成しているリスト。改行文字もぶち込んでいますが、第一引数と第二引数を除き、必須ではないです。単に生成したファイルを見やすくするためだけに存在しますね。

リストの第0引数と第1引数はLinux用のシェバングとRacketで使用する基本言語モジュールを指定する為にあるオマジナイです。Windowsの場合は第0引数は必要ないです。そして第2引数として、拡張ライブラリSRFI-1の読み込みが続き、その後、先程定義した関数群の定義を書き込んでいってます。

このリストの大きな特徴は準クオート(quasiquote: `)と呼ばれる記号によって生成されてる事です。これは言わば「穴あきリスト」を生成する為の記号で、これによって生成するリストは「一部分だけ」実行された結果をはめ込む事が出来る。具体的にはコンマ(,)以降のLispコードだけは実行されてリスト内に埋め込まれる。ここですね。

,(brainfuck 0 ''(0) (read-char)))

まだ関数brainfuckは書いてないですが、これがコンパイラの心臓部です。ここで心臓部を呼び出して、実行結果(つまりBrainfuckコードをLispコードに変換した結果)を埋め込みます。そうすれば完全で実行可能な変換済みのLispファイルが完成します。

関数brainfuckの第一引数はメモリアドレスへのポインタ、第二引数''(0)はメモリの0番地の初期値が0なので、それをリストで表現しています(クオートが二重なのは、コンマで一個クオートが解除されるので、最終的に'(0)の状態にしたいが為)。

関数read-charはwith-input-from-fileで開いた入力ポート(今はfile0、つまりBrainfuckのソースコード)から1文字読み込みます。これが関数brainfuckの最初の行動を表しています。

さて、これでコンパイラの概形は書き終えました。それではコンパイラの心臓部、brainfuckを書いていきます。

関数brainfuckは、制御構造を除き、まずは次のように書けます。

(define (brainfuck ptr memory c)
　(if (eof-object? c)
　　memory
　　(case c
　　　((#\>) (let ((ptr (+ ptr 1)))
　　　　(brainfuck ptr `(inc-ptr ,ptr ,memory) (read-char))))
　　　((#\<) (brainfuck (- ptr 1) `(dec-ptr ,(- ptr 1) ,memory) (read-char)))
　　　((#\+) (brainfuck ptr `(inc-val ,ptr ,memory) (read-char)))
　　　((#\-) (brainfuck ptr `(dec-val ,ptr ,memory) (read-char)))
　　　((#\.) (brainfuck ptr `(putchar ,ptr ,memory) (read-char)))
　　　((#\,) (brainfuck ptr `(getchar ,ptr ,memory) (read-char)))
　　　(else (brainfuck ptr memory (read-char))))))

関数brainfuckは先に見た通り、3引数の関数です。第一引数はポインタ、第二引数はメモリ(リスト)、第三引数はread-charをぶち込む為の場所、ですね。

全体は再帰関数として構成されていますが、まずは終了条件。関数read-charがファイル末端、つまりend-of-fileオブジェクトを読み込んだ時、生成したLispコード、つまりこの場合はmemoryですか、それを返します。

あとは、C言語のswitch文に当たるcase構文で、読み込んだ文字に従ってメモリを生成しながらbrainfuck自身を再帰呼び出ししていきます。#\と言うのは、Lispで「文字」を表す記号です。つまり、Brainfuckのソースコードから読み込んだ文字に従ってコードを生成していく。

ポイントとしては、ここでも、コード生成に対して準クオートを用いたリストを利用しています。関数名はここでは評価したくないんで、準クオートで評価を停止していますが、ポインタである引数(ptr)とメモリを表す引数(memory)は刻々と変化する情報として記録していきたいんで、コンマ(,)を使ってそれらだけは評価しています。

この状態だけで、例えば上で見せてたBrainfuckでの10を計算するコードをLispコードに変換してくれます。アレですね。

また、else以降はいわばデフォルト動作なんですが、Brainfuckは、仕様で定義された8文字以外は全てコメントとして無視されるので、「現在の状態のまま」brainfuckを再帰呼び出ししてそれらを凌いでいます。

さて、ここまでは簡単。ここからちょっとややこしい。制御構造ですね。

取り敢えず、Brainfuckの仕様に書かれてる事を引っこ抜いて来ますか。

[ ポインタが指す値が0なら、対応する ] の直後にジャンプする。C言語の「while(*ptr){」に相当。
] ポインタが指す値が0でないなら、対応する [ （の直後）にジャンプする。C言語の「}」に相当

うーむ、ぶっちゃけ、何書いてるんだかサッパリ分からん(苦笑)。

実は以前にも、コンパイラじゃなくってBrainfuckのインタプリタも書いた事あるんですが、いずれにせよ、この辺の制御構造を書くのは難しいですね。一発で綺麗に書けるアイディアを思いつかない。

単純に考えると、RacketやSchemeでの繰り返し構文を突っ込めば良いだけ、なんですが、これがなかなか、どう実装すれば上手く行くのか思いつかんかったです。

取り敢えず、Racket/Schemeの「繰り返し構文」を1つ紹介しましょう。Schemerには嫌われてるんですが(笑)、今回はdoと言う構文を用いてみます。

(do ((⟨variable1⟩ ⟨init1⟩ ⟨step1⟩)
　　...)
　　(⟨test⟩ ⟨expression⟩...)
　⟨command⟩...)

うーん、何書いてるかサッパリ分からんな(苦笑)。

ええと、例によって詳しくはこのページに譲りますが、いずれにせよ、

[ ポインタが指す値が0なら、対応する ] の直後にジャンプする。

なら、終了条件を明確に書けるdoが多分望ましいかな、ってそれだけで使うわけですが。いや、それって大事。紛れが無いですからね。

従って、<test>は次のようになります。

(zero? (list-ref memory (- (length memory) ,ptr 1)))

ポインタが指す値(従って実はLisp内部では変換された位置の値)が0の時に脱出する。

余談ですが、実は自分で設計しておきながら、すっかり「ポインタの値をそのまま使っちゃいけない(メモリが逆順の並びだから)」ってのを忘れてて(笑)、無限ループに陥って「原因は何だ?」って慌ててたのは秘密です(笑)。イカんな(苦笑)。

さて、繰り返しを実装するにあたって、ちょっと簡単な例を考えてみましょう。次のページから100を計算するBrainfuckコードを借りてきます。

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

繰り返しが一個入ってますね。

さて、[が出てくるまでは10を計算してるわけですが。実はここまでがdoの構文上、<init1>にあたる。つまり、繰り返しをする際の初期値になる。

`(do ((memory ,memory ⟨step1⟩)
　　...)
　　(
　(zero? (list-ref memory (- (length memory) ,ptr 1))) ⟨expression⟩...)
　⟨command⟩...)

まぁ、名前変えてもイイんですが、いずれにせよ、コンマが付いてないmemoryは変数名、コンマが付いてる,memoryは「doが出てくるまでに計算されてるメモリの結果」ですね。

そして次は<step1>を考える。100を計算するBrainfuckのコードで、繰り返しを無視すれば、そのまま進んで行って構わないわけです。

要は、<step1>の表す「更新」は、memoryにbrainfuckそのものを呼び出して適用する事。つまり、ここでやっぱり再帰呼び出しが必要となります。穴あきリストとして、ここに再帰結果を埋め込みます。

`(do ((memory ,memory ,(brainfuck ptr 'memory (read-char)))
　　...)
　　(
　(zero? (list-ref memory (- (length memory) ,ptr 1))) ⟨expression⟩...)
　⟨command⟩...)

埋め込まれたbrainfuck内部のmemoryがクオートされてる理由は、こいつが参照してるのはdo外部から渡されたmemoryではなく、do内部での変数名memoryを参照してるから、です。ややこしいんで、名前変えときゃ良かったな。

そして返り値である<expression>ですが、やっぱりmemoryを返せば良い。そして今回は副作用目的は何もないんで、<command>なんかも要らない。

従って、生成すべきdoを含んだテンプレートであるリストは次のようになります。

`(do ((memory ,memory ,(brainfuck ptr 'memory (read-char))))
　　((zero? (list-ref memory (- (length memory) ,ptr 1))) memory))

そして文字#\[に対応する条件節は全体的には次のようになりますね。

((#\[) (brainfuck ptr
　`(do ((memory ,memory ,(brainfuck ptr 'memory (read-char))))
　　　((zero? (list-ref memory (- (length memory) ,ptr 1))) memory))

　　(read-char)))

言わば再帰内再帰、ってのがこの制御構造(の半分)の特徴です。ポインタが指し示すメモリアドレスが0じゃない限り繰り返しをするテンプレートはこうやって生成出来る。

冷静に考えてみると、この部分の実装は結果、ある程度簡単ではあるんですが、問題は後半のこいつです。

] ポインタが指す値が0でないなら、対応する [ （の直後）にジャンプする。C言語の「}」に相当

どうすんべ、これ。#\[で殆ど繰り返しの実装は完了してるのに、#\]を読み込んだ時の、Cで言う"}"(と言うたった1文字・笑)を実装するためにはどんなコードを書けば良い・・・?

実はここで最大にハマってました(笑)。気づけば結果簡単なんですが、それを思いつくのが大変だった。

実際、適当に何か書いては生成されるLispコード(しかもコンパイラによって自動生成されたヤツなんで読みにくい・笑)を調べて行って・・・とかなり血なまぐさい事やってたんですね。

余談ですが、フツーにコンパイラ書いてる人たちも大変だと思いましたよ。何かバグあったら、吐き出されるアセンブリを読みながらバグの原因を追求していくわけでしょ(笑)?アセンブリ見たくないからコンパイラ開発してんのに、結果泥まみれでアセンブリと格闘せなアカン。こーゆー商売だけはしたくねぇよなぁ(笑)。低レベルの言語に関わり合いたくないんでLispなんてやってるワケですが、近い苦労をしてると「なんだこれ、俺は一体何やってんだ」とか思っちゃう(笑)。

んで、まぁ、色々と吐き出されたコードと格闘してたわけですが、結果何すりゃいいのか、は意外と簡単でした。最初にeof-object?での終了判定があったんですが、実は#\]も一種終了判定なんですよね。つまり、ここでは、再帰せずにmemoryをそのまま返せば良い。この時点でそれまでの「計算結果」がmemoryに詰め込まれてるんで、考えてみれば当然だったわけです。

従って、#\]での条件節は次のようになる。

((#\]) memory)

これ、多分まだピンと来てない人もいるでしょうが。要するに#\[で関数brainfuckの再帰呼び出し中にまたもやbrainfuckが呼び出されます。そしてBrainfuckのソースコードが内側に流れ込んでいくわけですが、#\]を見た時点で、memoryを持って内側のbrainfuckから計算が脱出するわけですね。その時の内側からの返り値であるmemoryは「今までの内側での計算結果」なわけですから、それがdoの<step1>にはめ込まれた時点で、それはdo内変数のmemoryの「更新情報」なわけです。・・・・・・難しい?

いや、多分落ち着いて考えてみれば分かるたぁ思うんですが・・・・・・。多分「血のしたたるような」生成されたコード(ワケワカメ)を見ればやってる事分かりますよ。多分。

100を計算するBrainfuckソースコードからはこんなLispコードが生成されています。

(inc-ptr 1

　(do ((memory (inc-val 0 ;; ここからdo内でのmemoryの初期条件 <init1>

　　　　　　　　(inc-val 0 ;; 実はこの部分の計算結果は10である

　　　　　　　　　(inc-val 0

　　　　　　　　　　　　　　　　(inc-val 0 (quote (0))))))))))))

　　　　　　　　(dec-ptr 0 ;; ここからdo内でのmemoryに対する更新手段

　　　　　　　　　(inc-val 1 ;; つまり<step1>であり、#\]の返り値である

　　　　　　　　　　(inc-val 1

　　　　　　　　　　　　　　　　　　　(inc-ptr 1

　　　　　　　　　　　　　　　　　　　　(dec-val 0 memory)))))))))))))))

　((zero? (list-ref memory (- (length memory) 0 1))) memory)))

一応、インデントとかしてみたけど、ヒデェなこれ(笑)。わはははは(笑)。

いや、こんな非人道的なLispコードでも、Racketは解釈して実行してくれるんだよなぁ。

'(100 0)

ヒデエ自動生成コードだけど結果はシンプル。メモリの0番地は0(つまり、ここが繰り返しの脱出フラグになっている)で、計算結果はキチンと100(1番地に格納)です。

凄いでしょ?凄い。「ヒデェコード」でもRacketはキチンと計算結果を返してくれる。コンパイラとして関数brainfuckはキチンと仕事してくれてるんですよ。偉いねぇ。

これでBrainfuckコンパイラは完成、です。お馴染みのHelloWorldプログラムのファイル(例えば"hello.bf")でも、読み込ませて下さい。コマンドは例えば、

(compile "hello.bf" "hello.rkt")

です。

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

なーんの実用性もないプログラミング言語、Brainfuckですが、端末上に「Hello, World!」って表示されたらそれなりに感動しますよ。