User:Zzo38/Untitled 2

This programming language consists of:

• Zero or more inputs, which are natural numbers
• Zero or more registers, each of which has a fixed maximum (defined by the program), and stores a queue of elements
• One or more basic blocks, one of which is the initial block

Each element of a queue is either a natural number, or a name of a input; the value of those inputs is also how much the element is worth in that case.

The maximum of a queue is defined by a polynomial of the program inputs (as the variables), with integer coefficients, but the result must be nonnegative for all possible combination of inputs. (For example, (x2-x) is OK, and (x2-2x+1) is OK, but (x2-2x) is not OK.)

The maximum of the queue defines the maximum total values of all elements of the queue that the register is allowed to store. (You can store an unlimited number of zeros in a queue, regardless of what the maximum is defined as.)

Instructions:

• Append a constant element to a register, if it fits (the element is either a natural number, or a name of a input)
• Move as much as will fit from the beginning of one register to the end of another (it can't be the same register)
• Clear a register
• Output the contents of a register (without clearing it)

Terminating instructions:

• Go to one basic block unconditionally
• Terminate the program
• Go to one of two basic blocks depending on whether or not a specified register is empty

(To clarify: The instruction to move from one register to another won't move anything if the number at the beginning of the queue to take from won't fit, and if the first number fits but then the second number won't fit, it will only move the first number and won't try the third, and so on.)

Syntax

First define the registers. Each one consists of:

• Register name (alphabets, digits, underscore; cannot start with a digit)
• A colon
• Polynomial to use: Each term has a plus or minus sign (may be omitted for the first term to assume plus), and then the coefficient (which may be omitted to assume 1), and then zero or more input names; a input name may optionally be followed by ^ and a number. Spaces are not allowed before and after the ^ sign.

After that put the basic blocks. The first one is the initial block.

Each basic block starts with the name (same format as a register name) in square brackets.

Each command in a basic block can be:

• To append a constant element, put the register name and then + and then the value (either a number or a input name).
• To move from one register to another, put the register to move to and then < and then the register to move from.
• To clear a register, put = and the register name.
• To output a register, put * and the register name.

At the end is the terminating command, which can be:

• To go unconditionally, put / and then the name of the target block.
• To terminate the program, put \$ by itself.
• To go conditionally, put a register name and then ? and then the block to go if it is empty and then ! and then the block to go if not empty.

All numbers are written in decimal notation. Spaces are (mostly) allowed between tokens. Comments can start with # and until end of a line.

Examples

If x is divisible by y:

a:y
b:x
c:1
[start]
a+y
b<a
b?start!end
[end]
c+1
b<c
*c
\$