Befunge

From Esolang

Jump to: navigation, search

Befunge is a two-dimensional esoteric programming language invented in 1993 by Chris Pressey with the goal of being as difficult to compile as possible.

Contents

[edit] History

Befunge is believed to be the first two-dimensional, ASCII-based, general-purpose (in the sense of "you could plausibly write Hunt the Wumpus in it" [1]) programming language. Its form was influenced in part by the multimedia scripting application AmigaVision, and in part by Forth.

The practice of multiprogramming was probably first developed in Befunge. The wire-crossing problem was also possibly first considered in the context of Befunge.

The original Befunge (known as "Befunge-93" to distinguish it from others) has spawned many descendants and remote cousins. The closest relative, and most direct extension, of Befunge-93 is Befunge-98 of the Funge-98 family of languages. Each Funge extends the central concepts of Befunge to a given number of dimensions (for example, Unefunge is one-dimensional, Trefunge is three-dimensional, Nefunge is n-dimensional, etc.).

[edit] Etymology

The word "Befunge" started life as a typographical error for the word "before", typed by Curtis Coleman at 4AM on a BBS chat system.

It was then reverse-endowed with a fictional morphology where it took on the meaning Be- (a corruption of the prefix bi-, for "two") + funge (fictional root of the word fungible, i.e. "interchange"). That is, to interchange (program codes with data) in two (dimensions).

The name is pronounced /bee-FUNJ/.

[edit] Language overview

A Befunge program consists of a two-dimensional playfield of fixed size. The playfield is initially loaded with the instructions of the program. It also doubles as an updateable storage unit.

Execution proceeds by the means of a program counter (-93) or instruction pointer (-98). The instruction pointer begins at a set location (the upper-left corner of the playfield) and is initially travelling in a set direction (right). As it encounters instructions, they are executed. The instructions may have an effect on the instruction pointer's direction and position (-98 only). The following, for example, is literally an infinite loop: 

>v
^<

Instructions may also affect the contents of a stack in the manner of Forth.

[edit] Instructions

Befunge-93 has the following commands:

Command Description
+ Add two top stack values
- Subtract two top stack values
* Multiply two top stack values
/ Division
% Modulo division
! Logical NOT
` Greater Than
> PC direction right
< PC direction left
^ PC direction up
v PC direction down
? Random PC direction
_ Horizontal IF
| Vertical IF
" Toggle stringmode
: Duplicate top stack value
\ Swap top stack values
$ Pop (remove) top stack value
. Output integer
, Output ASCII
# Bridge: jump over next command
g Get value from code
p Put value at code
& Input integer
~ Input character
@ End program
0 through 9 Push corresponding value onto the stack

[edit] Computational class

Because Befunge-93 programs are given an explicit limit of 80x25 cells on the size of their playfield, but are also given a working stack, any Befunge-93 program should be simulatable by a push-down automaton.

However, the converse is not true; there surely exist some push-down automata which cannot be simulated by any Befunge-93 program (because they contain more states than can be encoded in the 80x25 playfield).

Befunge-98 removes the fixed-size restriction on the playfield, and thus should be Turing-complete.

[edit] Compilation

As stated, the design goal for Befunge was to create a language which was difficult to compile. This was realized by two main features:

  • self-modifying - the p instruction can write new instructions into the playfield; and
  • multi-dimensional - the same instruction can be executed in four different contexts (in a left-to-right series of instructions, or right-to-left, or upward or downward.)

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

The bf2c 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 bf2c compiler is not correct since it does not handle p correctly, but it would not be impossible to make it do so (although the C language might not be well-suited for this.)

The Betty compiler, for example, treats every possible straight line of instructions as a subprogram, and if a p instruction alters that subprogram, that subprogram is recompiled. This is an interesting variation on just-in-time compilation, and it results in a much better advantage over an interpreter, since many instructions can be executed in native code without making intervening decisions on the 'direction' register.

There are also programs which combine a Befunge interpreter and a copy of a given Befunge program into a single executable, which runs the Befunge program when started. This might be considered a sort of pathological version of threaded code, and while it produces a similar effect as a compiler, that is, it generates a "native executable", it is not really considered the same thing. Sometimes such a tool is called a pseudo-compiler or linker. Tim's Befunge Compiler is one example.

[edit] Examples

Hello, world! 

<v"Hello world"0
 <,_@#:

Unix cat 

~:1+!#@_,

Factorial 

0&>:1-:v v *_$.@ 
  ^    _$>\:^

Sieve of Eratosthenes 

2>:3g" "-!v\  g30          <
 |!`"O":+1_:.:03p>03g+:"O"`|
 @               ^  p3\" ":<
2 234567890123456789012345678901234567890123456789012345678901234567890123456789

[edit] Related languages

Befunge was preceded in 1991 by a similar but less featureful language Biota, which was designed for experiments in self-reproduction. It was followed soon after, in 1994, by another similar language, Orthagonal, the design of which was spurred by a discussion on alt.folklore.computers. Each of these three languages originated (as far as anyone can tell) completely independently of the other two.

Befunge has also provided inspiration to the design of subsequent languages, the most similar of these are known as fungeoids. Most of the languages are not similar enough to be called direct descendants, but often the author mentions the influence of Befunge in the accompanying commentary. Such languages include Wierd, a two-dimensional Turing tarpit; Befreak, a reversible language; and PATH, which combines in elements of Brainfuck.

[edit] External resources

Retrieved from "http://www.esolangs.org/wiki/Befunge"
Personal tools