Befungeで遊ぶ - やっさんの雑記

今回は難解プログラミング言語の1つ、Befungeで遊んでみようと思います。
Befungeの言語仕様はwikipediaを見てもらえばいいと思いますが、大きな特徴はプログラムポインタがソースコード中を2次元的に動きまわることと、プログラム内の命令によって自分自身を書き換えられることでしょう。
ソースコードの大きさが無制限の場合はチューリング完全でC言語とかと同等のプログラミング能力を（理論上）持ちますが、今回は80桁25行に限定したのでチューリング完全というわけではありません。しかし、これだけでも結構書けるものです。

処理系

とりあえずまずは処理系を作ってみることにします。
命令の数が多くないので、そこまで大変ではありません（といっても4時間くらいかかりましたが）。
適当にJavaScriptで書いてみました。JSはあまり得意じゃないので汚いかもです。

var code = new Array(25);
var stack = new Array();
var x = 0;
var y = 0;

var direction = [[1, 0], [0, -1], [-1, 0], [0, 1]];
var dir = 0;
var skip = false;
var string = false;
var interval = 100;
var quit = false;

function escape(letter) {
    if (letter < 32 || letter >= 127) {
        return '&nbsp;';
    }
    switch (letter) {
        case '<'.charCodeAt(0):
            return '&lt;';
        case '>'.charCodeAt(0):
            return '&gt;';
        case '&'.charCodeAt(0):
            return '&amp;';
        case ' '.charCodeAt(0):
            return '&nbsp;';
        default:
            return String.fromCharCode(letter);
    }
}

// (x, y)がハイライトされた状態でソースコード表示
function show_code(source_code, x, y) {
    var rows = "ABCDEFGHIJKLMNOPQRSTUVWXY";
    var digit = "0123456789ABCDEF"
    var i, j;

    // 1行目の記述
    var text = "&nbsp;|&nbsp;";
    for (i = 0; i < Math.floor(x / 16); ++i) {
        text += i + "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";
    }
    if (x % 16 == 0) {
        text += "<div>" + Math.floor(x / 16) + "</div>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";
    } else {
        text += i;
        for (j = 1; i * 16 + j < x; ++j) {
            text += "&nbsp;";
        }
        text += "<div>&nbsp;</div>";
        for (++j; j < 16; ++j) {
            text += "&nbsp;"
        }
    }
    for (++i; i < 5; ++i) {
        text += i + "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";
    }
    text += "<br />";

    // 2行目の記述
    text += "&nbsp;|&nbsp;";
    for (i = 0; i < x; ++i) {
        text += digit[i % 16];
    }
    text += "<div>" + digit[i % 16] + "</div>";
    for (++i; i < 80; ++i) {
        text += digit[i % 16];
    }
    text += "<br />";

    // 3行目の記述
    text += "-+-";
    for (i = 0; i < x; ++i) {
        text += "-";
    }
    text += "<div>-</div>";
    for (++i; i < 80; ++i) {
        text += "-";
    }
    text += "<br />";

    // 4行目以降
    for (i = 0; i < y; ++i) {
        text += rows[i] + "|&nbsp;";
        for (j = 0; j < x; ++j) {
            text += escape(source_code[i][j]);
        }
        text += "<div>" + escape(source_code[i][j]) + "</div>";
        for (++j; j < 80; ++j) {
            text += escape(source_code[i][j]);
        }
        text += "<br />";
    }
    text += "<div>" + rows[i] + "|&nbsp;";
    for (j = 0; j < x; ++j) {
        text += escape(source_code[i][j]);
    }
    text += "</div><div id='pointer'>" + escape(source_code[i][j]) + "</div><div>";
    for (++j; j < 80; ++j) {
        text += escape(source_code[i][j]);
    }
    text += "</div><br />";
    for (++i; i < 25; ++i) {
        text += rows[i] + "|&nbsp;";
        for (j = 0; j < x; ++j) {
            text += escape(source_code[i][j]);
        }
        text += "<div>" + escape(source_code[i][j]) + "</div>";
        for (++j; j < 80; ++j) {
            text += escape(source_code[i][j]);
        }
        text += "<br />";
    }
    document.getElementById('source').innerHTML = text;
}

