[SUMMARY] Befunge (#184)

Writing a Befunge interpreter isn't terribly difficult. Some things  
need to be handled with care -- stack underflow and program counter  
wraparound, for example -- but overall Befunge is a pretty  
straightforward, stack-based language. That the program counter can  
move in two dimensions isn't really cumbersome in itself. The  
interpreter still executes code sequentially; code just "bends" about  
to suit the user's whim. I suspect most any Befunge program could be  
written in a single line, though it's certainly more convenient to  
have a 2D space.

I'm not going to do a long summary of any one of the interpreters.  
Most of the code I saw was easy to understand. For younger Rubyists,  
check out my solution (i.e. the first solution by Matthew Moss) for a  
plain, simple, no-frills approach. There is very little in my code  
that is spectacularly Ruby specific. (Also excuse a few bugs in my  
code; some, but not all, were discussed on the mailing list, but I  
never got around to revising my submission.)

For a summary, I will compare a few pieces of different solutions,  
just to show the various techniques used while writing these  
interpreters. Befunge isn't so fancy that it needs a fancy solution,  
but of course these techniques are certainly applicable to more  
complex systems.

First, a brief look at the stack. There really isn't much needed here,  
since Ruby's `Array` provides `push` and `pop` methods, and so can act  
as a stack with no extra code. However, one minor detail of Befunge is  
that if you pop an empty stack, it should return zero. Several  
submissions did this with a custom version of pop:

     def pop
       @stack.pop || 0
     end

If `@stack` is an empty array, `pop` returns `nil`. As `nil` evaluates  
to false in a boolean context, the logical-or operator `||` will then  
evaluate the right side, returning zero. If `pop` returned an actual  
value, the logical-or operator would short-circuit, skipping the right  
side. It works very similar to another submissions version of pop:

     def pop
       x = @stack.pop
       x.nil? ? 0 : x
     end

This is more explicit in intent, and perhaps clearer for those  
unfamiliar with `||`.

Let's look next at some implementations of the program counter. One  
implementation looked like this (code stripped down to relevant  
portions):

     PC = Struct.new(:row, :col, :direction)
     @pc = PC.new(0, 0, :right)

	def current_cell
	  @program[@pc.row][@pc.col]
	end
	
     def tick_pc
       case @pc.direction
       when :right
         if @pc.col == @program[@pc.row].size - 1
           @pc.col = 0
         else
           @pc.col += 1
         end
       # other direction cases here... implemented similarly
       end
     end

I like the use of Struct here to easily create a class (`PC`) with  
well-named members `row` and `col`. These seem more appropriate than  
`x` and `y`, since the typical access pattern into a 2D array (often  
as pulled from the file) will be row-first, then column. As you can  
see in `current_cell` here, the names make it very clear.  
`@program[@pc.y][@pc.x]` would also be correct, but the order of x and  
y is reversed from what might be expected, and so could be a source of  
bugs if the coder does not pay careful attention to this detail.

While I like the struct and cell access here, updating the program  
counter is a little cumbersome; it's not wrong, but it is a lot of  
code for what should be a simple operation: modular addition. Here is  
a version that's much more compact:

     def step
     	case @direction
     	when :right:	@PC_x += 1
     	when :left:		@PC_x -= 1
     	when :down:		@PC_y += 1
     	when :up:		@PC_y -= 1
     	end
     	@PC_x %= 80
     	@PC_y %= 25
     end

There is excess work being done: if `@PC_x` is updated, for example,  
we don't *need* to modulate `@PC_y`. However, the cost of this is  
likely to be rather low. The alternative is simply to move the modulo  
operations up into each case: minor code duplication for minor  
performance gains. Personally, I'd leave it as it is.

One note on the modulo operator. My own solution modified the program  
counter as such:

     @pc[0] = (@pc[0] - 1 + @hgt) % @hgt

Adding in `@hgt` before taking the modulo by `@hgt` was insurance that  
I would get an expected value, not knowing ahead of time whether the  
modulus of a negative number (as could happen if I simply subtracted 1  
from the pc) would be positive or negative. As it turns out, Ruby  
keeps the result positive if the second argument of the modulus  
operator is positive, so my insurance here was unnecessary.

Finally, let's take a look at "method" dispatch. As the program  
counter moves through the Befunge source code, each character  
represents an operation to be performed. The naive (umm... old-skool)  
implementation is a big case statement:

     when ?0..?9
        push (curr - ?0)
      when ?+, ?-, ?*, ?/, ?%
        b, a = pop, pop
        push a.send(curr.to_sym, b)
      when ?!
        push (pop.zero? ? 1 : 0)
      when ?,
	   print pop.chr
      when ?>
        @dir = :east
      # ...

Not very Rubyish. Let's look at something cooler. A number of  
solutions used a "code block" technique, creating a hash of code  
blocks, the various Befunge symbols as keys into that hash. Here's a  
portion of one submission:

     module Befunge
       Commands = {
         "0" => lambda { @stack.push(0) },
         "1" => lambda { @stack.push(1) },
         "2" => lambda { @stack.push(2) },
         # ...
         "*" => lambda { @stack.push(@stack.pop * @stack.pop) },
         "/" => lambda { val2, val1 = @stack.pop, @stack.pop;  
@stack.push(val1 / val2) },
         "%" => lambda { val2, val1 = @stack.pop, @stack.pop;  
@stack.push(val1 % val2) },
         # ...
         ">" => lambda { @pc.direction = :right },
         "<" => lambda { @pc.direction = :left },
         # ...
       }
     end

Executing the appropriate lambda block is done like so:

     def process_cell
       cell = current_cell
       raise "Unknown command: #{cell} at (#{@pc.col}, #{@pc.row})"  
if !Commands.include? cell
       instance_eval(&Commands[cell])
       cell
     end

`cell` is looked up in the `Commands` hash and passed to  
`instance_eval`. This executes the code block in the context of the  
interpreter (i.e. the object of `process_cell`). This ensures that the  
interpreter's `@stack` and `@pc`, etc. are available for access by  
these code blocks.

One last technique for handling these various commands is the "define  
method" technique: each Befunge symbol becomes a method of the  
interpreter. Here is a portion of that submission:

     class Befunge93
       instance_methods.each { |m| undef_method m unless (m =~ /^__| 
send/) }

	  (0..9).each do |d|
	    define_method :"#{d}" do
	      push d
	    end
	  end

	  %w{ + - * / % }.each do |o|
	    define_method :"#{o}" do
	      a, b = pop, pop
	      push b.send(:"#{o}", a)
	    end
	  end

	  # etc...

   	  def run
	    loop do
	      send @memory[@position]
	      move
	    end
	  end
	end
	
First, notice that we have code right in the class definition, outside  
of any method. If you're new to Ruby, this may look rather strange,  
but this code executes when the class is defined. Quite a handy thing:  
code that executes once at definition let's you do some very meta-ish  
things.

Here, we start with the interesting line at the top enumerating over  
all the class' instance methods. Most methods (except for `send` and a  
few special methods) are undefined; this gives us a "clean" object  
free of any methods that would interfere with the Befunge methods.

Next, `define_method` is called for all the Befunge symbols. (Only  
some shown here.) Inside `define_method` is the code for that  
particular Befunge symbols. Since we are defining instance methods on  
the interpreter itself, these bits of code can access other instance  
methods (such as `pop`). This sort of technique is very convenient for  
the digits and the arithmetic operators shown above, as their  
implementation is nearly identical. The direction changing commands  
are handled in a similar way, though the rest of the commands must be  
done individually (at which point, the hash of lambdas is more compact).

Finally, note how these defined methods are executed in `run`: via the  
`send` method, one of the few that was allowed to remain. The Befunge  
symbol is accessed via `@memory[@position]` and sent to the interpreter.


Thanks for all the submissions! I intentionally wrote a simple, case- 
based interpreter in the hopes that others would provide some more  
Ruby-ish solutions, and we got 'em. Now I'm off to write a Ruby  
interpreter in Befunge...