Forum: Ruby Befunge (#184)

Announcement (2017-05-07): www.ruby-forum.com is now read-only since I unfortunately do not have the time to support and maintain the forum any more. Please see rubyonrails.org/community and ruby-lang.org/en/community for other Rails- und Ruby-related community platforms.
Matthew M. (Guest)
on 2008-11-22 19:00
(Received via mailing list)
-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

The three rules of Ruby Q. 2:

1.  Please do not post any solutions or spoiler discussion for this
quiz until 48 hours have passed from the time on this message.

2.  Support Ruby Q. 2 by submitting ideas as often as you can!
Visit <http://splatbang.com/rubyquiz/>.

3.  Enjoy!

Suggestion:  A [QUIZ] in the subject of emails about the problem
helps everyone on Ruby T. follow the discussion.  Please reply to
the original quiz message, if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-

## Befunge (#184)

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][1]
interpreter. Befunge-93 is an esoteric programming language created by
Chris Pressey. Its features:

  * two-dimensional program space (i.e. 80x25 ASCII grid)
  * a program counter capable of moving through the program in four
directions
  * an integer stack for performing RPN-type calculations
  * can be self-modifying

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][2], at the bottom, contains a summary of commands.
Note that the digits 0-9, not mentioned in the table of command 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][3], 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.


[1]: http://catseye.tc/projects/befunge93/
[2]: http://catseye.tc/projects/befunge93/doc/befunge93.html
[3]: http://catseye.tc/projects/befunge93/eg/INDEX.html
[4]: http://catseye.tc/projects/funge98/
Matthew M. (Guest)
on 2008-11-25 00:06
(Received via mailing list)
Hopefully the quiz isn't intimidating... It's a fairly simple language
to implement. It took me about 30 minutes to get a simple,
straightforward version working (my submission, shown below), and I
may do some revisions later to try shrinking the code and making it
more Ruby-ish. (Also to handle some conditions not currently handled
well...) I mostly want to revise the run and step methods to be less
case-y.

Feel free to steal this and make it better, or just to look at to get
an idea of how to implement your own.


#!/usr/bin/env ruby

class Befunge93

   def self.load_and_run(filename)
     self.new(File.read(filename)).run
   end

   def initialize(text)
     rows = text.split(/[\r\n]+/)                              # split
input into rows
     @hgt = rows.size                                          # find
program height
     @wid = rows.max { |a, b| a.size <=> b.size }.size         # find
program width
     @code = rows.map { |row| row + " " * (@wid - row.size) }  # pad
