Befunge

related topics
{math, number, function}
{system, computer, user}
{@card@, make, design}
{album, band, music}
{line, north, south}

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

Contents

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 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, most notably 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 (however, it has been shown that Befunge-93 is Turing Complete with unbounded stack word size).[1] 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.

Compilation

As stated, the design goal for Befunge was to create a language which was difficult to compile. This was attempted with the implementation of self-modifying code (the 'p' instruction can write new instructions into the playfield) and a multi-dimensional playfield (the same instruction can be executed in four different directions).

Nevertheless, these obstacles have been overcome, to some degree, and Befunge compilers have been written using appropriate techniques.

The bef2c compiler included with the standard Befunge-93 distribution uses threaded code: each instruction is compiled to a snippet of C code, and control flows through the snippets just as it does in a Befunge interpreter (that is, conditionally on the value of some 'direction' register.) This does not result in a significant advantage over a good interpreter. Note that the bef2c compiler is not correct since it does not handle either 'p' or string mode, but it would not be impossible to make it do so (although the C language might not be well-suited for this).

Full article ▸

related documents
Finite state machine
Brute force attack
Selection sort
Fundamental theorem of arithmetic
Pell's equation
Delaunay triangulation
Binomial theorem
Tensor
Naive Bayes classifier
Affine transformation
Greatest common divisor
Polish notation
Brouwer fixed point theorem
Knapsack problem
Empty set
NP (complexity)
Direct product
Net (mathematics)
Grover's algorithm
Shell sort
Scientific notation
MathML
Curve
Graph theory
Tree automaton
Sheffer stroke
Cyclic group
Ordered pair
Root-finding algorithm
Partially ordered set