// 初期位置ハイライトでソースコード表示
function show_code_init(source_code) {
    var rows = "ABCDEFGHIJKLMNOPQRSTUVWXY";
    var digit = "0123456789ABCDEF"
    var i, j;

    // 1行目の記述
    var text = "&nbsp;|<div>&nbsp;</div>";
    for (i = 0; i < 5 ; ++i) {
        text += i + "&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;";
    }
    text += "<br />";

    // 2行目の記述
    text += "&nbsp;|<div>&nbsp;</div>0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF0123456789ABCDEF<br />";

    // 3行目の記述
    text += "-+<div>-</div>--------------------------------------------------------------------------------<br />";

    // 4行目の記述
    text += "<div>A|</div><div id='pointer'>&nbsp;</div><div>";
    for (j = 0; j < 80; ++j) {
        text += escape(source_code[0][j]);
    }
    text += "</div><br />";

    // 5行目以降
    for (i = 1; i < 25; ++i) {
        text += rows[i] + "|<div>&nbsp;</div>";
        for (j = 0; j < 80; ++j) {
            text += escape(source_code[i][j]);
        }
        text += "<br />";
    }

    document.getElementById('source').innerHTML = text;
}

// 逐次解釈・実行
function interpret() {
    var xx, yy, vv;
    show_code(code, x, y);
    document.getElementById('stack').innerHTML = stack.join("&nbsp;");
    if (string) {
        if (code[y][x] == '"'.charCodeAt(0)) {
            string = false;
        } else {
            stack.push(code[y][x]);
        }
    } else if (!skip) {
        switch (code[y][x]) {
            case '<'.charCodeAt(0):
                dir = 2;
                break;
            case '>'.charCodeAt(0):
                dir = 0;
                break;
            case '^'.charCodeAt(0):
                dir = 1;
                break;
            case 'v'.charCodeAt(0):
                dir = 3;
                break;
            case '_'.charCodeAt(0):
                xx = stack.pop();
                if (xx == 0) {
                    dir = 0;
                } else {
                    dir = 2;
                }
                break;
            case '|'.charCodeAt(0):
                xx = stack.pop();
                if (xx == 0) {
                    dir = 3;
                } else {
                    dir = 1;
                }
                break;
            case '?'.charCodeAt(0):
                dir = Math.floor(Math.random() * 4);
                break;
            case '#'.charCodeAt(0):
                skip = true;
                break;
            case '@'.charCodeAt(0):
                return 0;   // プログラム停止のサイン
            case '0'.charCodeAt(0):
                stack.push(0);
                break;
            case '1'.charCodeAt(0):
                stack.push(1);
                break;
            case '2'.charCodeAt(0):
                stack.push(2);
                break;
            case '3'.charCodeAt(0):
                stack.push(3);
                break;
            case '4'.charCodeAt(0):
                stack.push(4);
                break;
            case '5'.charCodeAt(0):
                stack.push(5);
                break;
            case '6'.charCodeAt(0):
                stack.push(6);
                break;
            case '7'.charCodeAt(0):
                stack.push(7);
                break;
            case '8'.charCodeAt(0):
                stack.push(8);
                break;
            case '9'.charCodeAt(0):
                stack.push(9);
                break;
            case '"'.charCodeAt(0):
                string = true;
                break;
            case '&'.charCodeAt(0):
                stack.push(parseInt(prompt("value?")));
                break;
            case '~'.charCodeAt(0):
                do {
                    xx = prompt("value?");
                } while (xx.length > 0);
                stack.push(xx.charCodeAt(0));
                break;
            case '.'.charCodeAt(0):
                document.getElementById('output').innerHTML += stack.pop() + "&nbsp;";
                break;
            case ','.charCodeAt(0):
                document.getElementById('output').innerHTML += escape(stack.pop());
                break;
            case '+'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(xx + yy);
                break;
            case '-'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(xx - yy);
                break;
            case '*'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(xx * yy);
                break;
            case '/'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(Math.floor(xx / yy));
                break;
            case '%'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(xx % yy);
                break;
            case '`'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                if (xx > yy) {
                    stack.push(1);
                } else {
                    stack.push(0);
                }
                break;
            case '!'.charCodeAt(0):
                xx = stack.pop();
                if (xx == 0) {
                    stack.push(1);
                } else {
                    stack.push(0);
                }
                break;
            case ':'.charCodeAt(0):
                xx = stack.pop();
                stack.push(xx);
                stack.push(xx);
                break;
            case '\\'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(yy);
                stack.push(xx);
                break;
            case '$'.charCodeAt(0):
                stack.pop();
                break;
            case 'g'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                stack.push(code[yy][xx]);
                break;
            case 'p'.charCodeAt(0):
                yy = stack.pop();
                xx = stack.pop();
                vv = stack.pop();
                code[yy][xx] = vv;
                break;
            default:
                break;
        }
    } else {
        skip = false;
    }
    x += direction[dir][0];
    y += direction[dir][1];
    if (x < 0) {
        x = 79;
    } else if (x >= 80) {
        x = 0;
    }
    if (y < 0) {
        y = 24;
    } else if (y >= 25) {
        y = 0;
    }
    return 1;
}

