Befunge

From Wikipedia, the free encyclopedia

Befunge is a stack-based, reflective, esoteric programming language. It 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.

1 History
2 Sample Befunge-93 code
3 Befunge-93 instruction list
4 See also
5 External links

[edit] History

The language was originally created by Chris Pressey in 1993 as an attempt to devise a language which is as hard to compile as humanly 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 Befunge-93 specification restricts each valid program to a grid of 80 instructions horizontally by 25 instructions vertically. Program execution which exceeds these limits "wraps around" to a corresponding point on the other side of the grid; a Befunge program is in this manner topologically equivalent to a torus. Since a Befunge-93 program can only have a single stack and its storage array is bounded, the Befunge-93 language is, unlike most machine languages, not Turing-complete. The later Funge-98 specification provides Turing-completeness by removing the size restrictions on the program; rather than wrapping around at a fixed limit, the movement of a Funge-98 instruction pointer follows a model dubbed "Lahey-space" after its originator, Chris Lahey. In this model, the grid behaves like a torus of finite size with respect to wrapping, while still allowing itself to be extended indefinitely.

[edit] Sample Befunge-93 code

The technique of using arrows to change control flow is demonstrated in the random number generator program below. Following the arrows round, the ? instructions send the instruction pointer in random cardinal directions until the pointer hits a digit, pushing it to the stack. Then the arrows navigate to the . to output the digit from the stack and return the pointer to the first directional randomiser. Note that there is no @ to terminate this program so it produces an endless stream of random numbers from 1 to 9.

vv  <      <
    2
    ^  v<
 v1<?>3v4
    ^   ^
>  >?>  ?>5^
    v   v
 v9<?>7v6
    v  v<
    8
 .  >  >   ^
^<

This is an example of the classic "Hello World!" program. First the letters "olleH" are pushed onto the stack as ASCII numbers. These are then popped from the stack in LIFO order and output as text characters to give "Hello". A space is character number 32 in ASCII, which here is constructed by multiplying 4 and 8, before being output as text. The remaining code then outputs "World!" in a similar way, followed by ASCII character 10 (a line feed character, moving the output cursor to a new line).

>              v
v  ,,,,,"Hello"<
>48*,          v
v,,,,,,"World!"<
>25*,@

[edit] Befunge-93 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
`p`	A "put" call (a way to store a value for later use). Pop y, x and v, then change the character at the position (x,y) in the program to the character with ASCII value v
`g`	A "get" call (a way to retrieve data in storage). Pop y and x, then push ASCII value of the character at that position in the program
`&`	Ask user for a number and push it
`~`	Ask user for a character and push its ASCII value
`@`	End program