Retrograde

Retrograde is a reversible programming language investigated by User:ImOnlyHereForReversibleComputing at least as early as July 2022, but first posted in August 2026. The language has an unusual control structure which is unexpectedly general and expressive despite the language being otherwise very minimalist.

Language Description

A Retrograde program operates on a tape of 1-bit memory cells, which extends infinitely to the left and right. The program has a data pointer which points at the current bit of the tape. All instructions in the language manipulate either the data pointer or the current bit the data pointer is pointing to.

In Retrograde, programs are able to explicitly reverse their own direction of execution, so, each instruction has both a "forward" behavior that is performed when the instruction is executed forward, and a "reverse" behavior that is performed when the instruction is executed in-reverse.

Instruction	Name	Forward Behavior	Reverse Behavior
*	Toggle	Toggle the current bit (if it's 0, set it to 1; otherwise, set it to 0).	Toggle the current bit (if it's 0, set it to 1; otherwise, set it to 0).
>	Shift Right	Move the data pointer to the next bit to the right.	Move the data pointer to the next bit to the left.
<	Shift Left	Move the data pointer to the next bit to the left.	Move the data pointer to the next bit to the right.
{	Turn Start	If the current bit is 1, jump to the matching } and reverse the direction of execution.	If the current bit is 1, jump to the matching } and reverse the direction of execution.
}	Turn End	If the current bit is 1, jump to the matching { and reverse the direction of execution.	If the current bit is 1, jump to the matching { and reverse the direction of execution.
/	Forward Half-Toggle	Toggle the current bit (if it's 0, set it to 1; otherwise, set it to 0).	Do nothing.
\	Reverse Half-Toggle	Do nothing.	Toggle the current bit (if it's 0, set it to 1; otherwise, set it to 0).

When the direction of execution is reversed, the instruction pointer moves backwards instead of forwards through the program, and the reverse version of each instruction is executed. If the direction of execution becomes reversed a second time, it returns to normal.

The program alternates:

• Executing the instruction currently under the instruction pointer using the behavior determined by the current direction of execution.
• Moving one step in the current direction of execution.

The program halts when the instruction pointer moves off either end of the program.

The core control structure, the "turn" statement, is somewhat like a structured programming version of the "reverse and branch" instructions from the Pendulum Instruction Set Architecture. A turn statement always executes its contents, but the current bit determines whether the block is executed forward or in-reverse. The language does not feature any primitive methods of executing code conditionally or in a loop, but turn statements can be used as a lower-level primitive to implement both of these behaviors.

Computational Class

Just the instructions *, >, {, and } are sufficient to simulate Reversible Bitfuck, proving that Retrograde is Turing complete.

Reversible Bitfuck Instruction	Retrograde Implementation
*	*
>	>
<	{*{*>*}*}
(	*{{*
)	}{*}}

Basic Program Structures

These are a collection of useful basic program building blocks that can be constructed from the language's instruction set.

Many of the control structures here that make use of the current bit as a condition operate on the expectation that any blocks of code they enclose will always revert the data pointer to its initial position before exiting. Some operate on the assumption that the block of code that they enclose is not allowed to modify the control structure's own condition bit. These restrictions will be noted in each section.

Toggle Reflector

The toggle reflector is a basic primitive for initiating or terminating backtracking. It negates the current bit and reverses the direction of execution:

{*}

Toggle reflection lies at the core of most useful control structures in the language, so it, or variants of it, pop up as a component of many other structures in this list.

Inverter

We can invert a given chunk of code by wrapping it in a certain brace structure. If we want to execute the inverse of a block of code, A, we can write:

{*{* A *}*}

Because the program will execute exactly two toggles in the way in and on the way out, this structure does not modify the input or output memory state of the block, and instead simply causes it to be executed in the opposite direction.

Loop/Conditional

As listed in the Computational Class section, we can implement a loop around a block of code, A as:

*{{* A }{*}}

The program enters the loop if the current bit is 1, then continues to loop until the current bit is 1 again at the end of the block. This can also effectively be used for conditionals, by simply ensuring that the condition bit does not change during the execution of the block.

For the loop to function correctly, it is expected that the data pointer will be reverted to its initial position when the contained code blocks completes (though in specialized cases, such as when seeking to a particular marker in memory, you may violate this intentionally). For the conditional to function correctly, the data pointer needs to be reverted to its initial position, and the value of the condition bit must not change.

Conditional with Else Block

We can make a slight modification to our loop/conditional to get a proper conditional statement with an else block. To execute A when the current bit is 1, and B when the current bit is 0, we can simply write:

*{{* A }{* B }}

For a conditional/else statement to function correctly, it is expected that the contained code does not modify its condition bit, and that the data pointer will be reverted to its initial position when either of the contained code blocks completes.

Bennett's Trick

Bennett's Trick consists of executing code to compute a value, using the computed value or copying it into memory elsewhere, then running the initial computation code in reverse to uncompute all of the intermediate values used in the calculation. Retrograde allows for a very concise implementation of Bennett's Trick with setup code A and usage/storage code B:

{ A { B *}}*

This executes A, then executes B, then executes A in reverse, then proceeds forward with the remainder of the program.

For Bennett's Trick to function correctly, it is expected that the contained code does not modify its condition bit, and that the data pointer will be reverted to its initial position when each contained code block completes. The condition bit also must be initially 0 and will be returned to a 0 state when the structure completes.

Symmetry-Breaking

Forward half-toggle (/) and reverse half-toggle (\) are reversible (the behavior of each direction of each instruction is individually reversible), but break the usual symmetry expected in reversible programs, since their forward and reverse behaviors are not inverses. Many common reversible programming practices implicitly depend on symmetry not being broken; for example, without careful management, symmetry-breaking can cause Bennett's Trick to stop working. However, these symmetry-breaking instructions act as "detectors" for the direction of execution, and this allows for the implementation of some reversible structures that would not be possible without breaking symmetry.

Clutch

A clutch statement sandboxes the reversal of execution of the block of code it encloses, for example, we can sandbox a block of code A by writing:

{/ A /}

If the code inside the block reverses the direction of execution before exiting, then the clutch statement will negate the current bit, then re-reverse the direction of execution, preventing the reversal from escaping the sandbox. Because this bit flip is storing the fact that the block reversed the direction of execution, if a clutch statement is executed when the current bit is 1, then it will initially begin executing its block in-reverse. However, it still maintains its sandboxing behavior, of toggling its bit to record sandboxed reversals, and forcing the program to resume in its original direction when the sandbox exits.

For a clutch statement to function correctly, it is expected that the contained code does not modify its condition bit, and that the data pointer will be reverted to its initial position when the contained code completes.

Direction-Conditional Execution

The forward and reverse half-toggles conditionally toggle a bit of memory based on the direction of execution; however, you might want to instead conditionally execute some arbitrary block of code based on the direction of execution. For this, you can use the following structures.

This structure runs its block only when code is executing forward:

\{{\}{\ A }{\}}

And this structure runs its block only when code is executing in reverse:

/{{/}{/ A }{/}}

The blocks for these structures should not reverse the direction of execution; if they do, the structure will begin to loop until the block reverses the direction of execution again.

Perfect Reflector

While a toggle reflector toggles a bit and then reverses the direction of execution, with symmetry-breaking, we can implement a "perfect reflector" that reverses the direction of execution without changing the state of the program's memory.

/{*}/

Perfect reflection is somewhat dangerous, as, unless symmetry-breaking code is used to detect the reversal, a perfect reflection will simply cause the program to rewind to its initial state and halt. Since perfect reflection largely serves no computational purpose, this makes it more something you need to know about only for the sake of avoiding it rather than using it.

Minimization

The instruction set provided above contains a number of extra instructions for I/O or halting the program. However, beyond that, even the core instructions are not strictly minimal for Turing completeness. We can create even smaller instruction sets equivalent to either the symmetry-abiding or symmetry-breaking core subsets of the language.

Minimization of *, <, >, { and }

The first thing to note for minimizing the core instruction set is that we do not need both < and >, as we can implement one in terms of the other using the inverter. For example, we can eliminate < by implementing it as:

{*{*>*}*}

Additionally, since an empty turn statement does nothing, and toggle is self-inverse, we can merge {} and * into a single pair of instructions that we duplicate strategically when we want one piece of functionality or the other:

Minimized Instruction	Retrograde Implementation
b	{
d	}*

With just these three instructions, we can reimplement all five of our original instructions.

Retrograde Instruction	Minimized Implementation
*	bd
{	b
}	dbd
>	>
<	bbdbbd>bdddbd

Further minimization may be possible.

Minimization of /, \, <, >, { and }

* can be implemented as /\. As a result, /, \, <, >, { and } are also a Turing complete subset of the language, one that supports symmetry-breaking. To minimize these instructions, we can define a new pair of instructions, p and q as:

Minimized Instruction	Retrograde Implementation
p	{/
q	\}

With just these two instructions, plus >, we can reconstruct all six of our starting instructions:

Retrograde Instruction	Minimized Implementation
>	>
<	pppqqqpppppqqqp>qqpppqqqq
{	pppppqqpqqq
}	pppqppqqqqq
/	ppppqqpqqq
\	pppqppqqqq

This minimization was identified by a computer search, exploiting the ease of analysis of non-shift instructions. Further minimization may be possible by integrating data pointer shifting into the minimized instructions.