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)