Hatena::ブログ(Diary)

YNote RSSフィード

2013-05-14

Ruby で Brainf*ck の処理系を作ってみる

 いまさら感ありますが、 Brainf*ck

 ただの変態難読言語だと思っていました。

 そしたらですよ!「チューリング完全」だとか、チューリングマシンに近いだとか、『計算機科学のかほり』を感じる記事を立て続けに拝見し、突然に興味がわいてきました。 SICP の勉強は絶賛停滞中の私ですが、早速実装。

f:id:yoshidaa:20130514225638g:image

 せっかくなので、こんな感じで動作の過程がわかるように、エスケープシーケンスを使って可視化してみた。

$ ruby bf.rb

で、"Hello, world!" を出力するプログラムを走らせる。

$ ruby bf.rb hoge.b

みたいな感じで入力に既存のファイルを渡すこともできる。さらに、

$ ruby bf.rb -w 0.02

みたいな感じで1ステップあたりのウェイト(秒)を指定することもできる。

require "optparse"

class Brainfuck
  TAPE_LENGTH = 0x10000
  
  def initialize( code )
    @tape         = Array.new(TAPE_LENGTH,0)
    @code         = code.gsub("\n","\r\n").scan(/./)
    @buf_output   = ""
    @tape_ptr     = 0
    @code_ptr     = 0
    @max_tape_ptr = 0
  end
  
  def interpret(c)
    interpreted = true
    case c
    when ">" then @tape_ptr += 1
    when "<" then @tape_ptr -= 1
    when "+" then @tape[@tape_ptr] = (@tape[@tape_ptr] + 1) & 0xFF
    when "-" then @tape[@tape_ptr] = (@tape[@tape_ptr] - 1) & 0xFF
    when "." then output(@tape[@tape_ptr])
    when "," then @tape[@tape_ptr] = input()
    when "["
      if @tape[@tape_ptr] == 0
        b = 1
        begin
          @code_ptr += 1
          b += 1 if @code[@code_ptr] == "["
          b -= 1 if @code[@code_ptr] == "]"
        end while ( b != 0 )
      end
    when "]"
      if @tape[@tape_ptr] != 0
        b = 1
        begin
          @code_ptr -= 1
          b -= 1 if @code[@code_ptr] == "["
          b += 1 if @code[@code_ptr] == "]"
        end while ( b != 0 )
      end
    else
      interpreted = false
    end
    @code_ptr    += 1
    @max_tape_ptr = [ @max_tape_ptr, @tape_ptr ].max
    interpreted
  end
  
  attr_reader :code, :code_ptr
  
  def output(c)
    @buf_output += c.chr
  end
  
  def input
    return STDIN.getc
  end
  
  def print_code
    code = @code.each_with_index.map{|c,i|
      s = ( i == @code_ptr ) ? sprintf("\033[31m%s\033[37m", c ) : c
    }.join("") + "\n"
  end
  
  def print_tape
    str = @tape.slice(0..@max_tape_ptr).each_with_index.map{|e,i|
      s = ( i == @tape_ptr ) ? sprintf("\033[34m[%3d]\033[37m", e) : sprintf("[%3d]", e)
    }.each_slice(20).map{|arr| arr.join("") }.join("\n") + "\n"
  end
  
  def print_env
    str  = "--- [Code] ---------------\n"   + print_code() + "\n"
    str += "--- [Tape] ---------------\n"   + print_tape() + "\n"
    str += "--- [STDOUT] ---------------\n" + @buf_output
    str.gsub("\r","\n")
  end
end

sample   = <<EOS
+++++++++[>++++++++>+++++++++++>+++++<<<-]>.>++.+++++++..+++.>-.
------------.<++++++++.--------.+++.------.--------.>+.
EOS

print    "\033[2J" # clear
$wait    = 0
opt      = OptionParser.new
opt.on('-w v') {|v| $wait = v.to_f }
opt.parse!(ARGV)

code    = ( ARGV[0] == nil ) ? sample : open( ARGV[0] ).read
b       = Brainfuck.new( code )
display = lambda{
  puts "\033[0;0H" + b.print_env()
  sleep($wait) if $wait > 0
}

while true
  inst = b.code[b.code_ptr]
  disp = b.interpret(inst)
  display.call if disp
  break if b.code[b.code_ptr] == nil
end

 入出力まわりが煩雑でいけてない感じだなぁ、、けど、思い切って公開しちゃいます!!

 ところで、Brainf*ck のコードはニーモニックのみのマシン語(3bit命令)、なんていう捉え方もできるな。なかなかおもしろい。

トラックバック - http://d.hatena.ne.jp/yoshidaa/20130514/1368540057