brainfu.k - perl と javascript による処理系

[初掲載 06.26 23:00; 最終更新 06.26 03:00]

その言語で書くより、その言語を書く方が簡単な言語、それがBF。

TAKESAKO @ Yet another Cybozu Labs: Brainf*ckで100までの素数を列挙してみるテスト

ね、簡単でしょ？

というわけで、JavaScriptとPerlによる実装を以下に。比較的わかりやすい実装にしてます。

JavaScript編

BF Source

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

入力

出力

ソースは以下のとおり。

function BF(str){
    this.code = []; this.output = []; this.input = []; this.data = [];
    this.pc = this.sp = 0;
    this.debug  = 0;
    this.step = function(){
      var op = bf.code[this.pc];
      var nest;
      if (bf.debug){
         document.writeln([op, bf.sp, bf.pc].join(","));
      }     
      switch (op) {
         case '<' : bf.sp--; break;
         case '>' : bf.sp++; break;
         case '+' : if(!bf.data[bf.sp]) bf.data[bf.sp] = 0;
                    bf.data[bf.sp]++ ; break;
         case '-' : if(!bf.data[bf.sp]) bf.data[bf.sp] = 0;
                    bf.data[bf.sp]--; break;
         case '.' : bf.output.push(bf.data[bf.sp]) ; break;
         case ',' : bf.data[bf.sp] = bf.input.shift() ; break;
         case '[' : if (bf.data[bf.sp]) break;
                    nest = 1;
                    while(nest){
                      bf.pc++;
                      nest += bf.code[bf.pc] == '[' ? +1
                            : bf.code[bf.pc] == ']' ? -1
                            : 0;
                    }
                    break;
         case ']' : nest = 1;
                    while(nest){
                      bf.pc--;
                      nest -= bf.code[bf.pc] == '[' ? +1
                            : bf.code[bf.pc] == ']' ? -1
                            : 0;
                    };
                    bf.pc--;
                    break;
      };
      bf.pc++;
    }
    this.init = function(str){
        str = str.replace(/[^<>\+\-\.\,\[\]]/, '');
        this.code = [];
        for (var i = 0; i < str.length; i++){
            this.code.push(str.charAt(i));
        }
        this.sp = 0; this.pc = 0;
        this.output = []; this.input = []; this.data = [];
    };
    this.stdin = function(str){
        for (var i = 0; i < str.length; i++){
            this.input.push(str.charCodeAt(i));
        }
    };
    this.stdout = function(){
        var str = '';
        for (var i = 0; i < this.output.length; i++){
            str += String.fromCharCode(this.output[i]);
        }
        return str;
    };
    this.run = function(){
        var op;
        while(op = this.code[this.pc]){
            if (this.pc < 0) break;
            this.step(this);
        }
    }
    this.init(str);
}

Perl編

CPANに上げられるよう、moduleとして実装してみました。

package Language::BF;
use 5.008001;
use strict;
use warnings;
our $VERSION = '0.01';

sub new{
    my $class = shift;
    my $bf = 
        bless { pc => 0, sp => 0, debug => 0,
                code => [], data => [], in => [],  out => [] }, $class;
    $bf->code(shift) if @_;
}

sub step {
    my $bf = shift;
    my $op = $bf->{code}[ $bf->{pc} ];
    $bf->{debug}
      and warn sprintf "pc=%d, sp=%d, op=%s", $bf->{pc}, $bf->{sp}, $op;
    {
        '<' => sub { $bf->{sp} -= 1 },
        '>' => sub { $bf->{sp} += 1 },
        '+' => sub { $bf->{data}[ $bf->{sp} ]++ },
        '-' => sub { $bf->{data}[ $bf->{sp} ]-- },
        '.' => sub { push @{ $bf->{out} }, $bf->{data}[ $bf->{sp} ] },
        ',' => sub { $bf->{data}[ $bf->{sp} ] = shift @{ $bf->{in} } },
        '[' => sub {
            return if $bf->{data}[ $bf->{sp} ];
            my $nest = 1;
            while ($nest) {
                $bf->{pc} += 1;
                $nest     +=
                    $bf->{code}[ $bf->{pc} ] eq '[' ? +1
                  : $bf->{code}[ $bf->{pc} ] eq ']' ? -1
                  : 0;
                die "matching ] not found!"
                    if $bf->{pc} > scalar @{ $bf->{code} };
            }
        },
        ']' => sub {
            my $nest = 1;
            while ($nest) {
                $bf->{pc} -= 1;
                $nest     -=
                    $bf->{code}[ $bf->{pc} ] eq '[' ? +1
                  : $bf->{code}[ $bf->{pc} ] eq ']' ? -1
                  : 0;
                die "matching [ not found!"
                    if $bf->{pc} < 0;
            }
            $bf->{pc}--;
        },
    }->{$op}();
    $bf->{pc}++;
}

