[QUIZ] Befunge (#184)


M

Matthew Moss

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

The three rules of Ruby Quiz 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 Quiz 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 Talk 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:
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/
 
Ad

Advertisements

M

Matthew Moss

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 [email protected]
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
 
R

Robert Dober

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=3D gets
push( x.bytes.first rescue x[0] )
when :north
@pc[0] =3D (@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
--=20
Ne baisse jamais la t=EAte, tu ne verrais plus les =E9toiles.

Robert Dober ;)
 
M

Matthew Moss

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

brabuhr

Matthew Moss said:
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)

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
 
R

Rob Biedenharn

Matthew Moss said:
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)

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

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 Biedenharn http://agileconsultingllc.com
(e-mail address removed)
 
Ad

Advertisements

B

brabuhr

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.

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
 
M

Matthew Moss

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

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

Matthew Moss

I guess you have some small typos here
I guess this has to go

Oops, yeah, handling . twice.
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 [email protected]

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

brabuhr

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

Advertisements

B

brabuhr

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

Frank Fischer

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
[email protected] ... PRINT X
[email protected] ... 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#
# #
# [email protected] > #
# #
# #
# [email protected] >#
###################

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
 
R

Robert Dober

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
 
Ad

Advertisements

A

Adam Shelly

## 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 Quiz #184
# requires Ruby 1.8
# -Adam Shelly

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
@[email protected]=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
@[email protected]_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{ @[email protected]_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) }],
[email protected] =>[: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)}
([email protected]).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 [email protected]
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
[email protected][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 && [email protected]_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
@[email protected][-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
 
B

brabuhr

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
 
Ad

Advertisements

J

Jeff Dallien

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 Quiz #85 have some methods which provide C-like division and
mod.

3-2/[email protected]

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 Quiz #184
# Jeff Dallien ([email protected])
#
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,
',' => :eek:utput_ascii,
'.' => :eek:utput_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 = [email protected]_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([" @",
"[email protected]",
"@@@@"])
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(["[email protected]"]) }.should raise_error(/Unknown
instruction/)
end
end

describe "add instruction" do
before :each do
run_program(["[email protected]"])
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(["[email protected]"])
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(["[email protected]"])
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:mad:"])
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(["[email protected]"])
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(["[email protected]"])
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(["[email protected]"])
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#[email protected]"])
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+*[email protected]"])
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(["[email protected]",
" * "])
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(["[email protected]"])
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*[email protected]"]) }.should raise_error
end
end
end

describe "put instruction" do
describe "within the 80x25 program space" do
before :each do
run_program(["[email protected]"])
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*[email protected]"]) }.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(["[email protected]",
" @ ",
">[email protected]"])
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([" [email protected]"])
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 ",
"[email protected] > ",
" @ "])
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(["[email protected] ",
">[email protected]",
" @ "])
end

it "should set the program counter direction based on the random
number" do
@pc.direction.should == :up
end
end
end
end
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top