rows, store code (r, c)
     @pc, @dir = [0, 0], :east
     @stack = []
     @stringmode = false
   end

   def run
     loop do
       if @stringmode
         case curr
         when ?"
           @stringmode = false
         else
           push curr
         end
       else
         case curr
         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 ?`
           b, a = pop, pop
           push (a > b ? 1 : 0)
         when ?.
           puts pop
         when ?>
           @dir = :east
         when ?<
           @dir = :west
         when ?^
           @dir = :north
         when ?v
           @dir = :south
         when ??
           @dir = [:east, :west, :north, :south][rand(4)]
         when ?_
           @dir = pop.zero? ? :east : :west
         when ?|
           @dir = pop.zero? ? :south : :north
         when ?"
           @stringmode = true
         when ?:
           push top
         when ?\\
           a = pop     # what about underflow?
           b = pop
           push a
           push b
         when ?$
           pop
         when ?.
           print pop
         when ?,
           print pop.chr
         when ?#
           step
         when ?g
           r, c = pop, pop
           push @code[r][c]
         when ?p
           r, c, v = pop, pop, pop
           @code[r][c] = v
         when ?&
           print "int?> "
           push gets.to_i
         when ?~
           print "chr?> "
           push gets[0]    # Ruby 1.8, maybe not 1.9?
         when ?@
           break
         end
       end
       step    # move program counter
     end
   end

   private

   def curr
     @code[ @pc[0] ][ @pc[1] ]
   end

   def step
     case @dir
     when :north
       @pc[0] = (@pc[0] - 1 + @hgt) % @hgt
     when :south
       @pc[0] = (@pc[0] + 1) % @hgt
     when :east
       @pc[1] = (@pc[1] + 1) % @wid
     when :west
       @pc[1] = (@pc[1] - 1 + @wid) % @wid
     end
   end

   def push(val)
     @stack.push(val)
   end

   def pop
     @stack.pop || 0
   end

   def top
     @stack.last || 0
   end
end

if __FILE__ == $0
   Befunge93.load_and_run(ARGV.shift)
end
Robert D. (Guest)
on 2008-11-25 00:56
(Received via mailing list)
On Mon, Nov 24, 2008 at 11:01 PM, Matthew M. 
<removed_email_address@domain.invalid> wrote:
> Hopefully the quiz isn't intimidating...
No but the debugger is so much work, and without the debugger there is
nothing my code does more than your's ;), but I have two weeks to
finish it ;)
I guess you have some small typos here
>        when ?.
>          puts pop
I guess this has to go
>        when ?.
>          print pop
shouldn't there be a space printed too?
>        when ?~
>          print "chr?> "
>          push gets[0]    # Ruby 1.8, maybe not 1.9?
            x= gets
            push( x.bytes.first rescue x[0] )
>    when :north
>      @pc[0] = (@pc[0] - 1 + @hgt) % @hgt
 I guess the + @hgt is a nop but ok it makes the reader more
comfortable with the code :), OTOH it took me
some time to work it's purpose out.

Cheers
Robert
--
Ne baisse jamais la tête, tu ne verrais plus les étoiles.

Robert D. ;)
Matthew M. (Guest)
on 2008-11-25 01:00
(Received via mailing list)
>>   when :north
>>     @pc[0] = (@pc[0] - 1 + @hgt) % @hgt
> I guess the + @hgt is a nop but ok it makes the reader more
> comfortable with the code :), OTOH it took me
> some time to work it's purpose out.


I tend to do (-1 + h) % h when I don't recall a language's particular
rules for dealing with negative mod.

In other words, if I don't know that (0-1)%h is safe, I do know that
(0-1+h)%h is safe and gets me what I want.
unknown (Guest)
on 2008-11-25 18:12
(Received via mailing list)
Matthew M. <removed_email_address@domain.invalid> wrote:
>        case curr
>        when ?0..?9
>          push (curr - ?0)
>        when ?+, ?-, ?*, ?/, ?%
>          b, a = pop, pop
>          push a.send(curr.to_sym, b)

My first thought was a big case statement like that, but wanted
something a bit more "fun".  My next thoughts were to try something
with lambda or define_method.  Here's a really rough, partial (and
almost entirely untested) implementation built around define_method:

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

  attr_accessor :stack, :memory, :position, :direction

  def initialize
    @stack = []
    @memory = {}
    @position = [0,0]
    @direction = [1,0]
  end

  def move
    @position[0] = (@position[0] + @direction[0]) % 80
    @position[1] = (@position[1] + @direction[1]) % 25
  end

  def run
    loop do
      send @memory[@position]
      move
    end
  end

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

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

  [
    [ '^', [ 0,-1] ],
    [ 'v', [ 0, 1] ],
    [ '<', [-1, 0] ],
    [ '>', [ 1, 0] ]
  ].each do |d|
    define_method :"#{d[0]}" do
      @direction = d[1]
    end
  end

  define_method :"." do
    print @stack.pop
  end

  define_method :"@" do
    puts
    exit
  end
end

bf = Befunge93.new

bf.memory = {
  [0,0] => "v", [1,0] => " ", [2,0] => " ", [3,0] => " ", [4,0] => " ",
  [0,1] => "1", [1,1] => "v", [2,1] => "<", [3,1] => " ", [4,1] => " ",
  [0,2] => "1", [1,2] => "3", [2,2] => "2", [3,2] => " ", [4,2] => " ",
  [0,3] => ">", [1,3] => "+", [2,3] => "^", [3,3] => " ", [4,3] => " ",
  [0,4] => " ", [1,4] => "-", [2,4] => " ", [3,4] => " ", [4,4] => " ",
  [0,5] => " ", [1,5] => ".", [2,5] => " ", [3,5] => " ", [4,5] => " ",
  [0,6] => " ", [1,6] => "@", [2,6] => " ", [3,6] => " ", [4,6] => " ",
  [0,7] => " ", [1,7] => " ", [2,7] => " ", [3,7] => " ", [4,7] => " ",
  [0,8] => " ", [1,8] => " ", [2,8] => " ", [3,8] => " ", [4,8] => " ",
}

bf.run #=> 3
Rob B. (Guest)
on 2008-11-25 18:47
(Received via mailing list)
On Nov 25, 2008, at 11:07 AM, removed_email_address@domain.invalid wrote:
>>     else
> almost entirely untested) implementation built around define_method:
>    @direction = [1,0]
>      move
>    define_method :"#{o}" do
>  ].each do |d|
>    puts
>  [0,3] => ">", [1,3] => "+", [2,3] => "^", [3,3] => " ", [4,3] => " ",
>  [0,4] => " ", [1,4] => "-", [2,4] => " ", [3,4] => " ", [4,4] => " ",
>  [0,5] => " ", [1,5] => ".", [2,5] => " ", [3,5] => " ", [4,5] => " ",
>  [0,6] => " ", [1,6] => "@", [2,6] => " ", [3,6] => " ", [4,6] => " ",
>  [0,7] => " ", [1,7] => " ", [2,7] => " ", [3,7] => " ", [4,7] => " ",
>  [0,8] => " ", [1,8] => " ", [2,8] => " ", [3,8] => " ", [4,8] => " ",
> }
>
> bf.run #=> 3

Seems like this program is:

1 1 + 2 3 + - .

Which seems to be -3, not 3.  I think you have your args out of
order.  Look at how the non-commutative ops are defined.

-Rob

Rob B.    http://agileconsultingllc.com
removed_email_address@domain.invalid
unknown (Guest)
on 2008-11-25 19:21
(Received via mailing list)
On Tue, Nov 25, 2008 at 11:42 AM, Rob B.
<removed_email_address@domain.invalid> wrote:
> at how the non-commutative ops are defined.
Yeah, that would be part of the entirely untested stuff ;-)

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

or, maybe some would prefer:
 %w{ - / }.each do |o|
   define_method :"#{o}" do
     a, b = @stack.pop, @stack.pop
     @stack.push b.send(:"#{o}", a)
   end
 end
Matthew M. (Guest)
on 2008-11-25 23:36
(Received via mailing list)
On Nov 25, 2008, at 11:15 AM, removed_email_address@domain.invalid wrote:

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

If you're going to fix the arg order of - and /, why wouldn't you do
the same for + and *?

Popping b first, then a, isn't a workaround; it's the correct method
according to spec. Why make + and * an exception to that?
Matthew M. (Guest)
on 2008-11-25 23:41
(Received via mailing list)
>
> I guess you have some small typos here
>>       when ?.
>>         puts pop
> I guess this has to go

Oops, yeah, handling . twice.

>
>>       when ?.
>>         print pop
> shouldn't there be a space printed too?

No. The following code (I think) outputs a null-terminated string
(view with monospace font):

    0"elloH"#v _@
             >.^

You wouldn't want spaces between every character.


>
>>       when ?~
>>         print "chr?> "
>>         push gets[0]    # Ruby 1.8, maybe not 1.9?
>            x= gets
>            push( x.bytes.first rescue x[0] )
>>

Nice, thanks.
Matthew M. (Guest)
on 2008-11-26 00:09
(Received via mailing list)
> No. The following code (I think) outputs a null-terminated string
> (view with monospace font):
>
>   0"elloH"#v _@
>            >.^

This one works a bit better (that is, it actually works):

037+"olleH":#v_@
              ,:
              >^
unknown (Guest)
on 2008-11-26 00:39
(Received via mailing list)
On Tue, Nov 25, 2008 at 4:30 PM, Matthew M. 
<removed_email_address@domain.invalid> wrote:
> If you're going to fix the arg order of - and /, why wouldn't you do the
> same for + and *?
>
> Popping b first, then a, isn't a workaround; it's the correct method
> according to spec. Why make + and * an exception to that?

Because I never read the spec?  :-)
(Though I did skim the wikipedia page.)

But, yeah, plus it would be much nicer to do them all at once (and
maybe throw % in too).
unknown (Guest)
on 2008-11-26 05:41
(Received via mailing list)
On Tue, Nov 25, 2008 at 11:07 AM,  <removed_email_address@domain.invalid> wrote:
> My first thought was a big case statement like that, but wanted
> something a bit more "fun".  My next thoughts were to try something
> with lambda or define_method.  Here's a really rough, partial (and
> almost entirely untested) implementation built around define_method:

Still not-tested :(, but less-incomplete:

class Befunge93
  instance_methods.each { |m| undef_method m unless (m =~ /^__|send/) }
  attr_accessor :stack, :memory, :position, :direction

  def initialize
    @stack, @memory, @position, @direction = [], {}, [0,0], [1,0]
  end

  def move
    @position[0] = (@position[0] + @direction[0]) % 80
    @position[1] = (@position[1] + @direction[1]) % 25
  end

  def run
    loop do
      send @memory[@position]
      move
    end
  end

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

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

  define_method :"!" do
    @stack.pop.zero? ? 1 : 0
  end

  define_method :"`" do
    a, b = @stack.pop, @stack.pop
    @stack.push (b > a ? 1 : 0)
  end

  define_method :":" do
    @stack.push @stack.last
  end

  define_method :"\\" do
    a, b = @stack.pop, @stack.pop
    @stack.push a; @stack.push b
  end

  define_method :"$" do
    @stack.pop
  end

  [
    [ '^', [ 0,-1] ],
    [ 'v', [ 0, 1] ],
    [ '<', [-1, 0] ],
    [ '>', [ 1, 0] ]
  ].each do |d|
    define_method :"#{d[0]}" do
      @direction = d[1]
    end
  end

  define_method :"?" do
    [[0,-1],[0,1],[-1,0],[1,0]][rand(4)]
  end

  [
    [ '_', [ 0, 1], [ 0,-1] ],
    [ '|', [ 1, 0], [-1, 0] ]
  ].each do |d|
    define_method :"#{d[0]}" do
      @direction = (@stack.pop.zero? ? d[1] : d[2])
    end
  end

  define_method :"#" do
    move
  end

  define_method :"." do
    print @stack.pop
  end

  define_method :"," do
    print @stack.pop.chr
  end

  define_method :"&" do
    push gets.to_i
  end

  define_method :"~" do
    push getc
  end

  define_method :g do
    a, b = @stack.pop, @stack.pop
    @stack.push @memory[[b,a]]
  end

  define_method :p do
    a, b, c = @stack.pop, @stack.pop, @stack.pop
    @memory[[b,a]] = c
  end

  define_method :"@" do
    puts
    exit
  end

  define_method :"\"" do
    move
    until (a = @memory[@position]) == "\""
      a[0,1].each_byte{|b| @stack.push b}
      move
    end
  end

  define_method :" " do
  end
