On Sat, Nov 22, 2008 at 8:55 AM, Matthew Moss <matt / moss.name> wrote:
> ## Befunge (#184)
> Your task for these two weeks is to write a [Befunge-93][1] interpreter.

My program follows. I tried to make it as self-documenting as
possible.  It's supposed to be a complete implementation, but it
crashes on life.bf, so I think I'm missing something.  I created a
rudimentary debugger to help figure it out - start it with `ruby -d
befunge.rb progfile`.  Unfortunately I couldn't track it down.

-Adam
-----------------------------
#befunge.rb
# a befunge interpreter for Ruby Quiz #184
# requires Ruby 1.8
# -Adam Shelly

module Befunge
    LineLen =80
    NumLines=25

  class VirtualMachine
    #the Program Counter
    class PC
      attr_reader :x,:y
      MOTION = {?>=>[1,0], ?<=>[-1,0], ?^=>[0,-1], ?v=>[0,1]}
      def initialize
        reset
      end
      def reset
        @x=@y=0
        set_dir ?>
      end
      def set_dir d
        d=MOTION.keys[rand(4)] if d==??
        @dir=d
      end
      def advance
        @x=(x+MOTION[@dir][0])%LineLen
        @y=(y+MOTION[@dir][1])%NumLines
      end
      def addr
        [@x,@y]
      end
      def to_s
        "[#{@x},#{@y}]:#{@dir.chr}"
      end
    end
  #new
    def initialize ostream = $stdout
      @stack = Array.new
      @pc = PC.new
      @stopped=@string_mode = false
      @break_at={}
      define_opcodes
      set_output ostream
    end
  #the language definition
    def define_opcodes
      @opcodes = {
      ?\s=>[:NOP, lambda{ }], #no-op
      ?+ =>[:ADD, lambda{ push(pop+pop)             }],
      ?* =>[:MUL, lambda{ push(pop*pop)             }],
      ?- =>[:SUB, lambda{ a=pop;push(pop-a)         }],
      ?/ =>[:DIV, lambda{ a=pop;push(pop/a)         }],
      ?% =>[:MOD, lambda{ a=pop;push(pop%a)         }],
      ?! =>[:NOT, lambda{ push(pop==0? 1: 0)        }],
      ?` =>[:GT , lambda{ push(pop>=pop ? 0: 1)     }],
      ?> =>[:RT , lambda{ @pc.set_dir ?>            }],
      ?< =>[:LF , lambda{ @pc.set_dir ?<            }],
      ?^ =>[:UP , lambda{ @pc.set_dir ?^            }],
      ?v =>[:DN , lambda{ @pc.set_dir ?v            }],
      ?? =>[:RND, lambda{ @pc.set_dir ??            }],
      ?_ =>[:IFH, lambda{ @pc.set_dir(pop==0??>:?<) }],
      ?| =>[:IFV, lambda{ @pc.set_dir(pop==0??v:?^) }],
      ?" =>[:STR, lambda{ @string_mode=!@string_mode}],
      ?: =>[:DUP, lambda{ push(a=pop);push a        }],
      ?\\=>[:SWP, lambda{ a,b=pop,pop;push a;push b }],
      ?$ =>[:POP, lambda{ pop                       }],
      ?. =>[:PRN, lambda{ @output<< pop.to_i.to_s   }],
      ?, =>[:PRC, lambda{ @output<< (pop%256).chr   }],
      ?# =>[:JMP, lambda{ @pc.advance               }],
      ?p =>[:PUT, lambda{ put(pop,pop,pop)          }],
      ?g =>[:GET, lambda{ push get(pop,pop)         }],
      ?& =>[:QN , lambda{ push query(:NUM)          }],
      ?~ =>[:QC , lambda{ push query(:CHAR)         }],
      ?@ =>[:STP, lambda{ @stopped=true             }]
      }
      (?0..?9).each{|v|@opcodes[v]=[:VAL,lambda{push v-?0}]}
    end
  #program control
    def load_program istream
      @mem = istream.readlines
      @mem.map!{|l| l.chomp.ljust(LineLen)}
      (NumLines- / mem.size).times { @mem<<' '*LineLen}
      raise "Program too big" if @mem.size>NumLines ||
@mem.find{|l|l.size>LineLen}
      @pc.reset
    end
    def run
      raise "No Program Loaded" unless @mem
      @stopped = false
      step until @stopped||@break_at[@pc.addr]
    end
    def step
      execute current_instruction
      advance_pc if !@stopped
    end
  #debug support
    def set_output ostream
      @output = ostream
    end
    def show_debug
      $stdout.write @mem
      $stdout.print '='*LineLen+"\nPC = #{@pc.to_s.ljust(12)}",
           "op = #{current_instruction.chr} ( #{getopcode.to_s.ljust(4)}) ",
           "Stack[#{@stack.nitems}]: [
#{(@stack[-[@stack.size,8].min,8].reverse||[])*' '} ]\n",
           '='*LineLen,"\n"
    end
    def set_breakpoint addr
      @break_at[addr]=true
    end
    def clear_breakpoints
      @break_at.clear
    end
private
  #status
    def current_instruction
      @mem[@pc.y][@pc.x]
    end
    def getopcode
      return :STR if @string_mode
      (@opcodes[current_instruction]||[:UNK])[0]
    end
  #code execution
    def execute op
      if @string_mode && op!=?"
        push op
      else begin
        inst=@opcodes[op]
        inst[1].call if inst
      rescue ZeroDivisionError
        push query(:ZDIV)
      rescue => err
        puts err
        show_debug
        @stopped=true
      end;end
    end
    def advance_pc
      if getopcode!=:STP
        @pc.advance
        @pc.advance while getopcode==:NOP && !@break_at[@pc.addr]
      end
    end
  #machine operations
    def push v
      @stack.push v
    end
    def pop
      @stack.pop||0
    end
    def put x,y,v
      @mem[x%LineLen][y%NumLines]=v%256
    end
    def get x,y
      @mem[x%LineLen][y%NumLines]
    end
    def query type
      print "\n#{type.to_s}?> "
      r = $stdin.gets||"\0"
      return r[0] if type==:CHAR
      r.to_i
    end
  end

  class Debugger
    def initialize vm
      @vm = vm
      @vm.set_output @linebuf=''
    end
    def run
      @vm.show_debug
      loop do
        print "DBG??"
        cmd = $stdin.gets||'q'
        case cmd.chomp.downcase[0]
          when ?q then break
          when ?s,?\s,nil
            @vm.step
            @vm.show_debug
          when ?r
            @vm.run
            @vm.show_debug
          when ?b
            @vm.set_breakpoint cmd.split[1,2].map{|n|n.to_i}
          when ?c
            @vm.clear_breakpoints
          else
            puts "DEBUG COMMANDS: (s)tep, (r)un, (b)reak x,y, (c)lear
breakpoints"
            puts "(you entered #{cmd.chomp.downcase})"
        end
        puts @linebuf,'-'*Befunge::LineLen
        @linebuf=@linebuf[-1,1] if @linebuf[-2]==?\n
      end
    end
  end
end

if __FILE__ == $0
  vm = Befunge::VirtualMachine.new
  raise "Usage: #{$0} filename" unless File.exists? ARGV[0]
  File.open(ARGV[0]){|f|vm.load_program f}
  if $DEBUG
    Befunge::Debugger.new(vm).run
  else
    vm.run
  end
end