Rec

Rec is an esoteric programming language created by User:D, designed to be a more "machine-friendly" version of Recur.
Besides being inspired by Recur, Rec is also inspired by how compilers handle local variables. i.e., local variables in a method are usually stored on a stack and accessed via a TOS-relative offset.
== Commands ==
Note: stack indexing starts at 0, so 0 references the top item of the stack, 1 references the second-to-top, etc. (It is implemented as stack[~x], where x is the index.)
* 123 Push the natural number (unbounded) onto the stack.
* / Successor; Pops a, pushes a+1.
* \ Predecessor; Pops a, pushes a-1.
* : Load; Pops x. Pushes the xth-to-last item onto the stack.
* ; Store; Pops v and x. Sets the xth-to-last item of the stack to v.
* [ ... ] Infinite loop: Execute ... forever. (The only defined way to exit a [ ... ] loop is via the ^ command.)
* ^ Pops x. If x==0, break out of the innermost [ ... ] loop. (Or terminates program, outside of a [ ... ] loop.)
== Stack operations in Rec ==
=== Drop ===
If you already know TOS is nonzero:
^
If you already know TOS is zero:
[^]
In general, 0 0;[^] or [^0^] works for all cases.
=== Dup ===
0:
=== Swap ===
1:1:2;0;
== Arithmetic operations ==
=== Addition ===
Only works if RHS is non-negative.
[0:^\1:/1;][^]
=== Multiplication ===
Similar to addition, only works for non-negative integers.
m n 0[2:^2:\2;1:[0:^\1:/1;][^]]1;[^0^]
== Logical operations ==
=== is_zero ===
Leaves the resulting boolean on the stack.
1[1:^0 0;0^]
== Other Examples ==
=== Truth machine ===
(Uses commands specific to the Python interpreter.)
R[0:P0:^]
=== Ackermann function ===
Leaves the resulting value on the stack.
0 0 0\ [0^ Initialize stack as [0 0 -1].
 -1 is used to check if the stack has only one item left ]
R R [0^ Push arguments onto stack ]
[ 0\\; 0\; [0^ Loop: store m & n into the first two numbers. [m n -1] ]
 [ 0\\:/ 0\: ^ [0^ Cond1: Push n+1 if m = 0. ]
 0\: \0; 1 0\\:^ [0^ Cond2: Push m-1, 1 if n = 0. ]
 0\: 0; 0\\: \ 0 ^ ] [0^ Else: Push m-1, m, n-1. ]
 1: / ^ [0^ Check if second-to-last item + 1 is 0. (i.e. = -1)]
]
Minified:
0 0 0\R R[0\\;0\;[0\\:/0\:^0\:\0;1 0\\:^0\:0;0\\:\0^]1:/^]
=== Fibonacci function ===
==== Iterative ====
x is the fib number you provide to the function. (Overrides the original number with 0;.)
x 0 1
[ 2:^
 2:\2;
 1:
 [0:^\1:/1;]
 [^]
 0:2:1;1;
]
[^0^]
0;
Minified:
x 0 1[2:^2:\2;1:[0:^\1:/1;][^]0:2:1;1;][^0^]0;
== Computational Class ==
Rec is Turing-complete, because we can translate brainfuck with a dynamically-extending tape to the language, with the following command addition:
* &: Add a 0 cell to the right of the tape.
Note: The TOS is used to simulate the tape pointer, with an initial value of -1
The conversion is as follows:
Initialization:
0\
&:
0:0 1;
+:
0::/1:;
-:
0::\1:;
<:
/
>:
\
[:
[0::^
]:
]
== Reference Implementation ==
The Python & C implementations of Rec comes with a debugging feature and a REPL.
You can enter the REPL without any command-line arguments.
Here are the added commands:
* P Pop from TOS, and print the integer with a newline.
* R Read a line from the input, and push that as an integer.
* p Pop TOS, print TOS as a character.
* r Read a single character from input, and push it as an integer.
* s "Dump stack"; Print the index of the last command executed before s, along with the command. Then, print the stack at the point when s is executed. (The C interpreter only prints the stack.)
* b Breakpoint; Starts debug mode at this place in the program.
:* Press newlines to step through the debugger, or Ctrl-D to exit.
=== Flags (Python interpreter only) ===
* -r Start REPL mode. 
* -d Start debug mode: Step through each command of the source.
You can type Ctrl-D to exit both the REPL and the debug mode.
== See also ==
* Recur
* Rec+
== External Resources ==
* Reference implementation (Python / C)
Category:Languages
Category:Low-level
Category:Implemented
Category:Turing complete
Category:Turing tarpits
Category:Stack-based
Category:2023