// 一定間隔で実行するための関数
function run_int() {
    var ret = interpret();
    if (ret != 0 && !quit) {
        setTimeout("run_int()", interval);
    } else {
        document.getElementById('exe').innerText = '実行';
        document.getElementById('exe').onclick = run;
        document.getElementById('clear').disabled = false;
    }
}

// 実行関数
function run() {
    document.getElementById('exe').innerText = '停止';
    document.getElementById('exe').onclick = stop;
    document.getElementById('clear').disabled = true;
    document.getElementById('output').innerHTML = '';

    x = y = 0;
    quit = false;
    stack = new Array();
    dir = 0;
    skip = string = false;
    interval = parseInt(document.getElementById('interval').value);

    // ソースコードの設定
    var txt = document.getElementById('befunge').value.split("\n");
    var i;
    for (i = 0; i < Math.min(25, txt.length) ; ++i) {
        code[i] = new Array(80);
        for (j = 0; j < Math.min(80, txt[i].length) ; ++j) {
            code[i][j] = txt[i].charCodeAt(j);
        }
        for (; j < 80; ++j) {
            code[i][j] = 0;
        }
    }
    for (; i < 25; ++i) {
        code[i] = new Array(80);
        for (var j = 0; j < 80; ++j) {
            code[i][j] = 0;
        }
    }
    show_code_init(code);

    if (interval > 0) {
        setTimeout("run_int()", interval);
    } else {
        while (interpret() != 0);
        document.getElementById('exe').innerText = '実行';
        document.getElementById('exe').onclick = run;
        document.getElementById('clear').disabled = false;
    }
}

// 停止用
function stop() {
    document.getElementById('exe').innerText = '実行';
    document.getElementById('exe').onclick = run;
    document.getElementById('clear').disabled = false;
    quit = true;
}

// 内容の全消去
function my_clear() {
    stack = new Array();
    document.getElementById('output').innerHTML = '';
    document.getElementById('stack').innerHTML = stack.join("&nbsp;");
    show_code_init(code);
}

// 初期化
for (var i = 0; i < 25; ++i) {
    code[i] = new Array(80);
    for (var j = 0; j < 80; ++j) {
        code[i][j] = 0;
    }
}

show_code_init(code);

だいぶダラダラと長くなってますが、3/8くらいがソースコードをキレイに表示するための関数で、処理本体は半分弱くらいです。残りは実行用のエントリポイントだとか初期化処理だとかその類のやつです。

HTMLの方もかなり適当で、

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
	<meta content="text/html; charset=utf-8" http-equiv="Content-Type" />
	<title>Befunge</title>
	<style type="text/css">
	div div {
		background-color:aqua;
		display:inline-block;
	}
	div div#pointer {
		background-color:lime;
		display:inline-block;
	}
	div.tt, div#source {
		display:inline-block;
		font-family:"ＭＳ ゴシック";
	}
	</style>
</head>
<body>
	<form>
	<textarea cols="80" rows="25" id="befunge"></textarea><br />
	<input type="text" size="5" id="interval" value="100" />ms
	<button type="button" onclick="run()" id="exe">実行</button>
	<button type="button" onclick="my_clear()" id="clear">クリア</button>
	</form>
	<div class="tt">出力: </div><div class="tt" id="output" style="background-color:yellow"></div><br />
	<div class="tt">スタック: </div><div class="tt" id="stack" style="background-color:yellow"></div><br />
	<br />
	<div class="tt">ソースコード</div><br />
	<div style="display:inline-block;font-family:'ＭＳ ゴシック'" id="source">
	</div>
	<script language="javascript" type="text/javascript" src="befung.js"></script>
</body>
</html>

