![]() ![]() 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. This code fragment therefore has a similar purpose to the wikipedia:C-element in asynchronous design, joining two distinct threads of execution. The asynchronous nature of the language means that y may end up being called first, but the synchronization still works. 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 example program above was based around a code fragment with this purpose the important definitions are The usual I/O convention is in unary, using a string of 1 bits of an appropriate length followed by a 0 bit.Īnnihilator 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 input will thus inevitably become a prefix of the output interpreters should delete the input from the output before outputting it.) 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. If the program exits in success, the successful thread's I/O list is output. 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. When I/O is enabled, the function names 0 and 1 are special. (This particular program cannot exit in failure, and exits in success with probability 1.) ,, ,, →, , Īnd then the program exits in success. This is called a "failure exit".Īnd 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: If at the time the first step runs, there are no threads (and thus none could be chosen), the program exits.If at the time the first step runs, the chosen thread has an empty call stack, the program exits.There are two conditions that can cause the program to exit: via periodically asking the operating system for new random bytes. Implementations on a computer must therefore mix in randomness from the outside world to their random choices, e.g. the sequence of choices will never repeat itself). ![]() 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. This is repeated until each remaining thread has a different function name at the top of its call stack. 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. 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. 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. Initially, there is only one thread, which has a call stack consisting of the single element main.Įxecution proceeds by alternating between the following two steps forever (or until the program exits): ![]() 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). This serves as the entry point for the program, but is not otherwise special.Īn Annihilator interpreter maintains a multiset of threads. However, any name that appears in a function body must have at least one definition.Ī function named main must be defined. It is legal to have multiple definitions for the same function. A function body is an ordered list, and can contain duplicate names. A function body may be empty, in which case the tab may be omitted. 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. The name of a function is a string of non-whitespace non-control-code characters (punctuation marks and similar are allowed). An Annihilator program consists of a number of function definitions. ![]()
0 Comments
Leave a Reply. |