WUUI

WUUI is a nondeterministic esoteric programming language designed in 2015 by User:ais523.

Data and expressions

A WUUI program conceptually stores data using an infinite array (called x) of unbounded nonnegative integers. At the start of the program (or whenever the program is restarted; see below), these are all zero. Whenever (to be precise, just after) any expression is evaluated, each of these integers can increase or decrease by 1, or remain the same (the probability of each of these events is conceptually approximately 1 in 3, but can be varied slightly in order to optimize an implementation, e.g. via replacing a binomial distribution with a bounded normal distribution). This random-walk of all the values in memory is the only way that any of them ever change; they cannot be set explicitly. In order to avoid having to maintain an infinite amount of state, interpreters are encouraged to update values lazily when their value is read (via remembering the last time it was read and catching up on all the random updates at that point), rather than trying to update the entire infinite array immediately when an expression is evaluated.

The only arithmetic operations that exist in the language are nonnegative integer constants, indexing of x via an expression, and division of an expression by a constant positive integer (which rounds downwards towards zero). The syntax for expressions is as follows (whitespace-insensitive):

<expression> ::= <number> | 'x' '[' <expression> ']' | <expression> '/' <number>
<number> ::= <digit> | <number> <digit>
<digit> ::= '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'

An expression is truthy if it evaluates to nonzero, or falsey if it evaluates to zero.

Control flow

A WUUI program consists entirely of no-ops (;), control flow commands , and/or the command output; (that outputs a single byte that's equal to the value y that in the range 0 to 255 inclusive that would maximises the value of x[y] (an interpreter can choose any possibility in the case of a tie); this expression is not actually evaluated). The control flow commands are while, until, unless, and if, each of which take an expression and a command as an argument. The commands do what their name would suggests: while evaluates the expression, exiting if it's falsey, or running the command and then repeating the whole process if it's truthy; until is the same as while but with falsiness and truthiness exchanged; unless evaluates the expression, then runs the command if it was falsey (and does not repeat the process); and if is the same as unless but with falsiness and truthiness exchanged.

The syntax for commands is as follows (again, whitespace-insensitive):

<command> ::= ';' | 'output;' | '{' <commandlist> '}' | <flowcommand> '(' <expression> ')' <command>
<flowcommand> ::= 'while' | 'until' | 'unless' | 'if'

An entire program is a single command.

Nondeterminism

Conceptually, a WUUI interpreter executes a program as described above, but with a twist: if the program should enter an infinite loop, the entire program restarts. The entire program is also allowed to restart "spontaneously" even if it is not stuck in an infinite loop; this allows for computable interpreters to be constructed via spontaneously restarting programs after a random length of time. However, the probability distribution of a spontaneous restart must be chosen such that for any finite number of evaluated expressions, a program that evaluates that number of expressions and then terminates must have a nonzero probability of not being spontaneously restarted in all that time. (That is, spontaneous restarts aren't allowed to prevent a terminating program from terminating, and thus heuristics such as "restart after N commands", for any fixed N, are disallowed; a legal algorithm would be "restart with 0.0001% probability after each command".)

If, after restarting, a WUUI program produces output, and it also produced output before restarting, then:

• If the output is the same in both programs, the second "copy" of it is ignored; once the restarted program "catches up" to where the original was, it produces output as normal;
• If the restarted program's output diverges from the original, it gets immediately restarted (as though it were stuck in an infinite loop).

Note that this does not mean that a WUUI program must terminate: if you write a program that necessarily enters an infinite loop, like while (1) ;, the interpreter will end up restarting it over and over again, indefinitely, which is a different sort of infinite loop.

Of course, this method of executing a program is mindbogglingly inefficient. Thus, an interpreter is allowed (and encouraged!) to do static analysis (or any other sort of analysis, such as a JIT) of the program to see which random walk possibilities have any chance of allowing the program to terminate, and which are guaranteed to force an infinite loop. It can then simply choose not to generate random numbers that would necessarily cause the program to enter an infinite loop before producing output (technically, before producing more output than a previous execution), as an execution with those random numbers will necessarily end up restarting itself out of existence.

Such analysis is likely to be quite complex, though. As a result, it seems to be very difficult to produce a WUUI interpreter that can run even relatively simple programs (even "Hello, world!" programs) with any sort of reasonable performance.

Programming in WUUI

Here's a simple example of a WUUI program:

until (x[0]);
if (x[1]/4) while(1);
unless (x[1]/4) while(1);

The first line sets the entirety of memory to random values (with a sort of modified exponential distribution), except for x[0], which is set to 1. The second line will enter an infinite loop (restarting the program) if the value of x[1] is greater than or equal to 4. The third line will enter an infinite loop if the value of x[1] is less than 4. Therefore, the only way for this program to terminate is if x[1] changed from 3 to 4 as a result of evaluating the loop test on the second line; and thus after the program runs, we know that x[0] has a value from 0 to 3 inclusive, x[1] has a value from 3 to 5 inclusive, and we don't know anything for certain about the rest of the array.

This technique is enough by itself to produce programs that operate on a fixed amount of data; the idea is that you establish a "guard range" of values that no element (that you use) of x can have except while you're intentionally trying to change it (with the range large enough that no element can walk from one side to the other in between checks on it). Then, between each command that does something, you check each variable that you aren't trying to change for values in the guard range, and restart the program (using an infinite loop) if such a variable has such a value. This means that interpreting each element as a single bit ("above range" / "below range"), you can ensure that the element will hold its value while you're operating on the others.

However, such power is only enough to produce a finite state automaton. The more interesting question is as to whether it's possible to reliably access unbounded amounts of storage in WUUI. There are definitely tricks you can do for looping over ranges of elements within x; for example, you can ensure (using infinite loops to reject any other behaviour) that x[x[1]] changes value more rapidly than a single value is capable of changing over the course of a loop, which in turn means that x[1] itself must be changing; and doing the same thing with x[x[1]/2] in an appropriate pattern will then force x[1] to change monotonically. The problem with combining this sort of trick with the tricks above to build an interpreter for a tape-based language is that the size of the guard range required depends on the number of elements you're iterating over, and division by constants is insufficient to test that values avoid a guard range of potentially varying size. Instead, you'd need to use indexing of x as a method of ensuring that values stay outside the guard range, which in turn means that you'd need to set up the guard range in memory with values high enough that they can't drift down to 0 during the life of the program. (Note that there isn't a need to know in advance how long the program will run for; you can guess, and then restart if your guess turned out to be too low.) It is currently unclear whether such a memory structure can be reliably set up under WUUI's rules.