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...
