Befunge

Appeared in:
1993
Influenced by:
Paradigm:
Typing discipline:
Versions and implementations (Collapse all | Expand all):
Programming language

Befunge is one of the oldest and the most famous two-dimensional esoteric programming languages.

Befunge was created in 1993 by Chris Pressey. He attempted to create a language which would be as hard to compile as possible. However, in next years quite a lot of implementations of this language appeared, as well as several dialects and modifications called Fungeoids. The language has two main dialects — the original Befunge-93 and the later Befunge-98.

The original specification of the language restricted the size of the grid on which the program should be written, which means that Befunge (unlike other esoteric languages) is not Turing-complete. But just like other esoteric languages, it has no practical value.

A program in Befunge is a two-dimensional playfield of fixed size. The cells of the playfield are initially filled with the instructions of the program. Befunge allows the program to be modified at runtime, so one can use the cells as random access memory (with some limitations: the instructions are stored as characters, so one can store only numbers up to 255). The playfield is a torus: once the instruction pointer moves beyond the border on one side, it reappears on the opposite side facing the same direction.

The program is executed using a program counter (-93) or instruction pointer (-98). At the beginning of the program the instruction pointer points at the upper-left cell of the playfield and is directed right. It moves one cell at a time in its direction. Whenever the pointer encounters an instruction, it is executed. Certain instructions might have an effect on the instruction pointer’s direction (Befunge-98 added instructions which can modify its position as well).

The main data structure in Befunge is a stack; all operations use it to get arguments and return the result. The only data type in the language is integer. Characters can be used for data I/O and for more convenient representation of character constants within the program; in this case they are processed as their ASCII-codes.

Befunge-93 specifies the following set of commands:

  • + — * / % Add, subtract, multiply, divide or perform modulo division of two top stack values. The bottom element is used as first operand, the top one — as the second
  • ! Logical NOT
  • ` Greater Than
  • < > ^ v Make instruction pointer face left, right, up or down
  • ? Make instruction pointer face random direction
  • _ | Horizontal/vertical IF. Both commands pop the topmost element of the stack; if it equals 0, they perform > v commands, otherwise they perform < ^ commands
  • " Toggle string mode. In string mode each character encountered by the instruction pointer is pushed on the stack (as its ASCII-code)
  • : Duplicate top stack value
  • \ Swap two topmost stack values
  • $ Pop (remove) top stack value
  • . , Output the top stack value as an integer/as a character with corresponding ASCII-code
  • # Bridge: jump over next command
  • g Read the value in the given cell of the playfield and push it on the stack
  • p Put the given value into the given cell of the playfield
  • & ~ Read an integer/a character from standard input and push it/its ASCII-code on the stack
  • 0..9 Push corresponding value on the stack* @ End program

The commands g and p work with the cells of the playfield. Both of them first pop y-coordinate (row index) from the stack, followed by x-coordinate (column index). Both coordinates start with 0, so (0, 0) denotes the top left corner of the field. p command which writes a value into the cell pops it from the stack after the coordinates.

Links:

Examples:

Hello, World!:

Example for versions befungee 0.2.0

First part of the example pushes the required values on the stack. 25* puts 10 on the stack (ASCII-code of new line), then " toggles string mode, in which each character of the program pushes its ASCII-code on the stack, and finally second " toggles string mode off.

Second part of the example is a loop which prints all values in the stack, starting from the topmost ones. > makes the instruction pointer move right (after the end of iteration). : duplicates the topmost element of the stack (i.e., the current character); due to usage of the bridge # this command is executed only when the instruction pointer moves to the right. , prints the topmost element of the stack; due to the bridge it is executed only when the IP moves to the left. _ allows the IP to pass to @ if the topmost element of the stack is 0 (or the stack is empty) and mirrors it back to moving left otherwise. The order of events within one iteration is:

  • duplicate the topmost element of the stack.
  • check, whether it’s equal to 0; if it is, break the loop. During this check the topmost element is always deleted.
  • print the topmost element of the stack. 
25*"!dlroW ,olleH" >:#,_@

Hello, World!:

Example for versions befungee 0.2.0

This example handles the task in a more straightforward way — puts ASCII-codes of characters on the stack one-by-one and prints them immediately after they get on the stack. 

89*,45*99*+,39*99*+::,,56*99*+,29+4*,48*,92+8*1-,56*99*+:,3+,,25*:*,56*3+,25*,@

Factorial:

Example for versions befungee 0.2.0

This example uses iterative factorial definition.The program consists of two loops — the first one calculates numbers from 16 to 1, the second one does the actual factorial calculation.

First of all we put 16 on top of the stack (as 4*4) — this will be the maximal number which has to be processed. The first loop follows, executed in clockwise order. One iteration puts into the stack a number which equals the previous one decremented. When this number becomes zero, loop breaks (_ in the second line), and the instruction pointer goes right.

Next the top element of the stack (0) is removed and 1 is placed there instead (this is the current factorial value). The second loop follows, executed in counter-clockwise order. One iteration performs the following actions:

  • \ — two top elements of the stack (the factorial calculated earlier and the next number) are swapped (the next number becomes the topmost). If the stack contains only one element, 0 is pushed on top of it.
  • :_ — if the next number is 0 (or if the stack is empty), the loop breaks.
  • . — next number is printed (its copy stays in the stack).
  • block ,,,,"! = " pushes characters in the stack and prints them immediately. The string is scanned right-to-left, but the characters are printed from topmost to lower ones, so for the programmer the string looks exactly the way it will be printed.
  • .:* — new factorial is calculated and printed (its copy stays in the stack).
  • ,*25 — newline printed. 
44* >:1-:v    v ,*25 .:* ,,,,"! = ".:_ @ 
    ^    _ $1 > \:                   ^

Fibonacci numbers:

Example for versions befungee 0.2.0

This example uses iterative definition of Fibonacci numbers. It is based on commands p and g which are used to modify source code of the program at the runtime, — they put a specific character at a certain cell of the program or read it from the cell to the stack, respectively. In this case they are used to store Fibonacci numbers outside of the stack. Loop counter is stored in the bottom element of the stack all the time. Since playfield cells can’t store values over 255, only the first 13 Fibonacci numbers are printed. 

031p132p 94+ > 31g 32g :. + 32g v
             | :-1,,", "p23 p13 <
             > "."::,,,@

CamelCase:

Example for versions befungee 0.2.0

This program processes the input string character-by-character. The only instructions executed before the loop are 152p — this puts value 1 in cell (5, 2) which will store 1 if the last character was not a letter, and 0 otherwise.

The main part of the program is the loop. One loop iteration reads (~) and processes one character of the input string. The loop breaks as soon as the character is its ASCII is 10 (: 25*- #v_ @), otherwise the instruction pointer goes to the second line (at v command). If the character is a lowercase letter, it is converted to uppercase to unify further processing (this is done by the part of the program before the first square block and the block itself). After this we check whether the letter is an uppercase letter. If it is not (pointer is back to line 1), we mark (5, 2) cell as 1, the character is removed from the stack, and the iteration is over. Otherwise we do one more check, this time on the value of (5, 2) cell, and depending on its outcome we keep the character or convert it to lowercase. Finally, the resulting character is printed, and the iteration is over. 

152p > ~ : 25*- #v_ @               >48*-v                    >152p $         v
                 > :: "`"` \"{"\` * |    > :: "@"` \"["\` * ! |    >    v
                                    >    ^                    >52g |    >052p,v
                                                                   >48*+^
     ^                                                                        <
 ( )
  |
  was last character a space (5,2)