184 Befunge

Description

Since next week is the Thanksgiving holiday here in the U.S., and since I will be away visiting family, this quiz has a duration of two weeks. It will be summarized on/about Thurs, December 4th.

Your task for these two weeks is to write a Befunge-93 interpreter. Befunge-93 is an esoteric programming language created by Chris Pressey. Its features:

Basically, the program counter (PC) starts in the upper-left cell of the program, initially moving to the right. At each cell, the command (i.e. a single character) in that cell is executed. Some commands can change the PC’s direction of movement; some commands put values on the stack or operate on the stack, and a few commands accept input or print output.

The specification, at the bottom, contains a summary of commands. Note that the digits 0-9, not mentioned in the summary but mentioned earlier in the spec, push themselves onto the stack. To get other values on the stack, you have a couple options. Mathematical operations is one way:

562**5+

Assuming the PC is moving right and starting at the left side, this will leave 65 on the stack. Another way is stringmode, initiated and terminated by quotes. The following also puts 65 on the stack:

"A"

At the Befunge-93 examples page, there are plenty of sample programs for you to test, documented with the program’s intent. Some programs were re-written by various developers in an attempt to shrink programs as much as possible. In particular, the “rand” series (generate a random number from 1 to 16) went through 16 revisions, going from 144 cells (12x12) to a mere 16 cells (16x1). My own submission was king for barely an hour, and looked like this:

>  v  <
vv # < 
14 >0^ 
+*v?1^ 
+  >2^p
. > 3^1
@>"<"1^

Some of the most interesting (i.e. insane) Befunge programs include life.bf, mandel.bf, pi2.bf, and wumpus.bf.

Summary

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…


Wednesday, February 04, 2009