トップ «前の日記(2007-12-06) 最新 次の日記(2007-12-09)» 月表示 編集

日々の流転


2007-12-07 [長年日記]

λ. A brainf*ck interpreter in Prolog

ふと、現実逃避にPrologでBrainf*ckの簡単なインタプリタを書いてみた。

brainfuck(Src) :- bf(Prog, Src, []), !, seq(Prog, []*[0], _).

bf([]) --> [].
bf([X|Y]) --> bf1(X), {!}, bf(Y).
bf(X) --> [_], bf(X).

bf1('>') --> ">".
bf1('<') --> "<".
bf1('+') --> "+".
bf1('-') --> "-".
bf1('.') --> ".".
bf1(',') --> ",".
bf1(w(X)) --> "[", bf(X), "]".

seq([], T, T).
seq([X|K], T1, T2) :- step(X, T1, T), seq(K, T, T2).

step('>', L*[X|R], [X|L]*R1) :- R=[_|_] -> R1=R ; R1=[0].  
step('<', [X|L]*R, L*[X|R]).
step('+', L*[X|R], L*[Y|R]) :- X=255 -> Y=0 ; Y is X+1.
step('-', L*[X|R], L*[Y|R]) :- X=0 -> Y=255 ; Y is X-1.
step('.', L*[X|R], L*[X|R]) :- put_byte(X).
step(',', L*[_|R], L*[X|R]) :- get_byte(X).
step(w(W), T1, T2) :- while(W, T1, T2).

while(W, T1, T2) :-
    T1=_*[0|_] -> T1=T2 ; seq(W, T1, T), while(W, T, T2).

多分一番メジャーなProlog処理系である SWI Prolog で実行してみる。

% pl 
?- consult(brainfuck).
% brainfuck compiled 0.00 sec, 9,300 bytes

Yes
?- brainfuck("
>+++++++++[<++++++++>-]<.>+++++++[<++++>-]<+.+++++++..+++.[-]>++++++++[<++
++>-]<.>+++++++++++[<+++++>-]<.>++++++++[<+++>-]<.+++.------.--------.[-]>
++++++++[<++++>-]<+.[-]++++++++++.").
Hello World!

Yes
?-

どうせなので、ファイルから読み込んで実行することも出来るようにしてみる。

brainfuck_file(FileName) :- readfile(FileName, X), !, brainfuck(X).

readfile(FileName, Str) :-
    see(FileName), get_byte(B), readfile_loop(B, Str), seen.

readfile_loop(-1, []) :- !. 
readfile_loop(H, [H|T]) :- get_byte(B), !, readfile_loop(B, T).

それはそうと、Brainf*ckって日本語訳するとやっぱり「脳姦」になるのだろうか? なんというか、氏賀Y太あたりの描くグロ絵を連想してしまって非常にアレでございます。(今回のエントリは実はこれを書きたかっただけ。← 最低です)

【2008-03-27】 WAMのindexing最適化によって不要になるカットを取り除いた。