みたいな感じで適当にちゃちゃーっと作っちゃいましょう。
これでBefungeで遊ぶ準備ができました（ようやく）。
なお、プログラムサイズは80桁25行以下限定です。
また、本当はデバッグ用にステップ実行機能をつけたかったのですが、めんどくさかったのと時間があまりなかったので省略。つけたい場合はお好みでどうぞ。プログラムの実行速度は制御できるようにしてあります。

まずはHello world

定番のプログラムですね。まずはこれで遊びましょう。
wikipediaに載ってるコードをそのままコピペしちゃいましょう。

v @_       v
>0"!dlroW"v 
v  :#     < 
>" ,olleH" v
   ^       <

これだけ見るとなんのこっちゃって感じなんですが、実際に動かしてみると動作の様子がよくわかると思います。
,とか!を表示させる文字列と命令記号と兼用させているところがちょっと工夫されているところでしょうか。
ぶっちゃけ、こんなややこしいことしなくても、単純にこれで十分だと思いますが。

                   v
>,v                 
|:<"Hello, World!"0<
@

もしくはこんな感じ。

0"!dlroW ,olleH">:v 
                ^,_@

どのプログラムも、数字の0に続いて、Hello, World!の文字をスタックに積んで、それを順に出力しているわけですね。
この時点で書字方向が左右逆だったり変な記号ばっかりで気持ち悪いんですが、とりあえずそこには目をつぶって先に進みましょう。

もう少し進んだプログラム

Hello worldしただけでは面白くないので、もう少し複雑なプログラムを書いてみましょう。
プログラミングの入門書によくある、「1からnまでの整数の和を求める」プログラムを書いてみましょう。公式を使うと面白くないので、for文を回して（？）求めたいと思います。
こんな感じで書けばいいですね。

0&>:!v v+ <
@.-#\_:00p^
  ^1 g0<

やっぱりこれだけ見てもなんのこっちゃなので、プログラムの構成法を書いておきます。
まず、今までに足した数の和と、足す数の上限を記録しておかないといけないので、0と、&でユーザが入力した数をスタックに積みます。問題はそのあとですね。
スタックの状態が

[sum][counter]

の状態から

[sum+counter][counter-1]

にしたいわけです。
どうすればいいかというと、もっていきたい状態の方から逆順に考えればよくて、(x, y)をソースコード中の適当な場所として

[sum+counter][counter-1]       --[counter]
[sum+counter][counter][1]      --[counter]
[sum+counter][counter]         --[counter]
[sum+counter][x][y]            --[counter]
[sum+counter][x]               --[counter]
[sum+counter]                  --[counter]
[sum][counter]                 --[counter]
[sum][coutner][counter][x][y]  --[???]
[sum][counter][counter][x]     --[???]
[sum][counter][counter]        --[???]
[sum][counter]                 --[???]

という感じで考えれば、やり方がわかりますね。--[counter]みたいなのは(x, y)に記録されているデータとします。
counterが非0であれば、

:xyp+xyg1-

という処理をすればいいわけです（xやyは適当な数字に置き換えましょう）。
counterが0のときはsumの値を表示してプログラムを終了するだけなので、

\.@

という処理をすればいいというのはすぐわかると思います。
あとはまあなんというか試行錯誤というか、ソースコードをいかに圧縮するかの戦いみたいな感じでしょうか。
もちろんいろんな実装方法があるので、例えばこんなのも考えられるでしょう。

v v>#<:00pv
0 -^_ \.@ +
>&>:^^1g00<

これの面白いところは、#の部分を左右にいったりきたりするところでしょうか。

もっと複雑なプログラム

FizzBuzzでもやってみることにしましょう。

&00p1>:00g`!v     v             <        >%\52*v v*86< 
>,v  +  v`1:_@v                          *#<   / +>\`| 
|:<", "0_v    #   #                      ^2 5:<: ,*    
     1   >:3%!10p:5%!20p10g20g*v^"Buzz"0_:52*\^_$v^2<  
>    $   ^     v!:<"Fizz Buzz"0_10gv       #     >:5^  
     ^        <_, ^         "Fizz"0_20g ^  ^         <

こんな感じでいいと思います。これをもっと短くするとかいうのはちょっとやりたくないですね（これでもちょっとはやりました）。
一番苦労したのは数字を表示する部分です。
普通なら.で簡単に出力できるんですが、数字の直後はスペースじゃなくてカンマにしたかったのでわざわざ自分で処理を書きました。
FizzBuzzの難しいところは、条件分岐がたくさんあるので、さっきのnまでの和を求めるプログラムみたいになってほしい状態が複雑なことですね。
そのまま考えるはちょっと難しいので、C言語で書いたソースコードをもとに考えてみます。