end

bf = Befunge93.new

#bf.memory = {
#  [0,0] => "v", [1,0] => " ", [2,0] => " ", [3,0] => " ", [4,0] => " ",
#  [0,1] => "1", [1,1] => "v", [2,1] => "<", [3,1] => " ", [4,1] => " ",
#  [0,2] => "1", [1,2] => "3", [2,2] => "2", [3,2] => " ", [4,2] => " ",
#  [0,3] => ">", [1,3] => "+", [2,3] => "^", [3,3] => " ", [4,3] => " ",
#  [0,4] => " ", [1,4] => "-", [2,4] => " ", [3,4] => " ", [4,4] => " ",
#  [0,5] => " ", [1,5] => ".", [2,5] => " ", [3,5] => " ", [4,5] => " ",
#  [0,6] => " ", [1,6] => "@", [2,6] => " ", [3,6] => " ", [4,6] => " ",
#  [0,7] => " ", [1,7] => " ", [2,7] => " ", [3,7] => " ", [4,7] => " ",
#  [0,8] => " ", [1,8] => " ", [2,8] => " ", [3,8] => " ", [4,8] => " ",
#}
#bf.run #=> -3

s = ">              vv  ,,,,,\"Hello\"<>48*,
vv,,,,,,\"World!\"<>25*,@"
16.times{|a|
  5.times{|b|
    bf.memory[[a,b]] = s[a + (b * 16), 1]
  }
}

