Befunge (#184)


#1

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

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


#2

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


#3

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.


#4

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


#5

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


#6

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


#7

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 :wink:

%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


#8

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.


#9

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?


#10

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? :slight_smile:
(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).


#11

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_@
,:
>^


#12

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(?:slight_smile: { 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.


#13

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 :stuck_out_tongue: 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”


#14

You wouldn’t want spaces between every character.
Oops got , and . mixed up.


#15

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


#16

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


#17

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.


#18

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


#19

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, ®un, (b)reak x,y, ©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


#20

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.