Annihilator

Annihilator is an esoteric programming language created by User:ais523 in 2020. It is asynchronous, nondeterministic and probabilistic, with no commands but the function call; conditionals are done via allowing the various nondeterministic threads of execution to annihilate each other if they happen to be in the same place at the same time.

Syntax

An Annihilator program consists of a number of function definitions. The name of a function is a string of non-whitespace non-control-code characters (punctuation marks and similar are allowed). A function definition consists of the name of the function, followed by a tab, followed by a space-separated list of the names of the functions it calls (its body), then a newline. A function body may be empty, in which case the tab may be omitted. A function body is an ordered list, and can contain duplicate names.

It is legal to have multiple definitions for the same function. However, any name that appears in a function body must have at least one definition.

A function named main must be defined. This serves as the entry point for the program, but is not otherwise special.

Semantics

An Annihilator interpreter maintains a multiset of threads. A thread is defined by its call stack, which is a list of function names (with the leftmost end of the list being considered the top of the stack). Initially, there is only one thread, which has a call stack consisting of the single element main.

Execution proceeds by alternating between the following two steps forever (or until the program exits):

• Function call. A random thread is chosen, and the function name at the top of its call stack is called; this causes that name to be popped from the stack, and replaced with the body of the definition of that name. If the function has multiple definitions, a copy of the chosen thread is made for each definition, and each copy uses a different definition of the function.
• Annihilation. If there are two or more threads which have the same function name at the top of their call stack, two of them (chosen at random) are destroyed. This is repeated until each remaining thread has a different function name at the top of its call stack.

These "random" choices must be made via a means that gives approximately equal probability to each option and each sequence of options, and via some mechanism that has an infinite period (i.e. the sequence of choices will never repeat itself). Implementations on a computer must therefore mix in randomness from the outside world to their random choices, e.g. via periodically asking the operating system for new random bytes.

There are two conditions that can cause the program to exit:

• If at the time the first step runs, the chosen thread has an empty call stack, the program exits. This is called a "success exit".
• If at the time the first step runs, there are no threads (and thus none could be chosen), the program exits. This is called a "failure exit".

Example

Here's an example program:

main	x y
x	x
x	a b z
x	b a z
z
z	x
y	c c a y
a
b
c

and an example of how its execution might proceed, showing the internal state after the function call (and if there's an annihilation, then showing the internal state after the annihilation after an arrow), with the function that randomly happened to be called on the next line bolded:

[main]
[x], [y]
[x], [a b z], [b a z], [y]
[x], [a b z], [b a z], [c c a y]
[x], [b z], [b a z], [c c a y] → [x], [c c a y]
[x], [c a y]
[x], [a b z], [b a z], [c a y]
[x], [a b z], [b a z], [a b z], [b a z], [c a y] → [x], [b a z], [b a z], [c a] → [x], [c a y]
[x], [a y]
[x], [a b z], [b a z], [a y] → [x], [b a z]
[x], [a b z], [b a z], [b a z] → [x], [a b z]
[x], [b z]
[x], [z]
[x], [a b z], [b a z], [z]
[x], [a b z], [b a z], [x], [] → [a b z], [b a z], []
[a b z], [a z], [] → []

and then the program exits in success. (This particular program cannot exit in failure, and exits in success with probability 1.)

I/O extension

When I/O is enabled, the function names 0 and 1 are special. Each thread has an I/O list, a list of bits, in addition to a call stack; a function call of 0 or 1 will append a 0 bit or 1 bit respectively to its I/O list. If the program exits in success, the successful thread's I/O list is output.

If input is provided to the program, then if at any point a thread's I/O list does not start with the provided input and is not (in its entirety) a prefix of the provided input, the thread is immediately destroyed. (The input will thus inevitably become a prefix of the output; interpreters should delete the input from the output before outputting it.)

The usual I/O convention is in unary, using a string of 1 bits of an appropriate length followed by a 0 bit.

Computational class

Annihilator has no problems producing an arbitrary effect at an arbitrary point, and its call stacks can be used to store data, so the only obstacle to a Turing-completeness proof is communication between threads (to allow two call stacks to be used at the same time). The example program above was based around a code fragment with this purpose; the important definitions are

x	x
x	a b z
x	b a z
z
z	x
y	a y
a
b

With these definitions present, a call to x will block until/unless y is called, at which point the thread calling y will be deleted and the thread calling x will return normally. The asynchronous nature of the language means that y may end up being called first, but the synchronization still works. This code fragment therefore has a similar purpose to the wikipedia:C-element in asynchronous design, joining two distinct threads of execution.

Note that once x is called, there is no obvious reliable way to "un-call" it; calling y and having execution continue as a consequence is the only safe way to continue. (Simply calling x again would un-call it with a fairly high probability, but not reliably (the a b z and b a z threads might hang around, un-called, until y were called some time later), and thus can't be used to prove Turing-completeness). However, it is possible to "reset" a pending x, replacing the tail of its call stack with the current thread's call stack:

r x (unreachable)
r a b (unreachable)
r b a (unreachable)
r s
s x
s a b z
s b a z
s t

((unreachable) represents arbitrary code that will be executed only in error / undefined behaviour conditions.)

When r is called while an earlier call to x is still in progress / not yet returned, this will eventually produce a call to t, but the earlier call to x will be abandoned and replaced with, effectively, a new call to x. (The setup is such that the a b… and b a… threads produced by the original call to x will be annihilated if they exist, and then the a b… and b a… threads produced by the call to r will be annihilated if they exist; the threads produced by the call to s might or might not be, but they will be equivalent to those produced by the new call to x, so it doesn't matter whether they survive or not. It is guaranteed that the t call cannot be produced until after the reset has occurred.

It seems highly likely that this sort of "resettable C-element" gives sufficiently powerful cross-thread communication to make it possible to implement, e.g., StackFlow. There is not yet an explicit construction for this, though; thus, although Annihilator is almost certainly Turing-complete, this has not yet been formally proven.

See also

• Countercall, which indirectly inspired Annihilator