bf.run #=> "Hello World!\n"
Einar Magnús Boson (Guest)
on 2008-11-26 07:02
(Received via mailing list)
Attachment: befunge2.rb (0 Bytes)
My take on it (in ruby 1.8.6 on leopard), please tell me of unrubyesqe
(that a word?) idioms I've used.

It's less terse than it could have been but I like how it let me
define the operations (see below) and it's fun to watch in debug mode!

My definitions:
   Directions = {
     ?^ => :up,
     ?> => :right,
     ?< => :left,
     ?v => :down
   }

   [?+, ?-, ?*, ?/, ?%].each do |ch|
     mk_i(ch) { push arg2.send(ch.chr.to_sym, arg1) }
   end

   Directions.each do |ch, dir|
     mk_i(ch) { turn dir }
   end

   (?0..?9).each do |i|
     mk_i(i) { push i.chr.to_i }
   end

   mk_i(?!)  { push arg1.zero? ? 1 : 0 }
   mk_i(??)  { turn Directions.values[rand(4)] }
   mk_i(?_)  { turn(arg1 == 0 ? :right : :left) }
   mk_i(?|)  { turn(arg1 == 0 ? :down : :up) }
   mk_i(?")  { toggle_stringmode }
   mk_i(?:)  { push arg1, arg1 }
   mk_i(?\\) { push arg1, arg2 }
   mk_i(?$)  { arg1 } # discard
   mk_i(?.)  { output arg1.to_s + " " }
   mk_i(?,)  { output arg1.chr }
   mk_i(?#)  { step }
   mk_i(?g)  { push instruction_get(arg2, arg1) }
   mk_i(?p)  { instruction_set(arg2, arg1, arg3) }
   mk_i(?&)  { push get_int }
   mk_i(?~)  { push get_chr }
   mk_i(?@)  { stop }
   mk_i(?\ ) {  } #nop
   mk_i(?`)  { push(arg2 > arg1 ? 1 : 0) }


Full solution attached, run with `ruby -d befunge2.rb [input_file]` to
see what's going on, `ruby befunge.rb [input_file]` to just run
normally.
Requires the highline gem, `sudo install highline`. That was the only
way I found to get characters from STDIN without the user having to
press enter after. The paging I use is very primitive though, is there
a way to make a console-app more usable, like non-blocking input
without manual threads, and printing at specific co-ordinates of the
terminal without having to send weird control sequences? How would you
write `less` in ruby? is there an example somewhere?

Having an exception signal normal halt is not very nice, I agree, but
this is a hack.
Frank F. (Guest)
on 2008-11-26 11:36
(Received via mailing list)
Attachment: befc.rb (0 Bytes)
Hi,

This post has not much to do with a solution of the current QUIZ, but
some
ideas about extensions to the QUIZ, so feel free to stop reading (and
sorry
for bothering you).

My current solution looks almost the same as the others, so it's not so
interesting.  But the QUIZ inspired me to another funny problem: Try to
generate Befunge-code automatically:

An easy observation is, that one can split up Befunge-code into some
linear
pieces.  Each piece of code is then connected to up to two following
pieces
(by a '|' or '_', I don't look at random-jumps here).  So the problem is
the following: given some linear pieces of codes and knowing their
connections, write a program that arranges those pieces in the 80x25 (or
whatever) lattice and add the right commands to realize the required
connections.  For example, assume a program that reads to variables and
prints the greater one.  The linear pieces are:

&:01p&:11p`     ... INPUT X,Y and TEST
01g.@           ... PRINT X
11g.@           ... PRINT Y

so you have 3 pieces, and two connection (one from the first to second
and
one from the first to the third, depending on the topmost value on the
stack).

A very simple approach is to put each piece in one line, leave some
lines
empty and use that empty lines to connect the pieces.  My implementation
of
this approach is attached to this message.  The example above would
generate the following code (without the '#'):
###################
#v            > v #
#> &:01p&:11p`|>  #
#             >  v#
#                 #
#  01g.@        > #
#                 #
#                 #
#  11g.@         >#
###################

The attached program includes the euclidian algorithm as a second
example,
i.e. the program generates a Befunge-program that reads two numbers and
computes the gcd.

I can imagine two interesting tasks:

1. write some simple high-level-language that can be compiled to linear
pieces of code with the correct connections.  Together with my example
one
could create a language-to-Befunge compiler (i.e. using Befunge
as 'assembly').  The language should support conditionals (IF, THEN,
ELSE)
and loops (WHILE), and perhaps, if you're really good, subroutines (the
latter would be more challenging, I think).

2. write better arrangements of the code-pieces.  In my implementation
much
space is wasted.  Remember, linear pieces do not need to be in one line,
the may contain turns or jumps or whatever.  So one can ask
  a. how to generate very compact code
  b. how to generate code with a visually nice layout (think of a
program
     computing Pi whose code looks like a Pi :))
  c. ...

These are just a view thoughts about extensions to the nice QUIZ.

Bye,
Frank
Robert D. (Guest)
on 2008-11-26 12:34
(Received via mailing list)
>
> You wouldn't want spaces between every character.
Oops got , and . mixed up.
Robert D. (Guest)
on 2008-11-26 23:47
(Received via mailing list)
For those who want to play around I have extended Matthew's code with
some enhancements to allow
1) dynamically add lines with p
2) dump memory and stack -->nstruction ?d
3) show the stack --> ?s
4) Halt execution until <Enter> is pressed  --> ?h
5) Enabled comment mode with ?=  thus = this is ignored = to make
programs (even LOL) more readable

