Rectangular Programming for Warped Minds

In light of the recent posts and discussions about multidimensional
numbers,today's pathological language is Recurse, a two-dimensional language - like Befunge, sort of. But I find it more interesting in its own peculiar little
way. It's actually a function-oriented two-dimensional language where every
function is rectangular.

Underneath the two-dimensional layout, Recurse is based on a pretty simple computational mechanism. There are two stacks of integers, a left stack and a right stack; and a single register containing an integer.

The basic commands are:

1. Push: push the value in the register onto one of the stacks; "{" for the left stack, and "}" for the right stack.
2. Pop: Pop a value from a stack into the register; "[" for the left, "]" for the right.
3. Unconditional set direction: set the direction that the instruction pointer will move. "^" for up, "v" for down, "<" for left, and ">" for right.
4. Load Constant: Load a single digit integer into the register. "0"-"9".
5. Read character: "?" - read an ascii character, and load it into the register.
6. Write character: "!" - output the register as an ASCII character.
7. Conditional Direction Change: "@" - if the register is 0, don't turn. If the register is positive, change the direction the the instruction pointer moves counter-clockwise; if it's negative, change the direction clockwise.
8. Return from function: "#"
9. Add: "a" pop a value l from the left stack, and a value r from the right stack, and set the register to l+r.
10. Subtract: "-" pop a value l from the left stack, and a value r from the right stack, and set the register to l-r.
11. Multiply: "m" pop a value l from the left stack, and a value r from the right stack, and set the register to l*r.
12. Divide: "d" pop a value l from the left stack, and a value r from the right stack, and set the register to l/r.
13. Remainder: pop a value l from the left stack, and a value r from the right stack, and set the register to l mod r.
14. Call function: any other character is treated as the name of a function,
    which is invoked.

A program consists of a rectangular grid. The grid is usually surrounded by "#" characters, with one exception for each direction. These four characters are the entry points for a function. When a function is called, the direction that the instruction pointer is moving is used to select an entry point. So if the pointer is moving down, then the function will be entered from the top entry point, so
that instructions can continue to be executed moving in the same direction. The functions name is the character that appears in both the top and bottom left
corners of the function grid.

When you're running a function, if the instruction pointer reaches the border, or
encounters a "#", it will return. Here's an example to clarify one of the more confusing aspects of that:

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

This function reverse the direction that the instruction pointer moves. Suppose that the IP is moving down. Then it will enter the function at the "v" on top. "v" tells the IP to keep going down. Then it hits the "^" character one step down, which switches the IP to move up. When it goes to move up, that's hitting the border - so instead of executing "v", it returns. It has the same pattern from all four directions, so no matter what way you're moving, this function will reverse the IP direction.

As usual, we'll start with a hello world program.

$v###############
>9n_3n{5}aA7A_3v#
#v3A}s}1{n7_n4A<#
#>nA3A6S8S4n{1Av<
$^###############

nv#####
>.}8{m#
#.m{8}<
n^#####

_v###
>.{!<
_^###

Av#####
>.}a{!#
#.!{a}<
A^#####

Sv#####
>.}s{!#
#.!{s}<
S^#####

There are five functions here: "$" (the main program), "n", "_", "A", and "S". The program starts executing "$" with the IP moving right.

The register gets set to 9, and then it calls "n" and "_".

"n" gets entered from the left; from the left, what n does is push the contents of the register onto the right stack, push an 8 onto the left stack, then multiply the tops of left and right; so it multiplies the contents of the register by 8.

Entered from the left "_" pushes the register onto the left stack, then prints the
contents of the register.

From the left, "A" pushes the register onto right, does an add, pushes the result onto left, and prints out a character. "S" is similar, except that it subtracts.

So if you go back to "$", you can see that it's a series of calculations to generate the characters of hello world, and output them one by one. First it calculates 9*8=72, the code for "H". Then it adds 24+5 to the 72 in the register, getting 101, the ascii code for "e". And so on. Looking at it, you can see that the main purpose of
the functions, particularly "A" and "S" is to save room in "$" - since it needs to be rectangular, it's necessary to be very space conscious; you have to make it fit,
which sometimes means pulling things out.

Here's another nice example. It inputs a number n, and recursively calculates the
nth fibonacci number.

 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^#################################

So... Is Recurse turing complete? The original author thinks so, but isn't sure. I'll be brave and say definitely "Yes". Recurse is capable of fully general
recursion: since it can full arithmetic, that means that it can compute arbitrary conditions for the terminating the recursion. It's also got unbounded storage in the two stacks. Two stacks is enough to turn a push-down automaton into a Turing-equivalent
machine; Recurse is at least as powerful as a two-stack PDA; it's got the
same storage capabilities, and richer control structure. So this is definitely
a Turing complete language.

It's also definitely quite a bizzare language - longer programs can get a whole
lot more interesting, and more fun. You can interleave different "functions" into the same rectangle, so that the function does different things depending on which direction you enter it from. But larger programs also suffer more from the rectagularity constraint - so you get a spagetti effect with lots of functions
scattered about to make the rectangles fit together the way you want them to. This is definitely not a language for the faint of heart - it's quite a challenge to make it do interesting things. But it's really quite fun!

I really quite like Recurse. The shame of it is that there's no interpreter available. It's not a difficult language to implement in principle; it's just a matter of sitting down and doing it. I might give it a shot when I have a chance.