BrainF*ck実装してみた

先週「Rubyで作る奇妙なプログラミング言語」をかってきた。

Rubyで作る奇妙なプログラミング言語 ~Esoteric Language~

一個一個つくっていけばかるーく言語処理系の実装の練習になるかなーという甘い期待のもと進める。
方針として「本に載っているソースは見ない」「感性の赴くままに適当に作る」

1つめの「HQ9+」は簡単なので省略
というわけで見るも無惨なソースをさらしてみる

主に3つのソースから構成

brainfuckproc.rb

実際の処理を行うBrainFuckProcクラス

brainfuck.rb

ソースを読み込んでBrainFuckProcインスタンスを呼び出す人 ジャンプ系の命令はこいつが担当

main.rb

処理系のメイン

dprint.rb

デバッグ用のdprintメソッドだけがあるファイル（省略)

brainfuckproc.rb

require "../lib/dprint.rb"

class BrainFuckProc
	def initialize
		@tape = Array.new
		@current_position = 0
	end

	def inc_pointer
		dprint "up #{@current_position}->#{@current_position + 1}"
		@current_position += 1
	end

	def dec_pointer
		dprint "down #{@current_position}->#{@current_position -1}"
		if @current_position == 0 then
			puts "ERROR - pointer lower limit"
			exit
		end
		@current_position -= 1
	end

	def inc_current_value
		if @tape[@current_position] == nil then
			@tape[@current_position] = 0
		end
		@tape[@current_position] += 1
		dprint @tape
	end

	def dec_current_value
		if @tape[@current_position] == nil || @tape[@current_position] == 0 then
			puts "ERROR - value at the pointer is 0"	
			exit
		end

		@tape[@current_position] -= 1
		dprint @tape
	end

	def print_current_value_char
		print @tape[@current_position].chr
	end

	def get_char_to_current_pos
		data = gets
		@tape[@current_position] = data[0]
	end

	def is_zero?
		if @tape[@current_position] == 0 || @tape[@current_position] == nil then
			return true
		else
			return false
		end
	end

	def jump_forward?
		jump?	
	end

	def jump_backward?
		jump?
	end

	def print_all_tape
		data = ""
		@tape.each do |val|
			if val then
				data.concat(val.chr)
			end
		end
		p "ALLDATA:#{data}"
	end
end

brainfuck.rb

require "brainfuckproc"
require "../lib/dprint.rb"

class BrainFuck
	def initialize(src_name)
		@src_name = src_name
		@bfpProc = BrainFuckProc.new()
	end

	def run
		File.open(@src_name) do |file|
			run_bfp(file)			
		end
	end

	def run_bfp io
		while ch = io.read(1) do
			case ch
			when ">":
				@bfpProc.inc_pointer
			when "<":
				@bfpProc.dec_pointer
			when "+":
				@bfpProc.inc_current_value
			when "-":
				@bfpProc.dec_current_value
			when ".":
				@bfpProc.print_current_value_char
			when ",":
				@bfpProc.get_char_to_current_pos
			when "[":
				jump_forward(io)
			when "]":
				jump_backward(io)
			when "*":
				@bfpProc.print_all_tape
			end
		end
	end

	def jump_forward(io)
		dprint "jump forward:"
		if !@bfpProc.is_zero? then
			dprint "no jump\n"
			return	
		end

		dprint "jump\n"
				
		stack_count = 0;
				
		while true do
			inner_ch = io.read(1)		
			if inner_ch == "" then # no matched clauses
				puts "ERROR - no matched clauses"
				exit
			end

			if inner_ch == "[" then
				stack_count += 1
			end

			if inner_ch == "]" then
				if stack_count > 0 then
					stack_count -= 1
					next
				else # stack_count == 0 -> matched found
					io.pos += 1
					break # ends here
				end
			end
		end
	end

	def jump_backward(io)
		dprint "jump backward:"
		if @bfpProc.is_zero? then
			dprint "no jump\n"
			return
		end

		dprint "jump\n"

		stack_count = 0;

		if io.pos < 2 then 
			puts "ERROR - guess only ] appears first?"
			exit
		end


		while io.pos > -1 do
			io.pos -= 2
			inner_ch = io.read(1)			
			if inner_ch == "" then # no more backwards
				puts "ERROR - no match clauses"
				exit
			end

			if inner_ch == "]" then
				stack_count += 1
			end
			
			if inner_ch == "[" then
				if stack_count > 0 then
					stack_count -= 1
					next
				else##matching
					#io.pos += 1
					break
				end
			end
		end
	end
end

main.rb

require "brainfuck"

bfp = BrainFuck.new(ARGV.shift)
bfp.run

ソース中にもあるように"*"という第9の命令が追加されています。
これはデバッグ＆趣味の用途としてテープにどんな値が書き込まれているかを表示するために付け足した。

Hello, World on BrainF*ck

処理系(のようなもの?)は書いたけど、BrainF*ckはかけないので、WikipediaからBrainF*ckのソースコートを拝借してきた

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

素で読めたら神になれる。

このソースの末尾に追加機能である"*"を付加して実行

$ ruby main.rb helworld2.bfk
Hello, world!"ALLDATA:\000Hd!"

結果としてこんな出力が得られる。
末尾の"ALLDATA:"以降がテープの内容。ASCIIコードに落とすと

[0, 72, 100, 33]

こんな状態で終わる。
なんと4つの領域しか使っていないとか。こんなの書けない