I found it quite helpful for debugging my Befunge programs
here it is, but the credit goes to Matthew of course.

http://pastie.org/324874

Enjoy
Robert
Robert D. (Guest)
on 2008-11-27 00:29
(Received via mailing list)
Update
> http://pastie.org/324874
in h one can enter Befunge instructions for debugging
and the current instruction shows red in the dump (H for spaces) in
ANSI terminals.
Adam S. (Guest)
on 2008-11-27 04:15
(Received via mailing list)
On Sat, Nov 22, 2008 at 8:55 AM, Matthew M. 
<removed_email_address@domain.invalid> 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 Q. #184
# requires Ruby 1.8
# -Adam S.

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)}
      (removed_email_address@domain.invalid).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
unknown (Guest)
on 2008-11-27 04:32
(Received via mailing list)
On Wed, Nov 26, 2008 at 4:41 PM, Robert D. 
<removed_email_address@domain.invalid>
wrote:
> For those who want to play around I have extended Matthew's code with
> some enhancements to allow
> 2) dump memory and stack -->nstruction ?d
> 3) show the stack --> ?s
> 5) Enabled comment mode with ?=  thus = this is ignored = to make
> programs (even LOL) more readable

Cool, I took a quick run at adding these couple of extensions to my
previous submission:

class Befunge93Extended < Befunge93
  define_method :"=" do
    move
    move until @memory[@position] == "="
  end

  define_method :"d" do
    puts
    25.times do |a|
      80.times do |b|
        print @memory[[b,a]].to_s
      end
      puts
    end
    s
  end

  define_method :"s" do
    puts
    puts "[#{@stack.join(":")}]"
  end
