HydraLoop

Variable names can be any sequence of ASCII letters, numbers, underscores. Variable names are case-sensitive.

Comments start with * and are up to the end of the line.

Each variable stores a list, and the elements of lists are also lists. It can also be treated as a number, the number being how many items.

Each variable initially stores a empty list.

Non-loop commands:

• X; sets X to a empty list.
• X,Y; adds a copy of the value of Y as an item at the end of X.

Loop commands:

• X[...] remembers the value of X at the beginning of the loop, and then executes ... for each leaf of X. It is a tree, for example a list such as (()()(()())) has four leafs, and a empty list () has one leaf (this is equal to how many "()" in this representation of this list).
• X,Y[...] remembers the value of X at the beginning of the loop, and then for each item of X, sets Y to a copy of that item and then executes the ... commands. For example, if X is ((())()) then it executes ... twice, first with Y set to (()) and second with Y set to the empty list ().
• X,Y,Z[...] does, while X is not empty, repeats the following steps:
  1. Remember the value of X.
  2. Execute the ... commands.
  3. Restore the value of X.
  4. Treat Y as a number, and modulo by the number of leaves of X. Find that leaf of X, where the first leaf is numbered zero, and delete that leaf.
  5. If the parent of the deleted leaf is not the root, then find the parent of the parent of the deleted leaf and make Z copies of that entire branch (treating Z as a number). The copies are added at the same level of that branch. For example, (()(()())) becomes (()(())(())(())(())) in the case that Y is 2 and Z is 3. If you have ((())) that becomes ((()())) when Z is 1, regardless of what Y is (since anything modulo 1 will be zero).

Note that for the "X,Y" and "X,Y,Z" loops, they do nothing if X is empty. (However, the "X" loop still executes even if X is empty.)

It is permitted (in both loop and non-loop commands) to have some or all of the variable names to be the same (although this is not required). For example, the empty loop X,X[] causes the value of X to be replaced by a copy of the last element of X.

Spaces are also allowed between commands.

Computational class

The first kind of loop (leaf loop) will always terminate because the tree has a finite number of leaves; you can't add an infinite number of leaves.

The second kind of loop (item loop) will always terminate because you cannot add an infinite number of items to a list.

The third kind of loop (hydra loop) will always terminate due to the hydra theorem, which says that the "hydra game" will always terminate. (The hydra game consists of a tree and each step deleting a leaf node and adding new branches according to the rules mentioned above, until there is no more left.)

Therefore, the program is guaranteed to terminate.

Examples

(TODO)