|
Befunge is a stack-based esoteric programming language which differs from conventional languages in that programs are arranged on a two-dimensional grid. "Arrow" instructions direct the control flow to the left, right, up or down, and loops are constructed by sending the control flow in a circle.
History
The language was originally created by Chris Pressey in 1993, as an attempt to devise a language as hard to compile as possible — note that the p command allows for self-modifying code. Nevertheless, a number of compilers have subsequently been written. A number of extensions to the original "Befunge-93" specification also exist, including Funge-98, which extends the concept to an arbitrary number of dimensions and can be multithreaded, with multiple instruction pointers operating simultaneously on the same space. Befunge-extensions and variants are called Fungeoids or just Funges.
The original specification restricts each valid Befunge program to a grid of 80 characters horizontally by 25 characters vertically. Thus, since a Befunge-93 program can only have a single stack and its storage array is bounded, the original Befunge-93 language is not Turing-complete. The later Funge-98 extensions provide Turing-completeness by adding the concept of "modes," including a "queue mode" in which certain instructions are redefined to make the data stack into a queue. Funge-98 programs can also be of unbounded extent; rather than wrapping around at the 80-column mark, a Funge-98 instruction pointer will obey the wrapping rules of what Chris Pressey has dubbed "Lahey-space," a model in which the grid behaves like a torus but still allows arbitrary expansion of the "active" grid area.
Sample Befunge code
The technique of using arrows to change control flow is demonstrated in the random number generator program below. The ? instruction sends the instruction pointer in a random cardinal direction.
vv < <
2
^ v<
v1<?>3v4
^ ^
> >?> ?>5^
v v
v9<?>7v6
v v<
8
. > > ^
^<
Instruction list
0-9 | Push this number on the stack |
+ | Addition: Pop a and b, then push a+b |
- | Subtraction: Pop a and b, then push b-a |
* | Multiplication: Pop a and b, then push a*b |
/ | Integer division: Pop a and b, then push b/a, rounded down. If a is zero, ask the user what result they want. |
% | Modulo: Pop a and b, then push the remainder of the integer division of b/a. If a is zero, ask the user what result they want. |
! | Logical NOT: Pop a value. If the value is zero, push 1; otherwise, push zero. |
` | Greater than: Pop a and b, then push 1 if b>a, otherwise zero. |
> | Start moving right |
< | Start moving left |
^ | Start moving up |
v | Start moving down |
? | Start moving in a random cardinal direction |
_ | Pop a value; move right if value=0, left otherwise |
| | Pop a value; move down if value=0, up otherwise |
" | Start string mode: push each character's ASCII value all the way up to the next " |
: | Duplicate value on top of the stack |
\ | Swap two values on top of the stack |
$ | Pop value from the stack |
. | Pop value and output as an integer |
, | Pop value and output as ASCII character |
# | Trampoline: Skip next cell |
g | Pop y and x, then push ASCII value of the character at that position in the program |
p | Pop y, x and v, then change the character at the position (x,y) in the program to the character with ASCII value v |
& | Ask user for a number and push it |
~ | Ask user for a character and push its ASCII value |
@ | End program |
See also
External links
|