end

bf = Befunge93Extended.new

bf.memory = {
  [0,0] => "d", [1,0] => "v", [2,0] => " ", [3,0] => " ", [4,0] => " ",
  [0,1] => " ", [1,1] => "1", [2,1] => " ", [3,1] => " ", [4,1] => " ",
  [0,2] => " ", [1,2] => "2", [2,2] => " ", [3,2] => " ", [4,2] => " ",
  [0,3] => " ", [1,3] => "3", [2,3] => " ", [3,3] => " ", [4,3] => " ",
  [0,4] => " ", [1,4] => "s", [2,4] => " ", [3,4] => " ", [4,4] => " ",
  [0,5] => " ", [1,5] => "=", [2,5] => " ", [3,5] => " ", [4,5] => " ",
  [0,6] => ">", [1,6] => "@", [2,6] => "#", [3,6] => "<", [4,6] => " ",
  [0,7] => " ", [1,7] => "=", [2,7] => " ", [3,7] => ".", [4,7] => " ",
  [0,8] => " ", [1,8] => ">", [2,8] => ">", [3,8] => "^", [4,8] => " ",
}
bf.run #=> "program"\n[]\n\n[1:2:3]\n3
unknown (Guest)
on 2008-11-27 05:00
(Received via mailing list)
On Wed, Nov 26, 2008 at 9:32 PM,  <removed_email_address@domain.invalid> wrote:
> On Wed, Nov 26, 2008 at 4:41 PM, Robert D. <removed_email_address@domain.invalid> wrote:
>> For those who want to play around I have extended Matthew's code with
>> some enhancements
>
> Cool, I took a quick run at adding these couple of extensions to my
> previous submission:

