Here is my solution. It's not a revolutionary implementation, but I
had an emphasis on readability and testing. I believe it correctly
runs all the example programs from the Befunge-93 site that the C
reference implementation does.
While debugging I had a "C interpreter mode" which did a few things
slightly differently such as division and mod with negative numbers to
match the behaviour of the reference implementation. I eventually
removed it for clarity since it didn't gain much, other than
accounting for those differences.
For example, the following program will output -1 when run with the C
implementation and -2 with a standard Ruby implementation. Solutions
to Ruby Quiz #85 have some methods which provide C-like division and
mod.
3-2/.@
I couldn't find a simple solution for single character input, so it
goes without. Thus for programs like namegame.bf you have to hit enter
between each character.
Spec file is below the source. Thanks for the interesting quiz.
Jeff Dallien
http://jeff.dallien.net/
------- befunge.rb
#!/usr/bin/env ruby
# Befunge-93 interpreter for Ruby Quiz #184
# Jeff Dallien (
[email protected])
#
class Stack
attr_reader :stack
def initialize
@stack = []
end
def pop
return 0 if @stack.empty?
@stack.pop
end
def push(value)
@stack.push(value)
end
def swap!
first = pop
second = pop
push(first)
push(second)
end
def dup!
top = pop
push(top)
push(top)
end
end
class Instruction
attr_reader :value
def initialize(value)
@value = value
end
# digits 0-9
def value_for_stack?
(@value[0] >= 48 && @value[0] <= 57)
end
# " (double quote) toggles string mode
def string_mode_toggle?
(34 == @value[0])
end
end
class ProgramCounter
attr_reader :x
attr_reader :y
attr_accessor :direction
def initialize
@x = 0
@y = 0
@direction = :right
end
def move!
send("move_#{@direction}!")
end
private
def move_right!
@x = (@x + 1) % 80
end
def move_left!
@x = (@x - 1) % 80
end
def move_down!
@y = (@y + 1) % 25
end
def move_up!
@y = (@y - 1) % 25
end
end
class BefungeProgram
def initialize
@program = []
end
def load_from_file(filename)
File.open(filename) do |f|
25.times do
add_program_line(f.gets.to_s)
end
end
end
def [](index)
@program[index]
end
def load_from_string_array(program_strings)
25.times do |index|
add_program_line(program_strings[index].to_s)
end
end
private
def add_program_line(line)
padded_line = line.chomp[0..80].ljust(80)
@program << padded_line.split('').map { |c| c[0] }
end
end
class Befunger
INSTRUCTION_TABLE = { '@' => :exit,
' ' => :blank,
'\\' => :swap,
':' => :dup,
'$' =>
op,
',' =>
utput_ascii,
'.' =>
utput_int,
'+' => :add,
'-' => :subtract,
'*' => :multiply,
'/' => :divide,
'%' => :mod,
'!' => :not,
'`' => :greater,
'>' =>
c_right,
'<' =>
c_left,
'^' =>
c_up,
'v' =>
c_down,
'?' =>
c_random,
'_' => :horizontal_if,
'|' => :vertical_if,
'g' => :get,
'p' =>
ut,
'&' => :input_value,
'~' => :input_character,
'#' => :bridge,
'"' => :toggle_string_mode
}
def initialize(program)
@program = program
@pc = ProgramCounter.new
@stack = Stack.new
@exit_called = false
@string_mode = false
end
def run
until @exit_called
execute_instruction
@pc.move!
end
end
private
# used so that output can be captured during testing
def output(value)
print value
STDOUT.flush
end
def read_instruction
Instruction.new(@program[@pc.y][@pc.x].chr)
end
def execute_instruction
instruction = read_instruction
if @string_mode && !instruction.string_mode_toggle?
@stack.push(instruction.value[0])
elsif instruction.value_for_stack?
@stack.push(instruction.value.to_i)
else
begin
send(INSTRUCTION_TABLE[instruction.value])
rescue TypeError, NoMethodError
raise "Unknown instruction: #{instruction.inspect}"
end
end
end
def exit
@exit_called = true
end
def blank
end
def swap
@stack.swap!
end
def dup
@stack.dup!
end
def pop
@stack.pop
end
def output_ascii
value = @stack.pop
output value.chr
end
def output_int
value = @stack.pop
output "#{value.to_i} "
end
def generic_math_instruction(operation)
rhs = @stack.pop
lhs = @stack.pop
result = lhs.send(operation, rhs)
@stack.push(result)
end
def add
generic_math_instruction('+')
end
def subtract
generic_math_instruction('-')
end
def divide
generic_math_instruction('/')
end
def mod
generic_math_instruction('%')
end
def multiply
generic_math_instruction('*')
end
def not
value = @stack.pop
result = (value == 0) ? 1 : 0
@stack.push(result)
end
def greater
rhs = @stack.pop
lhs = @stack.pop
result = (lhs > rhs) ? 1 : 0
@stack.push(result)
end
def pc_right
@pc.direction = :right
end
def pc_left
@pc.direction = :left
end
def pc_up
@pc.direction = :up
end
def pc_down
@pc.direction = :down
end
def pc_random
directions = [:right, :left, :up, :down]
@pc.direction = directions[rand(4)]
end
def horizontal_if
value = @stack.pop
@pc.direction = (value == 0) ? :right : :left
end
def vertical_if
value = @stack.pop
@pc.direction = (value == 0) ? :down : :up
end
def get
y = @stack.pop
x = @stack.pop
@stack.push(@program[y][x])
end
def put
y = @stack.pop
x = @stack.pop
@program[y][x] = @stack.pop
end
def input_value
input = $stdin.gets.to_i
@stack.push(input)
end
def input_character
input_char = $stdin.gets[0]
@stack.push(input_char)
end
def bridge
@pc.move!
end
def toggle_string_mode
@string_mode = !@string_mode
end
end
if $0 == __FILE__
if ARGV[0]
program = BefungeProgram.new
program.load_from_file(ARGV[0])
befunger = Befunger.new(program)
befunger.run
else
puts "Usage: ruby befunge.rb program.bf"
end
end
-------- befunge_spec.rb
require 'befunge'
describe Stack, "popping a value" do
before :each do
@it = Stack.new
end
it "should return a zero when attempting to pop from an empty stack"
do
@it.pop.should == 0
end
end
describe Befunger, "processing instructions" do
before :each do
@output = ''
@stack = Stack.new
@pc = ProgramCounter.new
@program = BefungeProgram.new
ProgramCounter.should_receive
new).and_return(@pc)
Stack.should_receive
new).and_return(@stack)
end
def run_program(program_strings)
@program.load_from_string_array(program_strings)
processor = Befunger.new(@program)
processor.should_receive
output).any_number_of_times { |o|
@output << o }
processor.run
end
describe "blank instruction" do
before :each do
run_program([" @",
"111@",
"@@@@"])
end
it "should not add any value the stack" do
@stack.pop.should == 0
end
it "should not change the program counter direction" do
@pc.direction.should == :right
end
end
describe "an unknown instruction" do
it "should raise an error" do
lambda { run_program(["=@"]) }.should raise_error(/Unknown
instruction/)
end
end
describe "add instruction" do
before :each do
run_program(["12+@"])
end
it "should put the result of the addition on the stack" do
@stack.pop.should == 3
end
end
describe "substract instruction" do
describe "with a positive result" do
before :each do
run_program(["65-@"])
end
it "should put the correct result on the stack" do
@stack.pop.should == 1
end
end
describe "with a negative result" do
before :each do
run_program(["56-@"])
end
it "should put the correct result on the stack" do
@stack.pop.should == -1
end
end
end
describe "multiplication instruction" do
before :each do
run_program(["55*@"])
end
it "should put the correct result on the stack" do
@stack.pop.should == 25
end
end
describe "mod instruction" do
describe "calculating with positive numbers" do
before :each do
run_program(["52%@"])
end
it "should put the correct value on the stack" do
@stack.pop.should == 1
end
end
describe "calculating with a negative number" do
before :each do
run_program(["1-2*3%@"])
end
it "should put the correct value on the stack" do
@stack.pop.should == 1
end
end
end
describe "division instruction" do
describe "calculating with positive numbers" do
before :each do
run_program(["93/@"])
end
it "should put the correct value on the stack" do
@stack.pop.should == 3
end
end
describe "calculating with negative numbers" do
before :each do
run_program(["3-2/@"])
end
it "should put the correct negative value on the stack" do
@stack.pop.should == -2
end
end
end
describe "swap instruction" do
before :each do
run_program(["123\\@"])
end
it "should swap the two top values of the stack" do
@stack.pop.should == 2
@stack.pop.should == 3
end
it "should not change the anything below the top two values" do
@stack.pop
@stack.pop
@stack.pop.should == 1
end
end
describe "duplication instruction" do
before :each do
run_program(["1
"])
end
it "should put two copies of the value on the stack" do
@stack.pop.should == 1
@stack.pop.should == 1
end
end
describe "pop instruction" do
before :each do
run_program(["123$@"])
end
it "should remove a value from the stack" do
@stack.pop.should == 2
@stack.pop.should == 1
end
it "should not output anything" do
@output.should == ''
end
end
describe "not instruction" do
describe "with a 0 on the top of the stack" do
before :each do
run_program(["0!@"])
end
it "should put a 1 on top of the stack" do
@stack.pop.should == 1
end
end
describe "with a non-zero value on the top of the stack" do
before :each do
run_program(["1!@"])
end
it "should put a 0 on top of the stack" do
@stack.pop.should == 0
end
end
end
describe "greater instruction" do
describe "with the larger value placed on the stack first" do
before :each do
run_program(["52`@"])
end
it "should place a 1 on the top of the stack" do
@stack.pop.should == 1
end
it "should remove the compared values from the stack" do
@stack.pop
@stack.pop.should == 0
end
end
describe "with the smaller value placed on the stack first" do
before :each do
run_program(["38`@"])
end
it "should put a 0 on the top of the stack" do
@stack.pop.should == 0
end
end
describe "comparing the same value" do
before :each do
run_program(["44`@"])
end
it "should place a 0 on the top of the stack" do
@stack.pop.should == 0
end
end
end
describe "bridge instruction" do
before :each do
run_program(["123#...@"])
end
it "should skip the next instruction" do
@output.should == "3 2 "
end
it "should leave remaining values on the stack" do
@stack.pop.should == 1
end
end
describe "ASCII output instruction" do
before :each do
run_program(["665+*1-,@"])
end
it "should output the ASCII character of the value on the top of
the stack" do
@output.should == "A"
end
end
describe "integer output instruction" do
before :each do
run_program(["665+*1-.@"])
end
it "should output the integer on the top of the stack, followed by
a space" do
@output.should == "65 "
end
end
describe "string mode" do
before :each do
run_program(["\"Ab\"@"])
end
it "should place the ASCII values on the stack" do
@stack.pop.should == 98
@stack.pop.should == 65
end
end
describe "get instruction" do
describe "getting a value from within the given program" do
before :each do
run_program(["11g@",
" * "])
end
it "should get the value from the program and put it on the
stack" do
@stack.pop.should == '*'[0]
end
end
describe "getting a value outside the given program but in the
program space" do
before :each do
run_program(["88g@"])
end
it "should put the ASCII value of the space character (32) on
the stack" do
@stack.pop.should == 32
end
end
describe "attempting to get a value outside the 80x25 program
space" do
it "should raise an error" do
lambda { run_program(["066*g@"]) }.should raise_error
end
end
end
describe "put instruction" do
describe "within the 80x25 program space" do
before :each do
run_program(["522p@"])
end
it "should put the correct value inside the program space" do
@program[2][2].should == 5
end
end
describe "outside the 80x25 program space" do
it "should raise an error" do
lambda { run_program(["1188*p@"]) }.should raise_error
end
end
end
describe "horizontal if instruction" do
def horizontal_if_program(stack_value)
run_program(["#{stack_value} v @ ",
'@,,,,"left"_"thgir",,,,, @ ',
' @ '])
end
describe "with a zero on top of the stack" do
before :each do
horizontal_if_program('0')
end
it "should move the program counter to the right" do
@output.should == "right"
end
end
describe "with a non-zero value on top of the stack" do
before :each do
horizontal_if_program('4')
end
it "should move the program counter to the left" do
@output.should == "left"
end
end
end
describe "vertical if instruction" do
def vertical_if_program(stack_value)
run_program(["#{stack_value} |@",
' 5 ',
' @ ',
' 4 '])
end
describe "with a zero on top of the stack" do
before :each do
vertical_if_program('0')
end
it "should move the program counter down" do
@stack.pop.should == 5
end
end
describe "with a non-zero value on top of the stack" do
before :each do
vertical_if_program('2')
end
it "should move the program counter up" do
@stack.pop.should == 4
end
end
end
describe "controlling the program counter direction" do
describe "to the up direction" do
before :each do
run_program([" ^@",
" @",
" 7"])
end
it "should set the program counter direction to :up" do
@pc.direction.should == :up
end
it "should move upwards and loop to the bottom of the program"
do
@stack.pop.should == 7
end
end
describe "to the down direction" do
before :each do
run_program(["v8@",
" @ ",
">v@"])
end
it "should set the program counter direction to :down" do
@pc.direction.should == :down
end
it "should move downwards and loop to the top of the program" do
@stack.pop.should == 8
end
end
describe "to the left direction" do
before :each do
run_program(["<@5"])
end
it "should set the program counter direction to :left" do
@pc.direction.should == :left
end
it "should move left and loop to the right side of the program"
do
@stack.pop.should == 5
end
end
describe "to the right direction" do
describe "as the default direction" do
before :each do
run_program([" 1@"])
end
it "should set the program counter direction to :right" do
@pc.direction.should == :right
end
it "should move right when a program starts" do
@stack.pop.should == 1
end
end
describe "and reaching the edge of the program" do
before :each do
run_program([" v ",
"2@ > ",
" @ "])
end
it "should move right and loop to the left side of the
program" do
@stack.pop.should == 2
end
end
end
describe "in a random direction" do
before :each do
srand(3) # force predictable 'random' numbers, will always
choose :up first
run_program(["v@ ",
">?@",
" @ "])
end
it "should set the program counter direction based on the random
number" do
@pc.direction.should == :up
end
end
end
end
