git @ Cat's Eye Technologies Befunge-93 / rel_2_22_2011_0318 doc / befunge93.html
rel_2_22_2011_0318

Tree @rel_2_22_2011_0318 (Download .tar.gz)

befunge93.html @rel_2_22_2011_0318raw · history · blame

<html><head><title>Befunge-93 Documentation</title></head>
<body>
<center><H1>Befunge-93 Documentation</H1>
<hr><font size=+1>
<i>Twisted, Deranged Programming Language in the
Tradition of </i><a href="http://www.muppetlabs.com/~breadbox/bf/">Brainf*ck</a>
<i>and</i> <a href="http://wouter.fov120.com/false/">False</a></font><p>
Chris Pressey, Cat's Eye Technologies<br>
<i>Original document September, 1993</i><br>
<i>Updated December, 1996</i><br>
<i>Updated Yet Again September, 2004</i><br>
</center>
<h3>The Basics of Befunge-93</h3>

<p>Most likely the most unique element of Befunge-93 programming is the
Program Counter (PC.)  In almost all computer programming languages,
the program counter is continually moving forward through the program,
occassionally jumping to another spot in the code (but continuing 
forward thereafter, nonetheless.)</p>

<p>The PC in Befunge-93, however, is subject to different rules.  It
may go <i>forward, backward, left, or right</i>.  A Befunge-93 program
is treated as an 80x25 torus (a page which wraps around on the edges)
of ASCII text.  Certain commands change the direction of the progress
of the PC.  By default, the PC points to the upper-left
corner of the program, and is oriented to travel left-to-right.</p>

<p>Each command in Befunge-93 is a single character, as is the largest
data unit that can be specified in the program source; Befunge-93 programs
have a maximum size of 80x25 total commands and data bytes.  There are
no run-time variables, only a single run-time stack.  Befunge-93 programs
allow for self-modification.  Due to the 2-dimensional nature of the PC,
they also allow for some extremely quirky code.</p>

<h3>The Stack</h3>

<p>Something like Forth and PostScript, Befunge-93 supports a LIFO, 
Reverse Polish Notation (RPN or <i>postfix</i>) stack of signed long 
integers (that is, each cell of the stack can hold as much as a C language
<code>signed long int</code> on the same platform.)  The act of
placing a value on the stack is called 
<i>pushing</i>, and the act of taking a value off the stack is 
called <i>popping</i>.  The digits from <code>0</code> to <code>9</code> are valid 
Befunge-93 commands which push their respective values
onto the stack.  A double quote <code>"</code>, when encountered, toggles 
<i>stringmode</i>, and while stringmode is active, all character 
cells will have their ASCII value
pushed onto the stack until another <code>"</code> is located.</p>

<p>There are a few basic calculation commands:
<ul>
<li><code>+</code> addition</li>
<li><code>-</code> subtraction</li>
<li><code>/</code> integer division
<li><code>*</code> multiplication
<li><code>%</code> modulo
<li><code>!</code> logical negation
</ul>
These are explained in greater detail in the Commands section.</p>

<p>In order to push a number greater than 9 on the stack, calculations
must be done with numbers less than or equal to 9.  In any other 
language
this would be a pain.  In Befunge-93 it is a joy.  For example, to 
push '123' onto the stack, one might push 9, then 9, then multiply 
(leaving 81), then push 7, then 6, then multiply (leaving 81 and 
42,) then add (leaving 123.)  In Befunge, this would look something
like :
<ul>
<code>99*76*+</code>
</ul>
This is, of course, assuming that the PC starts at or
before the first <code>9</code> and is working towards the right.
If this snippet represents a entire Befunge-93 program, this
assumption is correct: the PC starts at the upper-left of the
torus and is initially oriented to execute rightward.</p>

<p>NB.  If the stack is be empty when you pop something off,
be warned that this will <i>not</i> generate an underflow!  It will 
simply push a 0 value onto the stack.  Hope you can live with it!</p>

<h3>The Program Counter in Detail</h3>

