2006年06月27日 03:00 [Edit]

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)に直しました。


この記事へのトラックバックURL

この記事へのトラックバック
毎日コミュニケーションより献本御礼。 Rubyで作る奇妙なプログラミング言語 原悠 うれしい。そしてちょっぴり悔しい。 こういう本を、自分で書いてみたかった。
言語で遊ぼう! - 書評 - Rubyで作る奇妙なプログラミング言語【404 Blog Not Found】at 2009年01月03日 00:00
BFにはまっておられる奥さんに。 Kazuho@Cybozu Labs: brainf*ck でマジメに素数探索 また、速度の最適化もしていないので、実行にあたっては高速な処理系をご用意ください。試した範囲では、BF online では10秒ほどで結果が表示されましたが、弾さんの処理系では、1分た....
brainfu.k - BF2JS opimizing compiler【404 Blog Not Found】at 2006年07月04日 08:22
 「キミならどう書く 2.0 - ROUND 1 - 」の〆切は過ぎていますが、...
brainf*ck でマジメに素数探索【Kazuho@Cybozu Labs】at 2006年06月28日 17:23
 「キミならどう書く 2.0 - ROUND 1 - 」の〆切は過ぎていますが、...
brainf*ck でマジメに素数探索【Kazuho@Cybozu Labs】at 2006年06月28日 17:17
 竹迫さんのbpencodeを皮切りに、brainf*ck ネタが盛り上がってい...
brainf*ck で計算機【Kazuho@Cybozu Labs】at 2006年06月28日 12:03
たけさこさんがBrainF*ckでプログラムを書いていました。 ということで、世界最小のコンパイラ/インタプリタと言われている Brainf*ckで1??100までの素数を列挙してみました。 TAKESAKO @ Yet another Cybozu Labs: Brainf*ckで100までの素数を列挙してみるテスト 反応して
[プログラミング] 以前書いたBrainF*ck解説記事を公開してたのをすっかり忘れてた【mizuno_takaakiの日記】at 2006年06月28日 00:32
Language::BF 0.01 を Release したのでお知らせします。CPANの更新を待てない人はこちらから。 404 Blog Not Found:brainfu.k - perl と javascript による処理系CPANに上げられるよう、moduleとして実装してみました。
perl - Language::BF 0.01 released【404 Blog Not Found】at 2006年06月27日 17:52
この記事へのコメント
解説ありがとうございました。
僕がAcme::Brainfuckを知ったのはperldocjpを流し読みしていたのが直接のきっかけで、始めてこれを見たときは「なんだこれ、まぁいっかAcmeだし」
ぐらいに思ってしまったんです。
今回の一連のエントリを読んで、その考えを改めないといけないような気がしてきました。

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

Posted by Youth at 2006年06月27日 20:34
結果は変わらないですが、case ']' :の時にまず
> if (!bf.data[bf.sp]) break;
をすると余計なサーチが減るのでは?

> 8. ] ポインタが指す値が0でないなら、対応する [ にジャンプする。C言語の「}」に相当。
Posted by もとむら at 2006年06月27日 19:07
Youthさん、
Step実行ができることくらい、かな?
あちらはcompilerで、こちらはinterpreter、という違いもあるか。
Dan the Brainfu.ckr
Posted by at 2006年06月27日 14:38
JavaScript 版の , の実装について:

1) s/charAt/charCodeAt/

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

2) 入力バッファが FIFO じゃなく LIFO になっているような気がします
Posted by kazuho at 2006年06月27日 14:27
実装が違うのはソースを読めば何となく分かるのですが、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