|Computational class||Turing complete|
Exotic is an esolang invented by User:Hakerh400 in November 2020.
Exotic is a tree-rewriting language. It starts with a finite binary tree and modifies it according to some rules.
An expression can be one of the following:
- Term - Represented by
.. It is a unique value and contains no other expressions. It represents a leaf in the binary tree.
- Pair - Represented by
rightare some other expressions. It represents a node in the binary tree.
- Identifier - Represented by an alphanumeric string. It represents formal variable that can be any expression.
- Call - Represented by
targetis some other expression. It represents a rule application.
A rule consists of two expressions. The first expression represents the pattern and the second expression represents the replacement for that pattern. For example, the following rule
(. (a .)) (. a)
will replace anything of the form
(. (a .)), where
a can be any expression, with
(. a). The replacement happens only when the expression appears inside a call (prefixed by
We do not explain too much details here. For more information, see the implementation of the interpreter.
Input and output are binary strings. There is a bijection between binary strings and binary trees, but the mapping is a bit complicated, so we do not explain here in details how it works (see the implementation). Basically, given the input as a binary string (call it
input), the initial expression to start with will be
inputTree is obtained by converting
input into a binary tree. This is the main expression and the interpreter searches for
*expr patterns and matches them against rules (applies the most specific rule if multiple rules can be applied) until there are no more calls in the main expression. The result is the output of the program. Then we convert it back into a binary string and output it.
(. a) a a .
(. (. .)) (. .) (. ((. .) .)) *(. ((. .) .)) a .
Replace leading 1 with two 0s
If the input consists of a single 1 followed by zero or more 0s, then replace 1 with two 0s.
a . (. .) . (. (a b)) (. *(. a))