<p>There are 5 commands which unconditionally control the PC direction:
<code>&gt;</code>, <code>&lt;</code>, <code>v</code>, <code>^</code>,
and <code>?</code>.  <code>&gt;</code> makes the PC travel to the right; 
<code>&lt;</code> to the left; <code>v</code> down; <code>^</code> up;
and <code>?</code> in a <i>random</i> direction.  So, the following
example is an infinite loop:
<ul>
<code>&gt;&lt;</code>
</ul>
As is:
<ul>
<code>&gt;v<br>^&lt;</code>
</ul>
As is:
<ul>
<code>&gt;v&gt;v<br>&nbsp;&gt;^<br>^&nbsp;&nbsp;&lt;</code>
</ul>
Note that <code>&nbsp;</code> (space) is a null command which does nothing.</p>

<p>Should the PC encounter the 'edge' of the program, such as if 
you were to try to execute:
<ul>
<code>&lt;</code>
</ul>
The PC will 'wrap around' to the other 'edge' of the program.  This example,
then, is an infinite loop as well.</p>

<h3>Decision Making</h3>

<p>The standard 'if' statement in Befunge-93 is either
<code>_</code> or <code>|</code>, depending
on how you want to branch.  Both of these instructions
pop a value off the stack and check to
see if it is true (non-zero,) and change the direction of the PC
accordingly:

<ul>
<li><code>_</code> acts like <code>&lt;</code> if the value is true or <code>&gt;</code> if it is false; and</li>
<li><code>|</code> acts like <code>^</code> if the value is true or <code>v</code> if it is false.</li>
</ul>
</p>

<p>'While' loops can be made by sticking an 'if' in an infinite loop.
For example,
<ul>
<code>&gt;_@</code>
</ul>
(This program fragment pops all of the non-zero values off the
stack, and the first zero value, then exits [<code>@</code> is the exit command.])</p>

<h3>Input</h3>

<p>The <code>&amp;</code> (ampersand) command will get a numeric value (in decimal)
from the standard input and
push it on the stack.  <code>~</code> (tilde) will get the next ASCII character from 
standard
input and push it on the stack.</p>

<p>For example,
<ul>
<code>&,</code>
</ul>
...prints out "A" if the user types "65 ", and...
<ul>
<code>~.</code>
</ul>
...prints out "65 " if the user types "A".</p>

<h3>Output</h3>

<p>The <code>.</code> command will pop a value off the stack and output it as
a decimal integer, followed by a space, somewhat like Forth.  <code>,</code> will 
pop a value, interpret it as the ASCII value of a character, and output that character
(not followed by a space.)</p>

<p>For example,

<ul>
<code>665+*1-,</code>
</ul>
...prints out ASCII 65 ("A".), and...
<ul>
<code>665+*1-.</code>
</ul>
...prints out "65 ".</p>

<h3>Special Commands</h3>

<p><code>#</code> is the 'bridge' command... it causes the next command which would
normally be executed to be skipped over, and not executed.  For 
example,

<ul>
<code>&gt;123...@</code>
</ul>

would output "3 2 1 ", but

<ul>
<code>&gt;123#...@</code>
</ul>

would output "3 2 " with one of the '.''s being skipped.  Judicious 
use of <code>#</code> can make for very interesting code!</p>

<p><code>:</code> is the duplication command.  It makes a copy of the top element
of the stack.  This is useful, as demonstrated in the following program:

<ul>
<code>v.&lt;&gt;:|  @</code>
</ul>

This program makes duplicates of each value on the stacked, which is checked,
 and if non-zero, printed.</p>

<p><code>$</code> pops a value off the stack, but does nothing with it.  So,

<ul>
<code>123.$.@</code>
</ul>

results in "3 1 ".</p>

<p><code>\</code> swaps the top two elements of the stack.  So,

<ul>
<code>123\...@</code>
</ul>

results in "2 3 1 ".</p>

<p><code>`</code> (back-quote) is the 'greater-than' command.  It compares the top two 
values on the stack, and returns '1' if the first is greater than the 
second.  For example,

<ul>
<code>65`.</code>
</ul>

...outputs "1 " and...

