DIVCON

DIVCON is a reversible language inspired by Deadfish. Note: Reverse computation in DIVCON doesn't repeatedly execute the last instruction twice. In addition, the accumulator in DIVCON is initially set to 0.

Definitions

• A "branch" is the part where the accumulator is partitioned.
• The "root" of a program is the start of the program, it's where execution initially starts.
• A "leaf" of a program is the branch that's nested the deepest in a nesting of branches.

The DIVCON program form

Every DIVCON program is in the form of

AAAA

or

AAAX[BBB;CCC]

In a branch, you are allowed to nest another program.

Branching

For readability sake, I'd just write the general form of a branching statement.

AAAX[BBB;CCC]

The initial execution order is execution from A to B/C. After execution the A instructions, the accumulator resulting from that computation gets 'partitioned'. For example, if you partition 15 with the + operation, then you need to solve the equation a+b = 15. This results in 8 + 7, because 1) a and b has to be as close to each other as possible and 2) a has to be larger than b, if it's impossible to make them equal.

With the two partitioned accumulators, we execute the code block B with the left result a, and the code block C with the right result b.

Reversible branching

Given that DIVCON is reversible, there ought to be a way to reversedly execute the branching. Now the concept is simple: take the accumulators after executing B and C; B and C don't have to be reverse computed, they just need to do something (or nothing) to the accumulator; and then perform the specified operation X. So say after B, the accumulator is 3; After C; the accumulator is 4. The accumulator for code block A is set to 3 + 4 = 7. Then, we execute the code block A reversed.

What happens when the execution reaches the end? The program is automatically reverse-executed, from leaf (the deepest branches of the program) to the root (the start of the program), unless it's avoided via the # instruction. When the program counter reaches the root, there is no reverse execution by default, unless explicitly specified by the S instruction.

The execution after a branch

Here is a special condition that needs to be clarified:

+[A;B]*

In this situation, during reverse-computation, the trailing * is ignored, and it isn't part of the program. This program is equivalent to the following:

+[A;B]

How different branches are executed

The general idea is executing the left branch first, and then executing the right branch next. So if your program is like this (after branching, evidently):

...[ABCDE;ZYXWV]

Then, the instructions are executed in the order of ABCDEZYXWV.

Instruction list

Instruction name	Behavior not on a branch	Behavior on a branch
#	Skip the next byte if the accumulator = 0; unless the next byte is i or o, in which # always skips over them. If encountered during reverse-computation, and this character is the first character in the program, this character is ignored. If encountered on the last characters of the deepest layers of branch nesting, reverse computation on leaf is ignored. For an ignored reverse computation branch, whenever a branch requires the accumulator value after # has avoided it, the latest acc value before # would be used.	Partition by the previous character. Swap the operands of the branch during evaluation of reverse-execution. To be specific, the operands are swapped before the branch execution.
S	When encountered during reverse computation, reverse execution. If the execution direction is from root to leaf, S won't do anything to change the execution direction.	"Magic branch". Take the previous two characters: partition by the former operator, and then combine the two accumulators by the latter operator.
+	acc = acc + 1	Partition by addition; or, add the two partitioned accumulators.
-	acc = acc - 1	Partition by subtraction; or, subtract the two partitioned accumulators (left priority).
*	acc = acc * acc	Partition by multiplication; or, multiply the two partitioned accumulators.
/	acc = sign(acc)	Partition by division; or, divide the two partitioned accumulators. (left priority)
%	acc = acc % 2	Partition by modulo; or, modulo the two partitioned accumulators. (left priority)
=	acc == 0 ?	Partition by equality; or, perform equality between the two partitioned accumulators.
i	Take a numerical input from the console. Set acc to that. If no input left, there's no prompt and the acc isn't modified.	If the accumulator is >0, execute the left branch. Otherwise, execute the right branch.
o	Output the accumulator as a number to the console, (preferrably) with a trailing newline.	Undefined behavior
x[a;b]	Branch - partition the accumulator by x, apply the left accumulator to a, and the right to b.	If the branch is on a branch, the trailing branch is ommitted during partition, and the former branch in the source code replaces the behavior of the latter branch in the source code.

Unofficial extension

For easier string manipulation, immediate output strings and character input/output is added:

Instruction name	Behavior not on a branch	Behavior on a branch
"..."	Immediate output string, output `...` to the console.	Undefined behavior
O	Convert the accumulator number to character, and output the character to the console.	Undefined behavior
I	Take an ASCII character from the input.	Undefined behavior

Method of partition

