View source for Befunge

{{Short description|2-dimensional esoteric programming language}}
{{more citations needed|date=January 2012}}

{{Infobox programming language
 | name                   = Befunge
 | released               = {{Start date|1993}}
 | developer              = Chris Pressey
 | influenced by          = [[Forth (programming language)|Forth]], [[esoteric programming language#FALSE|FALSE]]
}}

'''Befunge''' is a two-dimensional [[stack-oriented programming language|stack-based]], [[Reflection (computer science)|reflective]], [[esoteric programming language]].<ref>{{Cite web|url=https://esolangs.org/wiki/Befunge|title = Befunge – Esolang}}</ref> 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. It has been described as "a cross between [[Forth (programming language)|Forth]] and [[Lemmings (video game)|Lemmings]]".<ref>{{cite web|url=http://cantor.res.cmu.edu/bozeman/befunge/beffaq.html|archive-url=https://web.archive.org/web/20010417044912/http://cantor.res.cmu.edu/bozeman/befunge/beffaq.html |title=The Befunge FAQ v.4|archive-date=2001-04-17|date=1997-11-04|access-date=2014-01-23}}</ref>

Befunge was created by Chris Pressey in 1993 for the Amiga. The language was designed to be as hard to compile as possible, featuring self-modifying code and a multi-dimensional playfield. Despite this, several compilers have been written for the language. The original Befunge-93 specification limited programs to an 80x25 grid, and while not Turing-complete, subsequent extensions like Funge-98 expanded the concept to achieve Turing completeness.

The name "Befunge" originated from a typing error in an online discussion. While it was designed to be difficult to compile, compilers such as bef2c and Betty have managed to implement the language using various techniques. Befunge programs are characterized by their use of arrows to change control flow, and they can produce outputs like random number sequences or classic "Hello, World!" messages.

== History ==
The language was originally created by Chris Pressey<ref>{{cite web |url=http://esolangs.org/w/index.php?title=Chris_Pressey&oldid=13199 |title=Chris Pressey |date=2008-12-18 |website=Esolang |author=Ais523 |access-date=2014-01-23}}</ref> in 1993 for the [[Amiga]], as an attempt to devise a language which is as hard to [[compile]] as possible. Note that the <code>p</code> 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 [[Multithreading (computer architecture)|multithreaded]], with multiple [[instruction pointer]]s 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 [[integer overflow|"wraps around"]] to a corresponding point on the other side of the grid; a Befunge program is in this manner [[Topology|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 not [[Turing-complete]] (however, it has been shown that Befunge-93 is Turing Complete with unbounded stack word size).<ref>{{cite web |url=http://esolangs.org/w/index.php?title=Talk:Befunge&oldid=38327 |title=Talk:Befunge |website=Esolang |date=2014-01-18 |author=Oerjan |access-date=2014-01-23}}</ref> 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.

==Etymology==
The word '''Befunge''' is derived from a [[typing error]] in an online discussion, where the word 'before' was intended.{{citation needed|date=March 2022}}

== 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 variation on [[just-in-time compilation]] 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.

== Sample Befunge-93 code ==
The technique of using arrows to change control flow is demonstrated in the random number generator program below.  The Befunge instruction pointer begins in the upper left corner and will travel to the right if not redirected.  Following the arrows around, the <code>?</code> 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 <code>.</code> to output the digit from the stack and return the pointer to the first directional randomiser. There is no <code>@</code> to terminate this program, so it produces an endless stream of random numbers from 1 to 9.
<syntaxhighlight lang="befunge">
 v>>>>>v
  12345
  ^?^
 > ? ?^
  v?v
  6789
  >>>> v
 ^    .<
</syntaxhighlight>
The following code is an example of the classic [[Hello world program|"Hello World!" program]]. First the letters "olleH" are pushed onto the stack as [[ASCII]] numbers. These are then popped from the stack in [[LIFO (computing)|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).
<syntaxhighlight lang="befunge">
>              v
v  ,,,,,"Hello"<
>48*,          v
v,,,,,,"World!"<
>25*,@
</syntaxhighlight>
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 (computing)|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 [[Control flow#Loops|loop]] that first duplicates the top value on the stack (so now the stack would look like "[[line feed|\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.
<syntaxhighlight lang="befunge">
 >25*"!dlrow ,olleH":v
                  v:,_@
                  >  ^
</syntaxhighlight>

==Befunge-93 instruction list==
{|
|-----
| width="10%" | <code>0-9</code>
| Push this number onto the stack.
|-----
| <code>+</code>
| Addition: Pop ''a'' and ''b'', then push ''a''+''b''
|-----
| <code>-</code>
| Subtraction: Pop ''a'' and ''b'', then push ''b''-''a''
|-----
| <code>*</code>
| Multiplication: Pop ''a'' and ''b'', then push ''a''*''b''
|-----
| <code>/</code>
| Integer division: Pop ''a'' and ''b'', then push ''b''/''a'', rounded towards 0.
|-----
| <code>%</code>
| Modulo: Pop ''a'' and ''b'', then push the remainder of the integer division of ''b''/''a''. 
|-----
| <code>!</code>
| Logical NOT: Pop a value. If the value is zero, push 1; otherwise, push zero.
|-----
| <code>`</code>
| Greater than: Pop ''a'' and ''b'', then push 1 if ''b''&gt;''a'', otherwise zero.
|-----
| <code>&gt;</code> || Start moving right
|-----
| <code>&lt;</code> || Start moving left
|-----
| <code>^</code> || Start moving up
|-----
| <code>v</code> || Start moving down
|-----
| <code>?</code>
| Start moving in a random cardinal direction
|-----
| <code>_</code>
| Pop a value; move right if value=0, left otherwise
|-----
| <code><nowiki>|</nowiki></code>
| Pop a value; move down if value=0, up otherwise
|-----
| <code>"</code>
| Start string mode: push each character's ASCII value all the way up to the next <code>"</code>
|-----
| <code>:</code> || Duplicate value on top of the stack
|-----
| <code>\</code> || Swap two values on top of the stack
|-----
| <code>$</code> || Pop value from the stack and discard it
|-----
| <code>.</code> || Pop value and output as an integer followed by a space
|-----
| <code>,</code>
| Pop value and output as ASCII character
|-----
| <code>#</code> || Bridge: Skip next cell
|-----
| <code>p</code>
| A "put" call (a way to store a value for later use). Pop ''y'', ''x'', and ''v'', then change the character at (''x'',''y'') in the program to the character with ASCII value ''v''
|-----
| <code>g</code>
| 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
|-----
| <code>&</code> || Ask user for a number and push it
|-----
| <code>~</code>
| Ask user for a character and push its ASCII value
|-----
| <code>@</code> || End program
|-----
| <code> </code>(space) || [[No-op]]. Does nothing
|}

Most one-dimensional programming languages require some syntactic distinction between [[comment (computer programming)|comment text]] and [[source code]] — although that distinction may be as trivial as [[Brainfuck]]'s rule that any character not in the set <code><nowiki>+-[]<>,.</nowiki></code> is a comment. Languages like [[Lisp (programming language)|Lisp]] and [[Python (programming language)|Python]] 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==
*[[Brainfuck]]
*[[Carnage Heart]] – PlayStation programming game using a similar language
*[[INTERCAL]]
*[[Whitespace (programming language)|Whitespace]]
*[[Malbolge]]
*[[Piet (programming language)|Piet]]

==References==
{{Reflist}}

==External links==
*[https://github.com/catseye/Befunge-93/blob/master/doc/Befunge-93.markdown Befunge-93 Specification]
*[https://github.com/catseye/Befunge-93 Befunge-93 Reference Implementation]
*[https://github.com/catseye/Funge-98/blob/master/doc/funge98.markdown Funge-98 Specification]

[[Category:Esoteric programming languages]]
[[Category:Stack-oriented programming languages]]
[[Category:Non-English-based programming languages]]
[[Category:Programming languages created in 1993]]
{{Esoteric programming languages}}