http://gist.github.com/29673
Frank F. (Guest)
on 2008-11-27 10:46
(Received via mailing list)
Attachment: befunge3.rb (0 Bytes)
Here is one of my (more) obfuscated implementations.  It's built
around 'define_method', too, but defines a method for each cell in the
data-array, representing the command in that cell.  It seems to work
with
some of the examples from the Befunge-page, but it's pretty slow.
Jeff Dallien (Guest)
on 2008-11-30 00:35
(Received via mailing list)
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 Q. #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 Q. #184
# Jeff Dallien (removed_email_address@domain.invalid)
#
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
Adam G. (Guest)
on 2008-11-30 23:51
Attachment: Befunge.zip (0 Bytes)
Hello all,

Here's my Befunge interpreter, my first submission for a Ruby-Quiz. I'm
a relative Ruby novice, so I doubt it's as elegant or clever as some of
the other solutions, but it does work, and runs even relatively
complicated Befunge programs such as befbef.bf and life.bf. The one
exception I've found so far is mandel.bf - because I chose to store
Befunge-space values as single-character Strings, and because Ruby
Strings will not hold negative (signed) bytes, and finally because
mandel.bf relies on storing negative values in the Befunge-space grid,
it cannot run correctly. I may go back and fix this later.

I intentionally avoided looking at anyone else's solutions while I was
working on this, as I wanted to keep it a challenge for myself. This may
mean that there are some boneheaded choices in the code, but I did learn
a lot doing this, which I think is the point.

Thanks,
- Adam G.
Matthew M. (Guest)
on 2008-12-01 00:10
(Received via mailing list)
On Nov 26, 2008, at 8:54 PM, removed_email_address@domain.invalid wrote:

> http://gist.github.com/29673
>


Note that Befunge-93 was revised and extended a bit into Funge 98
(http://quadium.net/funge/spec98.html
) for those curious. I just got back from vacation, so I haven't
compared these extensions with F98's and don't know if they're similar
or not.
Robert D. (Guest)
on 2008-12-01 00:36
(Received via mailing list)
On Sun, Nov 30, 2008 at 11:04 PM, Matthew M. 
<removed_email_address@domain.invalid> wrote:
b.com/29673
>>
>
>
> Note that Befunge-93 was revised and extended a bit into Funge 98
> (http://quadium.net/funge/spec98.html) for those curious. I just got back
> from vacation, so I haven't compared these extensions with F98's and don't
> know if they're similar or not.
By all means check it out but I will share the little I have read
Funge98 is N-dimensional  but I have only seen implementation details
for 3 dimensions.
The grid is not limited in size anymore... Befunge93 was an excellent
choice for the Quiz.
:)
R.
Matthew M. (Guest)
on 2008-12-03 23:58
(Received via mailing list)
Forwarding a submission from Chris J.:

====

Here's my submission for Ruby Q. 184 ...

http://github.com/yaychris/befunge-93/tree/master

It's not interactive on the command line, instead the run method takes
a hash with two arrays, one for integer input and the other for ASCII
input. The output is a string. The test/tc_sample_programs.rb file
runs many of the example programs.

Thanks,
Chris
Michael L. (Guest)
on 2008-12-04 07:02
(Received via mailing list)
Attachment: befunge.rb (0 Bytes)
> ## Befunge (#184)

I haven't actually finished a Ruby Q. since #13. Four years is a
long time! But this one I had to do. Literally the day before the quiz
was posted I was talking with some coworkers about Befunge, Brainf*ck,
and the like. That this was the very next Ruby Q. was fate.

Because I was going slowly, I peeked at some of the answers here, I
did borrow a little. I love to use the Hash of Procs approach to the
the command pattern, which someone here talked about. Matthew's trick
using % to do the wrap-arounds was really cool, so I had to use that.