This section is simply here to describe how exactly the partitioning system of DIVCON works. Below, the two accumulators are separated by the comma, where the left part is set to the left accumulator, and the right part is set to the right accumulator.

• +: Provided an input x, output ceil(x/2), floor(x/2).
• -: Provided an input x, output x, 0; unless x < 0, where the output is 0, x.
• *: Provided an input x, output a, b, where ab = x, where a and b are as close to each other as possible.
• /: Provided an input x, output x, 1. However, if x < 0, output 1, x.
• %: Provided an input x, output 2x+1, x+1.
• =: Provided an input x, output x, x.

Example programs

Primalty checker

i*[;-=o]

Explanation

i    Take a number input (E.g. 12)
     No-op
*[   Partition via multiplication (4, 3)
;    In the second branch:
-    Subtract the right accumulator by 1 (2)
=    Is this equal to 0? (0)
o    Output (Prime: 1 Non-prime: 0)
]    End the branch
Due to implicit reverse computations, IP automatically goes back to root. However, since there are no output instructions encountered, this does nothing significant to the user.

Add two inputted numbers

#o+[i;i]

Explanation

#  Skip the output instruction below, if the accumulator is 0 (which it indeed is initially)
o  Skipped by the # instruction.
+[ However, the + partitioning still does its job, assigning accumulators on the left and right both to 0.

i Take an integer input and set it to the value of the left accumulator.
;
i Take another integer input and set it to the value of the right accumulator.
] End the partition.

+       Sum the two accumulators (implicitly with reverse computation).

o      Output the sum.

#       This gets ignored.

Truth machine

Sio#

Explanation

S      Do nothing to reverse direction.
i      Take an integer input.
o      Output the integer.
#      If the integer is 0, stop the program.
o      Otherwise, output the integer again.
i      Since there is no input, this gets ignored.
S      Reverse direction and execute it again.

Average of the input

#o/[S-#[;i-#[;]];+]

-x

-#[;]

1/x

The same idea as above, added just for completeness.

/#[;]

Reversible I/O

When the direction is from root to leaf, take input; otherwise, output the accumulator, and skip the input part.

i#o

Explanation

i     Take an input
#     Skip this instruction.
o     DON'T output the accumulator (yet)

Reverse executed:

o    Output the accumulator.
#    Skip this instruction.
i    DON'T take an input from the console.

Downwards counter

i# S# -[o# -;]

A practical example - gettind rid of the =

It's probably quite confusing now, since = is already replaced by S. For this paragraph, you just need to know that accumulator = performs x == 0, and = on branch performs the same thing as S on a branch.

Accumulator =

To solve that, we simply need to devise a formula that checks whether x == 0. My solution is sign(x - 1) ** 2. How to represent that in DIVCON though? Well, the representation is basically:

-/*

- is decrement, / is sign, * is square.

Partition by =

The idea is simple: Partition by %, decrement both sides by 1, and divide the left side by 2. Here's our half product that produces 2x, x:

%[-;-]

As for division by 2, we just partition the left half by +, and then zero the right half (increment, sign, decrement). (The ending # is for avoiding reverse-computation.)

%[-+[;+/-#];-]

Tada! We've partitioned the accumulator into 2 equal values.

Check if two accumulators are equal

Unfortunately our alternative to = isn't reversible; that's why the = operation is made - to ease reversibility. Let's complete our example by checking equality. If x and y are equal, x - y = 0. X and Y are placeholders for the accumulator operations that lead to the -.

-[XX;YY]

The truthiness of this program is already correct, but in order to implement proper = behavior, we need to implement accumulator = here:

*/--[XX;YY]

Implementation of common loops

Do ... while loop

Evidently DIVCON doesn't have the implementation of a do while loop. However, this loop could be simulated: (The branch is ASCII-fied for easier readability.)

   
  #
  S
  -
 /#\
.   .
.   .
.   .
#   #

-# on a branch is basically operand-swapping -. So the left branch is set to 0, and the right is set to whatever the accumulator is before the branch.

How does this work? Since initially, the execution direction is from root to leaf, so S won't do anything to reverse program flow. Then, the integer in the accumulator is being partitioned via -, which means that the right branch could do whatever in the body.

Since there are trailing #'s being executed in the loop, reverse-computation isn't activated, and the accumulators are being conjugated via -. The # checks whether this accumulator is 0, and if so, the reverse execution instruction is ignored. Otherwise, reverse execution and continue the body.

Repeat loop

Using a similar logic, we could implement a repeat loop quite easily:

  .
  .
 /-\
S   .
#   .
    .
d   .
#   #

Official implementation

• Official. This is a partial implementation. (dead link)