Befunge
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 cycle.
. Nevertheless, a number of compiler
s 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). 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.
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).
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.
The BFC (BeFunge Compiler) for Win32 written by Andrew Carter (Uranium-239), simply uses a self-executing stub and modifies the preallocated 80x25 byte matrix inside the stub to execute any given befunge program. The negative effects of this technique include having an interpreter attached to every Befunge program. However, using optimization tricks, BFC V1.1 guarantees an executable size of only 5632 bytes.
v>>>>.
12345
^?^
> ? ?^
v?v
v6789>
The following code 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*,@
The following code is a slightly more complicated version. It adds the ASCII character 10 (a line feed character) to the stack, and then pushes "!dlrow ,olleH" to the stack. Again, LIFO ordering means that "H" is now the top of the stack and will be the first printed, "e" is second, and so on. To print the characters, the program enters a loop that first duplicates the top value on the stack (so now the stack would look like "\n!dlrow ,olleHH". Then the "_" operation will pop the duplicated value, and go right if it's a zero, left otherwise. (This assumes a compliant interpreter that "returns" 0 when popping an empty stack.) When it goes left, it pops and prints the top value as an ASCII
character. It then duplicates the next character and loops back to the "_" test, continuing to print the rest of the stack until it is empty and so the next value popped is 0, at which point "@" ends the program.
>25*"!dlrow ,olleH":v
v:,_@
> ^
Most one-dimensional programming languages require some syntactic distinction between comment text
and source code
— although that distinction may be as trivial as Brainfuck
's rule that any character not in the set
treat strings as comments in contexts where the values are not used. Similarly, in Befunge, there is no comment syntax: to embed documentation in the code, the programmer simply routes the control flow around the "comment" area, so that the text in that area is never executed.
Stack-oriented programming language
A stack-oriented programming language is one that relies on a stack machine model for passing parameters. Several programming languages fit this description, notably Forth, RPL, PostScript, and also many Assembly languages ....
, reflective
Reflection (computer science)
In computer science, reflection is the process by which a computer program can observe and modify its own structure and behavior at runtime....
, esoteric
Esoteric programming language
An esoteric programming language is a programming language designed as a test of the boundaries of computer programming language design, as a proof of concept, or as a joke...
programming language
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
. 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.
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 thep command allows for self-modifying codeSelf-modifying code
In computer science, self-modifying code is code that alters its own instructions while it is executing - usually to reduce the instruction path length and improve performance or simply to reduce otherwise repetitively similar code, thus simplifying maintenance...
. Nevertheless, a number of compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
s 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"
Integer overflow
In computer programming, an integer overflow occurs when an arithmetic operation attempts to create a numeric value that is too large to be represented within the available storage space. For instance, adding 1 to the largest value that can be represented constitutes an integer overflow...
to a corresponding point on the other side of the grid; a Befunge program is in this manner topologically
Topology
Topology is a major area of mathematics concerned with properties that are preserved under continuous deformations of objects, such as deformations that involve stretching, but no tearing or gluing...
equivalent to a torus
Torus
In geometry, a torus is a surface of revolution generated by revolving a circle in three dimensional space about an axis coplanar with the circle...
. 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). 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).
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
Just-in-time compilation
In computing, just-in-time compilation , also known as dynamic translation, is a method to improve the runtime performance of computer programs. Historically, computer programs had two modes of runtime operation, either interpreted or static 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.
The BFC (BeFunge Compiler) for Win32 written by Andrew Carter (Uranium-239), simply uses a self-executing stub and modifies the preallocated 80x25 byte matrix inside the stub to execute any given befunge program. The negative effects of this technique include having an interpreter attached to every Befunge program. However, using optimization tricks, BFC V1.1 guarantees an executable size of only 5632 bytes.
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 around, 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.v>>>>.
12345
^?^
> ? ?^
v?v
v6789>
The following code is an example of the classic "Hello World!" program
Hello world program
A "Hello world" program is a computer program that outputs "Hello world" on a display device. Because it is typically one of the simplest programs possible in most programming languages, it is by tradition often used to illustrate to beginners the most basic syntax of a programming language, or to...
. First the letters "olleH" are pushed onto the stack as ASCII
ASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
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*,@
The following code is a slightly more complicated version. It adds the ASCII character 10 (a line feed character) to the stack, and then pushes "!dlrow ,olleH" to the stack. Again, LIFO ordering means that "H" is now the top of the stack and will be the first printed, "e" is second, and so on. To print the characters, the program enters a loop that first duplicates the top value on the stack (so now the stack would look like "\n!dlrow ,olleHH". Then the "_" operation will pop the duplicated value, and go right if it's a zero, left otherwise. (This assumes a compliant interpreter that "returns" 0 when popping an empty stack.) When it goes left, it pops and prints the top value as an ASCII
ASCII
The American Standard Code for Information Interchange is a character-encoding scheme based on the ordering of the English alphabet. ASCII codes represent text in computers, communications equipment, and other devices that use text...
character. It then duplicates the next character and loops back to the "_" test, continuing to print the rest of the stack until it is empty and so the next value popped is 0, at which point "@" ends the program.
>25*"!dlrow ,olleH":v
v:,_@
> ^
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 |
Most one-dimensional programming languages require some syntactic distinction between comment text
Comment (computer programming)
In computer programming, a comment is a programming language construct used to embed programmer-readable annotations in the source code of a computer program. Those annotations are potentially significant to programmers but typically ignorable to compilers and interpreters. Comments are usually...
and source code
Source code
In computer science, source code is text written using the format and syntax of the programming language that it is being written in. Such a language is specially designed to facilitate the work of computer programmers, who specify the actions to be performed by a computer mostly by writing source...
— although that distinction may be as trivial as Brainfuck
Brainfuck
The brainfuck programming language is an esoteric programming language noted for its extreme minimalism. It is a Turing tarpit, designed to challenge and amuse programmers, and is not suitable for practical use...
's rule that any character not in the set
+-[]<>,. Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...
treat strings as comments in contexts where the values are not used. Similarly, in Befunge, there is no comment syntax: to embed documentation in the code, the programmer simply routes the control flow around the "comment" area, so that the text in that area is never executed.
See also
- brainfuckBrainfuckThe brainfuck programming language is an esoteric programming language noted for its extreme minimalism. It is a Turing tarpit, designed to challenge and amuse programmers, and is not suitable for practical use...
- Carnage HeartCarnage HeartCarnage Heart is a video game for the PlayStation, developed by Artdink. Its gameplay is a mecha-based, turn-based strategy game, where the player takes the role of a commander in a war fought by robots...
- Playstation programming game using a similar language - INTERCALINTERCALINTERCAL, a programming language parody, is an esoteric programming language that was created by Don Woods and James M. Lyon, two Princeton University students, in 1972. It satirizes aspects of the various programming languages at the time, as well as the proliferation of proposed language...
- WhitespaceWhitespace (programming language)Whitespace is an esoteric programming language developed by Edwin Brady and Chris Morris at the University of Durham . It was released on 1 April 2003 . Its name is a reference to whitespace characters...
- MalbolgeMalbolgeMalbolge is a public domain esoteric programming language invented by Ben Olmstead in 1998, named after the eighth circle of hell in Dante's Inferno, the Malebolge....
- Esoteric programming language#Funges
External links
- Cat's Eye Technologies, the original author's web site
- Esoteric languages wiki
- Official Funge-98 Specification
- ZBefunge, written in Inform
- Jeffrey Lee's Befunge archive
- BFC V1.1 Win32 compiler
- Yet Another Befunge93 Interpreter - An open source Befunge93 interpreter, written in Java
- Official home of the Rc/Funge-98 Interpreter
- BeQunge - An n-dimensional Funge-98 interpreter
- WASABI - A Superbly Asinine Befunge Interpreter An Open-Source Befunge93 IDE written in Java
- Conforming Concurrent Befunge-98 Interpreter Befunge-98 interpreter which conforms to the specifications and implements almost every fingerprint available
- Language::Befunge Befunge-98 PerlPerlPerl is a high-level, general-purpose, interpreted, dynamic programming language. Perl was originally developed by Larry Wall in 1987 as a general-purpose Unix scripting language to make report processing easier. Since then, it has undergone many changes and revisions and become widely popular...
module at CPANCPANCPAN, the Comprehensive Perl Archive Network, is an archive of nearly 100,000 modules of software written in Perl, as well as documentation for it. It has a presence on the World Wide Web at and is mirrored worldwide at more than 200 locations... - Language::Befunge::Debugger Graphic Befunge debugger written in Perl
- Fungi - A standards compliant Funge-98 interpreter and debugger written in Haskell.
- Inline::Befunge Perl module at CPAN to insert Befunge code into Perl code
- Visual Befunge Applet Visual Befunge Applet written in Java
- CoreLife, a 2 dimensional grid based programming language which predates Befunge