Most importantly, even before I saw all the talk about writing a
debugger, I had decided the real challenge was to make a GUI IDE for
Befunge. After looking at some options, I decided to implement it in
Rails. So that gave me a few days in which to learn Rails (I've been
procrastinating a few years on that). I also had to move my personal
web site to a Rails-friendly host (and way more Ruby/programmer
friendly, in general). So this quiz really helped me get going on my
"professional development" to-do list. :)

I didn't quite get all the way to an IDE, but it is fun to watch a
Befunge program execute. With fancy 2D graphics and 8-bit color and
everything.

I also didn't conquer the input problem, so I just have stub methods
that use random numbers for that.

So here my befunge.rb -- which acts as interpreter, debugger, and
Rails model class (you'd drop it in app/models)

If you want to see the Rails-based Befunge "IDE" in action, head over
to http://www.mikelibby.com/befunge

If anyone wants to see the relevant Rails bits, just ask and I'll put
it on GitHub.

-Michael C. Libby
www.mikelibby.com
Kay Johansen (Guest)
on 2008-12-04 15:05
(Received via mailing list)
My solution looks like, not surprisingly, a giant case statement; not
worth reprinting here.

I did write my solution test-first, here are my tests. I didn't do a
full
implementation, but it turned out sufficient to run the "beer" sample
programs.

Thank you for the quiz, Matt, it was fun!

-Kay

require 'befunge'
require 'test/unit'


class BefungeTest < Test::Unit::TestCase

   def test_output_numbers
     befunge("1234....@").expect "4321"
   end

   def test_exit
     befunge("1.@2.@").expect "1"
   end

   def test_pop_empty_stack_returns_zero
     befunge(".@").expect "0"
   end

   def test_add
     befunge("12+.@").expect "3"
   end

   def test_subtract
     befunge("73-.@").expect "4"
   end

   def test_multiply
     befunge("53*.@").expect "15"
   end

   def test_divide
     befunge("83/.@").expect "2"
   end

   def test_modulo
     befunge("73%.@").expect "1"
   end

   def test_not_nonzero_is_zero
     befunge("7!.@").expect "0"
   end

   def test_not_zero_is_one
     befunge("0!.@").expect "1"
   end

   def test_greater_than
     befunge("43`.@").expect "1"
   end

   def test_less_than
     befunge("34`.@").expect "0"
   end

   def test_equal
     befunge("44`.@").expect "0"
   end

   def test_duplicate
     befunge("5:..@").expect "55"
   end

   def test_swap
     befunge('87\..@').expect "87"
   end

   def test_skip
     befunge("5#.@").expect ""
   end

   def test_pop
     befunge("12$.@").expect "1"
   end

   def test_space_is_noop
     befunge("4 .@").expect("4")
   end

   def test_stringmode
     befunge('"A".@').expect("65")
   end

   def test_output_character
     befunge('"A",@').expect("A")
   end

   def test_left
     befunge('12#@.<@').expect('21')
   end

   def test_right
     befunge('1<>@#.').expect('1')
   end

   def test_down
     befunge( <<EOD
5v@
  .
  @
EOD
     ).expect "5"
   end

   def test_up
     befunge( <<EOD
3v@
   .
  >^@
EOD
     ).expect "3"
   end

   def test_loop_around_right
     befunge( <<EOD
   v
.@>1
EOD
     ).expect "1"
   end

   def test_loop_around_down
     befunge( <<EOD
  1v
  .
  @
  v<
EOD
     ).expect("1")
   end

   def test_if_goes_right_if_zero
     befunge("0:_.@").expect "0"
   end

   def test_if_goes_left_if_nonzero
     befunge("5:_.@").expect ""
   end

   def test_if_goes_up_if_nonzero
     befunge( <<EOD
v  >.@
>1:|@
    @
EOD
     ).expect("1")
   end

   def test_if_goes_down_if_zero
     befunge( <<EOD
v  @
>0:|@
    >.@
EOD
     ).expect("0")
   end

   def test_pad_input_lines_to_maximum_length
     befunge( <<EOD
1:v @
...
   >2^
EOD
     ).expect("1")
   end

protected

   def befunge(input)
     @befunge = Befunge.new(input)
     self
   end

   def expect(expected)
     assert_equal expected, @befunge.output
   end

end
Matthew M. (Guest)
on 2008-12-05 00:34
(Received via mailing list)
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 M.) 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...
This topic is locked and can not be replied to.