Thue is an esoteric programming language based on string rewriting rules. It is named after the Norwegian mathematician Axel Thue.

Essentially, you list substitution rules as lhs::=rhs where lhs is replaced with rhs.

Then you put another ::= on a new line to mark the end of the list and write down the initial state of the program. That state will be mutated step by step by applying the rules.

Thue is non-deterministic: any rule can be chosen if it can be applied to the current state.

To get a value from the input string, use ::: in rhs. You may use several ::: in one rule. Input commands run before output commands.

To output a value, use ~ in the right-side part of a rule. Any rhs can only contain one ~. If you want to output the current state, use ~~.

For comments, use #. Everything in a line that starts with it will be ignored.