#include <stdio.h>
int main(void)
{
  int n;
  int i = 1;
  int mod3, mod5;
  scanf("%d", &n);
  while (i <= n) {
    if (i > 1) {
      printf(", ");
    }
    mod3 = !(i % 3);
    mod5 = !(i % 5);
    if (mod3 && mod5) {
      printf("Fizz Buzz");
    } else if (mod3) {
      printf("Fizz");
    } else if (mod5) {
      printf("Buzz");
    } else {
      printf("%d", i);
    }
  }
  return 0;
}

C言語ならみなさん慣れ親しんでいる（はず）なので、これが正しくFizzBuzzを表示することはまあわかると思います。
それでは部分ごとに分けて考えてみます。

初期化

&でとってきた入力とi=1をスタックもしくはソースコードのどこかに保存します。どこに保存するのが適切かはこの段階ではまだよくわかりません。

", "の出力

iと1を比較してiの方が大きかったら", "を出力するので、この段階でiがスタックの先頭に来てないといけないですね。あとでiは頻繁に参照・更新することを考えると、iはスタックに置くほうがよさそうですね。

v_, v →1`v  
 ^!:<", "_$>→
>          ^

という雛形ができます（→はここから入る、←はここから出る印とします）。

条件振り分け

3とか5で割った余りをとりあえず変数に保存します（解説書いてて思った
のですが、ちょっと無駄かもしれません）。
最終的に

[i]          --[!(i%3)][!(i%5)]

とかいう感じになっていてほしいので、さっきのプログラムと同じ要領で考えると、(A, B), (C, D)をそれぞれ適当な場所として

:3%!ABq:5%!CDq

とすると、結果が保存できますね。
肝心の条件分岐ですが、Befungには、&&みたいな演算子がないので、掛け算で対応です。

→:3%!ABq:5%!CDqABgCDg*v
                   イ←_ABgv
                       ロ←_CDgv
                           ハ←_→ニ

イはFizz Buzzを表示するブロック、ロはFizzを表示するブロック、ハはBuzzを表示するブロックで、それぞれ抜けると最初のループ条件のところに戻ります。ニは次で説明する十進数表示ルーチンです。

十進数表示

残念ながらBefungeの.での数値表示は、C言語の

printf("%d ", number);

というのに相当し、数値の後ろにスペースが入ってしまいます。今はそれでは困るので、自分の手で1桁ずつ表示します。
1番下の桁の数は表示したい数を10で割った余りで、それより上の桁の数は表示したい数を10で割った商です。ということは、10で割った余りをスタックに積んでいって、商が0になった段階でASCIIコードで48足しながらスタックの先頭から表示していくと、ちょうどいい感じに表示されそうです。
10で割った余りをスタックに積んでいくには

→:52*\>:52*%\52*/v
      ^          _$→

でいいですね。あとは48を足しつつ表示していくので、

→>:52*\`v
 ^ ,+*86_$→

みたいな感じになります。なお、終了判定のためにスタックの底（から1つ上）に10を積んでいます（スタックから取り出した値が10以上ならループ脱出）。

初期化処理をもう一度

&で最初に拾ってきた値をスタックの底に積むと終了判定がうまく書けなかったので、ソースコードの適当な場所に値を記憶させることにします。
(E, F)に値を記憶させるとして、

→&EFp1 :00g`v
           @_→

という部品が出来上がりますね。
ループから戻ってくるときはカウンタに1を足して、上の:の直前の空白のところに戻ってくればいいわけです。

まとめ

こんな感じで出来上がった部品を組み合わせて、あとはいろいろ配置とかをいじくると完成すると思います。

感想

めんどくさい。二度と触りたくないけど、しばらくしたらまた触りたくなってそう。
あと、記事の面積の2/3くらいが自作処理系のソースコードになっちゃってる事実に触れてはいけない。

おまけ

JavaScript触りながら、「なんで文字定数ないねん！」とかいっぱいツッコミ入れながら書いてました。JSも触りたくない。

追記

記事書いた3時間後くらいにFizzBuzz見返してたら、なんじゃこのコードはわけわからんわーとなったので、いろいろ解説を追加しました。