Recurse

Recurse is a two-dimensional language based on Befunge and other, similar languages. It was created by MagiMaster. It was inspired, at least partly, by the fractal circuit mazes.

The code consists of one or more blocks. Each block of code is surrounded by a border of characters (usually #). The upper-left and lower-left characters of the border define the function's name. Also, along each border is an arrow defining the entry points for that function. The border is not considered part of the code. The simplest block is:

$v#
>.<
$^#

This block is named $, and defines the four entry points (>,^,< and v). Its code consists of a single '.' which evaluates as a nop by default.

Specification

Commands

The virtual machine running the code consists of two integer stacks and a single integer register.

The meaning of each character in the code space is:

• {, } - push the register onto the left or right stack, respectively (without modifying the register)
• [, ] - pop the left or right stack, respectively, and put the value in the register
• >, ^, <, v - set the direction of the instruction pointer
• 0-9 - set the register to that number
• ? - read one ASCII character to the register
• ! - output the register as an ASCII character
• @ - conditional turn: if the register is 0, go straight; if it's positive, turn CCW; else, turn CW
• # - return: ends the current function
• a, s, m, d, r - pop the top value from the left and right stack and set the register to their sum (difference, product, quotient, remainder), always using left op right
• any other character is evaluated as a nop unless it is the name of a function, in which case, that function is run using the appropriate entry point

Two other commands that might be useful would be:

• % - output the register as a base-10, signed integer
• & - read a base-10, signed integer into the register
• " - string mode (wimpmode)

These functions (except string mode) can be defined in terms of the other functions though.

Functions

Every function defines four entry points. (The actions of functions that don't define some of their entry points are undefined if they are called using those entry points.) When a function is called it begins running at the entry point pointing in the direction the instruction pointer is currently traveling. For example, if the pointer is travelling downward when a function is called, execution of that function will begin at its top entry point.

The function ends when the instruction pointer leaves the code area (where the border would be) or when it encounters a #. After a function returns, the instruction pointer continues from where that function was called, although in its new direction. This allows the definition of functions that affect the direction of the pointer. For example, a reverse function could be defined as:

Xv##
#^><
><v#
X#^#

Functions can call themselves recursively.

Programs

Each program is a collection of blocks. Execution begins at the left entry point of the $ block. The program terminates when the topmost copy of the $ function terminates ($ can be called recursively like any other function). The simplest block, shown above, is also the simplest valid program. Any lines outside of a block that begin with whitespace are ignored and can be used for comments.

Possible extensions

One possible extension would be to define include semantics. This would allow the % and & functions to be defined in a standard library.

Another possibility would be to define semantics for the redefinition of functions, such as: a call uses the topmost copy of the function below the current function. This would allow an infinite number of functions (as opposed to some number limited by the printable characters).

It might also be possible to define semantics for having multiple entry points in each direction, although it may not be worth the trouble.

The program and I/O could be based on UNICODE rather than ASCII. This would greatly increase the number of characters available.

It might be possible to place blocks more arbitrarily on a page, rather than just above each other. This would however require modifying the comment convention.

Various meta-operations could be added, such as calling functions by name in the register, loading a program character into the register, inspecting, popping and pushing on the call stack.

It is possible to define a very similar 1D language by changing the conditional turn to a conditional skip.

Possible free placement algorithm

The following algorithm to detect blocks should be nearly compatible with the original style. A comment would have to be rather unusual to be misinterpreted as containing blocks. This works by strictly enforcing that a block's border can contain no space characters, including the function name, that there cannot be non-space characters immediately to the left or right of a block, and by discarding anything that is not a reasonable block.

• A sequence of at least three non-space characters anywhere on a line starts a proto-block, unless it is part of a previous one.
• A proto-block extends to the next line if the characters directly below its left and right borders are non-spaces, and any characters just outside its borders are spaces. Otherwise it ends.
• A completed proto-block is discarded as a comment if either:
  • It has less than three rows.
  • Its last row contains spaces.
  • Its last row begins with a different character than its first one.
  • It has no entry points at all.
• Otherwise, the proto-block is a block.

Computational class

There is no proof, but the author strongly suspects Recurse is Turing complete. It shouldn't be too hard to write an interpreter for Brainfuck, although it hasn't been tried.

According to Mark C. Chu-Carroll on his Good Math, Bad Math blog, this is indeed Turing Complete, since it is at least as powerful as a two-stack PDA and has a richer control structure.

Examples

Hello, world!

Prints "Hello, world!"

 Main function
$###########v######################################
>..9n_3n{5Av# 'H' = 9*8       # 'w' = (2*8-1)*8-1 #
#vA3_[_A7_A<# 'e' = 'H'+3*8+5 # 'o' = 'W'-8       #
#>_[5n{4A_[v# 'l' = 'e'+7     # 'r' = 'o'+3       #
#vS1{n2[_n4<# 'l'             # 'l' = 'r'-6       #
#>n{1S_8S_3v# 'o' = 'l'+3     # 'd' = 'l'-8       #
#v[_S8_S6_A<# ',' = 5*8+ 4    # '!' = 4*8+1       #
#>4n{1A_[..!# ' ' = 4*8       #                   <
$###########^######################################

 Multiply by 8 (Bidirectional)
n####v#####
>{8}m#m}8{<
n####^#####

 Push on left stack and print (Bidirectional)
_##v###
>{!#!{<
_##^###

 Add (Bidirectional)
A##v###
>}a#a}<
A##^###

 Subtract (Bidirectional)
S##v###
>}s#s}<
S##^###

Fibonacci numbers

Reads a number from the input, echos it then prints the nth Fibonacci number to the output. (It uses % for the output, but defines the R function instead of using &.)

 Main function
$v####
>0Rf%<
$^####

 Given n in the register, recursively calculates the nth fibonacci
 number
fv########
#>{{2}sfv#
>@1#v}1}<<
#>0#>sf{a#
f^########

 Reads a positive decimal integer from the keyboard
 The register should be zeroed before calling
 Press space to terminate function
Rv#################################
##..........>v....>[#.............<
>{?!{6{8}m}s@>{9}s@>{9}a}5{}a}m{aR#
##..........>[#...>^..............#
R^#################################

Ackermann function

Prints the result of the Ackermann function with m=3 and n=5.

 Main function
$#######v
>3{5}k%#<
$#######^

 Ackermann(m, n)
k########################v
#......>{1}s}k_}[{{1}s{k_#
#..>{]}@1}}s{k_..........#
>[{@]}}1{a..............#<
k########################^

 Pop both stacks once while saving the register value
_#######v
>{][}[]#<
_#######^

Digital root calculator

Calculates and prints the digital root of a user supplied decimal integer.

 Main function
$#####v
>0{g%#<
$#####^

 Efficient calculation of digital root
 with special case for digit=0
g############v
#..>a{1}s{9v.#
>R}@]g#v}r}<#<
#..>[##>1{a{g#
g############^

 Reads a character from the keyboard
 If digit, return value in register
 Otherwise, return -1 in register
R####################v
>?{6v..>v.....>[0{1}s#
#v8{<>s@>{{9}s@>[....#
#>}m}^.>0{1}s#>^....#<
R####################^

99 bottles of beer

 Main function
$###################################################v
>i1n{4An{3Ab................vv.....................<#
#............................>p6n{2S!fpqbw[{v.......#
#v..........................................<.......#
#.....>ffp_pp6n{2S!wwwww+!!p>pp_pp5n{4A!+!wwwwwppp_^#
#.>{1S@ffppp6n{2S!wwwww+!!ppppp5n{4A!+!wwwwwppp....^#
#>@ffp_pp6n{2S!wwwww+!!ppp_pp5n{4A!+!wwwwwppp_p6n{2v#
#vA4{n1'S1{m}3{A7','S5'S1{m}3{A7','An5'S1{nA1{8!+!S<#
#>S'3S','7A{3}m{2S'1A'5S'3A'2n{3SS'2}d{6S','3}m{2A'v#
#v'A3'A2'S2{m}3{A5','S8'S2'S4'S2{m}3{A7','A4'A3{An2<#
#>2n{3SS'2}d{6S'[+!www1n{4An{3Abpp_pp6n{2S!........#<
$###################################################^

 Print number of bottles (Only left to right)
b###########################v
#...............>6nA{!]{1n{v#
>{}}0{]{1n{2A}d{@[]{vv{r}A2<#
#v1{An4!{{S2{nA2{8[@<.......#
#>A{!#.............>.>6nA{!#<
b###########################^

 Quaff one  (Only left to right)
q##########v
>>wwwwwv.<#<
#>#....>[@v#
#^......S1<#
q##########^

 Initiate tape (Only left to right)
i####################################v
>0}+}6n{4S*7nA*1n{2AA*7A*6S*3A*2n{1Av#
#v[*S2{m}3{A7*,*SA3{n1*S1{m}3{A7*,*S<#
#>*2n{2AS*2n{1SA*,*1n{4AA*2}d{5}m*1nv#
#vA1*A1{An1*A5{m}3*,*S3{Sn1*Sn1*A1{A<#
#>*,*3}m{5A*6A*1n{2AS*2n{3SS*+}0}2n{v#
#vA3*A5{m}3*,*AS2{n3*SA3{n1*[*A4{nS3<#
#>*1n{4AA*,*5A{3}m{1S*1A*,*0}2n{2Sn{v#
#v0*,*A1{An1*A6{m}3*,*S3*[*SS3{n2*A2<#
#>}2n{3Sn{3S*7A*1nA*[*5S*2n{3SS*,*0}#<
i####################################^

 Play (Only left to right)
p#####v
>v{!<#<
#>.]@{#
p#####^

 Forward (Only left to right)
f####v
>v{<#<
#>]@{#
f####^

 Rewind (Only left to right)
w####v
>v}<#<
#>[@}#
w####^

 Multiply by 8 (Bidirectional)
n####v#####
>{8}m#m}8{<
n####^#####

 Add (Bidirectional)
A##v###
>}a#a}<
A##^###

 Subtract (Bidirectional)
S##v###
>}s#s}<
S##^###

 Space (Bidirectional)
,###v####
>[4n#n4[<
,###^####

 Print 's' (Bidirectional)
_##########v###########
>2n{2Sn{3A!#!A3{nS2{n2<
_##########^###########

 Line Feed (Bidirectional)
+#####v######
>1n{2A#A2{n1<
+#####^######

 Push on left stack and print (Bidirectional)
'##v###
>{!#!{<
'##^###

 Push on both stacks (Bidirectional)
*##v###
>}{#}{<
*##^###

External resources

• Recurse interpreter implemented in Python.