Befunge

Befunge is an esoteric, funge-oid, reflective, and stack-based programming language. It differs from conventional languages in that programs are arranged on a two-dimensional grid. The instructions "arrow" they direct the flow control up, down, left, or right, and loops are built by directing the flow control in a circle.

History

Befunge was created by Chris Pressey in 1993 in an attempt to make a language as difficult to compile as humanly possible (note that the p command introduces the possibility of mutating code). However several compilers have been written. There are also several extensions to the original "Befunge-93" specification, including Funge-98, which extends the concept to an arbitrary number of dimensions and supports multiple threads of execution, with multiple instruction pointers operating simultaneously on the same space. Extensions and variants of Befunge are called Fungeoides or simply Funges.

The Befunge-93 specification restricts each valid program to a grid of 80*25 instructions (horizontal and vertical, respectively). If the execution of a program exceeds these limits, it "jumps" to a corresponding point on the other side of the grid; thus a program in Befunge is the topological equivalent of a torus. Since a Befunge-93 program can only have one stack and is limited in its storage space, the Befunge-93 language is not Turing complete, unlike most machine languages. The later Funge-98 specification provides Turing-completeness by removing restrictions on program size: instead of simply jumping to an opposite point at a fixed limit, the movement of a Funge-98 instruction pointer follows a pattern called " Lahey" in honor of its creator, Chris Lahey. In this model, the grid behaves like a torus of finite size with respect to these jumps, but it can be extended indefinitely.

Sample code in Befunge-93

We demonstrate the technique of using arrows to change flow control in the following random number generator program. Following the arrows, the ? commands send the command pointer in random cardinal directions until the pointer hits a digit, pushing it onto the stack. The arrows then navigate to . to pop the digit off the stack and return the pointer to the first directional scrambler. Notice that there is no @ to terminate this program, so it produces random numbers from 1 to 9 continuously.

vv Δ
2
^ v
v1 tax?
^
한? ?
v
v9 tax?
v
8
. .
^

This is an example of the classic "Hello world!" program. First the letters "olleH" as ASCII numbers. They are then popped from the stack in LIFO order and displayed as text characters to give "Hello". The space is character 32 in ASCII, which here is constructed by multiplying 4 by 8, before starting the text output. The rest of the code similarly displays "World!", followed by the ASCII character 10 (a line break).

▪ v
v,,, "Hello"
한48*, v
v,,,, "World!"
한25*,@

Instruction list for Befunge-93