sub run {
    my $bf = shift;
    $bf->step while ( $bf->{code}[ $bf->{pc} ] and $bf->{pc} >= 0 );
}

sub debug { my $bf = shift; $bf->{debug} = shift if @_;  $bf->{debug} };

sub code($$){
    my ($bf, $code) = @_;
    $code =~ tr/<>+\-.,[]//cd;
    $bf->{code} =  [ split //, $code ];
    $bf;
}

sub input($$){
    my ($bf, $input) = @_;
    $bf->{in} =  [ split //, $input ];
    $bf;
}

sub output($){
    my $bf = shift;
    join '', map {chr} @{$bf->{out}};
}

sub reset{
    my $bf = shift;
    $bf->{pc} = 0; $bf->{sp} = 0;
    $bf->{data} = []; $bf->{in} = []; $bf->{out} = [];
}
1;
__END__

「君ならどう書く?」のネタにすればよかったのに。Enjoy!

Dan the Brainfu.ker

追記:

Yet another brainfuck reference.

This word "matching" has confused some people. '[' and ']' nest just as brackets and parentheses normally do.

これを見落としてました。[]がきちんとnestするよう修正。

追記2.0

kazuhoさんのコメント

1) s/charAt/charCodeAt/
現状だと、入力値が文字コードに変更されないので、 ,. が正しく動作しません。
2) 入力バッファが FIFO じゃなく LIFO になっているような気がします

反映させました。厳密には、おかしかったのは,の実装ですね。あと、入力バッファーはFIFOが正しくLIFOが間違いで、LIFO(pop)になっていたのをFIFO(shift)に直しました。

Comments

実装が違うのはソースを読めば何となく分かるのですが、Language::BFとAcme::Brainfuckの本質的な違いってなんですか?

http://perldoc.jp/docs/modules/Acme-Brainfuck-1.1.1/Brainfuck.pod
http://search.cpan.org/~jaldhar/Acme-Brainfuck-1.1.1/lib/Acme/Brainfuck.pm

Posted by Youth at 2006年06月27日 11:27

JavaScript 版の , の実装について:

1) s/charAt/charCodeAt/

現状だと、入力値が文字コードに変更されないので、 ,. が正しく動作しません。

2) 入力バッファが FIFO じゃなく LIFO になっているような気がします

Posted by kazuho at 2006年06月27日 14:27

Youthさん、
Step実行ができることくらい、かな?
あちらはcompilerで、こちらはinterpreter、という違いもあるか。
Dan the Brainfu.ckr

Posted by 弾 at 2006年06月27日 14:38

結果は変わらないですが、case ']' :の時にまず
> if (!bf.data[bf.sp]) break;
をすると余計なサーチが減るのでは？
↓
> 8. ] ポインタが指す値が0でないなら、対応する [ にジャンプする。C言語の「}」に相当。

Posted by もとむら at 2006年06月27日 19:07

解説ありがとうございました。
僕がAcme::Brainfuckを知ったのはperldocjpを流し読みしていたのが直接のきっかけで、始めてこれを見たときは「なんだこれ、まぁいっかAcmeだし」
ぐらいに思ってしまったんです。
今回の一連のエントリを読んで、その考えを改めないといけないような気がしてきました。

Brainfuckって出来る子なんですね。

Posted by Youth at 2006年06月27日 20:34