From: Jeff Dallien <jeff@...>
Date: 2008-11-30T07:29:28+09:00
Subject: Re: Befunge (#184)

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 (jeff@dallien.net)
#
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,
                        '$'  => :pop,
                        ','  => :output_ascii,
                        '.'  => :output_int,
                        '+'  => :add,
                        '-'  => :subtract,
                        '*'  => :multiply,
                        '/'  => :divide,
                        '%'  => :mod,
                        '!'  => :not,
                        '`'  => :greater,
                        '>'  => :pc_right,
                        '<'  => :pc_left,
                        '^'  => :pc_up,
                        'v'  => :pc_down,
                        '?'  => :pc_random,
                        '_'  => :horizontal_if,
                        '|'  => :vertical_if,
                        'g'  => :get,
                        'p'  => :put,
                        '&'  => :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