<ul>
<code>25`.</code>
</ul>

...outputs "0 ".</p>

<h3>Self-Modification</h3>

<p>The last two commands that need to be explained are the ones that allow you to
examine and change the contents of the torus where the program is stored.  This
'playfield' can be used for auxilliary storage when the stack alone will not suffice,
but keep in mind that it also contains the running program.</p>

<p>The <code>g</code> command examines the contents of the playfield.
It pops a <i>y</i> coordinate off the stack, then an <i>x</i> coordinate.  It pushes the
value found at (<i>x</i>, <i>y</i>) onto the stack.  If the thing at (<i>x</i>, <i>y</i>)
is a Befunge-93 instruction, the value pushed will be the ASCII value of that
character.  From the point of view of the program text, <i>x</i> determines
the column and <i>y</i> determines the row; (0, 0) refers to the first (leftmost)
column and the first (topmost) row of the program source.</p>

<p>The <code>p</code> command alters the contents of the playfield.
It pops a <i>y</i> coordinate off the stack, then an <i>x</i> coordinate, and then
a value.  It places the value into the torus at (<i>x</i>, <i>y</i>).  If the program,
at some later point, executes the instruction at (<i>x</i>, <i>y</i>), it will be the
interpreted as the Befunge instruction in the ASCII character set with the same
value as was put there with the <code>p</code> instruction.</p>

<h3>Appendix A.  Command Summary</h3>

<pre>COMMAND         INITIAL STACK (bot->top)RESULT (STACK)
-------         -------------           -----------------
+ (add)         &lt;value1&gt; &lt;value2&gt;       &lt;value1 + value2&gt;
- (subtract)    &lt;value1&gt; &lt;value2&gt;       &lt;value1 - value2&gt;
* (multiply)    &lt;value1&gt; &lt;value2&gt;       &lt;value1 * value2&gt;
/ (divide)      &lt;value1&gt; &lt;value2&gt;       &lt;value1 / value2&gt; (nb. integer)
% (modulo)      &lt;value1&gt; &lt;value2&gt;       &lt;value1 mod value2&gt;
! (not)         &lt;value&gt;                 &lt;0 if value non-zero, 1 otherwise&gt;
` (greater)     &lt;value1&gt; &lt;value2&gt;       &lt;1 if value1 &gt; value2, 0 otherwise&gt;
&gt; (right)                               PC -&gt; right
&lt; (left)                                PC -&gt; left
^ (up)                                  PC -&gt; up
v (down)                                PC -&gt; down
? (random)                              PC -&gt; right? left? up? down? ???
_ (horizontal if) &lt;boolean value&gt;       PC-&gt;left if &lt;value&gt;, else PC-&gt;right
| (vertical if)   &lt;boolean value&gt;       PC-&gt;up if &lt;value&gt;, else PC-&gt;down
" (stringmode)                          Toggles 'stringmode'
: (dup)         &lt;value&gt;                 &lt;value&gt; &lt;value&gt;
\ (swap)        &lt;value1&gt; &lt;value2&gt;       &lt;value2&gt; &lt;value1&gt;
$ (pop)         &lt;value&gt;                 pops &lt;value&gt; but does nothing
. (pop)         &lt;value&gt;                 outputs &lt;value&gt; as integer
, (pop)         &lt;value&gt;                 outputs &lt;value&gt; as ASCII
# (bridge)                              'jumps' PC one farther; skips
                                        over next command
g (get)         &lt;x&gt; &lt;y&gt;                 &lt;value at (x,y)&gt;
p (put)         &lt;value&gt; &lt;x&gt; &lt;y&gt;         puts &lt;value&gt; at (x,y)
& (input value)                         &lt;value user entered&gt;
~ (input character)                     &lt;character user entered&gt;
@ (end)                                 ends program</pre>

<h3>The People Who Helped Make the Dream Reality</h3>

<p>Special thanks to Curtis Coleman, Jason Goga, Kalyna Zazelenchuk, Shawn Vincent, 
Mike Veroukis, Urban Mueller, and Wouter van Oortmerssen.</p>

</body>
</html>